Linear analysis of reduced-round CubeHash

Tomer Ashur; Orr Dunkelman

doi:10.1007/978-3-642-21554-4_27

Linear analysis of reduced-round CubeHash

Tomer Ashur
, Orr Dunkelman

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

4 Citations (Scopus)

16 Downloads (Pure)

Abstract

Recent developments in the field of cryptanalysis of hash functions has inspired NIST to announce a competition for selecting a new cryptographic hash function to join the SHA family of standards. One of the 14 second-round candidates was CubeHash designed by Daniel J. Bernstein. CubeHash is a unique hash function in the sense that it does not iterate a common compression function, and offers a structure which resembles a sponge function, even though it is not exactly a sponge function.

In this paper we analyze reduced-round variants of CubeHash where the adversary controls the full 1024-bit input to reduced-round CubeHash and can observe its full output. We show that linear approximations with high biases exist in reduced-round variants. For example, we present an 11-round linear approximation with bias of 2²³⁵, which allows distinguishing 11-round CubeHash using about 2⁴⁷⁰ queries. We also discuss the extension of this distinguisher to 12 rounds using message modification techniques. Finally, we present a linear distinguisher for 14-round CubeHash which uses about 2⁸¹² queries.

Original language	English
Title of host publication	International Conference on Applied Cryptography and Network Security
Editors	J. Lopez, G. Tsudik
Place of Publication	Berlin
Publisher	Springer
Pages	462-478
Number of pages	17
ISBN (Electronic)	978-3-642-21554-4
ISBN (Print)	978-3-642-21553-7
DOIs	https://doi.org/10.1007/978-3-642-21554-4_27
Publication status	Published - 2011
Externally published	Yes
Event	Applied Cryptography and Network Security - 9th International Conference - Nerja, Spain Duration: 7 Jun 2011 → 10 Jun 2011 Conference number: 2011

Publication series

Name	Lecture Notes in Computer Science
Publisher	SpringerLink
Volume	6715

Conference

Conference	Applied Cryptography and Network Security - 9th International Conference
Abbreviated title	ACNS
Country/Territory	Spain
City	Nerja
Period	7/06/11 → 10/06/11

Keywords

CubeHash
SHA-3 competition
Linear cryptanalysis

Access to Document

10.1007/978-3-642-21554-4_27

Author versionFinal author version , 150 KB

Cite this

@inproceedings{1fcd2870e2604e77a64d866a9247dfa6,

title = "Linear analysis of reduced-round CubeHash",

abstract = "Recent developments in the field of cryptanalysis of hash functions has inspired NIST to announce a competition for selecting a new cryptographic hash function to join the SHA family of standards. One of the 14 second-round candidates was CubeHash designed by Daniel J. Bernstein. CubeHash is a unique hash function in the sense that it does not iterate a common compression function, and offers a structure which resembles a sponge function, even though it is not exactly a sponge function. In this paper we analyze reduced-round variants of CubeHash where the adversary controls the full 1024-bit input to reduced-round CubeHash and can observe its full output. We show that linear approximations with high biases exist in reduced-round variants. For example, we present an 11-round linear approximation with bias of 2 235, which allows distinguishing 11-round CubeHash using about 2470 queries. We also discuss the extension of this distinguisher to 12 rounds using message modification techniques. Finally, we present a linear distinguisher for 14-round CubeHash which uses about 2812 queries.",

keywords = "CubeHash, SHA-3 competition, Linear cryptanalysis",

author = "Tomer Ashur and Orr Dunkelman",

year = "2011",

doi = "10.1007/978-3-642-21554-4\_27",

language = "English",

isbn = "978-3-642-21553-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "462--478",

editor = "J. Lopez and G. Tsudik",

booktitle = "International Conference on Applied Cryptography and Network Security",

address = "Germany",

note = "Applied Cryptography and Network Security - 9th International Conference, ACNS ; Conference date: 07-06-2011 Through 10-06-2011",

}

Ashur, T & Dunkelman, O 2011, Linear analysis of reduced-round CubeHash. in J Lopez & G Tsudik (eds), International Conference on Applied Cryptography and Network Security. Lecture Notes in Computer Science, vol. 6715, Springer, Berlin, pp. 462-478, Applied Cryptography and Network Security - 9th International Conference, Nerja, Spain, 7/06/11. https://doi.org/10.1007/978-3-642-21554-4_27

Linear analysis of reduced-round CubeHash. / Ashur, Tomer; Dunkelman, Orr.
International Conference on Applied Cryptography and Network Security. ed. / J. Lopez; G. Tsudik. Berlin: Springer, 2011. p. 462-478 (Lecture Notes in Computer Science; Vol. 6715).

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

TY - GEN

T1 - Linear analysis of reduced-round CubeHash

AU - Ashur, Tomer

AU - Dunkelman, Orr

N1 - Conference code: 2011

PY - 2011

Y1 - 2011

N2 - Recent developments in the field of cryptanalysis of hash functions has inspired NIST to announce a competition for selecting a new cryptographic hash function to join the SHA family of standards. One of the 14 second-round candidates was CubeHash designed by Daniel J. Bernstein. CubeHash is a unique hash function in the sense that it does not iterate a common compression function, and offers a structure which resembles a sponge function, even though it is not exactly a sponge function. In this paper we analyze reduced-round variants of CubeHash where the adversary controls the full 1024-bit input to reduced-round CubeHash and can observe its full output. We show that linear approximations with high biases exist in reduced-round variants. For example, we present an 11-round linear approximation with bias of 2 235, which allows distinguishing 11-round CubeHash using about 2470 queries. We also discuss the extension of this distinguisher to 12 rounds using message modification techniques. Finally, we present a linear distinguisher for 14-round CubeHash which uses about 2812 queries.

AB - Recent developments in the field of cryptanalysis of hash functions has inspired NIST to announce a competition for selecting a new cryptographic hash function to join the SHA family of standards. One of the 14 second-round candidates was CubeHash designed by Daniel J. Bernstein. CubeHash is a unique hash function in the sense that it does not iterate a common compression function, and offers a structure which resembles a sponge function, even though it is not exactly a sponge function. In this paper we analyze reduced-round variants of CubeHash where the adversary controls the full 1024-bit input to reduced-round CubeHash and can observe its full output. We show that linear approximations with high biases exist in reduced-round variants. For example, we present an 11-round linear approximation with bias of 2 235, which allows distinguishing 11-round CubeHash using about 2470 queries. We also discuss the extension of this distinguisher to 12 rounds using message modification techniques. Finally, we present a linear distinguisher for 14-round CubeHash which uses about 2812 queries.

KW - CubeHash

KW - SHA-3 competition

KW - Linear cryptanalysis

U2 - 10.1007/978-3-642-21554-4_27

DO - 10.1007/978-3-642-21554-4_27

M3 - Conference contribution

SN - 978-3-642-21553-7

T3 - Lecture Notes in Computer Science

SP - 462

EP - 478

BT - International Conference on Applied Cryptography and Network Security

A2 - Lopez, J.

A2 - Tsudik, G.

PB - Springer

CY - Berlin

T2 - Applied Cryptography and Network Security - 9th International Conference

Y2 - 7 June 2011 through 10 June 2011

ER -

Linear analysis of reduced-round CubeHash

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this