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

"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 sha_exp_rev.py that compute valid error vectors. 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.

Advertisements

## Leave a Reply