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

Abstract. S-Boxes are the key components of many cryptographic primitives and designing them to improve resilience to attacks such as linear or differential crypt-analysis 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