Research
When I learned about DES and its modes of use in 1988, I was struck by their ugliness. I figured it should be possible to come up with nicer designs. This has been the main goal of my research ever since: the design of symmetric cryptographic primitives and modes that are nice and original. Naturally, this involves cryptanalysis and the study of propagation properties where I try to improve on the descriptions given in cryptographic literature.
PhD
During my PhD (1988-1995) I mostly worked alone and proposed several bit-oriented lightweight designs: modules that can be used both as a stream cipher and a hash function, but also block ciphers. I had a great time during my PhD and it is the basis of all my work on crypto I did later, up to this day. It contained a lot of innovation, as I illustrate here below.
Some of my design innovations:
- Wide-trail strategy After the discovery of differential and linear cryptanalysis in the early nineties, there was quasi consensus in the cryptographic community that the answer for resistance against these attacks was building block ciphers with wider S-boxes. I disagreed and put forward the idea that a better answer was in building ciphers where all multiple-round trails have many active S-boxes. The way to do this: introduce a dedicated mixing layer θ and complement that with a suitable bit shuffle π. For the non-linear layer I restricted myself to a very lightweight shift-invariant non-linear mapping that I called χ.
- Stream/hash modules I introduced these cryptographic primitives after noticing that absorbing a message in hashing or MAC computation is similar to absorbing a diversifier (aka IV) in a stream cipher and that generating a digest or tag is similar to generating a key stream. This was also supported by my paper on resynchronization attacks at Eurocrypt 1993, showing that differential (and linear) cryptanalysis also apply to stream ciphers. Stream/hash modules such as Subterranean can be seen as a precursor of sponge functions.
- Bitslice ciphers By having a lot of symmetry in a round function, it can become very efficient in software using only bitwise Boolean and cyclic shift instructions. This is what I did with 3-Way and later also with BaseKing, the block cipher I'm most proud of. I heard Craig Costello once say about the FourQ elliptic curve that it is a miracle a curve with all those properties even exists. This is exactly what I thought of BaseKing and still do today. Anyway, I presented 3-Way at the first Fast Software Encryption Workshop (FSE) in Cambridge in 1993, four years later Eli Biham presented his bit-sliced implementations of DES at FSE 1997 in Haifa and in 2009 the circle closed with Emilia Kasper and Peter Schwabe that presented at CHES 2009 in Lausanne how they applied this technique for having AES software secure against cache miss attacks.
Some innovative mappings for use in round functions:
- The non-linear mapping χ This is the simplest non-linear shift-invariant mapping that is invertible.
I first used it in Cellhash and have been using it up to this day, including Keccak team designs Keccak and Xoodoo. I cannot think of another non-linear mapping that comes close. The only disadvantage is that for even length it is not invertible.
- Mixing layers based on error-correcting codes In the block ciphers 3-Way and BaseKing I used a mixing layer inspired by error-correcting codes. Much later, I found out it is equivalent to the extended binary Golay code.
- Sparse mixing layer with a dense inverse The mixing layer θ in Cellhash, Subterranean and StepRightUp (the predecessor of Panama) takes 2 bitwise additions per statebit and their inverses require many bitwise additions. We used mixing layers with the same feature in Keccak and Xoodoo.
Innovative concepts and formalism to describe and measure propagation properties:
- Correlation matrices Linear cryptanalysis of iterative ciphers is most naturally described by seeing the composition of functions as the product of their correlation matrices. This allows defining linear trails, the counterpart in linear cryptanalysis of differential trails.
- Branch number When comparing mixing layers for use in the round function of block ciphers, I was in need of a criterion for its diffusion power. I came up with the differential and linear branch numbers that seemed to be the most natural ones and by now they have become household names.
It was also the start of my strained relationship with some theories:
- Complexity theory This theory (as in P versus NP) is very popular in certain branches of cryptography. When comparing the security proof for the Even-Mansour construction with cryptanalysis of reduced-round versions of IDEA I noticed that for generic constructions it is sufficient to offer asymptotic security while for actual block ciphers any attack more efficient than exhaustive key search is considered a break. I found this unbalanced and expressed that in my (rump session) paper Limitations of Even-Mansour at Asiacrypt 1991. Fortunately, the situation has improved in symmetric crypto: most bounds in cryptographic claims and theorems are now concrete rather than asymptotic.
- Markov Cipher theory The block cipher IDEA came with this theory that looked very attractive. Basically it considers block cipher behaviour averaged over all keys and then assumes that the behaviour for particular keys is close to that average. In reality this is often not the case as I showed in my paper Weak keys of IDEA at CRYPTO 1994. Later, Vincent and I would find that also Rijndael is not well modeled as a Markov cipher.
Collaboration with Vincent Rijmen
In 1993 I first collaborated with Vincent Rijmen, in some consultancy work and this was a very positive experience. Two years later I defended my PhD thesis and due to some administrative complication my contract at the university ended one month after that. During this last month, I was looking into the block cipher Blowfish in the context of some cryptanalysis contest. Then I had a very promising idea to build a round function, very different from the constructions I had done before. After starting at my next job, that did not include cryptography, I continued working on this idea after working hours. I soon realized that this would go must faster with some help and contacted Vincent to collaborate on this. This was probably one of the best decisions of my research life, as it led via some intermediate stages to our AES submission Rijndael. Our cipher became the NIST standard AES in 2001, as documented in our Rijndael book.
Rijndael has become quite a success with massive real-world impact, see e.g. the NIST report The Economic Impacts of the Advanced Encryption Standard, 1996-2017. It has also inspired numerous other cryptographic designs. Despite its success, I am no longer enthousiastic about Rijndael as symmetric cryptography based on (bitslice) permutations is much nicer and more efficient than block-cipher-based crypto. I am now convinced that in, say, thirty years we will look back on block ciphers as we do now on rotor machines.
Still, I remain very proud of the research that Vincent and I did together. We have published the results of our collaboration before Rijndael became AES in our book. After its publication, Vincent and I continued our collaboration, investigating the propagation properties of Rijndael and proposed some MAC constructions. I refer to My papers page for our book and the most interesting papers we wrote together.
Keccak team
In 1998, our company Proton World hired a number of very talented people, including Gilles Van Assche and Michael Peeters. They were interested in doing research on crypto and in 1999 we started collaborating on block ciphers leading to a paper on masking of bitslice ciphers and our block cipher Noekeon (in collaboration with Vincent). In 2006 Guido Bertoni joined our effort and we started working on hash functions.
This was the start of the Keccak team, the most innovative design team in the history of symmetric crypto. Our research led to the sponge construction and the SHA-3 contest submission Keccak that was announced winner by NIST in 2012. Later, our colleague Ronny Van Keer joined us and we shifted our focus to authenticated encryption with instances Keyak and Ketje.
Since a few years Seth Hoffert, based in Lincoln, Nebraska, joined the Keccak team.
In this new constellation, we have developed a parallelizable permutation-based construction called farfalle, that can be used for all keyed symmetric cryptographic functions.
Later we designed a permutation that is ideally suited for this construction: Xoodoo resulting in the function Xoofff.
In parallel, we have started a long-term collaboration with Bart Mennink (formerly COSIC, now Radboud) on proving bounds for the generic security of our constructions.
ESCADA and SCALAR
Since October 2018, we are doing research in the context of my ESCADA project with 6 PhD students and several postdocs. ESCADA is about reducing the gap between the secure and the lightweight in symmetric crypto and focuses on lightweight round functions of algebraic degree 2. Since August 2019, together with Bart Mennink we also have an NWO-funded project called SCALAR with 2 PhD students and 1 postdoc. SCALAR is about building symmetric cryptography that makes use of available multipliers. Two industry-funded projects complement these research directions with lightweight and low-latency symmetric cryptography, involving two more PhD students and a part-time postdoc.
(top) |
Last modified: March 22, 2023 |