Difference between revisions of "FORK-256"
From The ECRYPT Hash Function Website
(→Collision Attacks) |
|||
| (13 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | == | + | == Specification == |
| + | * digest size: 256 bits | ||
| + | * max. message length: < 2<sup>64</sup> bits | ||
| + | * compression function: 512-bit message block, 4 streams with each 256-bit chaining variable | ||
<!-- | <!-- | ||
| − | * | + | * Specification: http://csrc.nist.gov/groups/ST/hash/documents/Sung_FORK-256.pdf |
| − | + | --> | |
| − | + | ||
| − | + | <bibtex> | |
| + | @inproceedings{fseHongCSLHLMC06, | ||
| + | author = {Deukjo Hong and Donghoon Chang and Jaechul Sung and Sangjin Lee and Seokhie Hong and Jaesang Lee and Dukjae Moon and Sungtaek Chee}, | ||
| + | title = {A New Dedicated 256-Bit Hash Function: FORK-256}, | ||
| + | pages = {195-209}, | ||
| + | url = {http://dx.doi.org/10.1007/11799313_13}, | ||
| + | booktitle = {FSE}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {4047}, | ||
| + | year = {2006}, | ||
| + | isbn = {3-540-36597-4}, | ||
| + | abstract = {This paper describes a new software-efficient 256-bit | ||
| + | hash function, FORK-256. Recently proposed attacks on MD5 and SHA-1 | ||
| + | motivate a new hash function design. It is designed not only to have | ||
| + | higher security but also to be faster than SHA-256. The performance of | ||
| + | the new hash function is at least 30% better than that of SHA-256 in | ||
| + | software. And it is secure against any known cryptographic attacks on hash functions.}, | ||
| + | } | ||
| + | </bibtex> | ||
| + | |||
| + | <!-- | ||
| + | <bibtex> | ||
| + | @MISC{nistHongSHLM05, | ||
| + | author = {Deukjo Hong and Jaechul Sung and Seokhie Hong and Sangjin Lee and Dukjae Moon}, | ||
| + | title = {A New Dedicated 256-bit Hash Function: FORK-256}, | ||
| + | howpublished = {NIST - First Cryptographic Hash Workshop, October 31-November 1}, | ||
| + | year = {2005}, | ||
| + | abstract = {This paper describes a new software-efficient 256-bit hash function, FORK-256. Recently proposed attacks on MD5 and SHA-1 motivate a new hash function design. It is designed not only to have higher security but also to be faster than SHA-256. The performance of the new hash function is at least 30% better than that of SHA-256 in software. And it is secure against any known cryptographic attacks on hash functions.}, | ||
| + | url = {http://csrc.nist.gov/groups/ST/hash/documents/Sung_FORK-256.pdf}, | ||
| + | } | ||
| + | </bibtex> | ||
--> | --> | ||
| Line 21: | Line 55: | ||
=== Collision Attacks === | === Collision Attacks === | ||
| + | <bibtex> | ||
| + | @inproceedings{fseMatusiewiczPBCP07, | ||
| + | author = {Krystian Matusiewicz and Thomas Peyrin and Olivier Billet and Scott Contini and Josef Pieprzyk}, | ||
| + | title = {Cryptanalysis of FORK-256}, | ||
| + | pages = {19-38}, | ||
| + | url = {http://dx.doi.org/10.1007/978-3-540-74619-5_2}, | ||
| + | editor = {Alex Biryukov}, | ||
| + | booktitle = {FSE}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {4593}, | ||
| + | year = {2007}, | ||
| + | isbn = {978-3-540-74617-1}, | ||
| + | abstract = {In this paper we present a cryptanalysis of a | ||
| + | new 256-bit hash function, FORK-256, proposed by Hong et al. at | ||
| + | FSE 2006. This cryptanalysis is based on some unexpected differentials | ||
| + | existing for the step transformation. We show their possible uses in | ||
| + | different attack scenarios by giving a 1-bit (resp. 2-bit) near collision | ||
| + | attack against the full compression function of FORK-256 running with | ||
| + | complexity of 2<sup>125</sup> (resp. 2<sup>120</sup>) and with negligible memory, and by exhibiting | ||
| + | a 22-bit near pseudo-collision. We also show that we can find collisions for | ||
| + | the full compression function with a small amount of memory with complexity not | ||
| + | exceeding 2<sup>126.6</sup> hash evaluations. We further show how to reduce this complexity | ||
| + | to 2<sup>109.6</sup> hash computations by using 2<sup>73</sup> memory words. Finally, we show that | ||
| + | this attack can be extended with no additional cost to find collisions for the | ||
| + | full hash function, i.e. with the predefined IV.}, | ||
| + | } | ||
| + | </bibtex> | ||
<bibtex> | <bibtex> | ||
| Line 29: | Line 91: | ||
year = {2007}, | year = {2007}, | ||
pages = {85-100}, | pages = {85-100}, | ||
| − | + | publisher = {Springer}, | |
| + | series = {Lecture Notes in Computer Science}, | ||
| + | volume = {4377}, | ||
| + | isbn = {3-540-69327-0}, | ||
| + | url = {http://dx.doi.org/10.1007/11967668_6}, | ||
abstract = {FORK-256 is a hash function presented at FSE 2006. Whereas SHA-like designs process messages in one stream, FORK-256 uses four parallel streams for hashing. In this article, we present the first cryptanalytic results on this design strategy. First, we study a linearized variant of FORK-256, and show several unusual properties of this linearized variant. We also explain why the linearized model can not be used to mount attacks similar to the recent attacks by Wang et al. on SHA-like hash functions. Second, we show how collision attacks, exploiting the non-bijectiveness of the nonlinear functions of FORK-256, can be mounted on reduced variants of FORK-256. We show an efficient attack on FORK-256 reduced to 2 streams and present actual colliding pairs. We expect that our attack can also be extended to FORK-256 reduced to 3 streams. For the moment our approach does not appear to be applicable to the full FORK-256 hash function.} } | abstract = {FORK-256 is a hash function presented at FSE 2006. Whereas SHA-like designs process messages in one stream, FORK-256 uses four parallel streams for hashing. In this article, we present the first cryptanalytic results on this design strategy. First, we study a linearized variant of FORK-256, and show several unusual properties of this linearized variant. We also explain why the linearized model can not be used to mount attacks similar to the recent attacks by Wang et al. on SHA-like hash functions. Second, we show how collision attacks, exploiting the non-bijectiveness of the nonlinear functions of FORK-256, can be mounted on reduced variants of FORK-256. We show an efficient attack on FORK-256 reduced to 2 streams and present actual colliding pairs. We expect that our attack can also be extended to FORK-256 reduced to 3 streams. For the moment our approach does not appear to be applicable to the full FORK-256 hash function.} } | ||
</bibtex> | </bibtex> | ||
| Line 44: | Line 110: | ||
=== Others === | === Others === | ||
| + | <bibtex> | ||
| + | @inproceedings{indocryptSaarinen07a, | ||
| + | author = {Markku-Juhani Olavi Saarinen}, | ||
| + | title = {A Meet-in-the-Middle Collision Attack Against the New FORK-256}, | ||
| + | booktitle = {INDOCRYPT}, | ||
| + | year = {2007}, | ||
| + | pages = {10-17}, | ||
| + | url = {http://dx.doi.org/10.1007/978-3-540-77026-8_2}, | ||
| + | editor = {K. Srinathan and C. Pandu Rangan and Moti Yung}, | ||
| + | publisher = {Springer}, | ||
| + | series = {LNCS}, | ||
| + | volume = {4859}, | ||
| + | isbn = {978-3-540-77025-1}, | ||
| + | abstract = {We show that a 2112.9 collision attack exists against the FORK-256 Hash Function. The attack is surprisingly simple compared to existing published FORK-256 cryptanalysis work, yet is the best known result against the new, tweaked version of the hash. The attack is based on “splitting†the message schedule and compression function into two halves in a meet-in-the-middle attack. This in turn reduces the space of possible hash function results, which leads to significantly faster collision search. The attack strategy is also applicable to the original version of FORK-256 published in FSE 2006.}, | ||
| + | } | ||
| + | </bibtex> | ||
Latest revision as of 11:30, 3 November 2008
Contents
1 Specification
- digest size: 256 bits
- max. message length: < 264 bits
- compression function: 512-bit message block, 4 streams with each 256-bit chaining variable
Deukjo Hong, Donghoon Chang, Jaechul Sung, Sangjin Lee, Seokhie Hong, Jaesang Lee, Dukjae Moon, Sungtaek Chee - A New Dedicated 256-Bit Hash Function: FORK-256
- FSE 4047:195-209,2006
- http://dx.doi.org/10.1007/11799313_13
BibtexAuthor : Deukjo Hong, Donghoon Chang, Jaechul Sung, Sangjin Lee, Seokhie Hong, Jaesang Lee, Dukjae Moon, Sungtaek Chee
Title : A New Dedicated 256-Bit Hash Function: FORK-256
In : FSE -
Address :
Date : 2006
2 Cryptanalysis
2.1 Best Known Results
2.2 Generic Attacks
2.3 Collision Attacks
Krystian Matusiewicz, Thomas Peyrin, Olivier Billet, Scott Contini, Josef Pieprzyk - Cryptanalysis of FORK-256
- FSE 4593:19-38,2007
- http://dx.doi.org/10.1007/978-3-540-74619-5_2
BibtexAuthor : Krystian Matusiewicz, Thomas Peyrin, Olivier Billet, Scott Contini, Josef Pieprzyk
Title : Cryptanalysis of FORK-256
In : FSE -
Address :
Date : 2007
Florian Mendel, Joseph Lano, Bart Preneel - Cryptanalysis of Reduced Variants of the FORK-256 Hash Function
- CT-RSA 4377:85-100,2007
- http://dx.doi.org/10.1007/11967668_6
BibtexAuthor : Florian Mendel, Joseph Lano, Bart Preneel
Title : Cryptanalysis of Reduced Variants of the FORK-256 Hash Function
In : CT-RSA -
Address :
Date : 2007
2.4 Second Preimage Attacks
2.5 Preimage Attacks
2.6 Others
Markku-Juhani Olavi Saarinen - A Meet-in-the-Middle Collision Attack Against the New FORK-256
