Improved Impossible Polytopic Attacks on Round-reduced DES

In Eurocrypt 2016, Tyge Tiessen introduced the d-difference which considering the differences between multiple plaintexts, and proposed the impossible polytopic attack on block cipher which effectively reducing the data complexity. In this paper, we improve the impossible polytopic attacks of round-reduced DES by some ideas like truncated differentials. Given the input 3-difference of each S-box in the third round, the number of the output 3-difference is actually smaller than the theoretical upper bound, which helps us reduce the memory complexity of the attack on 5-round DES from 2¹² bytes to 2^6.9 bytes and increase the success rate of the attack. Using the idea of truncated differentials, the time complexity of the attack on 6-round DES is reduced from 2^32.2 encryptions to 2^25.8 encryptions by selecting the output 3-differences of 6 S-boxes for key recovery. We also improve the attack on 7-round DES by using more plaintexts based on our improved attack on 6-round DES.