### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2018/811

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.