Stupid Compiler

Notes on things about stuff

[SHA, Right] What's Joux Talkin' Bout?

leave a comment »

"Differential Collisions in SHA-0"

Chabaud & Joux begin by attacking a weakened SHA-0 variation.  The first version, which
they call SHI1, is equivalent to SHA-0 with the addition operations in A_{i+1} replaced
with XORs and the f_i functions replaced by XOR.  This effectively removes the
non-linearity introduced by the f_i function and the addition operations.

The analysis of SHI1 begins by examing the effect of perturbations of the vector
W_{i} (0 <= i < 80) directly (instead of trying to study the perturbations of the
message block, M or W_i (0 <= i = 75 "since a perturbation in
round i is never corrected before round i + 6, and since all perturbations must be
corrected by round 80."

The intuitive explanation of the process

Important observation:
* The expansion process does not interleave bits!  This turns it into a function
from 16 bits to 80 bits over each bit in the word.

1. Find valid perturbations -- these are deduced by ensuring they fit the expansion
recurrence relation.  It is important to see that since the compression functions
starts primed with some A - E, the recurrence must actually start at the 11th word
(5 steps [A-E] behind the 16th that the recurrence is defined at).

The search is brute force with a search space of 2^16.  It is simple.

We will call the chosen error vector e_{0}

TODO: Include the functions taken from that compute valid error

2. Now, derive the global differential mask (which is M in the paper -- M is also
the message block... bad naming).  The global differential mask is derived by fixing
the flips found in the previous step with the differential path described in the
prebvious section.  Since the SHI1 defines all combination function in the
compression function as XOR, we can XOR the differential paths for all the bits
flipped in e_{0} to compute up with the global mask.  We will call the global mask
G.  We only need the first 16 words of this mask since those will define the rest of
it (via the expansion function).

NOTE: Maybe worth pointing out that this will generate a valid W' because e_{0}
satisfies (9).

3. Given the global mask M and *any* input message M, SHI1(M) == SHI1(M \xor G).

Collision!  Hooray!  Wait.  That's just SHI1.  It's all linear.  We just solved an
algebra equation.  Oh.

Written by dionthegod

April 29, 2008 at 5:42 am

Posted in Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: