Application Specific Block Ciphers and a Focus on the Linear Layer
Final Report Abstract
This project dealt with the design and the analysis of symmetric cryptography. Symmetric cryptography is, due to its major advantages in efficiency compared to its public-key counterparts, used in virtual all applications that handle sensitive data. For this reason, it is of crucial importance to understand the security of the symmetric primitives used. Moreover, the rise of new application areas with new resource constrains calls for new ciphers that outperform the existing primitives in their specific application domain. In this context, the advanced encryption standard, the AES, can be seen as the swiss-army knife of block ciphers, it can be used for a lot of different applications, but it is not optimized for specific applications. This ongoing demand for new ciphers is in particular reflected in the competition that NIST started, calling for the future standards for lightweight ciphers. The results of this project helped to build a good basis for several candidates in this competition. Moreover, we gained new fundamental insights into the security requirements of ciphers. For the part concerning the design of ciphers, the aim of this project was to focus on the less understood linear part of the round function of block ciphers. This part, which simply corresponds to the multiplication with a binary matrix has to be chosen carefully to achieve the security criteria on the one hand and be efficiently implementable on the other hand. One interesting question in this context can be phrased informally as follows: How many XORs operations are needed to implement the multiplication with a fixed primitive element in a finite field of given order. Here, we do not care about how the field is represented nor about the exact element multiplied with. This freedom nicely left a lot of room for possible improvements and interesting theoretical considerations. Interesting and surprisingly, for the linear layer, the largest improvement in efficiency was achieved by the technically most trivial approach: We could show that simply applying known algorithms, to heuristically compute efficient implementations of binary matrices, outperforms many rather sophisticated improvements. The main reasons for this was that many papers focused on local rather than global optimizations within the linear layer. When it comes to new fundamental insights into the security of ciphers, we like to highlight the improved understanding with respect to invariant attacks. Here we were able to construct new ideas that allowed to break several block ciphers. In a second phase, we established new criteria to avoid those attacks. Those criteria are nicely related to properties of the linear part of the round function. Putting all this together, several new ciphers have been developed with different optimization criteria in mind. The most influential one among those is probably the cipher SKINNY. This has been designed as a direct, academic, competitor for the block cipher Simon designed by the US National Security Agency (NSA). The main challenge was to be as efficient as Simon but, in sharp contrast to the NSA design, give strong security arguments on why SKINNY is a secure cipher. The success of SKINNY can best be seen by noticing that it is used in practice already (in particular in the French COVID-app) and that several NIST lightweight candidates use SKINNY as their fundamental building block.
Publications
- „Analyzing Permutations for AES-like Ciphers: Understanding ShiftRows,“ in CT-RSA, 2015
C. Beierle, P. Jovancovic, M. M. Lauridsen, G. Leander and C. Rechberger
(See online at https://doi.org/10.1007/978-3-319-16715-2_3) - „Observations on the SIMON Block Cipher Family,“ in CRYPTO, 2015
S. Kölbl, G. Leander and T. Tiessen
(See online at https://doi.org/10.1007/978-3-662-47989-6_8) - „Lightweight Multiplication in GF(2^n) with Applications to MDS Matrices,“ in CRYPTO, 2016
C. Beierle, T. Kranz and G. Leander
(See online at https://doi.org/10.1007/978-3-662-53018-4_23) - „Nonlinear Invariant Attack - Practical Attack on Full SCREAM, iSCREAM, and Midori64,“ in ASIACRYPT, 2016
Y. Todo, G. Leander and Y. Sasaki
(See online at https://doi.org/10.1007/978-3-662-53890-6_1) - „Strong 8-bit Sboxes with Efficient Masking in Hardware,“ in CHES, 2016
E. Boss, V. Grosso, T. Güneysu, G. Leander, A. Moradi and T. Schneider
(See online at https://doi.org/10.1007/978-3-662-53140-2_9) - „The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS,“ in CRYPTO, 2016
C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich and S. M. Sim
(See online at https://doi.org/10.1007/978-3-662-53008-5_5) - Shorter Linear Straight-Line Programs for MDS Matrices,“ in IACR Transaction of Symmetric Cryptography, 2017
T. Kranz, G. Leander, K. Stoffelen and F. Wiemer
(See online at https://doi.org/10.13154/tosc.v2017.i4.188-211) - „Proving Resistance Against Invariant Attacks: How to Choose the Round Constants,“ in CRYPTO, 2017
C. Beierle, A. Canteaut, G. Leander and Y. Rotella
(See online at https://doi.org/10.1007/978-3-319-63715-0_22) - (2018). “ShiftRows Alternatives for AES-like Ciphers and Optimal Cell Permutations for Midori and Skinny”. IACR Transactions on Symmetric Cryptology, 2018
Alfarano, G. N., Beierle, C., Isobe, T., Kölbl, S., & Leander, G.
(See online at https://doi.org/10.13154/tosc.v2018.i2.20-47)
