A Distinguisher for the Compression Function of SIMD-512

Tomislav Nad; Florian Mendel

doi:10.1007/978-3-642-10628-6_15

A Distinguisher for the Compression Function of SIMD-512

Tomislav Nad, Florian Mendel

Institute of Information Security (7050)

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

Abstract

SIMD is one of the round 2 candidates of the public SHA-3 competition hosted by NIST. It was designed by Leurent et al.. In this paper, we present a distinguisher attack on the compression function of SIMD-512. By linearizing the compression function we construct a linear code. Using techniques from coding theory to search for low Hamming weight codewords, we can find differential characteristics with low Hamming weight (and hence high probability). In the attack the differences are introduced only in the IV. Such a characteristic is the base for our distinguisher, which can distinguish the compression function of SIMD-512 from random with a complexity of 5·2425.28 compression function calls. Furthermore, we can distinguish the output transformation of SIMD-512 from random with a complexity of about 22·2425.28 compression function calls. So far this is the first cryptanalytic result for the SIMD hash function

Original language	English
Title of host publication	Progress in Cryptology - INDOCRYPT 2009
Editors	Bimal Roy, Nicolas Sendrier
Place of Publication	Berlin; Heidelberg
Publisher	Springer
Pages	219-232
ISBN (Print)	978-3-642-10627-9
DOIs	https://doi.org/10.1007/978-3-642-10628-6_15
Publication status	Published - 2009
Event	10th International Conference on Cryptology in India: INDOCRYPT 2009 - New Delhi, India Duration: 13 Dec 2009 → 16 Dec 2009

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5922

Conference

Conference	10th International Conference on Cryptology in India
Abbreviated title	INDOCRYPT 2009
Country/Territory	India
City	New Delhi
Period	13/12/09 → 16/12/09

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-642-10628-6_15

simd_attackFinal published version, 418 KB

EU - ECRYPT II - European network of excellence in cryptology - Phase II
Medwed, M. (Attendee / Assistant), Lamberger, M. (Attendee / Assistant), Rechberger, C. (Attendee / Assistant), Aigner, M. J. (Attendee / Assistant), Feldhofer, M. (Attendee / Assistant), Hutter, M. (Attendee / Assistant), Mendel, F. (Attendee / Assistant), Nad, T. (Attendee / Assistant), Kirschbaum, M. (Attendee / Assistant), Rijmen, V. (Attendee / Assistant), Tillich, S. (Attendee / Assistant), Schläffer, M. (Contact person), Posch, R. (Project manager) & Schmidt, J.-M. (Attendee / Assistant)
1/08/08 → 31/01/13
Project: Research project
FWF - Kryptoanalyse - Cryptanalysis by means of numerical methods
Schläffer, M. (Attendee / Assistant), Lamberger, M. (Attendee / Assistant), Rechberger, C. (Attendee / Assistant), Nad, T. (Attendee / Assistant), Rijmen, V. (Project manager) & Mendel, F. (Attendee / Assistant)
1/10/07 → 30/09/09
Project: Research project
Cryptography
Schläffer, M. (Attendee), Rijmen, V. (Coordinator), Oswald, M. E. (Contact person), Rechberger, C. (Attendee), Posch, R. (Contact person), Lamberger, M. (Attendee), Mendel, F. (Attendee), Eichlseder, M. (Attendee), Lipp, P. (Attendee), Nad, T. (Attendee) & Dobraunig, C. E. (Attendee)
1/01/95 → 31/01/19
Project: Research area

Cite this

@inproceedings{5e25e663eab64534985f7f2b5f79d41d,

title = "A Distinguisher for the Compression Function of SIMD-512",

abstract = "SIMD is one of the round 2 candidates of the public SHA-3 competition hosted by NIST. It was designed by Leurent et al.. In this paper, we present a distinguisher attack on the compression function of SIMD-512. By linearizing the compression function we construct a linear code. Using techniques from coding theory to search for low Hamming weight codewords, we can find differential characteristics with low Hamming weight (and hence high probability). In the attack the differences are introduced only in the IV. Such a characteristic is the base for our distinguisher, which can distinguish the compression function of SIMD-512 from random with a complexity of 5·2425.28 compression function calls. Furthermore, we can distinguish the output transformation of SIMD-512 from random with a complexity of about 22·2425.28 compression function calls. So far this is the first cryptanalytic result for the SIMD hash function",

author = "Tomislav Nad and Florian Mendel",

year = "2009",

doi = "10.1007/978-3-642-10628-6\_15",

language = "English",

isbn = "978-3-642-10627-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "219--232",

editor = "Bimal Roy and Nicolas Sendrier",

booktitle = "Progress in Cryptology - INDOCRYPT 2009",

address = "United States",

note = "10th International Conference on Cryptology in India : INDOCRYPT 2009, INDOCRYPT 2009 ; Conference date: 13-12-2009 Through 16-12-2009",

}

TY - GEN

T1 - A Distinguisher for the Compression Function of SIMD-512

AU - Nad, Tomislav

AU - Mendel, Florian

PY - 2009

Y1 - 2009

N2 - SIMD is one of the round 2 candidates of the public SHA-3 competition hosted by NIST. It was designed by Leurent et al.. In this paper, we present a distinguisher attack on the compression function of SIMD-512. By linearizing the compression function we construct a linear code. Using techniques from coding theory to search for low Hamming weight codewords, we can find differential characteristics with low Hamming weight (and hence high probability). In the attack the differences are introduced only in the IV. Such a characteristic is the base for our distinguisher, which can distinguish the compression function of SIMD-512 from random with a complexity of 5·2425.28 compression function calls. Furthermore, we can distinguish the output transformation of SIMD-512 from random with a complexity of about 22·2425.28 compression function calls. So far this is the first cryptanalytic result for the SIMD hash function

AB - SIMD is one of the round 2 candidates of the public SHA-3 competition hosted by NIST. It was designed by Leurent et al.. In this paper, we present a distinguisher attack on the compression function of SIMD-512. By linearizing the compression function we construct a linear code. Using techniques from coding theory to search for low Hamming weight codewords, we can find differential characteristics with low Hamming weight (and hence high probability). In the attack the differences are introduced only in the IV. Such a characteristic is the base for our distinguisher, which can distinguish the compression function of SIMD-512 from random with a complexity of 5·2425.28 compression function calls. Furthermore, we can distinguish the output transformation of SIMD-512 from random with a complexity of about 22·2425.28 compression function calls. So far this is the first cryptanalytic result for the SIMD hash function

U2 - 10.1007/978-3-642-10628-6_15

DO - 10.1007/978-3-642-10628-6_15

M3 - Conference paper

SN - 978-3-642-10627-9

T3 - Lecture Notes in Computer Science

SP - 219

EP - 232

BT - Progress in Cryptology - INDOCRYPT 2009

A2 - Roy, Bimal

A2 - Sendrier, Nicolas

PB - Springer

CY - Berlin; Heidelberg

T2 - 10th International Conference on Cryptology in India

Y2 - 13 December 2009 through 16 December 2009

ER -

A Distinguisher for the Compression Function of SIMD-512

Abstract

Publication series

Conference

Fields of Expertise

Access to Document

Fingerprint

Projects

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

FWF - Kryptoanalyse - Cryptanalysis by means of numerical methods

Cryptography

Cite this