First Results on Reverse-Engineering

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.

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.

Work in Progress