Difference between revisions of "SHA-1"

From The ECRYPT Hash Function Website
Line 69: 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{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>
 
−
@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>
Line 176: Line 142:
 
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>
 +
@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>

Revision as of 18:10, 25 March 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

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

  • We are not aware of any articles w.r.t. preimage attacks on SHA-1.

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=1977"