Section: New Results

Solving Systems in Finite Fields, Applications in Cryptology and Algebraic Number Theory.

Structural Cryptanalysis of McEliece Schemes with Compact Key.

A very popular trend in code-based cryptography is to decrease the public-key size by focusing on subclasses of alternant/Goppa codes which admit a very compact public matrix, typically quasi-cyclic (QC), quasi-dyadic (QD), or quasi-monoidic (QM) matrices. We show in [11] that the very same reason which allows to construct a compact public-key makes the key-recovery problem intrinsically much easier. The gain on the public-key size induces an important security drop, which is as large as the compression factor $p$ on the public-key. The fundamental remark is that from the $k\times n$ public generator matrix of a compact McEliece, one can construct a $k/p\times n/p$ generator matrix which is – from an attacker point of view – as good as the initial public-key. We call this new smaller code the folded code. Any key-recovery attack can be deployed equivalently on this smaller generator matrix. To mount the key-recovery in practice, we also improve the algebraic technique of Faugère, Otmani, Perret and Tillich (FOPT). In particular, we introduce new algebraic equations allowing to include codes defined over any prime field in the scope of our attack. We describe a so-called “structural elimination” which is a new algebraic manipulation which simplifies the key-recovery system. As a proof of concept, we report successful attacks on many cryptographic parameters available in the literature. All the parameters of CFS-signatures based on QD/QM codes that have been proposed can be broken by this approach. In most cases, our attack takes few seconds (the hardest case requires less than 2 hours). In the encryption case, the algebraic systems are harder to solve in practice. Still, our attack succeeds against several cryptographic challenges proposed for QD and QM encryption schemes. We mention that some parameters that have been proposed in the literature remain out of reach of the methods given here. weakness arising from Goppa codes with QM or QD symmetries. Indeed, the security of such schemes is not relying on the bigger compact public matrix but on the small folded code which can be efficiently broken in practice with an algebraic attack for a large set of parameters

Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups

The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show in [10], that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has no symmetry anymore. This result is obtained thanks to an operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold: the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (resp. Goppa) code provides the dual of an alternant (resp. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. Dür). This enables not only to present a unified view but also to generalize the construction of QC,QD and even quasi-monoidic (QM) Goppa codes. Lastly, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.

Factoring $N=p^r{q}^s$ for Large $r$ and $s$

D. Boneh, G. Durfee, and N. Howgrave-Graham showed at Crypto 99 that moduli of the form $N=p^{r}q$ can be factored in polynomial time when $r\simeq logp$. Their algorithm is based on Coppersmith’s technique for finding small roots of polynomial equations. In [27], we show that $N=p^r{q}^s$ can also be factored in polynomial time when $r$ or $s$ is at least ${(logp)}^3$; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli equal to a product of $k$ factors of prime powers $p_i^{r_i}$ ; we show that a non-trivial factor of $N$ can be extracted in polynomial-time if one of the exponents $r_i$ is large enough.

On the p-adic stability of the FGLM algorithm

Nowadays, many strategies to solve polynomial systems use the computation of a Gröbner basis for the graded reverse lexicographical ordering, followed by a change of ordering algorithm to obtain a Gröbner basis for the lexicographical ordering. The change of ordering algorithm is crucial for these strategies. In [33], we study the $p$-adic stability of the main change of ordering algorithm, FGLM. We show that FGLM is stable and give explicit upper bound on the loss of precision occuring in its execution. The variant of FGLM designed to pass from the grevlex ordering to a Gröbner basis in shape position is also stable. Our study relies on the application of Smith Normal Form computations for linear algebra.

Binary Permutation Polynomial Inversion and Application to Obfuscation Techniques

Whether it is for constant obfusation, opaque predicate or equation obfuscation, Mixed Boolean-Arithmetic (MBA) expressions are a powerful tool providing concrete ways to achieve obfuscation. Recent results introduced ways to mix such a tool with permutation polynomials modulo $2^n$ in order to make the obfuscation technique more resilient to SMT solvers. However, because of limitations regarding the inversion of such permutations, the set of permutation polynomials presented suffers some restrictions. Those restrictions allow several methods of arithmetic simplification, decreasing the effectiveness of the technique at hiding information. In [19], we present general methods for permutation polynomials inversion. These methods allow us to remove some of the restrictions presented in the literature, making simplification attacks less effective. We discuss complexity and limits of these methods, and conclude that not only current simplification attacks may not be as effective as we thought, but they are still many uses of polynomial permutations in obfuscation that are yet to be explored.

Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme

A common countermeasure against side-channel attacks consists in using the masking scheme originally introduced by Ishai, Sahai and Wagner (ISW) at Crypto 2003, and further generalized by Rivain and Prouff at CHES 2010. The countermeasure is provably secure in the probing model, and it was showed by Duc, Dziembowski and Faust at Eurocrypt 2014 that the proof can be extended to the more realistic noisy leakage model. However the extension only applies if the leakage noise increases at least linearly with the masking order n, which is not necessarily possible in practice. In [20], we investigate the security of an implementation when the previous condition is not satisfied, for example when the masking order n increases for a constant noise. We exhibit two (template) horizontal side-channel attacks against the Rivain-Prouff's secure multiplication scheme and we analyze their efficiency thanks to several simulations and experiments. Eventually, we describe a variant of Rivain-Prouff's multiplication that is still provably secure in the original ISW model, and also heuristically secure against our new attacks.

Faster Evaluation of SBoxes via Common Shares

In [28], we describe a new technique for improving the efficiency of the masking countermeasure against side-channel attacks. Our technique is based on using common shares between secret variables, in order to reduce the number of finite field multiplications. Our algorithms are proven secure in the ISW probing model with $n>t+1$ shares against $t$ probes. For AES, we get an equivalent of $2.8$ non-linear multiplications for every SBox evaluation, instead of 4 in the Rivain-Prouff countermeasure. We obtain similar improvements for other block-ciphers. Our technique is easy to implement and performs relatively well in practice, with roughly a $20\%$ speed-up compared to existing algorithms.

Information Extraction in the Presence of Masking with Kernel Discriminant Analysis

To reduce the memory and timing complexity of the Side-Channel Attacks (SCA), dimensionality reduction techniques are usually applied to the measurements. They aim to detect the so-called Points of Interest (PoIs), which are time samples which (jointly) depend on some sensitive information (e.g. secret key sub-parts), and exploit them to extract information. The extraction is done through the use of functions which combine the measurement time samples. Examples of combining functions are the linear combinations provided by the Principal Component Analysis or the Linear Discriminant Analysis. When a masking countermeasure is properly implemented to thwart SCAs, the selection of PoIs is known to be a hard task: almost all existing methods have a combinatorial complexity explosion, since they require an exhaustive search among all possible d-tuples of points. In this paper we propose an efficient method for informative feature extraction in presence of masking countermeasure. This method, called Kernel Discriminant Analysis, consists in completing the Linear Discriminant Analysis with a so-called kernel trick, in order to efficiently perform it over the set of all possible d-tuples of points without growing in complexity with d. We identify and analyse the issues related to the application of such a method. Afterwards, its performances are compared to those of the Projection Pursuit (PP) tool for PoI selection up to a 4th-order context. Experiments show that the Kernel Discriminant Analysis remains effective and efficient for high-order attacks, leading to a valuable alternative to the PP in constrained contexts where the increase of the order d does not imply a growth of the profiling datasets.

Polynomial Evaluation and Side Channel Analysis

Side Channel Analysis (SCA) is a class of attacks that exploits leakage of information from a cryptographic implementation during execution. To thwart it, masking is a common countermeasure. The principle is to randomly split every sensitive intermediate variable occurring in the computation into several shares and the number of shares, called the masking order, plays the role of a security parameter. The main issue while applying masking to protect a block cipher implementation is to specify an efficient scheme to secure the S-box computations. Several masking schemes, applicable for arbitrary orders, have been recently introduced. Most of them follow a similar approach originally introduced in the paper of Carlet et al published at FSE 2012; the S-box to protect is viewed as a polynomial and strategies are investigated which minimize the number of field multiplications which are not squarings. The paper [32] aims at presenting all these works in a comprehensive way. The methods are discussed, their differences and similarities are identified and the remaining open problems are listed.

Redefining the Transparency Order

In [7], we consider the multi-bit Differential Power Analysis (DPA) in the Hamming weight model. In this regard, we revisit the definition of Transparency Order (TO) from the work of Prouff (FSE 2005) and find that the definition has certain limitations. Although this work has been quite well referred in the literature, surprisingly, these limitations remained unexplored for almost a decade. We analyse the definition from scratch, modify it and finally provide a definition with better insight that can theoretically capture DPA in Hamming weight model for hardware implementation with precharge logic. At the end, we confront the notion of (revised) transparency order with attack simulations in order to study to what extent the low transparency order of an s-box impacts the efficiency of a side channel attack against its processing.