[cryptography] "folded" SHA1 vs HMAC for entropy extraction

Steven Bellovin smb at cs.columbia.edu
Thu Jan 5 17:14:31 EST 2012


On Jan 5, 2012, at 4:46 PM, Thor Lancelot Simon wrote:

> On Fri, Jan 06, 2012 at 07:59:30AM +1100, ianG wrote:
>> 
>> The way I treat this problem is that it is analogous to inventing
>> ones own algorithm.  From that perspective, one can ask:
> 
> What is?  The "folded" SHA, or the use of HMAC?
> 
> You do understand why it's important to obscure what's mixed back in,
> I assume.  If not, read the paper I referenced on the Linux RNG;
> by insufficently obscuring what went back into the pool, the
> implementors made an attack with only 2^64 complexity possible.
> 
> With the constraint that you can't just output exactly what you
> mix back in, a plain hash function without some further transformation
> won't suffice, whether it's MD4 or SHA512.  I am asking whether the
> use of HMAC with two different, well known keys, one for each purpose,
> is better or worse than using the "folded" output of a single SHA
> invocation for one purpose and the unfolded output of that same
> invocation for the other.


It bears a lot of thought.  By having the keys known, you're using
HMAC in a non-traditional way; the question is which security properties
still hold.  For example: suppose there was a preimage attack on which
ever hash function you use.  Since part of the input -- the keys -- to
the HMAC invocations is known, the preimage attack means that the attacker
can find "the" (or "a") rest-of-input that went into the hashes.  Since
you're hashing 4K bits down to 160(?), there is loss of information in
the hash, which is good -- but we don't know what this hypothetical
preimage attack is.  By contrast, the Linux scheme loses information
via the folding.  Are the two equivalent?  Again, I don't know.  But
you can't just assume that the HMAC properties transfer.  (I'd be
happier with your scheme were the keys secret, though admittedly then
I'd ask what happens if they leak.)

		--Steve Bellovin, https://www.cs.columbia.edu/~smb








More information about the cryptography mailing list