# Difference between revisions of "SHA-1"

(→Preimage Attacks) |
|||

(90 intermediate revisions by 7 users not shown) | |||

Line 1: | Line 1: | ||

− | + | == Specification == | |

− | [ | + | * digest size: 160 bits |

+ | * max. message length: < 2<sup>64</sup> bits | ||

+ | * compression function: 512-bit message block, 160-bit chaining variable | ||

+ | * Specification: [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 Secure Hash Standard] | ||

− | == | + | == Cryptanalysis == |

− | + | === Best Known Results === | |

− | |||

− | |||

− | |||

+ | 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. | ||

+ | ---- | ||

− | === | + | === Collision Attacks === |

− | |||

− | |||

− | |||

− | |||

− | ==== | + | <bibtex> |

− | In SHA-1, | + | @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> | ||

+ | @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> | ||

+ | ---- | ||

− | === | + | === 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> | ||

− | + | ---- | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | === 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> | ||

+ | @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> | ||

+ | @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> | ||

− | |||

− | |||

− | + | ---- | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− |

## Latest revision as of 10:34, 10 November 2008

## Contents

## 1 Specification

- digest size: 160 bits
- max. message length: < 2
^{64}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 2^{69} 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