Markov ciphers and differential cryptanalysis (Q4037447)

[For the entire collection see Zbl 0756.00008.] The paper considers the security of iterated block ciphers against the differential cryptanalysis developed by Biham and Shamir. Especially, it is investigated if the so-called Proposed Encryption Standard (PES), introduced by the authors in 1991, is resistant to differential cryptanalysis. The mentioned cryptanalysis is a chosen-plaintext attack on secret-key ciphers that are based on iterating a cryptographically weak function several times. The iterations are called rounds. Differential cryptanalysis analyzes the effect of the difference of a pair of plaintexts on the difference of succeeding round outputs in a iterated cipher. The authors use the concept of Markov ciphers to describe the probability of success of differential cryptanalysis on an \(r\)-round cipher depending on the existence of \((r-1)\)-round differentials with high probability. (An \(i\)-round differential is a couple \((\alpha,\beta)\) such that a pair of plaintexts with difference \(\alpha\) can result in a pair of \(i\)-th round outputs that have difference \(\beta\).) It is proved that PES including also its mini-versions is immune to differential cryptanalysis after sufficiently many \((\geq 7)\) rounds. As a result of these investigations a minor modification of PES is proposed. This modified cipher called Improved PES (IPES) is shown to be highly resistant against differential cryptanalysis.