An Anomalous Differential Attack on a Block Cipher

In this attack a differential propagates with difficulty for some 20, 40 and up to 64 rounds. We can say that the propagation encounters some “friction”, because the non-linear functions do not always behave as the attacker would like them to behave. Everything looks normal and this is what happens for all block ciphers all the time.

But then for 65, 80, 128 and more rounds, the propagation becomes easier and easier, the friction disappears, the differentials are reproduced MORE easily. This is for EXACTLY the same cipher spec, with different keys though. At the end of the day we discover that this block cipher configuration is not secure no matter how large is the number of rounds, and for any key.

Interestingly when we study what happens locally, say for up to 32 rounds, nothing unusual is observed and the ciphers exhibits no unusual behavior when the number of rounds is small.

This result was presented at ICISC 2020 in Seoul, Korea on 3 December 2020. We call this type of behavior “Non-Markovian propagation” and it is quite rare.

In addition we are able to transform a bug, or an outlier, something which researchers normally discard as inconvenient and problematic, into a feature. We show that this property helps the attacker, and it helps absolutely a lot, to the point that the cipher is never actually secure.

Some most interesting results in cryptanalysis are when something quite unexpected happens… contrary to the intuition ans contrary to the philosophy of 99.999% of ciphers ever made or studied: where authors systematically and maybe naively assume that probabilities do multiply and that they will decrease exponentially when you iterate the cipher. If so, it is sufficient to test a reduced-round version for high probability differentials. Here the probabilities decrease initially at an exponential rate, but later they behave abnormally and stay bounded by a small constant forever. A cipher can be insecure, even though it has no large probability differentials locally: it is a global long-term property only visible for a larger number of rounds like 64 or more, and only for very few special differences.

Here are the slides presented in normalextended version.
And here is a recorded video of my presentation.

Leave a Reply

Your email address will not be published. Required fields are marked *