Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Reconstructing an S-box from its Difference Distribution Table

Dunkelman, Orr and Huang, Senyang LU (2019) In IACR Transactions on Symmetric Cryptology 2019(2).
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 attacker 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 in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis).
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 straightforward... (More)
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 attacker 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 in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis).
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 straightforward guess-and-determine (GD) algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the GD algorithm. We tested our new algorithm on random S-boxes of different sizes, and for random 14-bit bijective S-boxes, our results outperform the GD attack by several orders of magnitude. (Less)
Please use this url to cite or link to this publication:
author
and
publishing date
type
Contribution to journal
publication status
published
subject
in
IACR Transactions on Symmetric Cryptology
volume
2019
issue
2
publisher
Ruhr-Universität Bochum
external identifiers
  • scopus:85069156653
ISSN
2519-173X
DOI
10.13154/tosc.v2019.i2.193-217
language
English
LU publication?
no
id
f33c9a6e-eb69-4543-adc1-e48d516d4ff4
date added to LUP
2021-12-03 13:07:42
date last changed
2022-04-27 06:16:50
@article{f33c9a6e-eb69-4543-adc1-e48d516d4ff4,
  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 attacker 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 in some analysis of S-boxes with unknown design criteria (e.g., in Biryukov and Perrin’s analysis).<br/>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 straightforward guess-and-determine (GD) algorithm proposed by Boura et al. Moreover, we show how to exploit this relation, and embed the knowledge obtained from it in the GD algorithm. We tested our new algorithm on random S-boxes of different sizes, and for random 14-bit bijective S-boxes, our results outperform the GD attack by several orders of magnitude.}},
  author       = {{Dunkelman, Orr and Huang, Senyang}},
  issn         = {{2519-173X}},
  language     = {{eng}},
  number       = {{2}},
  publisher    = {{Ruhr-Universität Bochum}},
  series       = {{IACR Transactions on Symmetric Cryptology}},
  title        = {{Reconstructing an S-box from its Difference Distribution Table}},
  url          = {{http://dx.doi.org/10.13154/tosc.v2019.i2.193-217}},
  doi          = {{10.13154/tosc.v2019.i2.193-217}},
  volume       = {{2019}},
  year         = {{2019}},
}