Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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}$

share|improve this question
    
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 at 8:34
    
@LightBit: And how do I reverse this construct? –  Nova May 17 at 15:06
    
$b = b' \oplus a' \, \pmod{2^n}$ $a = (a' \oplus b') - b' \, \pmod{2^n}$ –  LightBit May 17 at 17:37
1  
@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 at 17:58
    
@poncho: Sorry, my mistake. It doesn't. –  LightBit May 19 at 15:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.