Paper 2014/855

Relating Undisturbed Bits to Other Properties of Substitution Boxes

Rusydi H. Makarim and Cihangir Tezcan


Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability 1 for an S-Box. The existence of undisturbed bits was found in the S-Box of PRESENT and its inverse. A 13-round improbable differential attack on PRESENT was provided by Tezcan and without using the undisturbed bits in the S-Box an attack of this type can only reach 7 rounds. Although the observation and the cryptanalytic application of undisturbed bits are given, their relation with other properties of an S-Box remain unknown. This paper presents some results on mathematical properties of S-Boxes having undisturbed bits. We show that an S-Box has undisturbed bits if any of its coordinate functions has a nontrivial linear structure. The relation of undisturbed bits with other cryptanalytic tools such as difference distribution table (DDT) and linear approximation table (LAT) are also given. We show that autocorrelation table is proven to be a more useful tool, compared to DDT, to obtain all nonzero input differences that yield undisturbed bits. Autocorrelation table can then be viewed as a counterpart of DDT for truncated differential cryptanalysis. Given an nxm balanced S-Box, we state that the S-Box has undisturbed bits whenever the degree of any of its coordinate function is quadratic.

Available format(s)
Publication info
Published elsewhere. Spriver-Verlag Proceedings, Third International Workshop on Lightweight Cryptography for Security & Privacy (LightSec 2014)
block ciphersubstitution boxundisturbed bitstruncated differential
Contact author(s)
rusydi hasan @ gmail com
2014-10-22: received
Short URL
Creative Commons Attribution


      author = {Rusydi H.  Makarim and Cihangir Tezcan},
      title = {Relating Undisturbed Bits to Other Properties of Substitution Boxes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/855},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.