Cryptology ePrint Archive: Report 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.

Category / Keywords: S-box, DDT, LAT, the sign determination problem

Original Publication (with minor differences): IACR-FSE-2020

Date: received 2 Sep 2018, last revised 28 May 2019

Contact author: xiaohuangbuct at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190528:121546 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]