# Pseudo-Hadamard transform, most significant bit

For clarification: The Pseudo-Hadamard transformation is a reversible transformation of a bit string that provides cryptographic diffusion. Splitting a bit string (with bit length of $$2n$$) into two equally large bit strings $$a$$ and $$b$$ with size $$n$$:

\begin{align} a' &= a + b & \pmod{2^n}\\ b' &= a + 2b& \pmod{2^n} \end{align} Reverse:
\begin{align} b &=b' - a' & \pmod{2^n}\\ a &= 2a' - b' & \pmod{2^n} \end{align}

What about the most significant bit (the most right bit) of $$b$$ in $$b'$$? Multiplication with $$2$$ and $$\mod{2^n}$$ cut this off. We lose any possible diffusion of this bit in $$b$$. That can't be good. Especially SAFER K and SAFER SK are heavily relying on the pseudo-hadamard transformation, see SAFER at Wikipedia.

My first question:
How does this affect the whole security of a cypher with this transformation? Is there a know attack on SAFER which exploits this characteristic?

My second question:
How can we fix this? Is there any public solution for this problem? Maybe we can replace the multiplication? I did try something with a left rotation of 1, but that combination doesn't work. Either this doesn't work in general, or I just don't know the "other secret key" to reverse the transformation with rotation instead of multiplication:

\begin{align} a' &= a + b & \pmod{2^n}\\ b' &= a + rotL(b, 1)& \pmod{2^n} \end{align}

Reverse: (Warning, wrong equation)
\begin{align} b &= b' - a' & \pmod{2^n}\\ a &= rotL(a', 1) - b' & \pmod{2^n} \end{align}

• I don't think this is a problem. However you could improve it by doing: $a' = a + b \, \pmod{2^n}$ $b' = (a + b) ⊕ b\, \pmod{2^n}$ This would also add some non-linearity. – LightBit May 17 '14 at 8:34
• @LightBit: And how do I reverse this construct? – Nova May 17 '14 at 15:06
• $b = b' \oplus a' \, \pmod{2^n}$ $a = (a' \oplus b') - b' \, \pmod{2^n}$ – LightBit May 17 '14 at 17:37
• @LightBit: how would changing to $b' = (a+b)\oplus b \pmod{2^n}$ fix the "problem" that the msbit of $b'$ does not depend on the msbit of $b$? – poncho May 18 '14 at 17:58
• @poncho: Sorry, my mistake. It doesn't. – LightBit May 19 '14 at 15:05

The Pseudo-Hadamard Transform on $$n$$-bit integers $$a$$ and $$b$$ is defined as
\begin{align} a^\prime &= a + b &\pmod {2^n}\\ b^\prime &= a + 2b &\pmod {2^n} \end{align}
It is true that the most significant bit (MSB) of $$b^\prime$$ does not depend on the MSB of $$b$$. Whether or not this is a problem depends on exactly how it is used in the cipher. While I'm not aware of whether or not this makes any attacks possible on SAFER, Twofish, which also uses the PHT, considers this to be a non-issue. While the MSB is indeed lost, the reduction of security is insignificant, and any measures used to preserve the bit are not worth the performance impacts. From section 7.8 of the Twofish paper:
The two outputs of the $$g$$ functions ($$T_0$$ and $$T_1$$) are then combined using a PHT so that both of them will affect both 32-bit Feistel XOR quantities. 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. This bit could be regained using some extra operations, but the software performance would be significantly decreased, with very little apparent cryptographic benefit. In general, the most significant byte of this PHT output will still have a non-zero output difference with probability $$254/255$$ over all 1-bit input differences.