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

John Kelsey crypto.jmk at gmail.com
Fri Jan 31 19:26:56 EST 2014


On Sunday, January 19, 2014, Sergio Lerner <sergiolerner at pentatek.com>
wrote:

> I'm working in a password hashing construction (RandMemoHash, see
> http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/
> ).
>
> I need the fastest possible crypto "hash" function, even if breaking
> pre-image resistance requires about 2^32 operations. Collision
> resistance is unimportant. This is because the algorithm will repeatedly
> apply the reduced round hash function, so at the end, enough rounds will
> be applied.
> My first choice is SHA-256 with 16 rounds (out of 64). I want to find
> the best pre-image attack  that requires little memory.
> I searched for information on papers but all I found is attacks against
> 36 and more rounds.
>
> Two questions:

1.  Is the attack you care about finding a preimage, or inverting the
function?

Just to define terms my terms:  Suppose I give you F(x).  If you can find
x, then you can invert the function.  If you can find *any* value y such
that F(x)=F(y), whether y=x or not, you're finding a preimage.  If you can
find that y, but you need F(x) and x to do it, and you have to find
y!=x, you're finding a second preimage.

If you care about making sure the function can't be inverted, then looking
at most preimage attacks on hash functions isn't too helpful, because
they're worried about solving a different (easier) problem than you care
about.  If you can invert functions,  you can find preimages, but not in
general the other way around.  It's really rare to see an inversion attack
on a hash function.

2.  Do you need a 256-bit wide state, or could you do with less?

Part of what makes SHA256 expensive is the need to process so many bits of
state and message.   It has to process 256 bits of hash state, and 512 bits
of message block for each compression function call.  That imposes a
big cost which you may not need to pay.  You are probably just hashing a
very small block over and over again, so it sucks to pay the cost of
processing 512 bits of input each time, especially if you really only need
to keep hashing (say) 128 bits of state.  Or do you need to process the
whole password string at each iteration?  (If so, you probably do need a
hash function.)

If you only need a function that can't be inverted over a smallish state,
you might want to look at block ciphers.  If you have a block cipher
E(k,x), you can get a pretty good one-way function from

F(k) = E(k,constant)

Finding k in this case equals recovering the key given a single
known plaintext.  So it's hard to invert if the block cipher is strong.

I suspect that AES with three rounds will give you more than 32 bits of
security against inversion attacks with a single known plaintext.

If you need preimage resistance, but you are looking at a fairly small
state, you might want to look at smaller variants of some hash functions.
 There are smaller Keccak variants defined.  The 200-bit permutation
version can give you more than 32 bits of preimage resistance with a
128-bit input size, and if you are only worried about a 32 bit security
level, you probably can get away with a lot fewer rounds--maybe 8 or 10.



> Any idea?
>
> Thanks,
>  Sergio.


--John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140131/4919fb07/attachment.html>


More information about the cryptography mailing list