Difference between revisions of "SHA-256/224"

From The ECRYPT Hash Function Website
(→‎Collision Attacks)
(→‎Best Known Results)
 
(4 intermediate revisions by 2 users not shown)
Line 10: Line 10:
  
 
=== Best Known Results ===
 
=== Best Known Results ===
−
Collision attacks up to 21 out of 64 steps. Other non random behavior up to 25 steps. Both results are due to Nicolic and Biryukov.
+
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>
 
<bibtex>
Line 139: 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"