# Choice of reduction polynomial in Whirlpool's internal cipher

Whirlpool is an interesting little hash function in the Miyaguchi-Preneel family.

In my mind, it's most interesting feature is the design of internal cipher W, where the distinction between key and message is dropped, providing a symmetric symmetric cipher. This conceivably removes the need to test for weaknesses to related-key attacks, since if you can do something in the key you could just do it in the message, and makes a lot of sense as a hash function internal.

However, why did they change the field polynomial from that used in AES?

Table 1: Differences between RIJNDAEL and W

RIJNDAEL                                      W
Block size (bits)                          128, 160, 192, 224, or 256             always 512
Number of rounds                       10, 11, 12, 13, or 14                       always 10
Key schedule                              dedicated a priori algorithm            the round function itself
$GF(2^8)$ reduction polynomial

(0x11B)
$x^8+x^4+x^3+x+1$
(0x11D)
$x^8+x^4+x^3+x^2+1$

Origin of the S-box

mapping u → u-1 over $GF(2^8)$,
plus affine transform
recursive structure (see below)

Origin of the round constants    polynomials $x^i$ over $GF(2^8)$        successive entries of the S-box
Diffusion layer

left-multiplication by the
4×4 circulant MDS matrix
cir(2, 3, 1, 1)
right-multiplication by the
8×8 circulant MDS matrix
cir(1, 1, 4, 1, 8, 5, 2, 9)

The W S-box, which in the original submission is generated entirely at random (i.e. lacks any internal structure), by a recursive structure: the new 8×8 substitution box is composed of smaller 4×4 "mini-boxes" (the exponential E-box, its inverse, and the pseudo-randomly generated R-box).

More generally, why were several of the internal constants and methods changed?

-
nb: If someone wants to copy up the comparison table here they're more than welcome - the lack of table support on SE stopped me. Also, I have not tagged this with hash because its not actually about hash functions - its about a symmetric cipher that I've only seen used inside a particular hash function. –  figlesquidge Jan 27 at 13:51
"If someone wants to copy up the comparison table..." - Done. –  e-sushi Jan 27 at 16:54

According to the original NESSIE submission of Whirlpool:

"The ﬁnite ﬁeld ${\rm GF}(2^8)$ will be represented as ${\rm GF}(2)[x]/p(x)$, where $p(x) =$ $x^8 +$ $x^4 +$ $x^3 +$ $x^2 +$ $1$ is the ﬁrst primitive polynomial of degree $8$ listed in [19]. The polynomial $p(x)$ was chosen so that $g(x) = x$ is a generator of ${\rm GF}(2^8) \setminus \{0\}$."

The reference "[19]" is to Lidl & Niederreiter, Introduction to Finite Fields and Their Applications (Cambridge Univ. Press, 1986), which indeed, in Appendix 2, Table C, lists all the irreducible polynomials of degree 8 over ${\rm GF}(2)$ in lexicographic order. The first of these, $p(x) =$ $x^8 +$ $x^4 +$ $x^3 +$ $x +$ $1$, is the AES polynomial, and is irreducible but not primitive. The second one is the Whirlpool polynomial given above, and is the first primitive polynomial in the list.

Honestly, though, I have no idea why Whirlpool would require a primitive reduction polynomial, while Rijndael does not.

It might have something to do with a primitive polynomial allowing more efficient implementation on low-end platforms. In particular, as the Whirlpool submission notes, for primitive reduction polynomials, $g(x) = x$ is a generator of the full multiplicative group of the field, and, at least at a glance, the suggested implementation of the MDS matrix multiplication on 8-bit processors in the Whirlpool paper appears to make some use of this fact.

-
Ps. See also this related question. –  Ilmari Karonen Mar 23 at 20:15
Thanks for the answer Ilmari - and thank you 'Quarterly Reviews'! –  figlesquidge Mar 23 at 20:47

I guess that a single e-mail to Vincent Rijmen might solve this problem, but I would speculate that the new S-box should have been more hardware-friendly compared to that of Rijndael. The recursive structure of $W$ and smaller constants in the MDS matrix may have required another field representation.

-