Paper 2015/976

On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure

Alex Biryukov and Léo Perrin

Abstract

S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential cryptanalysis is well understood. In this paper, we investigate techniques that can be used to reverse-engineer S-box design and illustrate those by studying the S-Box $F$ of the Skipjack block cipher whose design process so far remained secret. We first show that the linear properties of $F$ are far from random and propose a design criteria, along with an algorithm which generates S-Boxes very similar to that of Skipjack. Then we consider more general S-box decomposition problems and propose new methods for decomposing S-Boxes built from arithmetic operations or as a Feistel Network of up to 5 rounds. Finally, we develop an S-box generating algorithm which can fix a large number of DDT entries to the values chosen by the designer. We demonstrate this algorithm by embedding images into the visual representation of S-box's DDT.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2015
DOI
10.1007/978-3-662-47989-6_6
Keywords
S-box design criteriaSkipjacklinearityfunctional decomposition problemefficient implementation
Contact author(s)
leo perrin @ uni lu
History
2015-10-12: received
Short URL
https://ia.cr/2015/976
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/976,
      author = {Alex Biryukov and Léo Perrin},
      title = {On Reverse-Engineering S-Boxes with Hidden Design Criteria or Structure},
      howpublished = {Cryptology ePrint Archive, Paper 2015/976},
      year = {2015},
      doi = {10.1007/978-3-662-47989-6_6},
      note = {\url{https://eprint.iacr.org/2015/976}},
      url = {https://eprint.iacr.org/2015/976}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.