Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Preimage Attacks)
 
(5 intermediate revisions by 3 users not shown)
Line 14: Line 14:
  
 
=== Collision Attacks ===
 
=== Collision Attacks ===
 +
 +
<bibtex>
 +
@inproceedings{sacryptCanniereMR07,
 +
  author    = {Christophe De Canni{\`e}re and Florian Mendel and Christian Rechberger},
 +
  title    = {Collisions for 70-Step SHA-1: On the Full Cost of Collision Search},
 +
  booktitle = {Selected Areas in Cryptography},
 +
  year      = {2007},
 +
  pages    = {56-73},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-77360-3_4},
 +
  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>
 
<bibtex>
 
@inproceedings{fseSugitaKPI07,  
 
@inproceedings{fseSugitaKPI07,  
Line 38: Line 55:
 
}
 
}
 
</bibtex>
 
</bibtex>
−
<bibtex>
 
−
@inproceedings{sacryptCanniereMR07,
 
−
  author    = {Christophe De Canni{\`e}re and Florian Mendel and Christian Rechberger},
 
−
  title    = {Collisions for 70-Step SHA-1: On the Full Cost of Collision Search},
 
−
  booktitle = {Selected Areas in Cryptography},
 
−
  year      = {2007},
 
−
  pages    = {56-73},
 
−
  url        = {http://dx.doi.org/10.1007/978-3-540-77360-3_4},
 
−
  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>
 
<bibtex>
 
@inproceedings{asiacryptCanniereR06,
 
@inproceedings{asiacryptCanniereR06,
Line 71: Line 71:
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@inproceedings{sacryptJutlaP06,
+
@inproceedings{cryptoWangYY05a,
−
   author    = {Charanjit S. Jutla and Anindya C. Patthak},
+
   author    = {Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu},
−
   title    = {Provably Good Codes for Hash Function Design},
+
   title    = {Finding Collisions in the Full SHA-1},
−
   booktitle = {Selected Areas in Cryptography},
+
   booktitle = {CRYPTO},
−
   year      = {2006},
+
   year      = {2005},
−
   pages    = {376-393},
+
   pages    = {17-36},
−
   url        = {http://dx.doi.org/10.1007/978-3-540-74462-7_26},
+
   url        = {http://dx.doi.org/10.1007/11535218_2},
−
   editor    = {Eli Biham and Amr M. Youssef},
+
   editor    = {Victor Shoup},
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   series    = {LNCS},
−
   volume    = {4356},
+
   volume    = {3621},
−
   isbn      = {978-3-540-74461-0},
+
   isbn      = {3-540-28114-2},
−
  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>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@inproceedings{sacryptPramstallerRR05a,
+
@inproceedings{eurocryptBihamCJCLJ05,
−
   author   = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
+
   author = {Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby},
−
   title     = {Impact of Rotations in SHA-1 and Related Hash Functions},
+
   title = {Collisions of SHA-0 and Reduced SHA-1},
−
   booktitle = {Selected Areas in Cryptography},
+
   booktitle = {EUROCRYPT},
−
   year     = {2005},
+
   year = {2005},
−
   pages     = {261-275},
+
   pages = {36-57},
−
   url        = {http://dx.doi.org/10.1007/11693383_18},
+
   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   = {Bart Preneel and Stafford E. Tavares},
+
   editor = {Ronald Cramer},
 +
  volume = {3494},
 +
  series = {LNCS},
 
   publisher = {Springer},
 
   publisher = {Springer},
−
  series    = {LNCS},
+
   isbn = {3-540-25910-4},
−
  volume    = {3897},
+
   url = {http://dx.doi.org/10.1007/11426639_3},
−
   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>
Line 115: Line 112:
 
   publisher = {Springer},
 
   publisher = {Springer},
 
   series    = {LNCS},
 
   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.},
 
   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}}
 
   url = {http://dx.doi.org/10.1007/b105222}}
Line 121: Line 119:
  
 
=== Preimage Attacks ===
 
=== Preimage Attacks ===
−
* We are not aware of any articles w.r.t. preimage attacks on SHA-1.
+
 
 +
<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>
 +
 
 
----
 
----
  
 
=== Others ===
 
=== 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>
 
<bibtex>
 
@inproceedings{fseMendelPRR06a,  
 
@inproceedings{fseMendelPRR06a,  
Line 143: Line 173:
 
in all published work to date. We point out that it is more accurate  
 
in all published work to date. We point out that it is more accurate  
 
to consider probabilities instead of conditions.},
 
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>
 
</bibtex>
  
 +
<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>
 
<bibtex>
 
@inproceedings{iswSatoh05,
 
@inproceedings{iswSatoh05,
Line 162: Line 224:
 
}
 
}
 
</bibtex>
 
</bibtex>
 +
  
 
----
 
----

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"