[149288] in cryptography@c2.net mail archive
Re: [Cryptography] Pre-image security of SHA-256 reduced to 16
daemon@ATHENA.MIT.EDU (Sergio Lerner)
Sat Feb 1 00:14:53 2014
X-Original-To: cryptography@metzdowd.com
Date: Fri, 31 Jan 2014 23:24:02 -0300
From: Sergio Lerner <sergiolerner@pentatek.com>
To: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
In-Reply-To: <CAGU4h9M4-HEW+0mR=Mv9f5GKsRe=gsYzqeyfKxK3NpgUKTLaOw@mail.gmail.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
This is a multi-part message in MIME format.
--===============8384634251824846407==
Content-Type: multipart/alternative;
boundary="------------000207030104000707040303"
This is a multi-part message in MIME format.
--------------000207030104000707040303
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
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@pentatek.com
> <mailto: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.
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?
--------------000207030104000707040303
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<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>
--------------000207030104000707040303--
--===============8384634251824846407==
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
--===============8384634251824846407==--
