CRUNCH

A candidate for the NIST hash competition (SHA-3)

Team

Submitter: Jacques Patarin (PRISM, University of Versailles Saint Quentin, France)
Team:
  • Louis Goubin (PRISM, UVSQ)
  • Mickael Ivascot (PRISM, UVSQ)
  • William Jalby (PRISM, UVSQ)
  • Olivier Ly (LABRI, Bordeaux University, France)
  • Valerie Nachef  (University of Cergy-Pontoise, France)
  • Joana Treger (UVSQ)
  • Emmanuel Volte (UCP)

Presentation

The algorithm enables to obtain digests of 224, 256, 384 and 512 bits. First an encryption permutation based on an unbalanced Feistel scheme with expanding functions will be designed.

This permutation will be a pseudorandom permutation from kn bits to kn bits using random  expanding functions from n bits to (k-1)n bits. Then a compression function is constructed by xoring two such permutations and choosing a number of bits depending on the desired length of the message digest.

The hash algorithm can be described in four stages: preprocessing, encryption permutation, compression function and  hash computations. Preprocessing involves padding the message, setting an initialization vector and an initial value. The hash computation uses 2 encryption permutations, the compression function together with the Merkle-Damgard construction.

The proposed hash algorithm (CRUNCH) has an extremely simple structure: basically the innermost loop amounts to accessing S-boxes and XORing the data accessed. Its simplicity is key to our design because it allows simple and efficient implementation on almost any microprocessor, it simplifies its protection and finally it makes easier to establish a direct relation between CRUNCH security and a generic (well known) security problem. The simplicity of its computational structure is compensated by the requirement of accessing (and storing) S-boxes  hose total size is around 1 MB. This storage requirement can be lifted by computing on the fly the S-boxes. Although it increases the computational requirements, it does not alter any properties on the security of CRUNCH.

Download

Specifications: crunch_specifications.pdf (last change 27/01/2009)

Slides presentation: crunch_presentation.pdf

New release package (7/02/2009) : rar (15MB) or directory


Comments, news

Use of the double pipe version of CRUNCH with another cipher: Katan (2012)
Here a version of crunch_256 of about 10KB (in 32 bits or 64 bits). The constants are calculated on the fly.

Contact: emmanuel.volte@aliceadsl.fr