10
$\begingroup$

I was looking at the algorithm for Twofish, and I noticed that in some places a XOR is used, but in others, they use "addition modulo-32." What makes modulo-32 special? Why not always use XOR? Why not always addition mod 32?

$\endgroup$
11
$\begingroup$

The combination between addition modulo $2^{32}$ (not modulo $32 = 2^5$) - indicated by $\boxplus$ in the diagram - and XOR (i.e. bitwise addition modulo $2$) - indicated by $\oplus$ - makes the algorithm more non-linear.

Each of them for itself is a linear operation, but over different groups (addition in $GF(2^{32})$ vs. addition in $Z/2^{32})$, and the combination is slightly non-linear over both groups.

Why modulo $2^{32}$? This operation is already implemented in many processors (Java's int addition is this, for example), and this makes implementation easy and efficient.

The later Threefish cipher used in Skein takes this to a new level, its nonlinearity depending exclusively on this simple combination, in a really large number of rounds.

$\endgroup$
  • $\begingroup$ For the PHT at least, this answer isn't correct. They used modular addition because it could be implemented more efficiently using the LEA instruction to perform several operations at once. This actually decreases security very slightly, since the most significant bit is lost in the PHT (see the AES submission paper). $\endgroup$ – forest Jan 12 at 5:06
  • $\begingroup$ @forest Don't you think that a simple XOR is similarly parallelizable as the modular addition? (The question was comparing XOR with add mod $2^32$, not modular addition with some other addition.) (Also, what is PHT in this context?) $\endgroup$ – Paŭlo Ebermann Jan 13 at 1:56
  • $\begingroup$ PHT refers to Pseudo-Hadamard Transform in this context. It's not that it's parallelizable so much as the fact that the LEA instruction is able to perform both the PHT and the subkey addition in just one clock (see section 7.4 and 7.5). For PHT over 32-bit integers $a$ and $b$, Twofish does $a^\prime = a + b \mod 2^{32}$ and $b^\prime = a + 2b \mod 2^{32}$. Section 7.8 explains how the security is decreased (very slightly): "The half of the PHT involving the quantity $T_0 + 2T_1$ will lose the most significant bit of $T_1$ due to the multiply by two." $\endgroup$ – forest Jan 13 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.