1
$\begingroup$

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 $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 and every round compute:

  1. $a_{i} \cdot INPUT \mod 2^{128}$
  2. Reverse 128-bit block.

So the next round input is an inverted block of previous round output. And it looks like it make a big difference. If we wouldn't reverse block - we got just keyed Lehmer random number generator with a modulus which is a power of two - and it is definitely not secure (because the low $k$ bits form a modulo-$2^{k}$ generator all by themselves).

But with "reversing" we get completely different results! It looks chaotic. I have no idea is 10 rounds enough - just guessing. Is this type of encryption secure? Do you see any obvious weaknesses? To analyze it we can choose smaller keys and smaller operating mode - for example 5-bit or 10-bit. A detailed analysis of this cipher can be difficult, my question is rather about some obvious weaknesses. The cipher appears to be unexpectedly good, despite being only a minor modification of the linear congruential generator. So either I don't notice something or it is quite a non-trivial proposition.

Comment 1: let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ "we can find many such $a$" can be replaced by: "that is odd $a$". $\endgroup$
    – fgrieu ♦
    Commented Sep 17, 2020 at 19:47

1 Answer 1

Reset to default
3
$\begingroup$

Is this type of encryption secure?

Nope (even if you make all the $a_i$ values odd, which you need to make it invertible).

It turns out that there are high probability differentials in this structure; in particular, you have a one-round differential with an input xor difference of (01111...11110) (that is, all bits except the first and last are flipped) and the output xor difference of (01111...11110); this differential holds with probability $> 0.5$. Because the output differential of round $X$ is the input differential of round $X+1$, the entire differential holds through the entire cipher with probability $> 2^{-10}$

Improve this answer
$\endgroup$
4
  • $\begingroup$ But does this difference allow to find the key, or is it just a problem because it makes it easier to guess the plaintext? $\endgroup$
    – Tom
    Commented Sep 19, 2020 at 21:44
  • 1
    $\begingroup$ @Tom: if you find a differential pair where the differential holds through 9 rounds and doesn't in the 10th, by examining the resulting two ciphertexts, you can recover the last round subkey. From that, you can use the LCG relationship to recover everything $\endgroup$
    – poncho
    Commented Sep 20, 2020 at 1:57
  • $\begingroup$ If I understand it properly, if we add third step: move with wrapping obtained block by $0-127$ steps, then to attack it in the same way, we have $128$ times smaller differential probability in every round. If we make $20$ rounds, we could have entire differential holds with probability about $128^{20}$. Then it could be secure from that type of attack. $\endgroup$
    – Tom
    Commented Sep 20, 2020 at 18:43
  • $\begingroup$ Is it good idea to make xoring before and after every round to avoid these problems? In general if round functions are insecure, xoring does not help. But maybe here it is a good idea? $\endgroup$
    – Tom
    Commented Nov 16, 2020 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.