Lehmer random number generator cipher - looking for differentials

Question

I'm looking for differentials in my kind of toy encryption scheme. I can't find any.

Let's consider linear congruential generator:

$X_{k+1} = a \cdot X_{k} \mod 2^{128}$

Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different output $X_{k+1}$ from $0$ to $2^{128}-1$. So we got bijection here (we can find many such odd $a$). Now let's say we will choose such 128-bit $a_{1},a_{2}, ..., a_{10}$ as a keys, randomly. We make $10$ rounds of encryption like that:

1. $a_{1} \cdot INPUT \mod 2^{128}$
2. Reverse $128$-bit block.
3. $a_{2} \cdot (2^{128}-INPUT) \mod 2^{128}$
4. $a_{3} \cdot INPUT \mod 2^{128}$
5. Reverse $128$-bit block.
6. $a_{4} \cdot (2^{128}-INPUT) \mod 2^{128}$

and so on...

Do you see any differentials here? Let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round. Of course it is just keyed Lehmer random number generator with a modulus which is a power of two - and such generators have problems with low bits, but I can't use it to find differentials in that case.

Answer 1

Do you see any differentials here?

Yes; consider a differential where one side is the value $X$ and the other side is the value $2^{127}-X$.

Your cipher consists of three operations:

• Multiplying the current value by an odd value $a_i$ modulo $2^{128}$

This operation preserves the differential with probability 1; one side would evaluate to $a_i \cdot X$ and the other side would evaluate to $a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X$

• Negating the current value (which is done as a part of rounds 2-10)

This operation preserves the differential with probability 1; this happens because $-(2^{127} - X) = 2^{127} - (-X)$

• Reversing the bits in the current value

This operation preserves the differential with probability 0.5; namely, if the lsbit of $X$ (equivalently, $2^{127} - X$) is a 1. This happens because, when the lsbit is a 1, this relationship is equivalent to the relation that $X \oplus (2^{127}-X) = 2^{127}-2$. This later relation is preserved when you reverse the bits, and hence the former one is as well.

This gives you a differential that holds with probability $2^{-10}$ through the ten rounds of the cipher.