30.10.2023
Propagation of Subspaces in Primitives with Monomial Sboxes
Abstract
Motivated by progress in the field of zero-knowledge proofs, so-called Arithmetization-Oriented (AO) symmetric primitives have started to appear in the literature, such as MiMC, Poseidon or Rescue. Due to the design constraints implied by this setting, these algorithms are defined using simple operations over large (possibly prime) fields. In particular, many rely on simple low-degree monomials for their non-linear layers. In this work, we show that the structure of the material injected in each round (be it subkeys in a block cipher or round constants in a public permutation) could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. Such chains of one-dimensional subspaces always exist over 2 rounds, and they can be extended to an arbitrary number of rounds provided that the round-constants are well chosen. As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet. Well-known security arguments, in particular based on the wide trail strategy, have been reused in the AO setting by many designers. Unfortunately, our results show their limits. To illustrate this, we present two new primitives (a tweakable block cipher and a permutation-based hash function) that are built using state-of-the-art security arguments, but which are actually deeply flawed.
Bio
Anne Canteaut is a Researcher in the COSMIQ project-team at INRIA, and an Honorary Doctor at the University of Bergen (Norway). Her main research interest is symmetric cryptography.
(Source & further details on: https://www.rocq.inria.fr/secret/Anne.Canteaut/English/index.html)
Photo copyright: © Inria / Photo C. Morel
Motivated by progress in the field of zero-knowledge proofs, so-called Arithmetization-Oriented (AO) symmetric primitives have started to appear in the literature, such as MiMC, Poseidon or Rescue. Due to the design constraints implied by this setting, these algorithms are defined using simple operations over large (possibly prime) fields. In particular, many rely on simple low-degree monomials for their non-linear layers. In this work, we show that the structure of the material injected in each round (be it subkeys in a block cipher or round constants in a public permutation) could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. Such chains of one-dimensional subspaces always exist over 2 rounds, and they can be extended to an arbitrary number of rounds provided that the round-constants are well chosen. As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet. Well-known security arguments, in particular based on the wide trail strategy, have been reused in the AO setting by many designers. Unfortunately, our results show their limits. To illustrate this, we present two new primitives (a tweakable block cipher and a permutation-based hash function) that are built using state-of-the-art security arguments, but which are actually deeply flawed.
Bio
Anne Canteaut is a Researcher in the COSMIQ project-team at INRIA, and an Honorary Doctor at the University of Bergen (Norway). Her main research interest is symmetric cryptography.
(Source & further details on: https://www.rocq.inria.fr/secret/Anne.Canteaut/English/index.html)
Photo copyright: © Inria / Photo C. Morel