|
|
| 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]]
| |
