On Sunday, January 19, 2014, Sergio Lerner <<a href="mailto:sergiolerner@pentatek.com">sergiolerner@pentatek.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I'm working in a password hashing construction (RandMemoHash, see<br>
<a href="http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/" target="_blank">http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/</a>).<br>
<br>
I need the fastest possible crypto "hash" function, even if breaking<br>
pre-image resistance requires about 2^32 operations. Collision<br>
resistance is unimportant. This is because the algorithm will repeatedly<br>
apply the reduced round hash function, so at the end, enough rounds will<br>
be applied.<br>
My first choice is SHA-256 with 16 rounds (out of 64). I want to find<br>
the best pre-image attack  that requires little memory.<br>
I searched for information on papers but all I found is attacks against<br>
36 and more rounds.<br>
<br></blockquote><div>Two questions:</div><div><br></div><div>1.  Is the attack you care about finding a preimage, or inverting the function?</div><div><br></div><div>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.</div>
<div><br></div><div>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.  </div>
<div><br></div><div>2.  Do you need a 256-bit wide state, or could you do with less?  </div><div><br></div><div>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.)  </div>
<div><br></div><div>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 <br>
</div><div><br></div><div>F(k) = E(k,constant)</div><div><br></div><div>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.  </div><div>
<br></div>I suspect that AES with three rounds will give you more than 32 bits of security against inversion attacks with a single known plaintext.  <div><br></div><div>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.  </div>
<div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Any idea?<br>
<br>
Thanks,<br>
 Sergio.</blockquote><div><br></div><div>--John</div></div>