1
$\begingroup$

I recently found a distinguisher for the PRF $f(s, i) = H(s || i)$ where $s$ is the seed and $i$ is a counter and $H$ is a cryptographic hash function, which is able to distinguish $f(s, i)$ from true random data very well with only $2^{30}$ bits of data.

I wondered whether this does affect the security of $H$. My first thought was that a cryptographic hash function should provide some level of randomness, but I'm not sure whether this goes as far as forcing $f(s, i)$ being a good PRF, so my question is whether the distinguisher to $f(s, i)$ lowers the security of $H$.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ To make the question more answerable, better define "insecure" or/and "the security of $H$". SHA-256 has the length-extension property, that is a distinguisher, and in most cases it does not matter from a security standpoint. A distinguisher that does not harm collision-resistance won't impact security of a signature scheme using the hash to extend the signing capacity to arbitrarily large messages. And so on: security depends on the context where $H$ is used. $\endgroup$
    – fgrieu ♦
    Oct 9, 2017 at 11:15
  • $\begingroup$ I didn't know $H$ when the PRF were given to me, it has turned out to be SHA2. $\endgroup$
    – VincBreaker
    Oct 9, 2017 at 13:41
  • $\begingroup$ If you have a distinguisher for anything resembling the question that works without knowing the constants of the round function of SHA2 nor oracle access to that round function, it is worth publication (after triple-check)! Rather, I think that the question nicely illustrates that the length-extension property of SHA2 can harm in come contexts that perform things with SHA2 that it is not intended to perform. SHA3 fixes it. $\endgroup$
    – fgrieu ♦
    Oct 9, 2017 at 14:05
  • $\begingroup$ @fgrieu: actually, it doesn't sound like the length extension property at all; all the messages being hashed are the same length. My guesses would be a) this is a really significant result, or b) VincBreaker misinterpreted his distinguisher output; does the distinguisher often trigger on lots of different $f$ samples (with different s's), and mostly doesn't trigger when given random data? $\endgroup$
    – poncho
    Oct 9, 2017 at 14:40
  • $\begingroup$ @poncho: I'm reading the question as allowing the size of one of $s$ or $i$ to vary, and then I can imagine a distinguisher on $f$ when $H$ is SHA2 (though nothing substantiating the $2^{30}$). Indeed, claims of distinguisher on hashes must be independently checked to avoid an embarrassing situation. $\endgroup$
    – fgrieu ♦
    Oct 9, 2017 at 14:46

0

Reset to default

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.