Ayoub Otmani

Magali Bardet, Manon Bertin, Alain Couvreur et al.

DAGS scheme is a key encapsulation mechanism (KEM) based on quasi-dyadic alternant codes that was submitted to NIST standardization process for a quantum resistant public key algorithm. Recently an algebraic attack was devised by Barelli and Couvreur (Asiacrypt 2018) that efficiently recovers the private key. It shows that DAGS can be totally cryptanalysed by solving a system of bilinear polynomial equations. However, some sets of DAGS parameters were not broken in practice. In this paper we improve the algebraic attack by showing that the original approach was not optimal in terms of the ratio of the number of equations to the number of variables. Contrary to the common belief that reducing at any cost the number of variables in a polynomial system is always beneficial, we actually observed that, provided that the ratio is increased and up to a threshold, the solving can be heavily improved by adding variables to the polynomial system. This enables us to recover the private keys in a few seconds. Furthermore, our experimentations also show that the maximum degree reached during the computation of the Gröbner basis is an important parameter that explains the efficiency of the attack. Finally, the authors of DAGS updated the parameters to take into account the algebraic cryptanalysis of Barelli and Couvreur. In the present article, we propose a hybrid approach that performs an exhaustive search on some variables and computes a Gröbner basis on the polynomial system involving the remaining variables. We then show that the updated set of parameters corresponding to 128-bit security can be broken with 2^83 operations.

Younes Hatri, Ayoub Otmani, Kenza Guenda

Authenticated Key Exchange (AKE) protocols represent an important cryptographic mechanism that enables several parties to communicate securely over an open network. Elashry, Mu and Susilo proposed in 2015 an Identity Based Authenticated Key Exchange (IBAKE) protocol where different parties establish secure communication by means of their public identities. The authors also introduced a new security notion for IBAKE protocols called resiliency, that is, if a shared secret between a group of parties is compromised or leaked, they can generate another completely new shared secret without the need to set up a new key exchange session. They then proved that their IBAKE protocol satisfies this security notion. We analyze the security of their protocol and prove that it has a major security flaw which renders it insecure against an impersonation attack. We also disprove the resiliency property of their scheme by proposing an attack where an adversary can compute any share secret key if just one secret bit is leaked.

Philippe Gaborit, Ayoub Otmani, Hervé Talé Kalachi

Encryption schemes based on the rank metric lead to small public key sizes of order of few thousands bytes which represents a very attractive feature compared to Hamming metric-based encryption schemes where public key sizes are of order of hundreds of thousands bytes even with additional structures like the cyclicity. The main tool for building public key encryption schemes in rank metric is the McEliece encryption setting used with the family of Gabidulin codes. Since the original scheme proposed in 1991 by Gabidulin, Paramonov and Tretjakov, many systems have been proposed based on different masking techniques for Gabidulin codes. Nevertheless, over the years all these systems were attacked essentially by the use of an attack proposed by Overbeck. In 2005 Faure and Loidreau designed a rank-metric encryption scheme which was not in the McEliece setting. The scheme is very efficient, with small public keys of size a few kiloBytes and with security closely related to the linearized polynomial reconstruction problem which corresponds to the decoding problem of Gabidulin codes. The structure of the scheme differs considerably from the classical McEliece setting and until our work, the scheme had never been attacked. We show in this article that this scheme like other schemes based on Gabidulin codes, is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck's attack on an appropriate public code. As an example we break concrete proposed $80$ bits security parameters in a few seconds.

Ayoub Otmani, Hervé Talé Kalachi, Sélestin Ndjeya

We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck's structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way correct less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometric transformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existing techniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed.

Alain Couvreur, Ayoub Otmani, Jean-Pierre Tillich et al.

The BBCRS scheme is a variant of the McEliece public-key encryption scheme where the hiding phase is performed by taking the inverse of a matrix which is of the form $\mathbf{T} +\mathbf{R}$ where $\mathbf{T}$ is a sparse matrix with average row/column weight equal to a very small quantity $m$, usually $m < 2$, and $\mathbf{R}$ is a matrix of small rank $z\geqslant 1$. The rationale of this new transformation is the reintroduction of families of codes, like generalized Reed-Solomon codes, that are famously known for representing insecure choices. We present a key-recovery attack when $z = 1$ and $m$ is chosen between $1$ and $1 + R + O( \frac{1}{\sqrt{n}} )$ where $R$ denotes the code rate. This attack has complexity $O(n^6)$ and breaks all the parameters suggested in the literature.

Alain Couvreur, Ayoub Otmani, Jean-Pierre Tillich

We present a polynomial time structural attack against the McEliece system based on Wild Goppa codes from a quadratic finite field extension. This attack uses the fact that such codes can be distinguished from random codes to compute some filtration, that is to say a family of nested subcodes which will reveal their secret algebraic description.

Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña et al.

Because of their interesting algebraic properties, several authors promote the use of generalized Reed-Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et \textit{al.} which hides the generalized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed-Solomon code.

Valérie Gauthier, Ayoub Otmani, Jean-Pierre Tillich

Baldi et \textit{al.} proposed a variant of McEliece's cryptosystem. The main idea is to replace its permutation matrix by adding to it a rank 1 matrix. The motivation for this change is twofold: it would allow the use of codes that were shown to be insecure in the original McEliece's cryptosystem, and it would reduce the key size while keeping the same security against generic decoding attacks. The authors suggest to use generalized Reed-Solomon codes instead of Goppa codes. The public code built with this method is not anymore a generalized Reed-Solomon code. On the other hand, it contains a very large secret generalized Reed-Solomon code. In this paper we present an attack that is built upon a distinguisher which is able to identify elements of this secret code. The distinguisher is constructed by considering the code generated by component-wise products of codewords of the public code (the so-called "square code"). By using square-code dimension considerations, the initial generalized Reed-Solomon code can be recovered which permits to decode any ciphertext. A similar technique has already been successful for mounting an attack against a homomorphic encryption scheme suggested by Bogdanoc et \textit{al.}. This work can be viewed as another illustration of how a distinguisher of Reed-Solomon codes can be used to devise an attack on cryptosystems based on them.

Valérie Gauthier, Ayoub Otmani, Jean-Pierre Tillich

Bogdanov and Lee suggested a homomorphic public-key encryption scheme based on error correcting codes. The underlying public code is a modified Reed-Solomon code obtained from inserting a zero submatrix in the Vandermonde generating matrix defining it. The columns that define this submatrix are kept secret and form a set $L$. We give here a distinguisher that detects if one or several columns belong to $L$ or not. This distinguisher is obtained by considering the code generated by component-wise products of codewords of the public code (the so called "square code"). This operation is applied to punctured versions of this square code obtained by picking a subset $I$ of the whole set of columns. It turns out that the dimension of the punctured square code is directly related to the cardinality of the intersection of $I$ with $L$. This allows an attack which recovers the full set $L$ and which can then decrypt any ciphertext.