[Cryptography] Pre-image security of SHA-256 reduced to 16 rounds

[John Kelsey]

On Feb 1, 2014, at 12:48 PM, Nemo <nemo at self-evident.org> wrote:
> 
> John Kelsey <crypto.jmk at gmail.com> writes:
> 
>> Just to define my terms: Suppose I give you F(x).  If you can find x,
>> then you can invert the function.
> 
> If the function is many-to-one (like, say, a hash function), then your
> definition of "invert" is pointless because it is vacuously
> impossible. For example, the function "x modulo 12" is non-invertible by
> your definition. This has nothing to do with cryptography.
 
No, this is a really important distinction, and one that otherwise pretty savvy people get mixed up all the time.  

Here's an example: If you have a smaller Keccak variant with a capacity of 80 bits, both collisions and preimages are easy to find with 2^{40} work.  However, suppose you have recovered a password file with lots of entries using this weak hash function.  The 2^{40} preimage attack doesn't help you *at all* in recovering passwords from the file.  

Here's another example:  The old RSAREF PRNG used MD5 in counter mode (Hash_DRBG in SP 800-90 uses SHA1 or SHA2 in counter mode) to generate outputs.  So you'd get pseudorandom output like

hash(C)
hash(C+1)
hash(C+2)
...
hash(C+n)

where all the additions were mod 2^{512} or something.

Now, a preimage attack (find *any* input x* such that hash(C+j)=hash(x) is of neglible value in attacking the PRNG.  But an attack that lets you go backwards and learn C (or the high 64 bits of C) from these outputs also allows you to break the PRNG.

For more examples, consider the use of hash functions to construct KDFs, or consider HMAC. 

> - Nemo

--John