# 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$:

$a' = a + b \, \pmod{2^n}$
$b' = a + 2b\, \pmod{2^n}$

Reverse:
$b = b' - a' \, \pmod{2^n}$
$a = 2a' - b' \, \pmod{2^n}$

(Source: Wikipedia)

What's 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. (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:

$a' = a + b \, \pmod{2^n}$
$b' = a + rotL(b, 1)\, \pmod{2^n}$

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

-
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