Research

I co-designed the block cipher SPARX, the first ARX-based block cipher for which we can formally bound the probabilities of the best differential and linear trails. I came up with the long trail strategy, i.e. the technique which allows SPARX to have this property.

The corresponding paper [1] was accepted at ASIACRYPT'16. It has its own page on the wiki of the cryptography group of the University of Luxembourg.

My then colleagues Alex Biryukov and Aleksei Udovenko and myself pioneered the field of S-Box reverse-engineering. S-Boxes are small non-linear functions that are usually specified via their lookup tables. They play a crucial role in security arguments. In fact, until we designed SPARX, the only known way to prove that a cipher was safe from single trails differential and linear attack hinged on the properties of the differential/linear S-Box (it corresponds to the wide trail strategy, famously used by the AES designers).

Unfortunately, some designers (read: the American and Russian secret services) do not explain the rationale behind the algorithms they have their respective countries standardize. With my colleagues, we devised new methods for recovering the design criteria and/or the structure used to design an S-Box using only its lookup table.

Through a statistical analysis, we showed that the F-table of the NSA-designed block cipher Skipjack, an 8-bit permutation, was engineered in a way that optimised its linear properties (see [2]).

We also studied the 8-bit permutation π shared by both the latest block cipher (Kuznyechik) and hash function (Streebog) standardized in Russia. Starting from a visual representation of the "Linear Approximation Table" (LAT) of π (see Figure 1), we recovered a hidden structure in this S-Box [3]. However, while investigating the a priori unrelated S-Box of the Belarussian standard block Belt, we found another completely different decomposition of π based on a discrete logarithm [4]. None of these two decompositions is really satisfactory; we thought when we found the second one that the real structure was a third one which has the other two as mere side effects.

This intuition was correct. I describe this third structure—as well as its consequences—in this page.

Back to my homepage

1. Daniel Dinu, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, Johann Großschädl, and Alex Biryukov. Design strategies for ARX with provable bounds: Sparx and LAX. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology – ASIACRYPT 2016, Part I, volume 10031 of Lecture Notes in Computer Science, pages 484–513. Springer, Heidelberg, December 2016. link to eprint.iacr.org.
2. Alex Biryukov and Léo Perrin. On reverse-engineering S-boxes with hidden design criteria or structure. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science, pages 116–140. Springer, Heidelberg, August 2015. link to eprint.iacr.org.
3. Alex Biryukov, Léo Perrin, and Aleksei Udovenko. Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 372–402. Springer, Heidelberg, May 2016. link to eprint.iacr.org.
4. Léo Perrin and Aleksei Udovenko. Exponential S-boxes: a link between the S-boxes of BelT and Kuznyechik/Streebog. IACR Transactions on Symmetric Cryptology, 2016(2):99–124, 2017. link to tosc.iacr.org.