Why does this SHA-1 relation hold?

Question

In De Canniere & Rechberger's 2008 paper "Preimages for Reduced SHA-0 and SHA-1", the following statement appears on page 6:

Suppose that we restrict ourselves to the first $j$ + 1 bits of each expanded message word $W_i$ (denoted by $W^{j...0}_i$), and that we keep all state bits constant except for those at bit position $j$ + 2 (referred to as $a^{j+2}_i$). In this case, we can derive a simple relation (by collecting all constant parts into a $j$ + 1-bit word $C^{j...0}_i$ and a 1-bit variable $c^j_i$), which holds as long as $0 \leq j < 25$: $$ W^{j...0}_i = C^{j...0}_i − (f(c^j_i , a^{j+2}_{i−2} , a^{j+2}_{i−3}) \ll j) − (a^{j+2}_{i−4} \ll j). $$

I've been trying to understand why this relation holds for many hours, and still can't figure out how it can be true.

• The $f$ function takes three inputs: $a_{i-1}^{j}$, $a_{i-2}^{j+2}$, and $a_{i-3}^{j+2}$. Therefore, $c_i^j = a_{i-1}^{j}$, but the text indicates that $c_i^j = a_{i}^{j+2}$. How is this possible?

• What has happened to the $A_{i+1}$ and $A_i$ terms? Have they somehow been incorporated into $C_i^{j..0}$ by the text "collecting all constant parts"?

I'd be grateful for anyone who can point me in the direction of source code that implements a preimage attack like this, but if no such thing exists, then I'll be happy for an explanation of the above, and I'll try to work out the rest of the details myself.

Edit: is there a typo? If so, what is the correct relation? I ask because I've just noticed that on the previous page, the error word relation is definitely incorrect. It should be

$$ E_i = W_i \oplus ((W_{i+3} \oplus W_{i+8} \oplus W_{i+14} \oplus W_{i+16}) \ggg s) $$

Answer 1

First let's write the original relation that they are deriving this one from:

$$ W_i = A_{i+1} - (A_i \lll 5) - f(A_{i-1}, A_{i-2} \ggg 2, A_{i-3} \ggg 2) - (A_{i-4} \ggg 2) - K_i $$

So, if everything in the state bits are fixed except the ones in position $j+2$, all the operations on the fixed bits could be gathered together and we can simplify the relation to the variable ones. Now, let's derive the new relation.

For now, let's put the $c_i^j$ aside and write the term related to $f$. Then the variables in $A_{i-2}$ and $A_{i-3}$ (which are $a_{i-2}^{j+2}$ and $a_{i-3}^{j+2}$) are mixing with the fixed value of $A_{i-1}$ (which is $a_{i-1}^j$), and the rest is fixed. Thus the term $f(a_{i-1}^j, a_{i-2}^{j+2}, a_{i-3}^{j+2})$, and the result is in position $j$, so the $\ll j$ is added. We can add the term $(a_{i-4}^{j+2} \ll j)$ (corresponding to the last term in original relation).

The remaining terms can be collected in the $C_i^{j..0}$. Although both of the $A_{i+1}$ and $A_i$ have variable bits at position $j+2$, they do not contribute to the value of bit positions $j..0$ of $W$. The only way they get involved is that by left rotation of ($A_i \lll 5$), the variable bit gets rotated and falls in $j..0$. It happens if $(j+2) + 5 > 31$, but they restrict the $j$ to $0\le j \lt 25$, so it doesn't happen.

And about the $E_i$ relations. Your relation is not quite right. We know that: $$ W_{i+16} = (W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i) \lll s $$ Therefore: $$ W_{i+16} \ggg s = W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i $$ and in other words: $$ W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i \oplus (W_{i+16} \ggg s) = 0 $$ if there is no error in calculating $W_i$s. So they define the error bit vectors as: $$ E_i = W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i \oplus (W_{i+16} \ggg s) $$ with the goal of making all $E_i$ equal to zero.