Paper 2018/811

Reconstructing an S-box from its Difference Distribution Table

Orr Dunkelman and Senyang Huang

Abstract

In this paper we study the problem of recovering a secret S-box from its difference distribution table (DDT). While being an interesting theoretical problem on its own, the ability to recover the S-box from the DDT of a secret S-box can be used in cryptanalytic attacks where the adversary can obtain the DDT (e.g., in Bar-On et al.’s attack on GOST), in supporting theoretical analysis of the properties of difference distribution tables (e.g., in Boura et al.’s work), or as a tool for developing an S-box with a unique differential trapdoor. We show that using the well established relation between the DDT and the linear approximation table (LAT), one can devise an algorithm different from the guess- and-determine algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the guess-and-determine algorithm, and we discuss when our new method gives better results than the simple guess and determine attack.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in FSE 2020
Keywords
S-boxDDTLATthe sign determination problem
Contact author(s)
xiaohuangbuct @ gmail com
History
2019-05-28: revised
2018-09-06: received
See all versions
Short URL
https://ia.cr/2018/811
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/811,
      author = {Orr Dunkelman and Senyang Huang},
      title = {Reconstructing an S-box from its Difference Distribution Table},
      howpublished = {Cryptology ePrint Archive, Paper 2018/811},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/811}},
      url = {https://eprint.iacr.org/2018/811}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.