Cryptanalysis of FORK-256

Krystian Matusiewicz; Thomas Peyrin; Olivier Billet; Scott Contini; Josef Pieprzyk

Cryptanalysis of FORK-256

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

^*Corresponding author for this work

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

4 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 2¹²⁵ (resp. 2¹²⁰) 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^126.6 hash evaluations. We further show how to reduce this complexity to 2^109.6 hash computations by using 2⁷³ 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 language	English
Title of host publication	Fast Software Encryption - 14th International Workshop, FSE 2007
Editors	Alex Biryukov
Place of Publication	Berlin ; New York
Publisher	Springer, Springer Nature
Pages	19-38
Number of pages	20
Volume	4593 LNCS
ISBN (Print)	354074617X, 9783540746171
Publication status	Published - 2007
Event	14th International Workshop on Fast Software Encryption, FSE 2007 - Luxembourg, Luxembourg Duration: 26 Mar 2007 → 28 Mar 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4593 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	14th International Workshop on Fast Software Encryption, FSE 2007
Country	Luxembourg
City	Luxembourg
Period	26/03/07 → 28/03/07

Keywords

hash functions
cryptanalysis
FORK-256
micro-collisions

Access to Document

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Cryptanalysis of FORK-256'. Together they form a unique fingerprint.

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). Springer, Springer Nature.

Matusiewicz, Krystian ; Peyrin, Thomas ; Billet, Olivier ; Contini, Scott ; Pieprzyk, Josef. / Cryptanalysis of FORK-256. Fast Software Encryption - 14th International Workshop, FSE 2007. editor / Alex Biryukov. Vol. 4593 LNCS Berlin ; New York : Springer, Springer Nature, 2007. pp. 19-38 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cb03b0089971414c8e2e4d12aa52030c,

title = "Cryptanalysis of FORK-256",

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.",

keywords = "hash functions, cryptanalysis, FORK-256, micro-collisions",

author = "Krystian Matusiewicz and Thomas Peyrin and Olivier Billet and Scott Contini and Josef Pieprzyk",

year = "2007",

language = "English",

isbn = "354074617X",

volume = "4593 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "19--38",

editor = "Alex Biryukov",

booktitle = "Fast Software Encryption - 14th International Workshop, FSE 2007",

address = "United States",

note = "14th International Workshop on Fast Software Encryption, FSE 2007 ; Conference date: 26-03-2007 Through 28-03-2007",

}

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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4593 LNCS, Springer, Springer Nature, Berlin ; New York, pp. 19-38, 14th International Workshop on Fast Software Encryption, FSE 2007, Luxembourg, Luxembourg, 26/03/07.

Cryptanalysis of FORK-256. / Matusiewicz, Krystian; Peyrin, Thomas; Billet, Olivier; Contini, Scott; Pieprzyk, Josef.

Fast Software Encryption - 14th International Workshop, FSE 2007. ed. / Alex Biryukov. Vol. 4593 LNCS Berlin ; New York : Springer, Springer Nature, 2007. p. 19-38 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4593 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Cryptanalysis of FORK-256

AU - Matusiewicz, Krystian

AU - Peyrin, Thomas

AU - Billet, Olivier

AU - Contini, Scott

AU - Pieprzyk, Josef

PY - 2007

Y1 - 2007

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

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

KW - hash functions

KW - cryptanalysis

KW - FORK-256

KW - micro-collisions

UR - http://www.scopus.com/inward/record.url?scp=38149037030&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:38149037030

SN - 354074617X

SN - 9783540746171

VL - 4593 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 19

EP - 38

BT - Fast Software Encryption - 14th International Workshop, FSE 2007

A2 - Biryukov, Alex

PB - Springer, Springer Nature

CY - Berlin ; New York

T2 - 14th International Workshop on Fast Software Encryption, FSE 2007

Y2 - 26 March 2007 through 28 March 2007

ER -

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