Integral Characteristics by Keyspace Partitioning

Abstract

In this work, we introduce a new method we call integral by keyspace partitioning to construct integral characteristics for some block ciphers by introducing new integral properties. We introduce the concepts of active with constant difference and identically active integral properties. Then, we divide the key space into equivalence classes and construct integral characteristics for each equivalence class individually by using these integral properties. We exploit the binary diffusion layer and key schedule algorithm of a block cipher to propagate these integral properties through rounds. We apply the new method to the Byte-oriented Substitution-Permutation Network (BSPN) cipher and Midori64 to show its effectiveness. We construct the first iterative integral characteristic for a block cipher to the best of our knowledge. We extend this iterative characteristic for the (M, n)-(BSPN) block cipher where each block of BSPN contains M number of n× n S-Boxes with the block and key sizes M· n. Using at most (M-12)+1 (only 106 when M= 16) chosen plaintexts, we mount key recovery attacks for the first time on BSPN and recover the key for the full round. The time complexity of the key recovery is almost independent of the number of rounds. We also use our method to construct an integral characteristic for Midori64, which can be utilized for a key recovery attack on 11-round Midori64. Our results impose a new security criteria for the design of the key schedule algorithm for some block ciphers.