# What's wrong with an iterative (with counter) hashed salted KDF?

It seems like the brain-dead simplest KDF would have a key-stretching structure that is not substantially different from $\text{hash}(S | P | S | P |\dots|S|P)$, where $S$ is a salt and $P$ is a password. Other protocols generally require lots of hashes-of-hashes-of-hashes; this one builds up one big string to hash. This naive version has some obvious problems with timing (longer passwords require longer to verify), but it also might be easier to parallelize because the structure is perfectly repetitive, and it might "fall into a fixed point" of the hash function's compression-function, whereby further repetitions do not increase security.

The obvious thing to do, then, involves pre-hashing the password and incorporating a counter. Just to make this question 100% unambiguous, one implementation of this idea in Node.js would be:

function createKDF(work_factor, output_length, hash_algorithm) {
var crypto = require('crypto'), hash_length, output_blocks;
function hash(string) {
var context = crypto.createHash(hash_algorithm);
context.update(string, 'utf8');
return context.digest();
}
hash_length = hash("").length;
// needed to support arbitrary output lengths
output_blocks = Math.ceil(output_length / hash_length);
function output_transform(bin_data) {
var buff = new Buffer(hash_length * output_blocks), i, bstring;
bstring = bin_data.toString('hex');
for (i = 0; i < output_blocks; i += 1) {
hash(i + ':' + bstring).copy(buff, i * hash_length);
}
return buff.slice(0, output_length).toString('hex');
}
return {
createSalt: function () {
return crypto.randomBytes(hash_length - 4).toString('hex');
},
kdf: function (pass, salt) {
var hpass = hash('nodejs-passwords-0:' + work_factor + ':' + output_length + ':' + pass),
salt_buff = new Buffer(salt, 'hex'),
buff = new Buffer(2 * hash_length),
hash_state = crypto.createHash(hash_algorithm),
round;
assert(salt_buff.length + 4 == hash_length);
// buffer: [32-bit counter][(N - 32)-bit fixed salt][N-bit hpass]:
salt.copy(buff, 4);
hpass.copy(buff, hash_length);
for (round = 0; round < work_factor; round += 1) {
buff.writeUInt32LE(round, 0);
hash_state.update(buff);
}
return output_transform(hash_state.digest());
}
};
}


The reason I ask is that this approach seems simple enough that, if it is secure, the common advice of "don't roll your own crypto" is somewhat wrong: there are a variety of implementations of $$\text{key} = h_1(0|S|h_2(P)|1|S|h_2(P)|2|S|h_2(P)\dots)$$which you can easily program to create a password-storage system which suits your particular application, if something like PBKDF2 or bcrypt or scrypt is not available in your programming environment.

(Of course Node.js has PBKDF2, so the above implementation is more to clarify the question of "what's wrong with this general approach?" rather than it is to be useful to a JS programmer.)

TL;DR: You put less of a burden an any attacker trying to brute-force this.

And please note: Implementing PBKDF2 shouldn't be much harder than implementing your approach.

Now let's head over to the explanation why "your" scheme is really bad for password-hashing.

The scheme you propose is that each try cost you exactly two hash-function evaluations. One for the first hashing of the password and another for the evaluation of the outer hash.

From a theoretical point of view this is bad because you don't require a certain amount calls to a given function that has a "lower bound" on speed. Memory operations XOR and similar don't count usually. So you have only two evaluations and can only tweak something that doesn't really make a difference.

The last point is that "your" scheme ignores the way how hash-functions work. Hash-functions tend to get faster (measured in bytes / cycle) the more data is fed into the function. So your scheme requires one large invocation with small workload per byte, hence you'd have to feed in much more data (10-1000x) to reach the same workload. PBKDF2 needs less because hash-functions are inefficient for small amounts of data.

To concern your question what would be the disadvantages against PBKDF2 and co.
PBKDF2 is standardized ("your" scheme isn't) and widely accepted for usage (although generally considered the worst option).
bcrypt is generally considered a good choice as it puts a burden on the minimal memory ("you" don't) and is hard to compute on GPUs ("your" scheme seems very GPU-friendly, like PBKDF2)
scrypt is generally considered a very good choice as it puts even more of a burden on the memory side and protects quite good against FPGAs and ASICs ("your" scheme doesn't).

• I agree that bcrypt and scrypt are better KDFs than PBKDF2, but my question is more precisely whether there is a security reason to prefer PBKDF2 to the "dirt-simple" approach. I do think that you're strangely accusing me of your own sin ("your scheme ignores the way how hash-functions work"), since the reason hash functions "get faster" is because of pre- and post-processing that isn't much related to their security properties. (In SHA256's case, for example, one hash of a 512-bit input is two compressions: the input and the fixed block 0x800000...00 inserted by the padding preprocessor.) – CR Drost Jun 9 '15 at 17:32
• @ChrisDrost First, If you think "I'm accusing you" in any offensive sense, then I have to excuse, my text wasn't meant to be offensive. The security property that is interesting for us here (in password-hashing) isn't collision resistance but rather preimage and 2nd preimage resistance and of course speed. If a calculation is slower with lesser parameters and can't be optimized further, it's a good construction. Pre- and postprocessing can be used to the derivators advantage using PBKDF2 but not using "your" scheme (sorry honestly don't know any better short name). – SEJPM Jun 9 '15 at 18:45
• Well then you should love the above construction. The above (running in interpreted JS!) with work_factor 10 million takes as long as Node.JS's PBKDF2 native code (C or C++) with work factor 200,000 and HMAC-SHA256. Each round of the latter may be 4 or 5 compression function calls; so in the same time you get over a factor-of-ten more "work" done. That's why I'm really interested in things like preimages, parallelization, and stuff -- and why I feel like your answer doesn't really get to the heart of the question. – CR Drost Jun 9 '15 at 19:16
• @ChrisDrost Well that you need more iterations for the same workload is actually bad for password-hashing as it's the aim of password-hashing to slow people down. By using such schemes you want to slow people down so they can't try as much as passwords in the same time as it's possible now. In fact parallelization is also something you want to avoid in most cases because attackers usually have more cores than you. – SEJPM Jun 9 '15 at 19:20
• Amendment to my earlier comment: there is also a hidden factor of 2 from the fact that PBKDF2 redoes the whole chain of computations twice to get a 512-bit key; that surprised me but it sort of makes sense. I must confess that I can't fathom the meaning of "more iterations for the same workload" -- compression function calls are the workload, so this phrase should be "more work for the same time", but obviously that's not BAD but GOOD for password hashing, since ASICs can be designed to cut through overhead. – CR Drost Jun 9 '15 at 19:32