Difference between revisions of "SHA-256/224"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Best Known Results)
 
(12 intermediate revisions by 5 users not shown)
Line 10: Line 10:
  
 
=== Best Known Results ===
 
=== Best Known Results ===
−
 
+
Collision attacks up to 24 out of 64 steps. Other non random behavior up to 31 steps. Both results are due to Indesteege et al (SAC 2008).
 +
Preimages on up to 24 steps due to Isobe and Shibutani (FSE 2009).
 
----
 
----
  
Line 19: Line 20:
  
 
=== Collision Attacks ===
 
=== Collision Attacks ===
 +
<bibtex>
 +
@INPROCEEDINGS{sacIndesteegeMPC08,
 +
  author = {Sebastiaan Indesteege and Florian Mendel and Bart Preneel and Christian
 +
Rechberger},
 +
  title = {Collisions and other Non-Random Properties for Step-Reduced SHA-256},
 +
  booktitle = {Selected Areas in Cryptography -- SAC 2008},
 +
  year = {2008},
 +
  volume = {5381},
 +
  series = {LNCS},
 +
  pages = {276-293},
 +
  publisher = {Springer},
 +
  abstract = {We study the security of step-reduced but otherwise unmodified SHA-256.
 +
We show the first collision attacks on SHA-256 reduced to 23 and
 +
24 steps with complexities $2^{18}$ and $2^{28.5}$, respectively.
 +
We give example colliding message pairs for 23-step and 24-step SHA-256.
 +
The best previous, recently obtained result was a collision attack
 +
for up to 22 steps. We extend our attacks to 23 and 24-step reduced
 +
SHA-512 with respective complexities of 2^{44.9} and 2^{53.0}. Additionally,
 +
we show non-random behaviour of the SHA-256 compression function
 +
in the form of free-start near-collisions for up to 31 steps, which
 +
is 6 more steps than the recently obtained non-random behaviour in
 +
the form of a semi-free-start near-collision. Even though this represents
 +
a step forwards in terms of cryptanalytic techniques, the results
 +
do not threaten the security of applications using SHA-256.},
 +
  doi = {10.1007/978-3-642-04159-4_18},
 +
  url = {http://dx.doi.org/10.1007/978-3-642-04159-4_18},
 +
}
 +
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{iswSanadhyaS08,
 +
  author    = {Somitra Kumar Sanadhya and Palash Sarkar},
 +
  title    = {Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family},
 +
  booktitle = {ISC},
 +
  year      = {2008},
 +
  pages    = {244-259},
 +
  abstract  = {Recently, at FSE ’08, Nikolic and Biryukov introduced a new technique for analyzing SHA-2 round function. Building on their work, but using other differential paths, we construct two different deterministic attacks against 21-step SHA-2 hash family. Since the attacks are deterministic, they are actually combinatorial constructions of collisions. There are six free words in our first construction. This gives exactly 2^192 different collisions for 21-step SHA-256 and exactly 2^384 different collisions for 21-step SHA-512. The second construction has five free words. The best previous result, due to Nikolic and Biryukov, for finding collisions for 21-step SHA-256 holds with probability 2-^19. No results on 21-step SHA-512 are previously known. Further, we provide evidence that the Nikolic-Biryukov differential path is unlikely to yield 21-step collisions for SHA-512.},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-85886-7_17},
 +
  editor    = {Tzong-Chen Wu and Chin-Laung Lei and Vincent Rijmen and Der-Tsai Lee},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5222},
 +
  isbn      = {978-3-540-85884-3},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{acispSanadhyaS08,
 +
  author    = {Somitra Kumar Sanadhya and Palash Sarkar},
 +
  title    = {Non-linear Reduced Round Attacks against SHA-2 Hash Family},
 +
  booktitle = {ACISP},
 +
  year      = {2008},
 +
  pages    = {254-266},
 +
  abstract  = {Most of the attacks against (reduced) SHA-2 family in literature have used local collisions which are valid for linearized version of SHA-2 hash functions. Recently, at FSE 2008, an attack against reduced round SHA-256 was presented by Nikolic and Biryukov which used a local collision which is valid for the actual SHA-256 function. It is a 9-step local collision which starts by introducing a modular difference of 1 in the two messages. It succeeds with probability roughly 1/3. We build on the work of Nikolic and Biryukov and provide a generalized nonlinear local collision which accepts an arbitrary initial message difference. This local collision succeeds with probability 1. Using this local collision we present attacks against 18-step SHA-256 and 18-step SHA-512 with arbitrary initial difference. Both of these attacks succeed with probability 1. We then present special cases of our local collision and show two different differential paths for attacking 20-step SHA-256 and 20-step SHA-512. One of these paths is the same as presented by Nikolic and Biryukov while the other one is a new differential path. Messages following both these differential paths can be found with probability 1. This improves on the previous result where the success probability of 20-step attack was 1/3. Finally, we present two differential paths for 21-step collisions for SHA-256 and SHA-512, one of which is a new path. The success probabilities of these paths for SHA-256 are roughly 2-^15 and 2^-17 which improve on the 21-step attack having probability 2^-19 reported earlier. We show examples of message pairs following all the presented differential paths for up to 21-step collisions in SHA-256. We also show first real examples of colliding message pairs for up to 20-step reduced SHA-512. },
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-70500-0_19},
 +
  editor    = {Yi Mu and Willy Susilo and Jennifer Seberry},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5107},
 +
  isbn      = {978-3-540-69971-2},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{fseNikolicB08,
 +
  author    = {Ivica Nikolic and Alex Biryukov},
 +
  title    = {Collisions for Step-Reduced SHA-256},
 +
  booktitle = {FSE},
 +
  year      = {2008},
 +
  pages    = {1-15},
 +
  abstract  = {In this article we find collisions for step-reduced SHA-256. We develop a differential that holds with high probability if the message satisfies certain conditions. We solve the equations that arise from the conditions. Due to the carefully chosen differential and word differences, the message expansion of SHA-256 has little effect on spreading the differences in the words. This helps us to find full collision for 21-step reduced SHA-256, semi-free start collision, i.e. collision for a different initial value, for 23-step reduced SHA-256, and semi-free start near collision (with only 15 bit difference out of 256 bits) for 25-step reduced SHA-256.},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-71039-4_1},
 +
  editor    = {Kaisa Nyberg},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5086},
 +
  isbn      = {978-3-540-71038-7},
 +
}
 +
</bibtex>
  
 +
<bibtex>
 +
@inproceedings{iciscSanadhyaS07,
 +
  author    = {Somitra Kumar Sanadhya and Palash Sarkar},
 +
  title    = {New Local Collisions for the SHA-2 Hash Family},
 +
  booktitle = {ICISC},
 +
  year      = {2007},
 +
  pages    = {193-205},
 +
  url        = {http://dx.doi.org/10.1007/978-3-540-76788-6_16},
 +
  editor    = {Kil-Hyun Nam and Gwangsoo Rhee},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4817},
 +
  isbn      = {978-3-540-76787-9},
 +
  abstract  = {The starting point for collision attacks on practical hash functions is a local collision. In this paper, we make a systematic study of local collisions for the SHA-2 family. The possible linear approximations of the constituent Boolean functions are considered and certain impossible conditions for such approximations are identified. Based on appropriate approximations, we describe a general method for finding local collisions. Applying this method, we obtain several local collisions and compute the probabilities of the various differential paths. Previously, only one local collision due to Gilbert-Handschuh was known. We point out two impossible conditions in the GH local collision and provide an example of an impossible differential path for linearized SHA-2 using this local collision. Sixteen new local collisions are obtained none of which have any impossible conditions. The probabilities of these local collisions are a little less than the GH local collision. On the other hand, the absence of impossible conditions may make them more suitable for (reduced round) collision search attacks on the SHA-2 family.},
 +
}
 
</bibtex>
 
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{fseMendelPRR06,
 +
  author    = {Florian Mendel and Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
 +
  title    = {Analysis of Step-Reduced SHA-256},
 +
  pages    = {126-143},
 +
  url        = {http://dx.doi.org/10.1007/11799313_9},
 +
  booktitle = {FSE},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {4047},
 +
  year      = {2006},
 +
  isbn      = {3-540-36597-4},
 +
  abstract  = {This is the first article analyzing the security of
 +
SHA-256 against fast collision search which considers the recent
 +
attacks by Wang et al. We show the limits of applying techniques known
 +
so far to SHA-256. Next we introduce a new type of perturbation vector
 +
which circumvents the identified limits. This new technique is then
 +
applied to the unmodified SHA-256. Exploiting the combination of Boolean
 +
functions and modular addition together with the newly developed technique
 +
allows us to derive collision-producing characteristics for step-reduced
 +
SHA-256, which was not possible before. Although our results do not threaten
 +
the security of SHA-256, we show that the low probability of a single
 +
local collision may give rise to a false sense of security.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 
@inproceedings{sacryptYoshidaB05,
 
@inproceedings{sacryptYoshidaB05,
 
   author    = {Hirotaka Yoshida and Alex Biryukov},
 
   author    = {Hirotaka Yoshida and Alex Biryukov},
Line 53: Line 177:
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
  
  
Line 63: Line 186:
  
 
=== Preimage Attacks ===
 
=== Preimage Attacks ===
−
 
+
<bibtex>
 +
@INPROCEEDINGS{fseIsobeS09,
 +
  author = {Takanori Isobe and Kyoji Shibutani},
 +
  title = {Preimage Attacks on Reduced Tiger and SHA-2},
 +
  booktitle = {Fast Software Encryption -- FSE 2009},
 +
  year = {2009},
 +
  editor = {Dunkelman, Orr},
 +
  volume = {5665},
 +
  series = {LNCS},
 +
  pages = {139-155},
 +
  publisher = {Springer},
 +
  url = {http://dx.doi.org/10.1007/978-3-642-03317-9}
 +
  abstract = {This paper shows new preimage attacks on reduced Tiger and SHA-2.
 +
Indesteege and Preneel presented a preimage attack on Tiger reduced
 +
to 13 rounds (out of 24) with a complexity of 2^{128.5}. Our new
 +
preimage attack finds a one-block preimage of Tiger reduced to 16
 +
rounds with a complexity of 2^{161}. The proposed attack is based
 +
on meet-in-the-middle attacks. It seems difficult to find “independent
 +
words” of Tiger at first glance, since its key schedule function
 +
is much more complicated than that of MD4 or MD5. However, we developed
 +
techniques to find independent words efficiently by controlling its
 +
internal variables. Surprisingly, the similar techniques can be applied
 +
to SHA-2 including both SHA-256 and SHA-512. We present a one-block
 +
preimage attack on SHA-256 and SHA-512 reduced to 24 (out of 64 and
 +
80) steps with a complexity of 2^{240} and 2^{480}, respectively.
 +
To the best of our knowledge, our attack is the best known preimage
 +
attack on reduced-round Tiger and our preimage attack on reduced-step
 +
SHA-512 is the first result. Furthermore, our preimage attacks can
 +
also be extended to second preimage attacks directly, because our
 +
attacks can obtain random preimages from an arbitrary IV and an arbitrary
 +
target.},
 +
}
 +
</bibtex>
  
 
----
 
----
  
 
=== Others ===
 
=== Others ===

Latest revision as of 10:08, 18 September 2009

1 Specification

2 Cryptanalysis

2.1 Best Known Results

Collision attacks up to 24 out of 64 steps. Other non random behavior up to 31 steps. Both results are due to Indesteege et al (SAC 2008). Preimages on up to 24 steps due to Isobe and Shibutani (FSE 2009).

2.2 Generic Attacks

2.3 Collision Attacks

Sebastiaan Indesteege, Florian Mendel, Bart Preneel, Christian

Rechberger - Collisions and other Non-Random Properties for Step-Reduced SHA-256

Selected Areas in Cryptography -- SAC 2008 5381:276-293,2008
http://dx.doi.org/10.1007/978-3-642-04159-4_18
Bibtex
Author : Sebastiaan Indesteege, Florian Mendel, Bart Preneel, Christian Rechberger
Title : Collisions and other Non-Random Properties for Step-Reduced SHA-256
In : Selected Areas in Cryptography -- SAC 2008 -
Address :
Date : 2008

Somitra Kumar Sanadhya, Palash Sarkar - Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family

ISC 5222:244-259,2008
http://dx.doi.org/10.1007/978-3-540-85886-7_17
Bibtex
Author : Somitra Kumar Sanadhya, Palash Sarkar
Title : Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family
In : ISC -
Address :
Date : 2008

Somitra Kumar Sanadhya, Palash Sarkar - Non-linear Reduced Round Attacks against SHA-2 Hash Family

ACISP 5107:254-266,2008
http://dx.doi.org/10.1007/978-3-540-70500-0_19
Bibtex
Author : Somitra Kumar Sanadhya, Palash Sarkar
Title : Non-linear Reduced Round Attacks against SHA-2 Hash Family
In : ACISP -
Address :
Date : 2008

Ivica Nikolic, Alex Biryukov - Collisions for Step-Reduced SHA-256

FSE 5086:1-15,2008
http://dx.doi.org/10.1007/978-3-540-71039-4_1
Bibtex
Author : Ivica Nikolic, Alex Biryukov
Title : Collisions for Step-Reduced SHA-256
In : FSE -
Address :
Date : 2008

Somitra Kumar Sanadhya, Palash Sarkar - New Local Collisions for the SHA-2 Hash Family

ICISC 4817:193-205,2007
http://dx.doi.org/10.1007/978-3-540-76788-6_16
Bibtex
Author : Somitra Kumar Sanadhya, Palash Sarkar
Title : New Local Collisions for the SHA-2 Hash Family
In : ICISC -
Address :
Date : 2007

Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen - Analysis of Step-Reduced SHA-256

FSE 4047:126-143,2006
http://dx.doi.org/10.1007/11799313_9
Bibtex
Author : Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen
Title : Analysis of Step-Reduced SHA-256
In : FSE -
Address :
Date : 2006

Hirotaka Yoshida, Alex Biryukov - Analysis of a SHA-256 Variant

Selected Areas in Cryptography 3897:245-260,2005
http://dx.doi.org/10.1007/11693383_17
Bibtex
Author : Hirotaka Yoshida, Alex Biryukov
Title : Analysis of a SHA-256 Variant
In : Selected Areas in Cryptography -
Address :
Date : 2005

Henri Gilbert, Helena Handschuh - Security Analysis of SHA-256 and Sisters

Selected Areas in Cryptography 3006:175-193,2003
http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3006{\&}spage=175
Bibtex
Author : Henri Gilbert, Helena Handschuh
Title : Security Analysis of SHA-256 and Sisters
In : Selected Areas in Cryptography -
Address :
Date : 2003


2.4 Second Preimage Attacks

2.5 Preimage Attacks

Takanori Isobe, Kyoji Shibutani - Preimage Attacks on Reduced Tiger and SHA-2

Fast Software Encryption -- FSE 2009 5665:139-155,2009
http://dx.doi.org/10.1007/978-3-642-03317-9
Bibtex
Author : Takanori Isobe, Kyoji Shibutani
Title : Preimage Attacks on Reduced Tiger and SHA-2
In : Fast Software Encryption -- FSE 2009 -
Address :
Date : 2009

2.6 Others

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