<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Thank you John for taking the time to
answer my question. Here are my additional comments...<br>
<br>
El 31/01/2014 09:26 p.m., John Kelsey escribió:<br>
</div>
<blockquote
cite="mid:CAGU4h9M4-HEW+0mR=Mv9f5GKsRe=gsYzqeyfKxK3NpgUKTLaOw@mail.gmail.com"
type="cite">On Sunday, January 19, 2014, Sergio Lerner <<a
moz-do-not-send="true" 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 moz-do-not-send="true"
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. <br>
</div>
</blockquote>
As I see the first two are the same, depending if the function F is
a one-way-permutation or a pseduo-random function. <br>
I don't care about second preimage resistance, and I don't care if
it's a permutation or a pseudo-random function <br>
<blockquote
cite="mid:CAGU4h9M4-HEW+0mR=Mv9f5GKsRe=gsYzqeyfKxK3NpgUKTLaOw@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>2. Do you need a 256-bit wide state, or could you do with
less? </div>
<div><br>
</div>
</blockquote>
<br>
<blockquote
cite="mid:CAGU4h9M4-HEW+0mR=Mv9f5GKsRe=gsYzqeyfKxK3NpgUKTLaOw@mail.gmail.com"
type="cite">
<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>
</blockquote>
<br>
No, actually the state could be as low as 64-bits, if finding a
preimage costs as much as 2^32 operations. <br>
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.<br>
<br>
<blockquote
cite="mid:CAGU4h9M4-HEW+0mR=Mv9f5GKsRe=gsYzqeyfKxK3NpgUKTLaOw@mail.gmail.com"
type="cite">
<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. <br>
</blockquote>
Yes, but then I need a function with a very fast (or inexistent)
key-schedule. Maybe XTEA.<br>
<blockquote
cite="mid:CAGU4h9M4-HEW+0mR=Mv9f5GKsRe=gsYzqeyfKxK3NpgUKTLaOw@mail.gmail.com"
type="cite">
<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>
</blockquote>
Where is this Keccak variant defined?<br>
<br>
</body>
</html>