Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Compression Function)
(→‎Preimage Attacks)
 
(97 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
== General Description ==
+
== Specification ==
  
−
SHA-1 is an iterated hash function. It can be used to
+
* digest size: 160 bits
−
compute a 160-bit hash value for messages having a length of less
+
* max. message length: < 2<sup>64</sup> bits
−
than <amsmath>$2^{64}$</amsmath> bits, cf. [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 Secure Hash Standard].
+
* compression function: 512-bit message block, 160-bit chaining variable
−
As most iterated hash functions, SHA-1 applies MD strengthening.
+
* Specification: [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 Secure Hash Standard]
  
 +
== Cryptanalysis ==
  
−
=== Compression Function ===
+
=== Best Known Results ===
−
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).
 
  
−
[[image:SHA1CompressionFunction.jpg|right|thumb|250px|The SHA-1 compression function]]
+
The best collision attack on full SHA-1 was published by Wang et al. It has complexity of 2<sup>69</sup> hash evaluations. The best collision example, a 70-step collision for SHA-1, was published by DeCanniere, Mendel and Rechberger.
 +
----
  
−
==== Message Expansion ====
+
=== Collision Attacks ===
−
The message expansion is defined as follows:
 
  
−
<amsmath>
+
<bibtex>
−
\begin{equation*}
+
@inproceedings{sacryptCanniereMR07,
−
W_i =
+
  author    = {Christophe De Canni{\`e}re and Florian Mendel and Christian Rechberger},
−
\begin{cases}
+
  title    = {Collisions for 70-Step SHA-1: On the Full Cost of Collision Search},
−
     M_i                                                            & \text{for $\phantom{1}0 \leq i \leq 15$} \\
+
  booktitle = {Selected Areas in Cryptography},
−
     (W_{i-3} \oplus W_{i-8} \oplus W_{i-14} \oplus W_{i-16}) \lr\ 1 & \text{for $16 \leq i \leq 79$}
+
  year      = {2007},
−
\end{cases}
+
  pages    = {56-73},
−
\end{equation*}
+
  url        = {http://dx.doi.org/10.1007/978-3-540-77360-3_4},
−
</amsmath>
+
  editor    = {Carlisle M. Adams and Ali Miri and Michael J. Wiener},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4876},
 +
  isbn     = {978-3-540-77359-7},
 +
  abstract  = {The diversity of methods for fast collision search in SHA-1 and similar hash functions makes a comparison of them difficult. The literature is at times very vague on this issue, which makes comparison even harder. In situations where differences in estimates of attack complexity of a small factor might influence short-term recommendations of standardization bodies, uncertainties and ambiguities in the literature amounting to a similar order of magnitude are unhelpful. We survey different techniques and propose a simple but effective method to facilitate comparison. In a case study, we consider a newly developed attack on 70-step SHA-1, and give complexity estimates and performance measurements of this new and improved collision search method.},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{fseSugitaKPI07,
 +
  author    = {Makoto Sugita and Mitsuru Kawazoe and Ludovic Perret and Hideki Imai},
 +
  title    = {Algebraic Cryptanalysis of 58-Round SHA-1},
 +
  pages    = {349-365},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-74619-5_22},
 +
  editor    = {Alex Biryukov},
 +
  booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4593},
 +
  year      = {2007},
 +
  isbn      = {978-3-540-74617-1},
 +
  abstract  = {In 2004, a new attack against SHA-1 has been proposed
 +
by a team leaded by Wang [15]. The aim of this article is to sophisticate
 +
and improve Wang’s attack by using algebraic techniques. We introduce
 +
new notions, namely semi-neutral bit and adjuster and propose then an
 +
improved message modification technique based on algebraic techniques.
 +
In the case of the 58-round SHA-1, the experimental complexity of our
 +
improved attack is 2<sup>31</sup> SHA-1 computations, whereas Wang’s method needs
 +
2<sup>34</sup> SHA-1 computations. We have found many new collisions for the 58-round SHA-1.
 +
We also study the complexity of our attack for the full SHA-1.}
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{asiacryptCanniereR06,
 +
  author    = {Christophe De Canni{\`e}re and Christian Rechberger},
 +
  title    = {Finding SHA-1 Characteristics: General Results and Applications},
 +
  pages     = {1-20},
 +
  url        = {http://dx.doi.org/10.1007/11935230_1},
 +
  editor    = {Xuejia Lai and Kefei Chen},
 +
  booktitle = {ASIACRYPT},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4284},
 +
  year      = {2006},
 +
  isbn      = {3-540-49475-8},
 +
  abstract  = {The most efficient collision attacks on members of the SHA family presented so far all use complex characteristics which were manually constructed by Wang et al. In this report, we describe a method to search for characteristics in an automatic way. This is particularly useful for multi-block attacks, and as a proof of concept, we give a two-block collision for 64-step SHA-1 based on a new characteristic. The highest number of steps for which a SHA-1 collision was published so far was 58. We also give a unified view on the expected work factor of a collision search and the needed degrees of freedom for the search, which facilitates optimization.},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{cryptoWangYY05a,
 +
  author    = {Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu},
 +
  title    = {Finding Collisions in the Full SHA-1},
 +
  booktitle = {CRYPTO},
 +
  year      = {2005},
 +
  pages    = {17-36},
 +
  url        = {http://dx.doi.org/10.1007/11535218_2},
 +
  editor    = {Victor Shoup},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3621},
 +
  isbn      = {3-540-28114-2},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{eurocryptBihamCJCLJ05,
 +
  author = {Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby},
 +
  title = {Collisions of SHA-0 and Reduced SHA-1},
 +
  booktitle = {EUROCRYPT},
 +
  year = {2005},
 +
  pages = {36-57},
 +
  abstract = {In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53–58 rounds can still be found faster than by birthday attacks. Part of the results of this paper were given by the first author in an invited talk in SAC 2004, Waterloo, Canada.},
 +
  editor = {Ronald Cramer},
 +
  volume = {3494},
 +
  series = {LNCS},
 +
  publisher = {Springer},
 +
  isbn = {3-540-25910-4},
 +
  url = {http://dx.doi.org/10.1007/11426639_3},
 +
}
 +
</bibtex>
  
 +
<bibtex>
 +
@inproceedings{ctrsaRijmenO05,
 +
  author    = {Vincent Rijmen and Elisabeth Oswald},
 +
  title    = {Update on SHA-1},
 +
  booktitle = {CT-RSA},
 +
  year      = {2005},
 +
  pages    = {58-71},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3376},
 +
  abstract  = {We report on the experiments we performed in order to assess the security of SHA-1 against the attack by Chabaud and Joux [5]. We present some ideas for optimizations of the attack and some properties of the message expansion routine. Finally, we show that for a reduced version of SHA-1, with 53 rounds instead of 80, it is possible to find collisions in less than 2^80 operations.},
 +
  url = {http://dx.doi.org/10.1007/b105222}}
 +
</bibtex>
 +
----
  
−
==== State Update Transformation ====
+
=== Preimage Attacks ===
−
<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>
 
  
−
=== Padding Method ===
+
<bibtex>
−
=== Constantsand Initial Value ===
+
@inproceedings{cryptoCanniereR08,
 +
  author    = {Christophe De Canni{\`e}re and Christian Rechberger},
 +
  title    = {Preimages for Reduced SHA-0 and SHA-1},
 +
  booktitle = {CRYPTO},
 +
  year      = {2008},
 +
  pages    = {179-202},
 +
  abstract  = {In this paper, we examine the resistance of the popular hash function SHA-1 and its predecessor SHA-0 against dedicated preimage attacks. In order to assess the security margin of these hash functions against these attacks, two new cryptanalytic techniques are developed: (1) Reversing the inversion problem: the idea is to start with an impossible expanded message that would lead to the required digest, and then to correct this message until it becomes valid without destroying the preimage property. (2) P^3 graphs: an algorithm based on the theory of random graphs that allows the conversion of preimage attacks on the compression function to attacks on the hash function with less effort than traditional meet-in-the-middle approaches. Combining these techniques, we obtain preimage-style shortcuts attacks for up to 45 steps of SHA-1, and up to 50 steps of SHA-0 (out of 80). },
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-85174-5_11},
 +
  editor    = {David Wagner},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5157},
 +
  isbn      = {978-3-540-85173-8},
 +
}
 +
</bibtex>
  
−
==== 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 ====
+
=== Others ===
−
<amsmath>
+
<bibtex>
−
\begin{equation*}
+
@inproceedings{cryptoJouxP07,
−
     \begin{aligned}
+
  author    = {Antoine Joux and Thomas Peyrin},
−
        A_0 &= \hex{67452301} \quad B_0 = \hex{EFCDAB89} \quad C_0 = \hex{98BADCFE}\\
+
  title    = {Hash Functions and the (Amplified) Boomerang Attack},
−
        D_0 &= \hex{10325476} \quad E_0 = \hex{C3D2E1F0}
+
  booktitle = {CRYPTO},
−
     \end{aligned}
+
  year      = {2007},
−
\end{equation*}
+
  pages    = {244--263},
−
</amsmath>
+
  url        = {http://dx.doi.org/10.1007/978-3-540-74143-5_14},
 +
  editor    = {Alfred Menezes},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4622},
 +
  isbn      = {978-3-540-74142-8},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{fseMendelPRR06a,
 +
  author    = {Florian Mendel and Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
 +
  title    = {The Impact of Carries on the Complexity of Collision Attacks on SHA-1},
 +
  pages     = {278-292},
 +
  url        = {http://dx.doi.org/10.1007/11799313_18},
 +
  booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4047},
 +
  year      = {2006},
 +
  isbn      = {3-540-36597-4},
 +
  abstract  = {In this article we present a detailed analysis of
 +
the impact of carries on the estimation of the attack complexity
 +
for SHA-1. We build up on existing estimates and refine them. We
 +
show that the attack complexity is slightly lower than estimated
 +
in all published work to date. We point out that it is more accurate
 +
to consider probabilities instead of conditions.},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{sacryptJutlaP06,
 +
  author    = {Charanjit S. Jutla and Anindya C. Patthak},
 +
  title    = {Provably Good Codes for Hash Function Design},
 +
  booktitle = {Selected Areas in Cryptography},
 +
  year      = {2006},
 +
  pages     = {376-393},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-74462-7_26},
 +
  editor    = {Eli Biham and Amr M. Youssef},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4356},
 +
  isbn      = {978-3-540-74461-0},
 +
  abstract  = {We develop a new technique to lower bound the minimum distance of quasi-cyclic codes with large dimension by reducing the problem to lower bounding the minimum distance of a few significantly smaller dimensional codes. Using this technique, we prove that a code which is similar to the SHA-1 message expansion code has minimum distance at least 82, and that too in just the last 64 of the 80 expanded words. Further the minimum weight in the last 60 words (last 48 words) is at least 75 (52 respectively). We expect our technique to be helpful in designing future practical collision-resistant hash functions. We also use the technique to find the minimum weight of the SHA-1 code (25 in the last 60 words), which was an open problem.},
 +
}
 +
</bibtex>
  
−
== Claimed/Expected Security Margins ==
+
<bibtex>
 +
@inproceedings{sacryptPramstallerRR05a,
 +
  author    = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
 +
  title    = {Impact of Rotations in SHA-1 and Related Hash Functions},
 +
  booktitle = {Selected Areas in Cryptography},
 +
  year      = {2005},
 +
  pages    = {261-275},
 +
  url        = {http://dx.doi.org/10.1007/11693383_18},
 +
  editor    = {Bart Preneel and Stafford E. Tavares},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3897},
 +
  isbn      = {3-540-33108-5},
 +
  abstract  = {SHA-1 uses a single set of rotation constants within the compression function. However, most other members of the MD4 family of hash functions use multiple sets of rotation constants, i.e. the rotation amounts change with the step being processed. To our knowledge, no design rationales on the choice of rotation constants are given on any of these hash functions. This is the first paper that analyzes rotations in iterated hash functions. We focus on SHA-1-like hash functions and use recent developments in the analysis of these hash functions to evaluate the security implications of using multiple sets of rotation constants in the compression function instead of a single set. Additionally, we give some observations on the set of constants used in SHA-0 and SHA-1.},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{iswSatoh05,
 +
  author    = {Akashi Satoh},
 +
  title    = {Hardware Architecture and Cost Estimates for Breaking SHA-1},
 +
  booktitle = {ISC},
 +
  year      = {2005},
 +
  pages    = {259-273},
 +
  url        = {http://dx.doi.org/10.1007/11556992_19},
 +
  editor    = {Jianying Zhou and Javier Lopez and Robert H. Deng and Feng Bao},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3650},
 +
  isbn      = {3-540-29001-X},
 +
  abstract  = {The cryptanalysis of hash functions has advanced rapidly, and many hash functions have been broken one after another. The most popular hash function SHA-1 has not been broken yet, but the new collision search techniques proposed by Wang et al. reduced the computational complexity down to $2^{69}$, which is only 1/2,000 of the $2^{80}$ operations needed for a birthday attack. The complexity is still too large even for today's supercomputers, but no feasibility study of breaking SHA-1 using specialized hardware has been reported. The well known brute force attack on DES simply repeats the DES operation $2^{56}$ times at a maximum, but the complexity of $2^{69}$ hash operations to break SHA-1 does not mean $2^{69}$ SHA-1 operations. Complex procedures using SHA-1 functions are required, and the total number of operations based on the probability of a collision occurrence is almost equivalent to the $2^{69}$ SHA-1 operations. Therefore, we describe a procedure and propose an LSI architecture to find real collisions for SHA-1 in this paper. The hardware core was synthesized by using a 0.13-$\micro m$ CMOS standard cell library, and its performances in speed, size, and power consumption were evaluated. A \$10 million budget can build a custom hardware system that would consist of 303 personal computers with 16 circuit boards each, in which 32 SHA-1-breaking LSIs are mounted. Each LSI has 64 SHA-1 cores that can run in parallel. This system would find a real collision in 127 days.},
 +
}
 +
</bibtex>
  
−
== Security Anaylsis ==
 
  
−
* Best know attack: <amsmath>\begin{displaymath}2^{63}\end{displaymath}</amsmath> 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]]
 

Latest revision as of 11:34, 10 November 2008

1 Specification

  • digest size: 160 bits
  • max. message length: < 264 bits
  • compression function: 512-bit message block, 160-bit chaining variable
  • Specification: FIPS 180-2 Secure Hash Standard

2 Cryptanalysis

2.1 Best Known Results

The best collision attack on full SHA-1 was published by Wang et al. It has complexity of 269 hash evaluations. The best collision example, a 70-step collision for SHA-1, was published by DeCanniere, Mendel and Rechberger.

2.2 Collision Attacks

Christophe De Canni\`ere, Florian Mendel, Christian Rechberger - Collisions for 70-Step SHA-1: On the Full Cost of Collision Search

Selected Areas in Cryptography 4876:56-73,2007
http://dx.doi.org/10.1007/978-3-540-77360-3_4
Bibtex
Author : Christophe De Canni\`ere, Florian Mendel, Christian Rechberger
Title : Collisions for 70-Step SHA-1: On the Full Cost of Collision Search
In : Selected Areas in Cryptography -
Address :
Date : 2007

Makoto Sugita, Mitsuru Kawazoe, Ludovic Perret, Hideki Imai - Algebraic Cryptanalysis of 58-Round SHA-1

FSE 4593:349-365,2007
http://dx.doi.org/10.1007/978-3-540-74619-5_22
Bibtex
Author : Makoto Sugita, Mitsuru Kawazoe, Ludovic Perret, Hideki Imai
Title : Algebraic Cryptanalysis of 58-Round SHA-1
In : FSE -
Address :
Date : 2007

Christophe De Canni\`ere, Christian Rechberger - Finding SHA-1 Characteristics: General Results and Applications

ASIACRYPT 4284:1-20,2006
http://dx.doi.org/10.1007/11935230_1
Bibtex
Author : Christophe De Canni\`ere, Christian Rechberger
Title : Finding SHA-1 Characteristics: General Results and Applications
In : ASIACRYPT -
Address :
Date : 2006

Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu - Finding Collisions in the Full SHA-1

CRYPTO 3621:17-36,2005
http://dx.doi.org/10.1007/11535218_2
Bibtex
Author : Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu
Title : Finding Collisions in the Full SHA-1
In : CRYPTO -
Address :
Date : 2005

Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, William Jalby - Collisions of SHA-0 and Reduced SHA-1

EUROCRYPT 3494:36-57,2005
http://dx.doi.org/10.1007/11426639_3
Bibtex
Author : Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, William Jalby
Title : Collisions of SHA-0 and Reduced SHA-1
In : EUROCRYPT -
Address :
Date : 2005

Vincent Rijmen, Elisabeth Oswald - Update on SHA-1

CT-RSA 3376:58-71,2005
http://dx.doi.org/10.1007/b105222
Bibtex
Author : Vincent Rijmen, Elisabeth Oswald
Title : Update on SHA-1
In : CT-RSA -
Address :
Date : 2005

2.3 Preimage Attacks

Christophe De Canni\`ere, Christian Rechberger - Preimages for Reduced SHA-0 and SHA-1

CRYPTO 5157:179-202,2008
http://dx.doi.org/10.1007/978-3-540-85174-5_11
Bibtex
Author : Christophe De Canni\`ere, Christian Rechberger
Title : Preimages for Reduced SHA-0 and SHA-1
In : CRYPTO -
Address :
Date : 2008

2.4 Others

Antoine Joux, Thomas Peyrin - Hash Functions and the (Amplified) Boomerang Attack

CRYPTO 4622:244--263,2007
http://dx.doi.org/10.1007/978-3-540-74143-5_14
Bibtex
Author : Antoine Joux, Thomas Peyrin
Title : Hash Functions and the (Amplified) Boomerang Attack
In : CRYPTO -
Address :
Date : 2007

Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - The Impact of Carries on the Complexity of Collision Attacks on SHA-1

FSE 4047:278-292,2006
http://dx.doi.org/10.1007/11799313_18
Bibtex
Author : Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : The Impact of Carries on the Complexity of Collision Attacks on SHA-1
In : FSE -
Address :
Date : 2006

Charanjit S. Jutla, Anindya C. Patthak - Provably Good Codes for Hash Function Design

Selected Areas in Cryptography 4356:376-393,2006
http://dx.doi.org/10.1007/978-3-540-74462-7_26
Bibtex
Author : Charanjit S. Jutla, Anindya C. Patthak
Title : Provably Good Codes for Hash Function Design
In : Selected Areas in Cryptography -
Address :
Date : 2006

Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Impact of Rotations in SHA-1 and Related Hash Functions

Selected Areas in Cryptography 3897:261-275,2005
http://dx.doi.org/10.1007/11693383_18
Bibtex
Author : Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : Impact of Rotations in SHA-1 and Related Hash Functions
In : Selected Areas in Cryptography -
Address :
Date : 2005

Akashi Satoh - Hardware Architecture and Cost Estimates for Breaking SHA-1

ISC 3650:259-273,2005
http://dx.doi.org/10.1007/11556992_19
Bibtex
Author : Akashi Satoh
Title : Hardware Architecture and Cost Estimates for Breaking SHA-1
In : ISC -
Address :
Date : 2005


Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=SHA-1&oldid=2249"