The SIMD Hash Function
Description
SIMD is a new hash function family, which has been submitted as a SHA-3 candidate. SIMD is based on a familiar Merkle-Damgård design, where the compression function is built from a Feistel-like cipher in Davies-Meyer mode. However there are some innovations in this design: the internal state is twice as big as the output size, we use a strong message expansion, and we use a modified feed-forward in the compression function. This mode of operation is secure against generic attacks. The most important component of SIMD is its message expansion, which is designed to give a high minimal distance. This allows to prove that SIMD is secure against differential cryptanalysis.
SIMD features a small scale parallelism, inside the compression function. This can be used to write an efficient implementation with vector instructions (SIMD). Such instructions are available on many widely used architectures: SSE on x86, Altivec on PowerPC, IwMMXt on ARM. Therefore, SIMD is quite fast on NIST reference platform:
| OS mode: | 32 bit | 64 bit |
|---|---|---|
| Speed of SIMD on a Core2 | ||
| SIMD-256 | 12 cpb | 11 cpb |
| SIMD-512 | 13 cpb | 12 cpb |
Independent measures from eBASH gives:
| Processor: | Core i5 | Core 2 (45 nm) | Core 2 (65 nm) |
|---|---|---|---|
| Speed measured by eBASH (2010.05.15) | |||
| SIMD-256 | 7.51 cpb | 9.18 cpb | 11.34 cpb |
| SIMD-512 | 8.63 cpb | 10.02 cpb | 12.05 cpb |
Moreover, the compression function of SIMD can be parallelized on two cores for improved performances.
News
Finalists and winner
SIMD was not selected as a SHA-3 finalist, and NIST has now annouced the winner: Keccak. Congratulations to the Keccak team!
Security Analysis
A security analysis of SIMD is now available. This paper provides three important contributions to the security analysis of SIMD. First, we show a new free-start distinguisher based on symmetry relations. However, this distinguisher in much weaker than other symmetry-based distinguishers because each pair of symmetric states can only be used with a single message. Second, we give a formal proof of security in the presence of some distinguishers, including symmetry-based distinguishers, and differential path with a non-zero difference in the chaining value. Third, we study differential path with a non-zero difference in the message, and show that the probability of such paths is at most of the order of 2n/2. This shows that SIMD is resistant to differential cryptanalysis.
Typo in the submission document
A typo in the specification of SIMD has been reported by Luca Henzen and Thomas Pornin. Page 22, algorithme 1, ligne 32, the constant 24 should actually be 25. This constant is used as a rotation in the compression part. The document available on this page has been fixed. The code was using the correct value, so the test vector are not affected by this typo.
The rationale behind using 25 instead of 24 is that we want to use a relatively small set of rotation amount to allow for more efficient implementations. In particular, these offset needs to be inside registers on some architecture and it helps if they are used multiple times before changing to a new set of rotations.
Second Round
SIMD has been accepted in the second round of NIST SHA-3 competition.
We took this opportunity to do some more study of the design, and we realized that the rotations and the permutations used in SIMD were not as good as expected. Therefore we decided to tweak the design by changing those rotations and permutations. The tweaked version runs at the same speed as the original one.
The tweak is described in this note, and updated submission documents are now available.
Download
Tweaking SIMD, description of the tweak (2009-09-15). | SIMD Is a Message Digest, submission document (tweaked version with typo fixed — 2010-02-23). | Full submission package, with Implementations and KAT-MCT (tweaked version with typo fixed — 2010-02-23). | Presentation of SIMD, (presented at the first SHA-3 conference — 2009-02-27). | Security Analysis of SIMD, (2010-06-01).