11
$\begingroup$

In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs.

The Wikipedia article on cryptographic hash functions mentions that

In practice, collision resistance is insufficient for many practical uses. In addition to collision resistance, it should be impossible for an adversary to find two messages with substantially similar digests; or to infer any useful information about the data, given only its digest. In particular, should behave as much as possible like a random function (often called a random oracle in proofs of security) while still being deterministic and efficiently computable.

It seems to me that in practice hash functions are usually considered to be PRFs. Is this valid and are commonly used compression functions all PRFs?

Note: The Bellare paper states

(There are to date no attacks that compromise the pseudorandomness of the compression functions of MD5 or SHA-1.)

Has this changed since then?

An interesting related paper by Kim et al., also from 2006, gives distinguishers for HMAC based on SHA-0 and HAVAL to distinguish it from HMAC with a random function. Which at least hints that it might be hard to determine if a compression function is a PRF.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

(There are to date no attacks that compromise the pseudorandomness of the compression functions of MD5 or SHA-1.)

Has this changed since then?

Not as far as I know.

It seems to me that in practice hash functions are usually considered to be PRFs. Is this valid and are commonly used compression functions all PRFs?

Note that there are two ways to define the PRFness of a hash function. A compression function is a function $f(x_1, x_2)$, where $x_1$ is the state input (either the IV or the previous block output) and $x_2$ is the current data block. You can take either $g_k(x) = f(k, x)$ of $g'_k(x) = f(x, k)$ when you consider whether it is PRF.

For SHA-1 and SHA-2 $f(x, k)$ is relied on when using the SHACAL ciphers. (Or actually, SHACAL relies on them being pseudorandom permutations, PRP.) However, for HMAC the opposite, $f(k, x)$, matters (as well, see comments).

E.g. since there are no known attacks on full SHACAL-2, you could assume that SHA-256 is PRF up to around $2^{128}$ calls (birthday bound for distinguishing PRP from PRF). However, that would not necessarily apply to the way it is used in HMAC... but there is no known attack on that either.

SHA-3 has more explicit security claims regarding its pseudorandomness, but it does not use a compression function in the normal sense, but a sponge function instead.

TL;DR: the compression function of the currently secure hash functions, like SHA-256, seems likely to be PRF, though it is not a property that the designers claimed. The compression function of the weak MD5 or SHA-1 might still be PRF, but I would not rely on it if I did not have to, since their use is deprecated. And if you want something with security claims regarding this, you could look into SHA-3 instead.

Improve this answer
$\endgroup$
10
  • $\begingroup$ For NMAC, PRFness of $f(k, x)$ only matters, but for HMAC, which is NMAC with additional key derivation using $k_1=f(\mathit{IV}, \mathit{ipad}\oplus K)$ and $k_2=f(\mathit{IV}, \mathit{opad}\oplus K)$, you need something like PRFness of $f(x, k)$ also. The specific property needed is that the above $k_1$ and $k_2$ should look like independent uniform random keys, which can be obtained if $f(x, k)$ is a related-key secure PRF. $\endgroup$
    – AYun
    Jan 7, 2018 at 11:54
  • $\begingroup$ @AYun, that is a good point, but for a collision resistant hash function is that not moot? I.e. as long as $f(k, x)$ is a (related key secure?) PRF and the hash collision resistant, $f(x, k)$ does not matter. $\endgroup$
    – otus
    Jan 7, 2018 at 12:16
  • $\begingroup$ otus, at the least, $f(\mathit{IV}, \mathit{ipad}\oplus K)$ should be indistinguishable from uniform random. Here, the value $x=\mathit{IV}$ is known and fixed, and $k=\mathit{ipad}\oplus K$ serves as a uniform random secret key, so if $f(x, k)$ is a PRF, then at least that is guaranteed. I don't think that this follows only from PRFness of $f(k, x)$ and collision resistance, because instantiating $f(k, x)$ with $k=\mathit{IV}$ wouldn't work, since $\mathit{IV}$ would be a known and fixed key, so not at all secret. $\endgroup$
    – AYun
    Jan 7, 2018 at 12:29
  • $\begingroup$ @AYun, but isn't that like saying that $K=IV$ would not work for HMAC because it is fixed? The definition of PRF assumes a secret key, and instantiating with $k=IV$ is not possible in HMAC barring a preimage attack. (Anyway, I corrected the answer by inverting the statement. PRFness of $f(x,k)$ is enough for SHACAL, but not for HMAC, whether or not it is also required.) $\endgroup$
    – otus
    Jan 7, 2018 at 12:42
  • $\begingroup$ HMAC is keyed not by the $\mathit{IV}$, but keyed by the 'message' part with a secret key $K$, and that in turn produces two keys $k_1=f(\mathit{IV}, \mathit{ipad}\oplus K)$ and $k_2=f(\mathit{IV}, \mathit{opad}\oplus K)$ for the underlying NMAC. These derived keys should look like random, and here, $\mathit{IV}$ is fixed, and $\mathit{ipad}\oplus K$ is random. Since $\mathit{IV}$ is not at all random, this cannot be the key material for this key derivation process; the other arguments, $\mathit{ipad}\oplus K$ and $\mathit{opad}\oplus K$ are. $\endgroup$
    – AYun
    Jan 7, 2018 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.