Cryptanalysis of FORK-256

Krystian Matusiewicz*, Thomas Peyrin, Olivier Billet, Scott Contini, Josef Pieprzyk

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

5 Citations (Scopus)

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 2125 (resp. 2120) 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 2126.6 hash evaluations. We further show how to reduce this complexity to 2109.6 hash computations by using 273 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.

Original languageEnglish
Title of host publicationFast Software Encryption - 14th International Workshop, FSE 2007
EditorsAlex Biryukov
Place of PublicationBerlin ; New York
PublisherSpringer, Springer Nature
Pages19-38
Number of pages20
Volume4593 LNCS
ISBN (Print)354074617X, 9783540746171
Publication statusPublished - 2007
Event14th International Workshop on Fast Software Encryption, FSE 2007 - Luxembourg, Luxembourg
Duration: 26 Mar 200728 Mar 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4593 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other14th International Workshop on Fast Software Encryption, FSE 2007
CountryLuxembourg
CityLuxembourg
Period26/03/0728/03/07

    Fingerprint

Keywords

  • hash functions
  • cryptanalysis
  • FORK-256
  • micro-collisions

Cite this

Matusiewicz, K., Peyrin, T., Billet, O., Contini, S., & Pieprzyk, J. (2007). Cryptanalysis of FORK-256. In A. Biryukov (Ed.), Fast Software Encryption - 14th International Workshop, FSE 2007 (Vol. 4593 LNCS, pp. 19-38). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4593 LNCS). Berlin ; New York: Springer, Springer Nature.