Preimage attack on the parallel FFT-hashing function

Chang Donghoon; Yung Moti; Sung Jaechul; Hong Seokhie; Lee Sangjin

Preimage attack on the parallel FFT-hashing function

Chang Donghoon, Yung Moti, Sung Jaechul, Hong Seokhie, Lee Sangjin

Department of Mathematics

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

Abstract

The parallel FFT-Hashing function was designed by C. P. Schnorr and S. Vaudenay in 1993. The function is a simple and light weight hash algorithm with 128-bit digest. Its basic component is a multi-permutation which helps in proving its resistance to collision attacks. In this work we show a preimage attack on the parallel FFT-Hashing function using 2^t+64 + 2 ^128-t time complexity and 2^t memory, which is less than the generic complexity 2¹²⁸. Specifically, when t = 32, we can find a preimage using 2⁹⁷ time and 2³² memory. Our method can be described as "disseminative-meet-in-the-middle-attack". we actually use the properties of multi-permutation (helpful against collision attack) to our advantage in the attack. Overall, this type of attack (beating the generic one) demonstrates that the structure of the parallel FFT-Hashing function has some weaknesses when preimage attack is considered (and relevant). To the best of our knowledge, this is the first attack on the parallel FFT-Hashing function.

Original language	English
Title of host publication	Information Security and Privacy - 12th Australasian Conference, ACISP 2007, Proceedings
Pages	59-67
Number of pages	9
State	Published - 2007
Event	12th Australasian Conference on Information Security and Privacy, ACISP2007 - Townsville, Australia Duration: 2 Jul 2007 → 4 Jul 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4586 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th Australasian Conference on Information Security and Privacy, ACISP2007
Country/Territory	Australia
City	Townsville
Period	2/07/07 → 4/07/07

Keywords

Cryptographic hash function
Preimage attack
The parallel FFT-hashing function

Cite this

Donghoon, C., Moti, Y., Jaechul, S., Seokhie, H., & Sangjin, L. (2007). Preimage attack on the parallel FFT-hashing function. In Information Security and Privacy - 12th Australasian Conference, ACISP 2007, Proceedings (pp. 59-67). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4586 LNCS).

@inproceedings{c325678488f9415da1724fcaa2a18406,

title = "Preimage attack on the parallel FFT-hashing function",

abstract = "The parallel FFT-Hashing function was designed by C. P. Schnorr and S. Vaudenay in 1993. The function is a simple and light weight hash algorithm with 128-bit digest. Its basic component is a multi-permutation which helps in proving its resistance to collision attacks. In this work we show a preimage attack on the parallel FFT-Hashing function using 2t+64 + 2 128-t time complexity and 2t memory, which is less than the generic complexity 2128. Specifically, when t = 32, we can find a preimage using 297 time and 232 memory. Our method can be described as {"}disseminative-meet-in-the-middle-attack{"}. we actually use the properties of multi-permutation (helpful against collision attack) to our advantage in the attack. Overall, this type of attack (beating the generic one) demonstrates that the structure of the parallel FFT-Hashing function has some weaknesses when preimage attack is considered (and relevant). To the best of our knowledge, this is the first attack on the parallel FFT-Hashing function.",

keywords = "Cryptographic hash function, Preimage attack, The parallel FFT-hashing function",

author = "Chang Donghoon and Yung Moti and Sung Jaechul and Hong Seokhie and Lee Sangjin",

year = "2007",

language = "English",

isbn = "3540734570",

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

pages = "59--67",

booktitle = "Information Security and Privacy - 12th Australasian Conference, ACISP 2007, Proceedings",

note = "12th Australasian Conference on Information Security and Privacy, ACISP2007 ; Conference date: 02-07-2007 Through 04-07-2007",

}

Donghoon, C, Moti, Y, Jaechul, S, Seokhie, H & Sangjin, L 2007, Preimage attack on the parallel FFT-hashing function. in Information Security and Privacy - 12th Australasian Conference, ACISP 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4586 LNCS, pp. 59-67, 12th Australasian Conference on Information Security and Privacy, ACISP2007, Townsville, Australia, 2/07/07.

Preimage attack on the parallel FFT-hashing function. / Donghoon, Chang; Moti, Yung; Jaechul, Sung et al.
Information Security and Privacy - 12th Australasian Conference, ACISP 2007, Proceedings. 2007. p. 59-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4586 LNCS).

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

TY - GEN

T1 - Preimage attack on the parallel FFT-hashing function

AU - Donghoon, Chang

AU - Moti, Yung

AU - Jaechul, Sung

AU - Seokhie, Hong

AU - Sangjin, Lee

PY - 2007

Y1 - 2007

N2 - The parallel FFT-Hashing function was designed by C. P. Schnorr and S. Vaudenay in 1993. The function is a simple and light weight hash algorithm with 128-bit digest. Its basic component is a multi-permutation which helps in proving its resistance to collision attacks. In this work we show a preimage attack on the parallel FFT-Hashing function using 2t+64 + 2 128-t time complexity and 2t memory, which is less than the generic complexity 2128. Specifically, when t = 32, we can find a preimage using 297 time and 232 memory. Our method can be described as "disseminative-meet-in-the-middle-attack". we actually use the properties of multi-permutation (helpful against collision attack) to our advantage in the attack. Overall, this type of attack (beating the generic one) demonstrates that the structure of the parallel FFT-Hashing function has some weaknesses when preimage attack is considered (and relevant). To the best of our knowledge, this is the first attack on the parallel FFT-Hashing function.

AB - The parallel FFT-Hashing function was designed by C. P. Schnorr and S. Vaudenay in 1993. The function is a simple and light weight hash algorithm with 128-bit digest. Its basic component is a multi-permutation which helps in proving its resistance to collision attacks. In this work we show a preimage attack on the parallel FFT-Hashing function using 2t+64 + 2 128-t time complexity and 2t memory, which is less than the generic complexity 2128. Specifically, when t = 32, we can find a preimage using 297 time and 232 memory. Our method can be described as "disseminative-meet-in-the-middle-attack". we actually use the properties of multi-permutation (helpful against collision attack) to our advantage in the attack. Overall, this type of attack (beating the generic one) demonstrates that the structure of the parallel FFT-Hashing function has some weaknesses when preimage attack is considered (and relevant). To the best of our knowledge, this is the first attack on the parallel FFT-Hashing function.

KW - Cryptographic hash function

KW - Preimage attack

KW - The parallel FFT-hashing function

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

M3 - Conference contribution

AN - SCOPUS:38149101695

SN - 3540734570

SN - 9783540734574

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

SP - 59

EP - 67

BT - Information Security and Privacy - 12th Australasian Conference, ACISP 2007, Proceedings

T2 - 12th Australasian Conference on Information Security and Privacy, ACISP2007

Y2 - 2 July 2007 through 4 July 2007

ER -

Preimage attack on the parallel FFT-hashing function

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this