### Security Analysis of SIMD

Charles Bouillaguet, Pierre-Alain Fouque, and Gaëtan Leurent

##### Abstract

In this paper we study the security of the SHA-3 candidate SIMD. We first show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once. In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage. Finally, in the third part we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of $2^{n/2}$ using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
SIMDSHA-3hash functiondistinguishersecurity proof with distinguishers
Contact author(s)
Gaetan Leurent @ ens fr
History
Short URL
https://ia.cr/2010/323

CC BY

BibTeX

@misc{cryptoeprint:2010/323,
author = {Charles Bouillaguet and Pierre-Alain Fouque and Gaëtan Leurent},
title = {Security Analysis of SIMD},
howpublished = {Cryptology ePrint Archive, Paper 2010/323},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/323}},
url = {https://eprint.iacr.org/2010/323}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.