On hash breaks, was Re: First quantum crypto bank transfer

[Joseph Ashwood]

----- Original Message ----- 
From: "Jerrold Leichter" <jerrold.leichter at smarts.com>
Subject: Re: On hash breaks, was Re: First quantum crypto bank transfer


> | (they all have backup
> | plans that involve the rest of the SHA series and at the very least
> | Whirlpool).
> Moving to a larger hash function with no underlying theory isn't very far 
> from
> the "million-bit key" algorithms you see all over the place.  Bigger 
> probably
> can't be worse, but is it really better?

The key expansion problem is why the rest of the SHA series is present, and 
Whirlpool is present because of the fundamental flaw problem. The truth is 
that having a diversity of options for this is simple enough, it takes only 
a small amount of additional work to allow a cryptographic function to be 
easily replaced, and making it replacable by 1000 is only marginally more 
difficult than 2, the four I listed are well-built, which is why they are 
the recommended ones.

> Suppose a year ago I offered the following bet:  At the next Crypto, all 
> but
> one of the widely-discussed hash functions will be shown to be 
> fundamentally
> flawed.  What odds would you have given me?

I think it would be important to change the phrasing a bit to make the odds 
more quantifiable, simply chagne "At the next Crypto" to "By the end of the 
next Crypto." With that said considering history, I would've put the odds at 
~~5:1 (Current hash functions seem to be broken quite often, and being the 
house I want the odds in my favor). But you are correct in that this 
represents a major advance in the state of the art, one that has taken large 
portions of the security community completely blind, I simply took the 
opportunity to push the concept of good business planning into this as a way 
that allows a good escape plan should anything happen.

> What odds would you have given me
> on the following bet:  At the next Crypto, an attack against AES that is
> substantially better than brute force will be published?  If the odds were
> significantly different, how would you have justified the difference?

Very different odds actually, we as a group have a much better understanding 
of block ciphers than hash functions, as evidence the just published 4 for 
the price of 2 break (cryptography list post by "Hal Finney" Subject: More 
problems with hash functions 8/20/2004). However AES has one of the smallest 
security margins available, so let's put it around 10:1, I really don't 
expect a break, but I would not be excessively shocked to see one made. It 
is for this very reason that again I recommend to all my clients that the 
have backup plans here as well, all the AES finalists, and Camellia because 
of it's Nessie selection.



> Let's update the question to today:  Replace "widely-discussed hash 
> functions"
> with "SHA-1 and the related family".  Keep the AES bet intact.  But let's 
> got
> out 5 years.  Now what odds do you give me?  Why?
SHA series     1:1
AES               3:1
Whirlpool       3:1 (even though it wasn't asked)
Camellia         3:1
Of SHA and Whirlpool being felled by the same attack in the next 5 years 
100:1
AES and Camellia by the same attack within 5 years 30:1

SHA in five years because the SHA methodology is showing some cracks, there 
are only minor differences between SHA-0 and SHA-1, and the differences 
between SHA-1 and SHA-256/384/512 are basically just matters of scale, I 
expect to see a major break against the methodology within 10 years, and 
with the current renewed interest in hash functions I expect the manpower to 
be available very soon to find that break.

AES is a very solid algorithm, but it's security margin is too close for me, 
this is always solid evidence that a break may be just around the corner, 
that the evidence is that various agencies don't have a break is irrelevant, 
the current evidence is that the general cryptographic community is < 10 
years behind and gaining quickly..

Whirlpool has the same odds as AES because the underlying cipher is based on 
the same methodology, by the same people, so if it has a flaw it is likely 
to be extremely similar.

Camellia simply does not have the examination behind it that the AES 
finalists do, something that makes me nervous and why it is only a backup 
algorithm.

SHA and Whirlpool are unlikely to all at the same time because they have 
fundamentally different cores, SHA is a hash constructed primitive, 
Whirlpool a block cipher constructed primitive based on a chaining mode. 
This makes the odds of a single attack felling both slim at best. This odd 
is probably slanted too far in my favor.

AES and Camellia by the same attack is more likely because the tools against 
block ciphers are generally cross borders capable, and the differences 
between the styles in Camellia and AES are simply not great enough to 
prevent this. The difference in the styles though represents the additional 
3.333:1 odds.

All my odds on this are conservative and based on sloppy meanings (you and I 
may have very different meanings for "substantially better than brute 
force), but I believe them to be conservative by approximately the same 
amount. Obviously these odds are dependent on variables that are not 
covered, for example if some information only requires 2^80 security the 
odds of AES surviving 50 years is vastly better than the odds I gave, but if 
it requires 2^255.999999 the odds of a break are much higher, and for such a 
case I would already be recommending a layered solution (e.g. 3-AES).
                Joe

Trust Laboratories
Changing Software Development
http://www.trustlaboratories.com 

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com