|
|
|
|
|
|
|
Résumé.
LoRaWAN is a worldwide deployed IoT security protocol. We provide an extensive analysis of the version 1.0, which is the currently deployed version, and we show that it suffers from several weaknesses. We introduce several attacks, including practical ones, that breach the network availability, data integrity, and data confidentiality, and target either an end-device or the backend system.
Based on the inner weaknesses of the protocol, these attacks do not lean on potential implementation or hardware bugs. Likewise they do not entail a physical access to the targeted equipment and are independent from the means used to physically protect secret parameters.
Finally we propose practical recommendations aiming at thwarting the attacks, while at the same time being compliant with the specification, and keeping the interoperability between patched and unmodified equipment.
Résumé.
A cryptanalytic time-memory trade-off is a technique that aims to reduce the time needed to perform an exhaustive search. Such a technique requires large-scale precomputation that is performed once for all and whose result is stored in a fast-access internal memory. When the considered cryptographic problem is overwhelmingly-sized, using an external memory is eventually needed, though. In this paper, we consider the rainbow tables – the most widely spread version of time-memory trade-offs. The objective of our work is to analyze the relevance of storing the precomputed data on an external memory (SSD and HDD) possibly mingled with an internal one (RAM). We provide an analytical evaluation of the performance, followed by an experimental validation, and we state that using SSD or HDD is fully suited to practical cases, which are identified.
This work was presented in ACISP 2017 and is a joint work with Gildas Avoine, Xavier Carpent and Barbara Kordy
Résumé.
The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions F, G and H and she has to find three inputs x, y and z such that F(x) oplus G(y) oplus H(z) = 0. The 3XOR problem is a difficult case of the more-general k-list birthday problem.
Wagner's celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to F, G and H is minimal. If they are n-bit random functions, it is possible to solve the problem with roughly O(2^{n/3}) queries. In this setting, the folklore quadratic algorithm finds a solution after O(2^{2n/3}) operations. We present a 3XOR algorithm, with complexity O(2^{2n/3} / n) in times and O(2^{n/3}) in space. This algorithm is practical: it is up to 3x faster than the quadratic algorithm. Furthermore, we show that it is possible to adapt this algorithm to any number of queries, so that it will always be at least as good as, if not better than, Wagner's descendants in the same settings.
We also revisit a 3SUM algorithm by Baran-Demaine-Pvtrascu which is asymptotically n^2 log^2 n times faster than the quadratic algorithm when adapted to the 3XOR problem, but is otherwise completely impractical. To gain a deeper understanding of these problems, we embarked on a project to solve actual 3XOR instances for the SHA256 hash function. We believe that this was very beneficial and we present practical remarks, along with a 96-bit 3XOR for SHA256.
This work has been presented in FSE'18. This is joint work with Charles Bouillaguet and Pierre-Alain Fouque.
Résumé.
Le domaine des communications est un domaine en pleine évolution. Les nombreuses avancées technologiques conduisent à la production d’un nombre croissant de données qui doivent être traitées, transmises et/ou stockées : celles-ci sont principalement des sons, des images ou des textes. Elles proviennent, en particulier, des activités liées aux satellites (défense, télédétection, cartographie, etc.) du multimédia (photographie numérique, webcam, etc.). L’explosion d’internet au cours des dix dernières années est un exemple parfait de la croissance des communications. La représentation de ces informations sous forme numérique fiabilise leur transmission à travers des réseaux informatiques et facilite leur manipulation. La numérisation engendrant le multimédia présente cependant un inconvénient : elle requiert une capacité de stockage importante, une bande passante considérable et surtout une protection efficace des données échangées dans un monde marqué par de multiples menaces.
Les techniques de cryptographie ne garantissent pas toujours toute la sécurité souhaitée. Dans ces conditions, la stéganographie peut être une alternative ou compléter ces algorithmes. La stéganographie est l’art de la communication secrète. Depuis l’avènement de la stéganographie moderne, dans les années 2000, de nombreuses approches basées sur les codes correcteurs d’erreurs ont été proposées pour réduire le nombre de modifications du support de couverture tout en insérant le maximum de bits. Les travaux de Jessica Fridrich ont montréque les codes à matrices creuses approchent le mieux la limite théorique d’efficacité d’insertion. L’Objectif de cette présentation est de présenter nos activités de recherche :
Résumé.
Explicit arithmetic on elliptic curves over finite fields has received a lot of attention as it is an important component of choosing a good elliptic curve as the basis of a discrete-log based cryptosystem. The case of higher dimensional Abelian varieties has also been studied in the case that they arise as Jacobians of curves. In all of these cases, the equation of the curve plays an important role. However, for a general Abelian variety, one has neither curves nor equations. It then becomes an interesting and potentially important problem to develop arithmetic in this context. We will explain joint work with Pramath Sastry in which we develop algorithms for addition on an Abelian variety. The work should be considered a first step in a long program yet to be developed.
Résumé.
Le chiffrement fonctionnel est une technique émergente en cryptographie dans laquelle une autorité toute puissante est capable de distribuer des clés permettant d’effectuer des calculs sur des données chiffrées de manière contrôlée. La mode dans ce domaine est de construire des schémas qui sont aussi expressifs que possible, c’est-à-dire du chiffrement fonctionnel qui permet l’évaluation de n’importe quel circuit. Ces contributions délaissent souvent l’efficacité ainsi que la sécurité. Elles reposent sur des hypothèses fortes, très peu étudiées, et aucune construction n’est proche d’être pratique.
Le but de cette thèse est d’attaquer ce défi sous un
autre angle: nous essayons de construire des schémas
de chiffrement fonctionnel les plus expressifs que nous
le pouvons en se basant sur des hypothèses standards,
tout en conservant la simplicité et l’efficacité des constructions.
C’est pourquoi nous introduisons la notion de
chiffrement fonctionnel pour l’évaluation de produits
scalaires, où les messages sont des vecteurs x, et
l’autorité peut transmettre des clés correspondants à
des vecteurs y qui permettent l’évaluation du produit
scalaire
Résumé.
La carte à puce est à la base de la sécurité des systèmes informatiques. Elle a fait ses preuves dans de nombreux secteurs en tant que moyen de paiement ou d’authentification. L’objectif de cette présentation est de reconsidérer la sécurité de ces cartes face à des nouveaux modèles d’adversaires : la substitution d’algorithme et les ordinateurs quantiques. Dans un premier temps, nous nous intéresserons à la famille de protocoles sécurisés SCP (de l’anglais Secure Channel Protocols). Nous présenteront la notion des attaques par substitution d’algorithmes, qui a été développée après la révélation de Snowden. Nous montrons qu’il existe un membre de la famille SCP qui résiste aux modifications malveillantes dans les implémentations des schémas cryptographiques. Dans un deuxième temps, nous chercherons à rendre les schémas post-quantiques pratiques pour les systèmes à puissance de calcul limitée. En particulier, nous étudions l’échantillonnage de distributions gaussiennes discrètes. Il y a deux problèmes dans les algorithmes d’échantillonnage : ils ont besoin d’un espace de stockage important et/ou ils impliquent très souvent des opérations mathématiques qui ne sont pas disponibles sur les cartes comme le calcul d’une exponentielle sur des nombres réels à précision arbitraire. Nous présenterons des premiers pas vers des nouvelles approches qui sont mieux adaptées aux cartes.
Résumé.
Cette exposé traite l’implémentation matérielle de la méthode CIOS (Coarsely Integrated Operand Scanning) de la multiplication modulaire de Montgomery. Dans ce travail nous avons combiné cette méthode CIOS avec une architecture systolique efficace. D'après nos connaissances, c'est la première implémentation d'une telle conception. Nos architectures visaient à réduire le nombre de cycles d'horloge de la multiplication dans les corps finis. Les résultats d'implémentation proposées pour les algorithmes CIOS se concentrent sur différents niveaux de sécurité utiles en cryptographie. Cette architecture a été conçue pour utiliser le DSP48 flexible sur les FPGA de Xilinx. Nos architectures sont évolutives et dépendent uniquement du nombre et de la taille des mots. Par exemple, nous fournissons des résultats d'implémentation pour des mots de 8, 16, 32 et 64 bits en 33, 66, 132 et 264 cycles d'horloge.
Résumé.
The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual OK^vee of the ring of integers OK of a specified number field K. In primal-RLWE, the secret instead belongs to OK. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers OK of a number field K but a polynomial ring Z[x]/f for a monic irreducible f in Z[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is nonuniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for RLWE. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.
Based on joint work with Miruna Roșca and Damien Stehlé.
Résumé.
Adaptive oblivious transfer (OT) is a protocol where a sender initially commits to a database {M_i}_{i=1}^N . Then, a receiver can query the sender up to k times with private indexes ρ_1, …, ρ_k so as to obtain M_{ρ_1}, …, M_{ρ_k} and nothing else. Moreover, for each i ∈ [k], the receiver’s choice ρ_i may depend on previously obtained messages {M_ρ_j}_{j < i} . Oblivious transfer with access control (OT-AC) is a flavor of adaptive OT where database records are protected by distinct access control policies that specify which credentials a receiver should obtain in order to access each M_i . So far, all known OT-AC protocols only support access policies made of conjunctions or rely on ad hoc assumptions in pairing-friendly groups (or both). In this paper, we provide an OT-AC protocol where access policies may consist of any branching program of polynomial length, which is sufficient to realize any access policy in NC^1. The security of our protocol is proved under the Learning-with-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a result of independent interest, we provide protocols for proving the correct evaluation of a committed branching program on a committed input.
Résumé.
Dans cet exposé je m’intéresse au calcul du couplage Optimal Ate en considérant les nouveaux niveaux de sécurité. En effet, fin 2016, les optimisations sur le calcul de logarithme discret sur les corps finis ont mené à un changement au niveau de niveau de sécurité du calcul des couplages. Par exemple, la courbe BN (la plus adéquate pour le calcul du couplage) possédant avant un niveau de sécurité de 128 bits mais maintenant que 100 bits après les résultats de Barbulescu et Kim. Récemment, Barbulescu et Duquesne ont conclut que la courbe elliptique la plus adéquate pour le calcul du couplage Optimal Ate pour le niveau de sécurité 128 bits est KSS16 et non pas BN. Notre but était de vérifier la conclusion de Barbulescu et Duquesne en passant à l'implémentation soft. Dans notre travail, nous avons étudié deux points: Le premier point concerne le calcul de l'algorithme de Miller optimisé pour le couplage Optimal Ate sur les courbes KSS16. Cette optimisation est grâce à la multiplication creuse '8-sparse-multiplications'.
Le deuxième point concerne l'implémentation du couplage Optimal Ate sur les courbes elliptiques: KSS16, BN et BLS12 en utilisant les nouvelles paramétrisations qui rassurent un niveau de sécurité de 128 bits. Notre étude comparative a confirmé que la courbe BN reste un fort candidat pour le calcul du couplage Optimal Ate. Cette conclusion nous a ouvert plusieurs points de recherche que nous sommes actuellement en train de les voir tels que le calcul du carré compressé dans F_{p^{16}} afin d'accélérer le calcul du couplage optimal Ate sur les courbes de degré de plongement k=16 (la meilleure théoriquement). Aussi chercher la courbe optimale pour les hauts niveaux de sécurité (voir 192 et 256).
Résumé.
Nous nous intéressons à des modes opératoires parallèles pour une fonction de hachage supposée être à taux unitaire, avec un état interne de la même taille qu'un bloc du message. Calculatoirement, une telle fonction a la caractéristique intéressante de ne nécessiter que k appels à la primitive sous-jacente pour traiter un message de k blocs. Afin de concrétiser une telle fonction, nous utilisons une variante de la construction de Merkle-Damgård (Coron et al., CRYPTO 2005). Nous construisons alors une fonction de hachage s'appuyant sur cette dernière au moyen d'un arbre ayant toutes ses feuilles à la même profondeur. Dans ce travail, nous caractérisons les structures arborescentes à utiliser pour réduire au mieux le temps d'exécution de la fonction qui en résulte. Ensuite, sans affecter ce temps d'exécution, nous montrons comment réduire le nombre de processeurs. En particulier, nous cherchons à libérer les processeurs le plus rapidement possible à chaque étape du calcul. Enfin, nous donnons un exemple de fonction de hachage utilisant ces optimisations et les résultats de Bertoni et al. (IJIS 2014), qui assure son indifférentiabilité d'une fonction de hachage idéale.
Résumé.
We introduce a new variant MP-LWE of the Learning With Errors problem (LWE) making use of the Middle Product between polynomials modulo an integer q. We exhibit a reduction from the Polynomial-LWE problem (PLWE) parametrized by a polynomial f, to MP-LWE which is defined independently of any such f. The reduction only requires f to be monic with constant coefficient coprime with q. It incurs a noise growth proportional to the so-called expansion factor of f. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the MP-LWE hardness assumption. The scheme is hence secure under the assumption that PLWE is hard for at least one polynomial f of degree n among a family of f’s which is exponential in n.
This talk is based on https://eprint.iacr.org/2017/628.pdf, a paper accepted at Crypto 2017. This is joint work with Amin Sakzad, Damien Stehlé and Ron Steinfeld.