One-way Compression Function - Hirose

Hirose

The Hirose double-block-length one-way compression function consists of a block cipher plus a permutation p. It was proposed by Shoichi Hirose in 2006 and is based on a work by Mridul Nandi.

It uses a block cipher whose key length k is larger than the block length n, and produces a hash of size 2n. For example, any of the AES candidates with a 192- or 256-bit key (and 128-bit block).

Each round accepts a portion of the message m_i that is k−n bits long, and uses it to update two n-bit state values G and H.

First, m_i is concatenated with H_i−1 to produce a key K_i. Then the two feedback values are updated according to:

• G_i = E_Ki(G_i−1) ⊕ G_i−1
• H_i = E_Ki(p(G_i−1)) ⊕ p(G_i−1).

p(G_i−1) is an arbitrary fixed-point-free permutation on an n-bit value, typically defined as

• p(x) = x ⊕ c

for an arbitrary non-zero constant c. (All-ones may be a convenient choice.)

Each encryption resembles the standard Davies–Meyer construction. The advantage of this scheme over other proposed double-block-length schemes is that both encryptions use the same key, and thus key scheduling effort may be shared.

The final output is H_t||G_t. The scheme has the rate R_Hirose = (k−n)/2·n relative to encrypting the message with the cipher.

Hirose also provides a proof in the Ideal Cipher Model.