Re: [TLS] Entropy of SHA-2 and the P_SHA256-based PRF

[Hugo Krawczyk <hugo at ee.technion.ac.il>]

Merkle-Damgard iteration does not solve this problem. The Gligorski-Klima paper's findings apply to all the common M-D instantiations: The MD and SHA-1/SHA2 families.

However, the loss in entropy has little effect in practical security if by "practical security" we mean security against computationally bounded attackers. 

For example, under the modeling of the compression functions as random functions (as done in the Gligorski-Klima paper) one can PROVE that HMAC, in spite of the entropy reduction, is a secure PRF (i.e., it has been proven that if the underlying compression function family is pseudorandom then HMAC is a pseudorandom function; and if one models the compression functions as random then they are, in particular, also pseudorandom).

So even if there is a loss of statistical entropy, this is something that a computationally bounded attacker cannot exploit.

This should not come as a surprise. It is very common to have in cryptography probability spaces with very limited statistical entropy and yet secure enough for cryptographic purposes. The most common such object is  a pseudorandom generator PRG (or stream cipher). It takes a seed of length n and generates, say, 10n bits of output that are pseudorandom. Clearly, the distribution generated by the PRG contains no more than n bits of entropy (very small relative to the 10n strings it generates) and yet it is secure as a PRG. The point is, as before, that in the security of a PRG we only consider attackers that cannot distinguish the output of the PRG from random uniform bits using FEASIBLE computation. Yes, a computationally unlimited attacker (say one working time 2^n) will be able to  distinguish between uniform and PRG output, but we consider those infeasible.

Leaving the realm of PRFs abd PRGs, one can ask what is the consequence of entropy reduction in cryptographic hash functions. One setting where these questions arise naturally is in designing randomness extractors via such hash functions (a randomness extractor takes a source with some given min-entropy and generates an output that is statistically close to uniform). In this setting, paper [DGHKR'04] already identified the problem, also pointed out in the Gligorski-Klima paper, that a last fixed (or close to fixed) block in a M-D construction kills the statistical extraction properties of the M-D hash functions (with narrow-pipe underlying functions such as the SHA family). However, [DGHKR'04]  also proves that this is NOT a problem in the cryptographic extraction setting. That is, if one models the compression functions as random functions (or, more realistically, as pseudorandom functions), then  the M-D construction does provide a secure *computational* extractor. Here, by "computational extractor" one means the transformation from an entropy source to a distribution that is computationally indistinguishable from uniform (see [Kra'10]). This results holds even with a last fixed block.

To summarize: Yes, M-D functions do not behave as perfect random functions but when used judiciously they provide enough of pseudorandomness for cryptographic applications (HMAC, extraction, KDF, etc). Of course, if the underlying compression function is not even a good pseudo-random family then the constructions based on them may well be insecure -- but the Gligorski-Klima paper models them as random in which case the weaknesses pointed out are statistical only but inapplicable to the crypto world of computationally bounded adversaries. (In particular, of no consequence to the use of these functions in HMAC, the TLS protocol, etc.)

Hugo

[DGHKR'04] Dodis-Hastad-Gennaro-Krawczyk-Rabin, Crypto 2004.
[Kra10] Krawczyk, Cryptographic Extraction and Key Derivation: The HKDF Scheme, Crypto'10 (http://eprint.iacr.org/2010/264)

On Wed, Jul 14, 2010 at 7:35 PM, Martin Rex <mrex at sap.com> wrote:

Brian Smith wrote:
>
> Here is an interesting paper regarding the entropy of the output of SHA-2
> with a special mention of the TLS 1.2 PRF. If I am understanding correctly,
> SHA-2 reduces the entropy of a random input by half the first time it is
> applied, and the entropy slowly decreases every time it is applied
> thereafter.
>
> "For illustration we can say that the entropy of E(PRF[1]) = 253.463, but
> the entropy of E(PRF[60]) = 250.00."
>
> "Practical consequences of the aberration of narrow-pipe hash designs from
> ideal random functions"
>
> Danilo Gligoroski and Vlastimil Klima
>
> http://eprint.iacr.org/2010/384

A few observations.

Section 4.4 of this paper talks about PBKDF1
("Password based key derivation function 1" from PKCS#5),
and PBKDF1 was defined for MD2 and MD5 by PKCS#5 v1.5 and expanded
to SHA-1 by PKCS#11.

I assume that SHA-256 would more likely be used with PBKDF2
(which may share the relevant properties with PBKDF1
 with respect to the described effect of slow entropy depletion).

I assume that the effect of increased collisions for highly iterated
hashes similarly affect SHA-1 and MD5 password hashes.


I'm wondering whether an approach like this would compensate
the effect:

 Hash( user | pw | iteratedHash( Hash(pw | user | salt) ) )


-Martin
_______________________________________________
TLS mailing list
TLS at ietf.org
https://www.ietf.org/mailman/listinfo/tls