On the provable security of block ciphers from their components

Speaker:  Massimilano Sala - Universita' di Trento
  Tuesday, May 28, 2013 at 2:30 PM 2:15 p.m. rinfresco; 2:30 p.m. inizio seminario
Block ciphers form a class of ciphers which are used worldwide to protect confidential information. The most famous block ciphers are the 3DES, i.e. the Triple Data Encryption Standard which is used mainly for e-payments or other electronic money exchange, and the AES, i.e. the Advanced Encryption Standard which is used for most of the remaining cases. 
We are particularly interested in ciphers which have a structure similar to that of the AES, which we call "translation-based" (tb), since the round keys act like translations. The main components of a tb ciphers are the mixing layer and the S-Boxes. A mixing-layer is a linear map acting on the whole message space, while an SBox is a highly nonlinear permutation acting on a small (sub)field. Due the linearity of the mixing-layer, the cryptographic robustness of a tb cipher lies mostly in the nonlinearity of its SBoxes. 
In this talk we will present the following results:

1) the permutation group (acting on the whole message space) generated by the round permutations of a tb cipher can be  proved to be large (a small group opens the door to efficient attacks).
   To be more precise, it is primitive under natural constraints on the Sboxes and, imposing stronger nonlinearity hypotheses, it can be proved to be the alternating group.
    The primitivity is obtained from standard methods in (finite) group theory, while the proof for the alternating group requires deeper results such the O'Nan Scott Theorem on the classification of (maximal) primitive groups. 
    These results are jointly with F. Dalla Volta and A. Caranti [1,2,3], for the original binary case, and jointly with the same coauthors plus R. Aragona, for the extension to any positive characteristic.

2) we have classified all 4-bit SBoxes w.r.t. to some nonlinearity properties that we propose and which are linked to the above-mentioned results. This analysis was funded by Telsy SPA, http://www.telsy.com, a company working in communications security mainly for government applications.
    These results [4] are jointly with C. Fontanari, V. Pulice and A. Rimoldi.

[1]  http://arxiv.org/abs/math/0510166, Abelian regular subgroups of the affine group and radical rings
[2] http://arxiv.org/abs/0806.4135, On some block ciphers and imprimitive groups
[3] http://arxiv.org/abs/0812.1629, An application of the O'Nan-Scott theorem to the group generated by the round functions of an AES-like cipher
[4] http://arxiv.org/abs/1102.3882, On weakly APN functions and 4-bit S-Boxes

Ca' Vignal 3 - Piramide, Floor 0, Hall Verde

Contact person
Francesca Mantese

Publication date
May 14, 2013