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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered May 13, 2012 at 18:28
-
$\begingroup$ For the PHT at least, this answer isn't correct. They used modular addition because it could be implemented more efficiently using the
LEAinstruction 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, 2019 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$ Jan 13, 2019 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
LEAinstruction 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, 2019 at 11:25