Cosmiq Homepage | Léo Perrin's Homepage | S-box Reverse-Engineering

First Results on Reverse-Engineering

Table of Contents

1 Context

Some of my main results in symmetric cryptanalysis deal with S-Box reverse-engineering. S-Boxes are small non-linear functions operating typically on 4 or 8 bits that are usually specified via their lookup tables. Some designers (read: the American and Russian secret services) do not explain the rationale behind the algorithms they have standardizes by their respective countries. This obviously raises the following questions:

  1. How were the S-Boxes used chosen?
  2. What kind of structures do they contain?

A significant part of my PhD work has been devoted to the design of techniques capable of answering these questions. The main results I established with my then colleagues Alex Biryukov and Aleksei Udovenko are the following ones.

2 On Skipjack

The block cipher Skipjack was designed by the NSA in the late 1980's/early 1990's. It was supposed to be a part of a critical failure the Clipper chip. We proved that its F-Table, an 8-bit permutation, was engineered using a non-trivial approach which improved its linear properties. While we found an algorithm capable of generating S-Boxes with properties very similar to those of the F-table, the details of the design process of this structure remain unknown. The paper presenting these results (among others) was accepted at CRYPTO'15 (see below). We also put it on eprint.

I did try to ask NSA cryptographers at cryptography conferences but they (quite plausibly) claimed to be too young to know.

3 On the Russian Standards

Work in Progress


Last Update (by me): 19/02/2020