Séminaire ALI/SALSA

9 avril 2010

11h30 Jérome Lacan
Quelques applications de la théorie des codes dans les réseaux

Ces dernières années, plusieurs thèmes de recherche mêlant le domaine de la théorie de codes correcteurs d'erreurs et celui des réseaux de communications ont émergé. Les exemples les plus connus sont les codes à effacement (erasure code), qui permettent de compenser les pertes de paquets de données dans les réseaux, et le codage réseau (network coding), qui permet notamment d'améliorer le débit global dans certains types de réseaux. Dans cet exposé, nous rappellerons tout d'abord ces différents concepts. Pour chacun des points abordés, nous tenterons de mettre en évidence les problèmes ouverts, tant au niveau du codage que des réseaux. Nous illustrerons cette présentation avec certaines de nos contributions sur les codes à effacement (codes MDS, Reed-Muller, protection inégale...), sur le codage réseau ainsi que sur des approches multi-couches.

26 mars 2010

10h00 Eleonora Guerrini
Codes systématiques et idéaux polynomiaux

Dans cet exposé un modèle algébrique pour la caractérisation des codes correcteurs systématiques est présenté. L'intérêt pour cette famille dérive de la volonté de généraliser les codes linéaires afin de rechercher des codes qui soient optimaux du point de vue de la distance. En fait, il est possible démontrer que tout code linéaire est équivalent à un code systématique, mais il existe des codes systématiques non-linéaires à distance plus grande de tout linéaire qui partage les même paramètres n (longueur) k (dimension). A la base de cette approche, le fait que tout code systématique est en correspondance avec la base de Groebner réduite de son idéal d'annulation. Grâce à cette correspondance, nous décrivons un algorithme qui, étant donnés n,k,d entiers, fournit la caractérisations des codes systématiques avec paramètres n,k et distance au moins d. Le point central de l'algorithme est le calcul de la base de Groebner d'un certain idéal B(n,k,t) qui est invariant sous l'action d'un groupe de permutations et présente de propriétés d'inclusions dans d'autres idéaux du même type (par ex. dans B(n+1,k,t+1) et B(n+1,k+1,t)).

Avec des techniques similaires, il est possible aussi de formuler un algorithme pour le calcul de la distribution des distances d'un code systématique et une nouvelle borne pour la distance de ces codes.

11h00 Vanessa Vitse
Calcul d'indice sur courbes elliptiques définies sur des extensions de corps de petit degré et application au problème static Diffie-Hellman

En 2008 et 2009, Gaudry et Diem ont proposé une méthode de calcul d'indice pour la résolution du DLP sur des courbes définies sur des corps finis non premiers. On présentera dans cet exposé une variante de cette méthode permettant d'améliorer la complexité asymptotique du DLP sur $E(F_q^n)$ lorsque $\log q \leq c n^3$. En particulier, il devient possible avec notre approche d'obtenir rapidement des relations sur $E(F_q^5)$, ce qui n'est pas le cas avec la méthode initiale de Gaudry et Diem sur ce type de courbes.

On donnera également un exemple pratique d'application de ce calcul d'indice : on montrera comment résoudre le problème static Diffie-Hellman à l'aide d'un oracle sur courbe elliptique définie sur corps fini non premier de 130 bits plus rapidement que par les attaques classiques.

19 fevrier 2010

10h00 Mate Soos
Enhanced Handling of XOR Constraints in DPLL-based SAT Solvers and Applications to Cryptography

DPLL-based SAT solvers are highly optimised algorithms to solve systems of constraints expressed in Conjunctional Normal Form (CNF). In this paper, we improve DPLL-based SAT solvers to automatically recognise and treat XOR functions given their CNF representations. Once XOR-s have been extracted, they are pre-processed such as to remove needless functions, and binary XOR-s are treated as anti- and equivalences. Finally, the anti- and equivalent variables are replaced. Furthermore, during search, binary XOR-s are regularly searched for and treated, thus repeatedly shrinking the original problem. XOR- s are optionally also put into (potentially separate) matrixes and Gaussian elimination is executed on-the-fly on these matrixes, guiding and early- aborting the search. The combined effect of these optimisations can be a speed factor of up to 2 for stream ciphers such as Bivium.

11h00 Sylvain Duquesne
Arithmétique RNS dans GF(p^k) et application au calcul de couplages

Ces dernières années, l'utilisation des couplages en cryptographie a connu un certain succès, en particulier en permettant la réalisation de nouveaux protocoles (signatures courtes, cryptographie basée sur l'identité, ...). Nous expliquerons dans cet exposé comment l'utilisation d'une arithmétique basée sur le RNS (c'est à dire une représentation des nombres via leurs restes modulo des petits entiers) permet d'accélérer le calcul de ces couplages. Nous traiterons en particulier les cas des courbes MNT et BN très en vogue actuellement.

29 janvier 2010

11h00 Marcelo Kaihara
Modular Arithmetic in Public-key Cryptology: Algorithms and applications

Most of the public-key based cryptologic systems are based on modular arithmetic operations with a large modulus. The performance of these systems highly depends on the algorithms for computing the underlying basic arithmetic operations; specifically, the modular multiplication and the modular division. In this talk, a review of most relevant algorithms for these operations will be presented explaining the different platform-dependent (hardware/software) and application-dependent (cryptography/cryptanalysis) design considerations.

13 novembre 2009

10h00 François-Xavier Standaert
Recent Results on Side-Channel Attacks and Countermeasures

Traditionally, cryptographic algorithms provide security against an adversary who has only black box access to cryptographic devices. That is, the only thing the adversary can do is to query the cryptographic algorithm on inputs of its choice and analyze the responses, which are always computed according to the correct original secret information. However, such a model does not always correspond to the realities of physical implementations. During the last decade, significant attention has been paid to the physical security evaluation of cryptographic devices. In particular, it has been demonstrated that actual attackers may be much more powerful than what is captured by the black box model. For example, they can actually get a side-channel information, based on the device's physical computational steps. As a consequence, some kind of obfuscation is required to protect integrated circuits from these physical attacks. This is especially important for small embedded devi ces (e.g. smart card, RFIDs, sensor networks, ...) that can typically be under and adversary's control for a short period of time. This implies new theoretical concerns (how to exactly model and evaluate these physical threats) and practical ones (how to prevent them). In this talk, I will discuss different results in the area of side-channel attacks, with a particular focus on formal tools that can be used to evaluate physical security on a fair basis. Starting from an introductive view of the field, I will describe some well known attacks and countermeasures, present a framework for the analysis of side-channel key-recovery from Eurocrypt 2009 and finally discuss the connection of this framework with recent works in leakage-resilient cryptography.

11h00 Mathieu Renauld
Algebraic Side-Channel Attacks

In this talk, I will introduce algebraic side-channel attacks which are a new type of hybrid attacks, combining side-channel and classical cryptanalysis. Side-channel attacks are usually quite separated from classical attacks (linear, algebraic cryptanalysis...), as the side-channel recovery phase targets directly the key bits. Recent attacks, however, tried to combine a side-channel phase with a more computational key recovery step. One of these new hybrid attacks is the algebraic side-channel attack, presented at CHES '09. The idea is to combine an algebraic attack with side-channel information (for example, the Hamming weights of the data transiting on the bus of the device). This combination seems indeed natural: the algebraic attack basically consists in solving a block cipher as a huge system of non-linear Boolean equations, and the side-channel information can easily be translated into Boolean equations that are added to the system. The resulting enhanced system can be solved in reasonable time, provided enough side-channel information is recovered. Algebraic side-channel attacks present several interesting properties. They can exploit side-channel information from all the rounds of the block cipher (contrarily to a classic DPA which exploits only information from the first/last rounds) and thus require less power traces than a standard DPA (for example, this attack is able to break the AES block cipher with only one power trace). They can also succeed in an unknown plaintext/ciphertext context and break some masked implementations. In the end, algebraic side-channel attacks illustrate the possible tradeoff between a pure side-channel attack, which requires few calculations but a lot of measurements, and an hybrid attack, which requires less measurements and compensate with a more intensive computation phase. This type of attack also shows that the time taken by the encryption can have a big influence on the security, as more clock cycles imply more leaked information and more potential targets for the algebraic side-channel attack.

16 octobre 2009

10h00 Martin Albrecht
Plaintext Recovery Attacks against SSH

In this talk we will talk about a variety of plaintext-recovering attacks against SSH as presented at IEEE S&P 2009. We implemented a proof of concept of our attacks against OpenSSH, where we can variably recover 14 bits of plaintext from an arbitrary block of ciphertext with probability 2^{-14} and 32 bits of plaintext from an arbitrary block of ciphertext with probability 2^{18} . These attacks assume the default configuration of a 128-bit block cipher operating in CBC mode. We will explain why a combination of flaws in the basic design of SSH leads implementations such as OpenSSH to be open to our attacks, why current provable security results for SSH do not cover our attacks, and how the attacks can be prevented in practice.

11h00 Matthieu Finiasz
Bounds for the Design of Code-based Cryptosystems [ slides ]

Several alternatives to number theory-based cryptography exist. However, due to the complexity of the attacks against them, selecting secure parameters for these alternatives is often complicated. Code-based cryptosystems are somehow easier to analyze than their lattice or multivariate counterparts as the best known attacks have a more predictable behaviour. However, as time passes, the best attacks become more and more complicated and the evaluation of their cost can be a challenge. Here, we propose to study some idealized versions of these attacks and propose some lower bounds on their complexity. These lower bounds should hold for any further improvement of the existing techniques and can thus be used when selecting parameters for a new code-based construction.

29 mai 2009

10h00 Cédric Tavernier [ slides ]
Finding Good Linear Approximations of Block Ciphers and its Application to Cryptanalysis of Reduced Round DES

(Travail en collaboration avec Ilya Dumer, Grigory Kabatiansky, Pierre Loidreau, Rafael Fourquet et Thomas Roche.)
We present an algorithm determining the list of linear approximations of a m-variate Boolean function within a given bias epsilon. If we have enough time we will present a such algorithm with optimal complexity, i.e. equivalent to the dimension of the output m/espilon2. We show how to adapt this algorithm in order to find multiple approximations of 8 rounds of the DES with biases of the same order as the best bias obtained by Matsui. We propose a new very efficient resulting attack based on a soft decision decoding technique of first order Reed-Muller codes. Finally we give an application of this algorithm to side channel attack by considering Hamming distance model. We show that three rounds of DES implemented in asynchronous or one round of AES can be broken with few measures.

11h00 Emmanuel Prouff
Combining Information Theory and Side Channels to Attack (Secure) Implementations

Side Channel Analysis (SCA) is a cryptanalytic technique that consists in analyzing the physical leakage produced during the execution of a cryptographic algorithm embedded on a physical device. This side channel leakage is indeed statistically dependent on the intermediate variables of the computation which enables key recovery attacks. A large variety of SCA performed on embedded devices involve the linear correlation coefficient as wrong-key distinguisher. This coefficient is actually a sound statistical tool to quantify linear dependencies between univariate variables. However, when those dependencies are non-linear, the correlation coefficient stops being pertinent so that another statistical tool must be investigated. Recent works showed that the Mutual Information (MI for short) measure is a promising candidate, since it detects any kind of statistical dependency. Substituting it for the correlation coefficient may therefore be considered as a natural extension of the existing attacks. Nevertheless, the first applications published at CHES 2008 have revealed several limitations of the approach and have raised several questions. In this presentation, we expose the theoretical foundations behind MI-based attacks and we clarify its limitations and assets. We apply it against a flawed countermeasure and we compare its efficiency with the one of correlation-based attacks. We also extend the works recently published at CHES 2008 conference. We argue that in critical contexts (when implementations are protected with masking) MI-based attacks potentially bring improvements compared to existing attacks, because they directly extend to multivariate statistics while, e.g. correlation or Kocher's difference-of-mean generally need to be tweaked to apply to such contexts. Our argumentation will be based on theoretical analyses and on simulations and practical experiments on both hardware and software implementations.

3 avril 2009

10h00 Ayoub Otmani [ slides ]
Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. The secret permutation is then extracted by basically solving an over-constrained linear system. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix.

The other variant uses quasi-cyclic low density parity-check codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on low density parity-check codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity $O\left( n3 \right)$ where $n$ is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic low density parity-check codes requires the search of codewords of low weight which can be done with about $2^{37}$ operations for the specific parameters proposed.

11h00 Jean-Pierre Tillich [ slides ]
Fonctions de hachage fondés sur des produits dans des groupes non-commutatifs

(travail en commun avec Gilles Zémor)

Dans cet exposé, nous analysons la sécurité d'une proposition récente de fonction de hachage de Charles, Goren et Lauter. Le calcul de cette fonction est obtenu par un produit de matrices $2 times 2$ à coefficients dans un corps fini. Ce schéma présente l'attrait que sa sécurité est reliée à un problème notoirement difficile, qui est celui de trouver des factorisations courtes et non triviales de l'identité dans un groupe non commutatif au moyen d'un ensemble fixe de générateurs. Néanmoins, nous montrons que ce problème peut être résolu pour le choix particulier de générateurs effectué par Charles, Goren et Lauter. Cela nous permet de trouver des collisions pour cette fonction de hachage en temps (quasi) polynomial. Enfin, une réparation possible sera proposée.

6 mars 2009

9h40 Julien Bringer
Schémas d'identification à divulgation nulle de connaissance et respectant la sphère privée

At first glance, for an identification protocol, privacy and zero-knowledgeness are quite similar properties. A scheme is private when no information is revealed on the prover; and in a zero-knowledge (ZK) scheme, communications should not leak provers' secrets. Until recently, privacy threats were only partially formalized and some zero-knowledge schemes have been proposed so far to ensure privacy.

In this talk, we explain why the intended goal is not reached. Following the privacy model introduced by Vaudenay at Asiacrypt'07, we reconsider the analysis of these schemes. In particular, we describe a framework which enables to transform some generic ZK scheme into private scheme. As a relevant example we then apply, and improve it further, this framework to the GPS scheme. This leads to efficient implementations of zero-knowledge identification schemes which respect privacy.

Joint work with Hervé Chabanne (Sagem Sécurité, TELECOM Paristech) and Thomas Icart (Sagem Sécurité, Université du Luxembourg), to appear at ASIACCS'09.

11h00 Sylvain Guilley [ slides ]
De la puissance des analyses de consommation

La consommation des circuits électroniques CMOS dépend directement de leur activité. Cette propriété est bien connue dans le domaine de la conception de circuits basse consommation, où toutes opérations superflues sont bannies. Il y a dix ans, une autre exploitation de ce phénomène a été utilisée pour attaquer des circuits cryptographiques. Par exemple, une simple analyse de consommation permet de suivre au fil de son exécution les branchements pris lors d'un calcul d'exponentiation (comme RSA) : comme ceux-ci sont conditionnels à la clé secrète, un attaquant peut directement lire la clé sur une seule trace de consommation acquise par un oscilloscope. Des attaques différentielles, nommées DPA, permettent de tester des valeurs de registres, même lorsque le flot de contrôle de l'algorithme ne fuit aucune information sur les secrets, comme dans le cas de DES ou AES.

Dans ce séminaire, j'illustrerai sur des cas concrets comment réaliser, mais aussi comment entraver, les attaques de type DPA. Je présenterai aussi quelques applications récentes à ces techniques, aussi variées que :
- la rétro-conception de logiques inconnues et
- le test en ligne de composants ou de cartes.
En conclusion, je donnerai quelques éléments au sujet des points innovants qui motivent la création de la spin-off http://www.Secure-IC.com/.

6 février 2009

9h40 Sorina Ionica [ slides ]
Calcul des couplages sur les courbes elliptiques en coordonnées d'Edwards

L'introduction récente des courbes d'Edwards a considérablement réduit le coût de l'addition sur les courbes elliptiques. Durant cette présentation, on donnera des nouvelles formules pour le calcul des couplages sur les courbes d'Edwards. Notre methode donne des performances similaires à celles de l'algorithme de Miller en coordonnées Jacobiennes, ce qui est très intéressant pour les protocoles utilisant des couplages sur les courbes elliptiques. Le nouvel algorithme permet à l'implementation d'un tel protocol d'être entierement faite en coordonées d'Edwards, ce qui est très important pour les dispositifs sur lesquels le calcul des inversions dans un corps fini est très cher (typiquement sur les cartes à puce). Notre méthode est plus rapide que celle proposée récemment par Das et Sarkar pour le calcul des couplages en coordonnées d'Edwards pour des courbes supersingulières.

11h00 Maria Naya-Plasencia [ slides ]
Internal collision attack on Maraca

We present an internal collision attack against the new hash function Maraca which has been submitted to the SHA-3 competition. This attack requires 2^{237} calls to the round function and its complexity is lower than the complexity of the generic collision attack when the length of the message digest is greater than or equal to 512. It is shown that this cryptanalysis mainly exploits some particular differential properties of the inner permutation, which are in some sense in contradiction with the usual security criterion which guarantees the resistance to differential attacks.

5 décembre 2008

9h40 Frederik Armknecht [ slides ]
A New Approach for Algebraically Homomorphic Encryption

Homomorphic encryption schemes preserve the underlying algebraic structure which allows for performing operations in encrypted domain without the need for re-encryption. They have many applications, such as electronic voting, private information retrieval, or multiparty computation. Up to now, several secure and efficient group homomorphic encryption schemes are known, e.g., RSA, ElGamal, Paillier, and Damgaard-Jurik.

However, the existence of an efficient and provably secure algebraically homomorphic scheme, i.e., one that supports both addition and multiplication operations, is a long stated open problem. All proposals so far are either insecure or not provable secure, inefficient, or allow only for one multiplication (and arbitrary additions). As only very limited progress has been made on the existing approaches in the recent years, the question arises whether new methods can lead to more satisfactory solutions.

In this talk we give an introduction to and an overview of the field of (algebraically) homomorphic encryptions. Then, we present a novel approach for constructing a provably secure algebraically homomorphic scheme which is based on coding theory. It allows for arbitrary many additions and for a fixed, but arbitrary number of multiplications and works over arbitrary finite fields. Besides, it possesses some useful properties, like adaptive plaintext space expandability, support of infinite fields, and inherent error-correcting. We discuss the advantages and limitations of the proposed scheme and sketch some possible further work.

The appropriate paper can be found on http://eprint.iacr.org/2008/422.

11h00 Joana Treger [ slides ]
Attaques génériques sur les schémas de Feistel avec permutations

Les schémas de Feistel ont été conçus pour construire des permutations de [1,2^(2n)], à partir d'applications (fonctions internes) de [1,2^n]. On s'intéresse ici aux attaques génériques sur les schémas de Feistel, dans le cas où les fonctions internes sont des permutations, au lieu de fonctions. Les attaques sont génériques dans le sens où les permutations internes sont supposées aléatoires. Malgré l'utilisation de tels schémas dans la conception d'algorithmes à clé secrète (ex : Twofish, Camelia, DEAL), ils n'ont pas été le sujet de nombreuses études. Nous allons voir que leur comportement est souvent différent de celui des schémas de Feistel classiques (avec fonctions internes). Plus précisément, nous allons voir que les attaques sont souvent moins efficaces, par exemple sur 3, 6 ou 9 tours de schémas de Feistel. Pour une taille d'entrée de 2n bits, les attaques trouvées nécessitent strictement moins de 2^(2n) messages quand le nombre de tours est inférieur ou égal à 5. Pour un nombre de tours plus grand, des attaques permettant de distinguer un générateur de permutations de Feistel (avec permutations internes) d'un générateur de permutations aléatoires seront également exposées.

31 octobre 2008

9h40 Charles Bouillaguet
Exploiting the Algebraic Structure of the RadioGatun Hash Function: Application to Collision Finding

Dans cet exposé, je vais présenter une première analyse de la fonction de hashage RadioGatun. Cette fonction a été proposée par Bertoni, Daemen, Peeters et Van Assche en 2006, lors du second NIST Hash Workshop. RadioGatun est le dernier-né d'une famille de fonctions conçues par Joan Daemen entre autre, qui diffère radicalement de la famille SHA/MD qui a été standardisée et qui est largement utilisée. RadioGatun possède un gros état interne de 58 mots, dont la taille constitue un paramètre : avec des mots de 1 bit, on a une version jouet facile à analyser, tandis qu'avec des mots de 64 bits, on obtient la véritable fonction.

Nous nous sommes particulièrement intéressé à la version à 1 bit, pour laquelle il est possible de trouver des chemins différentiels par force brute. En exploitant la structure algébrique particulièrement simple de la fonction de ronde (sur le corps à 2 élements), il est possible de produire des collisions qui suivent un chemin donné plus vite que par recherche exhaustive. Pour cela, on calcule l'image réciproque d'une variété affine par la fonction de ronde en utilisant des bases de Gröbner pour un ordre d'élimination. Cette technique permet également de produire des pseudo-collisions en trouvant un point dans une variété affine, ou bien de tester si un chemin différentiel est possible, en testant si une variété est vide.

J'expliquerai pourquoi cette attaque fonctionne, c'est-à-dire que je montrerai dans la structure de RadioGatun ce qui permet le calcul rapide des bases de Gröbner d'une part. D'autre part, je justifierai que la recherche de collisions sur des fonctions de hashage dotées d'une structure algébrique simple offre un contexte favorable aux attaques algébriques.

Références :

11h00 Dongdai Lin
On Simultaneous Resettability of Zero Knowledge Arguments

Because of their useful applications in the design of cryptographic protocols in a variety of settings, zero-knowledge protocols have received a significant amount of attention from the research community since it was introduced by S. Goldwasser et al. in 1989. Generally, it is crucial for an honest party involved in multiple executions of a cryptographic protocols to refresh his randomness each run in order to preserve the security. A natural question, of both theoretic and practical interest, is whether it is possible to realize some cryptographic task in such a way that honest party can use a fixed random tape in multiple executions of the resulting protocol without sacrificing its security, this is the so called resettability problems of zero knowledge protocols. In this talk, we will first recall some basic notion of zero knowledge, some problems and results, and then focus on our current research progress on the study of the simulataneous resettability conjecture which was proposed by Barak et al. in FOCS 2001.

19 septembre 2008

9h40 Alexander May
Solving RSA Problems with Lattice Reduction

This survey addresses the problems of factoring and inverting the RSA function. We define practically relevant relaxed instances of these problems that can be solved in polynomial time. These problem instances are modelled by polynomial equations with small roots. In order to recover the roots, we make use of a method due to Coppersmith which is in turn based on the famous LLL lattice reduction.

As new applications of the method we present an improved Hastad attack on RSA in the case of several RSA encryptions of the same underlying message, and an algorithm for factoring N=pq given 70% of the bits of p in any positions.

11h00 Luk Bettale
Attaques algébriques sur des systèmes sous-déterminés issus de la cryptographie

Dans cet exposé, je vais vous présenter le travail que j'ai réalisé sur des schémas de signature (TRMS) et de hachage basés sur des systèmes polynomiaux multivariés. Ces systèmes ont la particularité d'être sous-déterminés, et nous avons tenté de trouver un compromis pour une approche hybride résolution par base de Gröbner/spécialisation de variables.