Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(General)
Line 15: Line 15:
 
* ?
 
* ?
 
* etc.
 
* etc.
 
 
[[image:SHA1CompressionFunction.jpg|right|thumb|The SHA-1 compression function]]
 
 
[[image:SHA1StateUpdateTransformation.jpg|right|thumb|One step of the SHA-1 state update transformation]]
 
 
== General Description ==
 
 
SHA-1 is an iterated hash function. It can be used to
 
compute a 160-bit hash value for messages having a length of less
 
than 2<sup>64</sup> bits, cf. [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf  FIPS 180-2 Secure Hash Standard].
 
As most iterated hash functions, SHA-1 applies MD strengthening.
 
 
 
=== Compression Function ===
 
The compression function processes input message blocks of 512 bits and
 
produces a 160-bit chaining value. The compression function of
 
SHA-1 basically consists of two parts: the message expansion and
 
the state update transformation. The chaining variable <amsmath>$h_{i-1}$</amsmath> (''iv'' in the first iteration) is added to the output of the state update transformation (feed forward).
 
 
==== Message Expansion ====
 
In SHA-1, the message expansion is defined as follows. A single
 
512-bit input message block block is represented by 16 32-bit
 
words, denoted by <amsmath>$M_i$</amsmath>, with <amsmath>$0 \leq i \leq 15$</amsmath>. The message input is linearly expanded into 80 32-bit words <amsmath>$W_i$</amsmath> defined as follows:
 
 
<amsmath>
 
\begin{equation*}
 
W_i =
 
\begin{cases}
 
    M_i                                                            & \text{for $\phantom{1}0 \leq i \leq 15$} \\
 
    (W_{i-3} \oplus W_{i-8} \oplus W_{i-14} \oplus W_{i-16}) \lr\ 1 & \text{for $16 \leq i \leq 79$}
 
\end{cases}
 
\end{equation*}
 
</amsmath>
 
 
==== State Update Transformation ====
 
 
The state update transformation starts from a fixed initial value
 
''iv'' for 5 32-bit registers <amsmath>$A,B,\dots,E$</amsmath> (also
 
referred to as state variables) and updates these registers in 80
 
steps (<amsmath>$i = 0,\dots,79$</amsmath>) by using the word <amsmath>$W_i$</amsmath> and the step
 
constant <amsmath>$K_i$</amsmath> in step <amsmath>$i$</amsmath>. One step of the state update transformation is defined as
 
 
<amsmath>
 
\begin{equation*}
 
\begin{aligned}
 
    A_{i+1} &= A_i \lr 5 + W_i + f(B_i,C_i,D_i) + K_i\\
 
    B_{i+1} &= A_i\\
 
    C_{i+1} &= B_i \rr \\
 
    D_{i+1} &= C_i\\
 
    E_{i+1} &= D_i
 
\end{aligned}
 
\end{equation*}
 
</amsmath>
 
 
The function <amsmath>$f$</amsmath> depends on the step number: steps <amsmath>$i=0,\dots,19$</amsmath> use the ''IF-function'' referred to as <amsmath>$f_{if}$</amsmath> and steps <amsmath>$i = 40,\dots,59$</amsmath> use the ''MAJ-function'' referred to as <amsmath>$f_{maj}$</amsmath>. The
 
remaining steps, use a 3-input XOR referred to as <amsmath>$f_{xor}$</amsmath>. The Boolean functions are defined as follows:
 
 
<amsmath>
 
\begin{eqnarray*}
 
f_{if}(B,C,D) &=& (B\wedge C) \oplus (\neg B\wedge D) \\
 
f_{maj}(B,C,D) &=& (B\wedge C) \oplus (B\wedge D) \oplus (C\wedge D)\\
 
f_{xor}(B,C,D) &=& B \oplus C \oplus D
 
\end{eqnarray*}
 
</amsmath>
 
 
=== Padding Method ===
 
=== Constants and Initial Value ===
 
 
==== Constants ====
 
<amsmath>
 
\begin{equation*}
 
    \begin{aligned}
 
        K_i &= \hex{5A827999} \quad \text{for $i=\phantom{0}0,\dots,19$} \\
 
        K_i &= \hex{6ED9EBA1} \quad \text{for $i=20,\dots,39$} \\
 
        K_i &= \hex{8F1BBCDC} \quad \text{for $i=40,\dots,59$} \\
 
        K_i &= \hex{CA62C1D6} \quad \text{for $i=60,\dots,79$} \\
 
    \end{aligned}
 
\end{equation*}
 
</amsmath>
 
 
==== Initial Value ====
 
<amsmath>
 
\begin{equation*}
 
    \begin{aligned}
 
        A_0 &= \hex{67452301} \quad B_0 = \hex{EFCDAB89} \quad C_0 = \hex{98BADCFE}\\
 
        D_0 &= \hex{10325476} \quad E_0 = \hex{C3D2E1F0}
 
    \end{aligned}
 
\end{equation*}
 
</amsmath>
 
 
== Claimed/Expected Security Margins ==
 
 
== Security Anaylsis ==
 
 
* Best know attack: 2<sup>63</sup> by Wang et.al.
 
* Best known collision example: 64-step collision by De Canniere and Rechberger
 
 
something like: best know attack to date: kind of attack, which variant has been looked at (e.g. round-reduced), complexity, and reference to paper and abstract.
 
 
may be make here a new page with the other cryptanalysis results.
 
 
* [http://mediawiki.iaik.tugraz.at/index.php/SHA-1CryptAnalysis [Detailed overview of cryptanalysis results for SHA-1]]
 

Revision as of 14:10, 16 October 2006

1 General

2 Cryptanalysis

We can try to give the basic infrmation: so block size general construction of compression functions etc. NO DETAILS. Just reference to the paper proposing the hash function. Then we list the attacks or preliminary analyses. We give the abstract and our opinion about this attack. For instance 2nd-preimages in much less than 2n. Opinion could be: very nice observation, generic, but still not practical since extreme message lengths are required.

I think we should go this way. Esecially we should clearly say what is

  • broken
  • wounded
  •  ?
  • etc.