The SIMD Hash Function

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 (more detailed performance figures can be found on eBASH):

OS mode:	32 bit	64 bit
Speed of SIMD on a Core2
SIMD-256	12 cpb	11 cpb
SIMD-512	13 cpb	12 cpb

Moreover, the compression function of SIMD can be parallelized on two cores for improved performances.

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.

SIMD Updates

SIMD has been presented in the first SHA-3 conference in Leuven. The slides of the presentation are available in the download section.

An updated version of the submission document is also available, with many typos corrections. These version contains some additional material wrt. the updated NIST version.

The implementation have also been updated, and now includes:

• A vectorized version of SIMD-256 and SIMD-512 for x86 processors with SSE2, and PowerPC processors with Altivec
• A vectorized version of SIMD-256 for ARM processors with IwMMXt instructions (aka WMMX).

Typos in the original submission

There were some mistakes in the original submission:

• The permutations in the Feistel part of SIMD-512 were used in a different order in the code and in the description. The submission document has been modified to match the implementation.
• There was a typo in the description of the inner codes. The constants that give an optimal minimal distance are 185 and 233, but in the original submission, 223 was used instead of 233 in some places. The original implementation also used 223, so the KAT-MCT have been regenerated.

Some extra sections have also been added to the submission document, to give some extra explanations about the design.

Tweaking SIMD, description of the tweak (2009-09-15). | SIMD Is a Message Digest, submission document (tweaked version — 2009-09-15). | Full submission package, with Implementations and KAT-MCT (tweaked version — 2009-09-15). | Presentation of SIMD, (presented at the first SHA-3 conference — 2009-02-27).