Improved integral attacks without full codebook

The integral attack, exploits the balanced property of the output in the distinguisher. Usually, adversaries append some rounds after the distinguisher, guess the corresponding key bits and check whether the target bits are balanced. Few works add rounds before the distinguisher to make the key recovery attack. In the first full-round attack on MISTY1, Todo adds one FL layer (key-dependent linear function) before the distinguisher. In this study, the authors extend his method and give a general method, which they can use to extend some rounds (non-linear) before the distinguisher to attack more rounds with data complexity smaller than the whole space and little extra time consumption. The basic idea is that for different subkeys guessed in the forward rounds, they set different constant values for the input of the distinguisher. Finally, the selected data space is not full. For substitution permutation network (SPN) (Feistel with SPN round function) structures with 4 bit S-box and bit permutation, they estimate the data complexity when adding one round before the distinguishers for all 4 bit S-boxes. Using the method, they improve the integral attacks on PRESENT, RECTANGLE, TWINE and LBlock, and their results could cover one more round.