In this paper we look at the security of two block ciphers which were both claimed in the published literature to be secure
against differential crypt-analysis (DC). However, a more careful examination shows that none of these ciphers is very secure
against... differential cryptanalysis, in particular if we consider attacks with sets of differentials. For both these ciphers
we report new perfectly periodic (iterative) aggregated differential attacks which propagate with quite high probabilities.
The first cipher we look at is GOST, a well-known Russian government encryption standard. The second cipher we look at is
PP-1, a very recent Polish block cipher. Both ciphers were designed to withstand linear and differential cryptanalysis. Unhappily,
both ciphers are shown to be much weaker than expected against advanced differential attacks. For GOST, we report better and
stronger sets of differentials than the best currently known attacks presented at SAC 2000  and propose the first attack
ever able to distinguish 16 rounds of GOST from random permutation. For PP-1 we show that in spite of the fact, that its S-box
has an optimal theoretical security level against differential cryptanalysis , , our differentials are strong enough
to allow to break all the known versions of the PP-1 cipher.
Authors:Nicolas T. Courtois, Theodosis Mourouzis, Anna Grocholewska-Czuryło and Jean-Jacques Quisquater
Differential Cryptanalysis (DC) is one of the oldest known attacks on block ciphers. DC is based on tracking of changes in the differences between two messages as they pass through the consecutive rounds of encryption. However DC remains very poorly understood. In his textbook written in the late 1990s Schneier wrote that against differential cryptanalysis, GOST is “probably stronger than DES”. In fact Knudsen have soon proposed more powerful advanced differential attacks however the potential space of such attacks is truly immense. To this day there is no method which allows to evaluate the security of a cipher against such attacks in a systematic way. Instead, attacks are designed and improved in ad-hoc ways with heuristics [6–13,21]. The best differential attack known has time complexity of 2179 .
In this paper we show that for a given block cipher there exists an optimal size for advanced differential properties. This new understanding allows to considerably reduce the space to be searched for “good” truncated differential properties suitable for an attack.