On hash breaks, was Re: First quantum crypto bank transfer
ashwood at msn.com
Tue Aug 24 18:32:24 EDT 2004
----- 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
> the "million-bit key" algorithms you see all over the place. Bigger
> 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
> one of the widely-discussed hash functions will be shown to be
> 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
> with "SHA-1 and the related family". Keep the AES bet intact. But let's
> out 5 years. Now what odds do you give me? Why?
SHA series 1:1
Whirlpool 3:1 (even though it wasn't asked)
Of SHA and Whirlpool being felled by the same attack in the next 5 years
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
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
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).
Changing Software Development
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography