[149287] in cryptography@c2.net mail archive
Re: [Cryptography] Pre-image security of SHA-256 reduced to 16
daemon@ATHENA.MIT.EDU (John Kelsey)
Sat Feb 1 00:13:18 2014
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <52DBD50D.2020808@pentatek.com>
Date: Fri, 31 Jan 2014 19:26:56 -0500
From: John Kelsey <crypto.jmk@gmail.com>
To: Sergio Lerner <sergiolerner@pentatek.com>
Cc: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============5746882781650750224==
Content-Type: multipart/alternative; boundary=001a1136c0ba13fc7704f14d5991
--001a1136c0ba13fc7704f14d5991
Content-Type: text/plain; charset=ISO-8859-1
On Sunday, January 19, 2014, Sergio Lerner <sergiolerner@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
--001a1136c0ba13fc7704f14d5991
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
On Sunday, January 19, 2014, Sergio Lerner <<a href=3D"mailto:sergiolern=
er@pentatek.com">sergiolerner@pentatek.com</a>> wrote:<br><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;p=
adding-left:1ex">
I'm working in a password hashing construction (RandMemoHash, see<br>
<a href=3D"http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-=
functions/" target=3D"_blank">http://bitslog.wordpress.com/2013/12/31/stric=
t-memory-hard-hash-functions/</a>).<br>
<br>
I need the fastest possible crypto "hash" function, even if break=
ing<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 =A0that 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. =A0Is the =
attack you care about finding a preimage, or inverting the function?</div><=
div><br></div><div>Just to define terms my terms: =A0Suppose I give you F(x=
). =A0If you can find x, then you can invert the function. =A0If you can fi=
nd *any*=A0value y such that F(x)=3DF(y), whether y=3Dx or not,=A0you'r=
e finding a preimage. =A0If you can find that y, but you need F(x) and x to=
do it, and you have to find y!=3Dx,=A0you're finding a second preimage=
.</div>
<div><br></div><div>If=A0you=A0care about making sure the function can'=
t be inverted, then looking at most preimage attacks on hash functions isn&=
#39;t too helpful, because they're worried about solving a different (e=
asier) problem than you care about. =A0If you can invert functions,=A0=A0yo=
u can find preimages, but not in general=A0the other way around. =A0It'=
s really rare to see an inversion attack on a=A0hash function. =A0</div>
<div><br></div><div>2. =A0Do you need a 256-bit wide state, or could you do=
with less? =A0</div><div><br></div><div>Part of what makes SHA256 expensiv=
e is the need to process so many bits of state and message. =A0 It has to p=
rocess 256 bits of hash state, and 512 bits of message block for each compr=
ession function call. =A0That imposes a big=A0cost which=A0you may not need=
to pay. =A0You 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 tim=
e, especially if you really only need to keep hashing (say) 128 bits of sta=
te. =A0Or do you need to process the whole password string at each iteratio=
n? =A0(If so, you probably do need a hash function.) =A0</div>
<div><br></div><div>If you only need a function that can't be inverted =
over a smallish state, you=A0might want to look at block ciphers. =A0If you=
have a block cipher E(k,x), you can get a pretty good one-way function fro=
m=A0<br>
</div><div><br></div><div>F(k) =3D E(k,constant)</div><div><br></div><div>F=
inding k in this case equals recovering the key given a single known=A0plai=
ntext. =A0So it's hard to invert if the block cipher is strong. =A0</di=
v><div>
<br></div>I suspect that AES with three=A0rounds will give you more than 32=
bits of security against inversion attacks with a single known plaintext. =
=A0<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 som=
e hash functions. =A0There are smaller Keccak variants defined. =A0The 200-=
bit permutation version can give you more than 32 bits of preimage resistan=
ce with a 128-bit input size, and if you are only worried about a 32 bit se=
curity level, you probably can get away with a lot fewer rounds--maybe 8 or=
10. =A0</div>
<div><div><br></div><div>=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Any idea?<br>
<br>
Thanks,<br>
=A0Sergio.</blockquote><div><br></div><div>--John</div></div>
--001a1136c0ba13fc7704f14d5991--
--===============5746882781650750224==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============5746882781650750224==--
