Re: [Hash] BOF Goals

[Jon Callas <[e-mail]>]

Paul's asked me to discuss more, particularly so we can have more email 
discussions prior to Paris. He's also rightly pointed out that my CFRG 
discussion isn't here, and without good cross-referencing, I shouldn't 
assume people here have read it. So here's the note that I sent some 
time ago:



Begin forwarded message:

From: Jon Callas <[e-mail]>
Date: 13 June 2005 3:38:10 PM PDT
To: [e-mail]
Subject: Re: [Cfrg] new i-d: randomized hashing

On 13 Jun 2005, at 7:18 AM, Ben Laurie wrote:

> D. J. Bernstein wrote:
>> Ben Laurie writes:
>>> It seems to me that life would be generally easier if you defined a 
>>> modified hash function H_r(m) and then constructed H'(m)=(r,H_r(m)). 
>>> This way transport of r happens automatically, but the hash gets 
>>> wider.
>> Even better, use the extra space for a longer _deterministic_ hash. 
>> For
>> example, instead of using 96 bits for r and 160 bits for SHA-1 output,
>> simply use SHA-256.
>
> That assumes we're confident SHA-256 won't have similar flaws.
>

Ben brings up a good point, but I side with Dan Bernstein. I think 
SHA-256 is the right way to go, and we don't need anything else until 
we get new hash functions that have the attributes we want.

I am quite confident that SHA-256 has similar flaws to SHA-1 and all 
the others, but I think the right thing to do for the time being is to 
just use it. This is what we've done in PGP.

Here's my reasoning why:

SHA-1 is supposed to have 80 bits of security. Our present knowledge of 
it has it around 69. (I will handwave what this means, because yes, I 
know that this isn't pre-image collision, it doesn't apply to hmacs or 
similar constructions, etc.) It's thus missing 11 bits of security.

SHA-256 is supposed to have 128 bits of security. If we assume a 
similar flaw, SHA-256 should be missing about 17.6 bits of security. 
(That's (11/80) * 128.)

Let's take that 17.6 and round it up to 38. Yup, thirty-eight. Not 
twenty-eight, not eighteen. I have a cynical rounding function. That 
gives us 90 bits of security.

At 90 bits of security, I'm happy to live with SHA-256 for a while. I 
believe that the hash function we *want* to be using hasn't been 
written yet. (My guess is that it will be announced around the time of 
Asiacrypt '06, and papers published in FSE '07. We're not going to be 
comfortable with it until early '08, but will still whine and mutter 
about it until September '09. The FIPS for it won't appear -- sorry, 
I'm not going to make that cheap joke; NIST will actually make a FIPS 
before the whining stops.)

At 90 bits of security, we can live with it for another five years. And 
this assumes my rounding function, which scopes the "similar" flaw in 
SHA-256 to actually be a million times more devastating than the SHA-1 
one. If my rounding function should round 17.6 to 28 instead, then 
SHA-256 will last for another 15 years just fine. I think that factor 
of 1024 takes into account a additional decade of semiconductor 
improvements adequately. If my rounding function should round 17.6 to 
18, then SHA-256, while flawed, can live out its natural life. Normal 
engineering improvements can dispose of it sometime in the indefinite 
future -- probably around '09. (Oh, and if it were 80, then we could 
use it for all the same things we expect SHA-1 to do at the mere cost 
of being slow and big.)

We also know that there's no real mathematical insight that Wang and 
others have. It is true that attacks don't get worse, they only get 
better, but there's no reason to think that the attacks on any of the 
hash functions are going to get different in kind, merely in degree. I 
believe that SHA-256 has at least 100 bits of security in it. That's 
why my gedankenexperiment backs it down to 90.

Any number of people have observed that we have taken one basic 
construction for hash functions has been a bunch of tweaks, rather than 
a design change. Everything we have has at some level the same 
architecture. My concern about randomized hashing is that I see it as 
another tweak. Yes, it's a tweak in a higher level construct, but it's 
still a tweak. It's a tweak that requires more fundamental changes to 
the protocols and systems that *use* hash functions than merely 
swapping in a new function. That one is bad enough. I also see no 
reason why this is going to change our core mechanisms of operating. If 
we learn how to make a good hash function sometime between 2010 and 
2020, then that's within the pragmatic safety considerations of 
SHA-256. If something extraordinary happens, then gosh darnit, SHA-512 
should work. I can't believe that SHA-512 will have less than 128 bits 
of security. I'm sorry, I don't. If I'm proved wrong, then we really, 
really don't know what we're doing, and there are many dramatic things 
in information security we have to change.

So to sum up -- this is all interesting, to make randomized hashing, 
but why should I trust it, why should I convert to it? Why am I not 
jumping from the frying pan into another frying pan? Especially when my 
present plan is to use SHA-256, and if that is unacceptable, SHA-512. 
Does anyone believe that they're really that broken? Or to sum up my 
summary, in waiting for the right hash function, am I waiting for 
Godot?

	Jon


_______________________________________________
Cfrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg



________________________________________________________________
This message could have been secured by PGP Universal. To secure
future messages from this sender, please click this link:

https://keys.pgp.com/b/b.e?r=hash%40ietf.org&n=I6LW%2FTFegliptjmtozrp%2Bg%3D%3D

_______________________________________________
Hash mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/hash