Financial Cryptography

FWIW, here's the little Perl program I wrote to convert the HEX back to binary so I could check the results. A real nerd could do this in one line.....

while (<>) {
@words = split(' ', $_);
foreach $w (@words) {
my $i;
for ($i = 0; $i < 4; $i++) {
$w =~ s/(..)//;
my $byte = $1;
print pack("H*", $byte);
}
}
}

I was originally flustered by the byte ordering coming out swapped in the above hex text, but that seems to be an artifact of their machine, not mine.

Greg Rose wrote, in summary of Crypto:

Eli Biham -- has collisions on 34 (out of 80) rounds of SHA-1, but can extend that to probably 46. Still nowhere near a break.

Antoine Joux -- his team announced the collision on SHA-0 earlier this week. There is concentration on the so-called "IF" function in the first 20 rounds... f(a,b,c) = (a & b) ^ (~a & c). That is, the bits of a choose whether to pass the bits from b, or c, to the result. The technique (and Eli's) depends on getting a "near collision" in the first block hashed, then using more near collisions to move the different bits around, finally using another near collision to converge after the fourth block hashed. This took 20 days on 160 Itanium processors. It was about 2^50 hash evaluations.

Xiaoyun Wang was almost unintelligible. But the attack works with "any initial values", which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes. It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. The attack on Haval takes about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can improve it). SHA-0 about 2^40 (1000 times better than Joux).

Xuejia Lai clarified that the paper on E-print has been updated with correct initial values. They were initially byte-reversed, which they blamed on Bruce Schneier.

Greg.

In the light of day and less inebriated, I'd like to clarify some of what I wrote last night, and maybe expand a bit. My original account wasn't what I'd like to think of as a record for posterity.

Greg.

At 13:11 2004-08-18 +1000, Greg Rose wrote:

> Xiaoyun Wang was almost unintelligible.

This was not meant as a criticism. It just meant you had to concentrate really hard. Her English is much better than my Chinese.

> But the attack works with "any initial values", which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes.

As mentioned previously, the idea is to produce a good "partial collision" with the first blocks input to the hash, and then from two similar starting points, find subsequent blocks that correct them back to the same output. So, for a given input chaining vector, it takes about an hour to get the partial collisions in the first input block. From there, they can compute subsequent "second blocks" to produce the collisions in a few minutes.

Note that they did two entirely new collisions for MD5 overnight, communicating back to China, when they found out about the endianness problems. No-one can now argue that they can't find collisions at will.

> It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it.

With further hindsight, and Phil Hawkes' help, I understand now. The technique needs to alternate between single bit (xor) differences and subtractive differences, with careful conditioning of the bits affected to make sure the right carries do, or don't, propagate. This is explained in Phil's upcoming paper about SHA-2 cancellations, which was presented later in the rump session. That should be on e-print in the next couple of days. The Chinese team is also writing a much more detailed paper, but it will take longer.

There has been criticism about the Wang et. al paper that "it doesn't explain how they get the collisions". That isn't right. Note that from the incorrect paper to the corrected one, the "delta" values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. How they got this insight, we'll have to wait for... but the "method" is already there.

Greg.

Jon Callas writes on one of the crypto lists:

I'm still at Crypto. SHA-1 is still safe. There have been a lot of unconfirmed reports about all sorts of things.

The bottom line is that SHA-1 is the most analyzed, still-safe hash function we have. That is also the bad news. There needs to be a lot more work on hash functions. However, none of the attacks we learned of this week apply to SHA-1.

Jon