# 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 2^{n/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).