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

[Sergio Lerner]

Thank you John for taking the time to answer my question. Here are my
additional comments...
 
El 31/01/2014 09:26 p.m., John Kelsey escribió:
> On Sunday, January 19, 2014, Sergio Lerner <sergiolerner at pentatek.com
> <mailto: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. 
As I see the first two are the same, depending if the function F is a
one-way-permutation or a pseduo-random function.
I don't care about second preimage resistance, and I don't care if it's
a permutation or a pseudo-random 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.)  
>

No, actually the state could be as low as 64-bits, if finding a preimage
costs as much as 2^32 operations.
Nevertheless it must be the case that the cost of "hashing" a fixed
length message must be lower. E.g. for a 80 byte message, applying 10
times a 8-byte input/digest function F should cost less than using a
single 80-byte  i/d 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. 
Yes, but then I need a function with a very fast (or inexistent)
key-schedule. Maybe XTEA.
>
> 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.  
>
Where is this Keccak variant defined?

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