Cryptanalysis of Luffa v2 Components

Dmitry Khovratovich; Maria Naya-Plasencia; Andrea Röck; Martin Schläffer

doi:10.1007/978-3-642-19574-7_26

Cryptanalysis of Luffa v2 Components

Dmitry Khovratovich, Maria Naya-Plasencia, Andrea Röck, Martin Schläffer

Institute of Information Security (7050)

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

Abstract

We develop a number of techniques for the cryptanalysis of the SHA-3 candidate Luffa, and apply them to various Luffa components. These techniques include a new variant of the rebound approach taking into account the specifics of Luffa. The main improvements include the construction of good truncated differential paths, the search for differences using multiple inbound phases and a fast final solution search via linear systems. Using these techniques, we are able to construct non-trivial semi-free-start collisions for 7 (out of 8 rounds) of Luffa-256 with a complexity of 2104 in time and 2 102 in memory. This is the first analysis of a Luffa component other that the permutation of Luffa v1. Additionally, we provide new and more efficient distinguishers also for the full permutation of Luffa v2. For this permutation distinguisher, we use a new model which applies first a short test on all samples and then a longer test on a smaller subset of the inputs. We demonstrate that a set of right pairs for the given differential path can be found significantly faster than for a random permutation.

Original language	English
Title of host publication	Selected Areas in Cryptography
Editors	Alex Biryukov, Guang Gong, Douglas R. Stinson
Publisher	Springer
Pages	388-409
ISBN (Electronic)	978-364219573-0
DOIs	https://doi.org/10.1007/978-3-642-19574-7_26
Publication status	Published - 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	6544 LNCS
ISSN (Electronic)	1611-3349

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-642-19574-7_26

FWF - kryptographische Hashfu - Cryptanalysis of modern cryptographic hash functions II
Nad, T. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)), Schläffer, M. (Co-Investigator (CoI)), Lamberger, M. (Co-Investigator (CoI)) & Rijmen, V. (Principal Investigator (PI))
1/02/10 → 31/01/13
Project: Research project
EU - ECRYPT II - European network of excellence in cryptology - Phase II
Schmidt, J.-M. (Co-Investigator (CoI)), Nad, T. (Co-Investigator (CoI)), Kirschbaum, M. (Co-Investigator (CoI)), Feldhofer, M. (Co-Investigator (CoI)), Schläffer, M. (Co-Investigator (CoI)), Aigner, M. J. (Co-Investigator (CoI)), Rechberger, C. (Co-Investigator (CoI)), Lamberger, M. (Co-Investigator (CoI)), Tillich, S. (Co-Investigator (CoI)), Medwed, M. (Co-Investigator (CoI)), Hutter, M. (Co-Investigator (CoI)), Rijmen, V. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)) & Posch, R. (Principal Investigator (PI))
1/08/08 → 31/01/13
Project: Research project
Cryptography
Schläffer, M. (Co-Investigator (CoI)), Oswald, M. E. (Co-Investigator (CoI)), Lipp, P. (Co-Investigator (CoI)), Dobraunig, C. E. (Co-Investigator (CoI)), Mendel, F. (Co-Investigator (CoI)), Eichlseder, M. (Co-Investigator (CoI)), Nad, T. (Co-Investigator (CoI)), Posch, R. (Co-Investigator (CoI)), Lamberger, M. (Co-Investigator (CoI)), Rijmen, V. (Co-Investigator (CoI)) & Rechberger, C. (Co-Investigator (CoI))
1/01/95 → 31/01/19
Project: Research area

Cite this

Khovratovich, D., Naya-Plasencia, M., Röck, A., & Schläffer, M. (2010). Cryptanalysis of Luffa v2 Components. In A. Biryukov, G. Gong, & D. R. Stinson (Eds.), Selected Areas in Cryptography (pp. 388-409). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6544 LNCS). Springer. https://doi.org/10.1007/978-3-642-19574-7_26

Cryptanalysis of Luffa v2 Components. / Khovratovich, Dmitry; Naya-Plasencia, Maria; Röck, Andrea et al.
Selected Areas in Cryptography. ed. / Alex Biryukov; Guang Gong; Douglas R. Stinson. Springer, 2010. p. 388-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6544 LNCS).

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

Khovratovich, D, Naya-Plasencia, M, Röck, A & Schläffer, M 2010, Cryptanalysis of Luffa v2 Components. in A Biryukov, G Gong & DR Stinson (eds), Selected Areas in Cryptography. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6544 LNCS, Springer, pp. 388-409. https://doi.org/10.1007/978-3-642-19574-7_26

@inproceedings{45a992c7453d4d31b8174eb4150f9b17,

title = "Cryptanalysis of Luffa v2 Components",

abstract = "We develop a number of techniques for the cryptanalysis of the SHA-3 candidate Luffa, and apply them to various Luffa components. These techniques include a new variant of the rebound approach taking into account the specifics of Luffa. The main improvements include the construction of good truncated differential paths, the search for differences using multiple inbound phases and a fast final solution search via linear systems. Using these techniques, we are able to construct non-trivial semi-free-start collisions for 7 (out of 8 rounds) of Luffa-256 with a complexity of 2104 in time and 2 102 in memory. This is the first analysis of a Luffa component other that the permutation of Luffa v1. Additionally, we provide new and more efficient distinguishers also for the full permutation of Luffa v2. For this permutation distinguisher, we use a new model which applies first a short test on all samples and then a longer test on a smaller subset of the inputs. We demonstrate that a set of right pairs for the given differential path can be found significantly faster than for a random permutation. ",

author = "Dmitry Khovratovich and Maria Naya-Plasencia and Andrea R{\"o}ck and Martin Schl{\"a}ffer",

year = "2010",

doi = "10.1007/978-3-642-19574-7_26",

language = "English",

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

publisher = "Springer",

pages = "388--409",

editor = "Alex Biryukov and Guang Gong and Stinson, {Douglas R.}",

booktitle = "Selected Areas in Cryptography",

}

TY - GEN

T1 - Cryptanalysis of Luffa v2 Components

AU - Khovratovich, Dmitry

AU - Naya-Plasencia, Maria

AU - Röck, Andrea

AU - Schläffer, Martin

PY - 2010

Y1 - 2010

N2 - We develop a number of techniques for the cryptanalysis of the SHA-3 candidate Luffa, and apply them to various Luffa components. These techniques include a new variant of the rebound approach taking into account the specifics of Luffa. The main improvements include the construction of good truncated differential paths, the search for differences using multiple inbound phases and a fast final solution search via linear systems. Using these techniques, we are able to construct non-trivial semi-free-start collisions for 7 (out of 8 rounds) of Luffa-256 with a complexity of 2104 in time and 2 102 in memory. This is the first analysis of a Luffa component other that the permutation of Luffa v1. Additionally, we provide new and more efficient distinguishers also for the full permutation of Luffa v2. For this permutation distinguisher, we use a new model which applies first a short test on all samples and then a longer test on a smaller subset of the inputs. We demonstrate that a set of right pairs for the given differential path can be found significantly faster than for a random permutation.

AB - We develop a number of techniques for the cryptanalysis of the SHA-3 candidate Luffa, and apply them to various Luffa components. These techniques include a new variant of the rebound approach taking into account the specifics of Luffa. The main improvements include the construction of good truncated differential paths, the search for differences using multiple inbound phases and a fast final solution search via linear systems. Using these techniques, we are able to construct non-trivial semi-free-start collisions for 7 (out of 8 rounds) of Luffa-256 with a complexity of 2104 in time and 2 102 in memory. This is the first analysis of a Luffa component other that the permutation of Luffa v1. Additionally, we provide new and more efficient distinguishers also for the full permutation of Luffa v2. For this permutation distinguisher, we use a new model which applies first a short test on all samples and then a longer test on a smaller subset of the inputs. We demonstrate that a set of right pairs for the given differential path can be found significantly faster than for a random permutation.

U2 - 10.1007/978-3-642-19574-7_26

DO - 10.1007/978-3-642-19574-7_26

M3 - Conference paper

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

SP - 388

EP - 409

BT - Selected Areas in Cryptography

A2 - Biryukov, Alex

A2 - Gong, Guang

A2 - Stinson, Douglas R.

PB - Springer

ER -

Cryptanalysis of Luffa v2 Components

Abstract

Publication series

Fields of Expertise

Access to Document

Fingerprint

Projects

FWF - kryptographische Hashfu - Cryptanalysis of modern cryptographic hash functions II

EU - ECRYPT II - European network of excellence in cryptology - Phase II

Cryptography

Cite this