Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Specification)
(→‎Preimage Attacks)
 
(8 intermediate revisions by 4 users not shown)
Line 31: Line 31:
 
}
 
}
 
</bibtex>
 
</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>
 
<bibtex>
 
@inproceedings{asiacryptCanniereR06,
 
@inproceedings{asiacryptCanniereR06,
Line 46: Line 69:
 
   isbn      = {3-540-49475-8},
 
   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.},
 
   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>
 +
----
 +
 +
=== Preimage Attacks ===
 +
 +
<bibtex>
 +
@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>
 
</bibtex>
  
 +
----
 +
 +
=== Others ===
 +
<bibtex>
 +
@inproceedings{cryptoJouxP07,
 +
  author    = {Antoine Joux and Thomas Peyrin},
 +
  title    = {Hash Functions and the (Amplified) Boomerang Attack},
 +
  booktitle = {CRYPTO},
 +
  year      = {2007},
 +
  pages    = {244--263},
 +
  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>
 
<bibtex>
 
@inproceedings{sacryptJutlaP06,
 
@inproceedings{sacryptJutlaP06,
Line 82: Line 208:
 
}
 
}
 
</bibtex>
 
</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},
 
−
  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>
 
−
----
 
−
 
−
=== Preimage Attacks ===
 
−
* We are not aware of any articles w.r.t. preimage attacks on SHA-1.
 
−
----
 
−
 
−
=== Others ===
 
−
 
 
<bibtex>
 
<bibtex>
 
@inproceedings{iswSatoh05,
 
@inproceedings{iswSatoh05,
Line 119: Line 224:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
 +
 
----
 
----
−
 
−
== eHash Recommendation (optional) or eHash Opinion ==
 
−
Something like: SHA-1 is considered to be broken. Please do not incorporate SHA-1 in new application any longer. Try to migrate to another hash function.
 

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"