Generate secure password hashes without access to PBKDF2 or bcrypt

Question

Given is a system, which does provide only implementations of fast hash algorithms (MD5, SHA1, SHA-256, SHA-512). There is no implementation of PBKDF2, bcrypt or scrypt available. The system does provide a generateDigest(algo, input) and generateMac(algo, salt, input) function. The system has also the ability to securely store a private key for the MAC-function. Due to some language restrictions, it is undesirable to implement one of the key derivation functions.

Despite its lack of an adequate key derivation function, the system should be used to generate hashes for given passwords and store them.

I wonder if it would be possible to do some simple key stretching by repeatedly calling generateMac() with the HMAC_SHA512 algorithm:

algo = 'HMAC_SHA512'

for (i = 0; i++; i < ROUNDS) {
    input = generateMac(algo, salt, input)
}

From a naive point of view, this does look like a feasible solution to slow down attacks on the hashes. But i do lack the experience and knowledge, if it would be a right way of doing it cyptographically.

Answer 1

Actually you are quite near on implementing PBKDF2. It is kind of iterated HMAC execution. So have a look here and just implement the missing parts: PBKDF2

Answer 2

As Thor already notes, you code is already quite close to PBKDF2, and it would not be difficult to turn it into a proper PBKDF2 implementation.

Specifically, here's some (vaguely C / C++ / C# / Java / JavaScript like) pseudocode to implement PBKDF2-HMAC-SHA512, given a function HMAC_SHA512(key, message):

function PBKDF2_HMAC_SHA512 (password, salt) {
    const blockId = "\x00\x00\x00\x01";  // = INT_32_BE(1)
    var message = salt + blockId;
    var output = "\x00" x (512 / 8);

    for (var j = 0; j < iterationCount; j++) {
        message = HMAC_SHA512(password, message);
        output ^= message;
    }
    return output;
}

Note: This code assume that you want exactly one hash output block's worth of output (i.e. 512 / 8 = 64 bytes for SHA-512). If you need less, just truncate the output.

If you need more output, the PBKDF2 spec says you should increment blockId and run the code above again to generate more output blocks, but that's a rather inefficient method and I'd personally advise against it — instead, I'd suggest taking the output of the code above and using HKDF-Expand (from RFC 5869) to stretch it to the desired size. HKDF is also easy to implement using HMAC-SHA512:

function HKDF_Expand_HMAC_SHA512 (key, info, bytes) {
    var output = "", temp = "";

    if ((512 / 8) * 255 < bytes) {
        fail("Requested key length too large.");
    }

    for (var j = 0; (512 / 8) * j < bytes; j++) {
        temp = HMAC_SHA512(key, temp + info + chr(j + 1));
        output += temp;
    }
    return output.substr(0, bytes);
}

The key parameter to HKDF-Expand is the input pseudorandom key, i.e. the output of PBKDF2. The info parameter is an arbitrary string (analogous to the salt for PBKDF2) that allows you to derive multiple quasi-independent output keys from the same input key, and bytes is, obviously, the requested output length in bytes.

Note that both of the functions above return (and expect HMAC_SHA512 to return) their output as raw byte strings. Encoding the final output into some printable format (e.g. hex or base64), if desired, is up to the caller.

Also note that neither of these functions, being pseudocode, has obviously been tested. Please verify your own implementation using published test vectors, and/or by comparing the output to a known good implementation.

^{Notation: In both routines, when applied to string variables, the operator + denotes string concatenation, x denotes repetition, and ^ denotes bitwise XOR; the shorthand notations a += b and a ^= b mean the same as a = a + b and a = a ^ b respectively. The notation \x00 inside a double-quoted string denotes a null byte, and \x01 denotes a byte with the numeric value 1; in the HKDF-Expand code, chr(n) takes a number n between 0 and 255 inclusive, and returns a one-byte string containing a byte with the numerical value n. For a string variable s, s.substr(0, n) returns the first n bytes of s.}