Practical pseudo-collisions for hash functions ARIRANG-224/384

Jian Guo; Krystian Matusiewicz; Lars R. Knudsen; San Ling; Huaxiong Wang

doi:10.1007/978-3-642-05445-7_9

Practical pseudo-collisions for hash functions ARIRANG-224/384

Jian Guo^*, Krystian Matusiewicz, Lars R. Knudsen, San Ling, Huaxiong Wang

^*Corresponding author for this work

School of Computing

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

4 Citations (Scopus)

Abstract

In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to 2⁰ and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity 2²³ and close to 2⁰, respectively. We implemented the attacks and provide examples of appropriate pairs of H,M values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.

Original language	English
Title of host publication	Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers
Editors	Michael J. Jacobson Jr., Vincent Rijmen, Reihaneh Safavi-Naini
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	141-156
Number of pages	16
ISBN (Print)	3642054439, 9783642054433
DOIs	https://doi.org/10.1007/978-3-642-05445-7_9
Publication status	Published - Sept 2009
Event	16th Annual International Workshop on Selected Areas in Cryptography, SAC - 2009 - Calgary, Canada Duration: 13 Aug 2009 → 14 Aug 2009

Publication series

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

Other

Other	16th Annual International Workshop on Selected Areas in Cryptography, SAC - 2009
Country/Territory	Canada
City	Calgary
Period	13/08/09 → 14/08/09

Keywords

ARIRANG
Hash function
Practical
Pseudo-collision

Access to Document

10.1007/978-3-642-05445-7_9

Cite this

Guo, J., Matusiewicz, K., Knudsen, L. R., Ling, S., & Wang, H. (2009). Practical pseudo-collisions for hash functions ARIRANG-224/384. In M. J. Jacobson Jr., V. Rijmen, & R. Safavi-Naini (Eds.), Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers (pp. 141-156). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5867 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-642-05445-7_9

Guo, Jian ; Matusiewicz, Krystian ; Knudsen, Lars R. et al. / Practical pseudo-collisions for hash functions ARIRANG-224/384. Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers. editor / Michael J. Jacobson Jr. ; Vincent Rijmen ; Reihaneh Safavi-Naini. Berlin; Heidelberg : Springer, Springer Nature, 2009. pp. 141-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1f6512ef97794d9fa41424144cf4369f,

title = "Practical pseudo-collisions for hash functions ARIRANG-224/384",

abstract = "In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to 20 and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity 223 and close to 20, respectively. We implemented the attacks and provide examples of appropriate pairs of H,M values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.",

keywords = "ARIRANG, Hash function, Practical, Pseudo-collision",

author = "Jian Guo and Krystian Matusiewicz and Knudsen, {Lars R.} and San Ling and Huaxiong Wang",

year = "2009",

month = sep,

doi = "10.1007/978-3-642-05445-7_9",

language = "English",

isbn = "3642054439",

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

publisher = "Springer, Springer Nature",

pages = "141--156",

editor = "{Jacobson Jr.}, {Michael J.} and Vincent Rijmen and Reihaneh Safavi-Naini",

booktitle = "Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers",

address = "United States",

note = "16th Annual International Workshop on Selected Areas in Cryptography, SAC - 2009 ; Conference date: 13-08-2009 Through 14-08-2009",

}

Guo, J, Matusiewicz, K, Knudsen, LR, Ling, S & Wang, H 2009, Practical pseudo-collisions for hash functions ARIRANG-224/384. in MJ Jacobson Jr., V Rijmen & R Safavi-Naini (eds), Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5867 LNCS, Springer, Springer Nature, Berlin; Heidelberg, pp. 141-156, 16th Annual International Workshop on Selected Areas in Cryptography, SAC - 2009, Calgary, Canada, 13/08/09. https://doi.org/10.1007/978-3-642-05445-7_9

Practical pseudo-collisions for hash functions ARIRANG-224/384. / Guo, Jian; Matusiewicz, Krystian; Knudsen, Lars R. et al.
Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers. ed. / Michael J. Jacobson Jr.; Vincent Rijmen; Reihaneh Safavi-Naini. Berlin; Heidelberg: Springer, Springer Nature, 2009. p. 141-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5867 LNCS).

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

TY - GEN

T1 - Practical pseudo-collisions for hash functions ARIRANG-224/384

AU - Guo, Jian

AU - Matusiewicz, Krystian

AU - Knudsen, Lars R.

AU - Ling, San

AU - Wang, Huaxiong

PY - 2009/9

Y1 - 2009/9

N2 - In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to 20 and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity 223 and close to 20, respectively. We implemented the attacks and provide examples of appropriate pairs of H,M values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.

AB - In this paper we analyse the security of the SHA-3 candidate ARIRANG. We show that bitwise complementation of whole registers turns out to be very useful for constructing high-probability differential characteristics in the function. We use this approach to find near-collisions with Hamming weight 32 for the full compression function as well as collisions for the compression function of ARIRANG reduced to 26 rounds, both with complexity close to 20 and memory requirements of only a few words. We use near collisions for the compression function to construct pseudo-collisions for the complete hash functions ARIRANG-224 and ARIRANG-384 with complexity 223 and close to 20, respectively. We implemented the attacks and provide examples of appropriate pairs of H,M values. We also provide possible configurations which may give collisions for step-reduced and full ARIRANG.

KW - ARIRANG

KW - Hash function

KW - Practical

KW - Pseudo-collision

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

U2 - 10.1007/978-3-642-05445-7_9

DO - 10.1007/978-3-642-05445-7_9

M3 - Conference proceeding contribution

AN - SCOPUS:70549112029

SN - 3642054439

SN - 9783642054433

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

SP - 141

EP - 156

BT - Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers

A2 - Jacobson Jr., Michael J.

A2 - Rijmen, Vincent

A2 - Safavi-Naini, Reihaneh

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 16th Annual International Workshop on Selected Areas in Cryptography, SAC - 2009

Y2 - 13 August 2009 through 14 August 2009

ER -

Guo J, Matusiewicz K, Knudsen LR, Ling S, Wang H. Practical pseudo-collisions for hash functions ARIRANG-224/384. In Jacobson Jr. MJ, Rijmen V, Safavi-Naini R, editors, Selected Areas in Cryptography - 16th Annual International Workshop, SAC 2009, Revised Selected Papers. Berlin; Heidelberg: Springer, Springer Nature. 2009. p. 141-156. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-05445-7_9

Practical pseudo-collisions for hash functions ARIRANG-224/384

Abstract

Publication series

Other

Keywords

Access to Document

Other files and links

Fingerprint

Cite this