The team is involved in the following seminars :

Team seminar

The team seminar usually takes place every two weeks on Tuesday at 11am.

Post-quantum resistant cryptography in TLS

05/29, Les Minquiers, Mohamed SABT

LWE without modular reduction and improved side-channel attacks against BLISS

05/15, Les Minquiers, Pierre-Alain FOUQUE

Proving physical proximity using symbolic models

04/03, F302, Alexandre DEBANT

For many modern applications like e.g contactless payment, and keyless systems, ensuring physical proximity is a security goal of paramount importance. Formal methods have proved their usefulness when analysing standard security protocols. However, existing results and tools do not apply to e.g. distance-bounding that aims to ensure physical proximity between two entities. This is due in particular to the fact that existing models do not represent in a faithful way the locations of the participants, and the fact that transmission of messages takes time. In this work, we propose several reduction results: When looking for an attack, it is actually sufficient to consider a simple scenario involving at most four participants located at some specific locations. An interesting consequence of our reduction results is that it allows one to reuse ProVerif, an automated tool developed for analysing standard security protocols. As an application, we analyse several distance-bounding protocols, as well as a contactless payment protocol.

Practical Implementation of Ring-SIS/LWE based Signature and IBE

04/03, F302, Pauline BERT

Lattice-based signature and Identity-Based Encryption are well-known cryptographic schemes, and having both efficient and provable secure schemes in the standard model is still a challenging task in light of the current NIST post-quantum competition. We address this problem in this paper by mixing standard IBE scheme, à la ABB (EUROCRYPT 2010) on Ring-SIS/LWE assumptions with the efficient trapdoor of Peikert and Micciancio (EUROCRYPT 2012) and we provide an efficient implementation. Our IBE scheme is more efficient than the IBE scheme of Ducas, Lyubashevsky and Prest based on NTRU assumption and is based on more standard assumptions. We also describe and implement the underlying signature scheme, which is provably secure in the standard model and efficient.

Revisiting and Improving Algorithms for the 3XOR Problem

02/20, F302, Claire Delaplace

The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. Here, 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 H. She has to find three inputs x, y and z such that F(x) xor G(y) xor H(z) is 0. 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 them some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. We restrict our attention to solving the 3XOR problem for which the total number of queries is minimal. If F is an n-bit random function, we want 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 that generalizes an idea of Joux, with complexity O(2^(2n/3) / n). This algorithm is practical: it is up to 3 times faster than the quadratic algorithm. We also revisit a 3SUM algorithm by Baran-Demaine-Patrascu 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.

Rescuing LoRaWAN 1.0.

02/13, F302, Loïc Ferreira

Cache attacks: From side channels to fault attacks

10/26 (Thursday, 4:30pm), F302, Clémentine Maurice

Attack-Defense Trees For Computer Security

10/10, F402, Angèle Bossuat

Attack–defense trees are a rather simple yet potent and efficient way to represent and evaluate security scenarios involving a (malicious) attacker, and a defender. During my internship, I have made some progress extending the pre-existing attack-defense trees model in various directions: repeated labels, wellformedness, and distinction between reactions and preventions. I will present the results in an extended version of the oral presentation I did for the university last month.

How to Handle Rainbow Tables with External Memory

5/23, F402, Florent Tardif

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 ex- ternal memory is eventually needed, though. 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.

Fast Lattice-Based Encryption: Stretching Spring

5/9, F402, Claire Delaplace

Anomaly Detection in Streams with Extreme Value Theory

4/12 (Wednesday), F402, Alban Siffer

Anomaly detection in time series has attracted considerable attention due to its importance in many real-world applications including intrusion detection, energy management and finance. Most approaches for detecting outliers rely on either manually set thresholds or assumptions on the distribution of data. We propose a new approach to detect outliers in streaming univariate time series based on Extreme Value Theory that does not require to hand-set thresholds and makes no assumption on the distribution: the main parameter is only the risk, controlling the number of false positives. Our approach can be used for outlier detection, but more generally for automatically setting thresholds, making it useful in wide number of situations. We also experiment our algorithms on various real-world datasets which confirm its soundness and efficiency.

Structure-Preserving Chosen-Ciphertext Security With Shorter Verifiable Ciphertexts

3/27 (Monday, 2pm), F402, Chen QIAN

Structure-preserving cryptography is a world where messages, signatures, ciphertexts and public keys are entirely made of elements of a group over which a bilinear map is efficiently computable. While structure-preserving signatures have received much attention the last 6 years, structure-preserving encryption schemes have undergone slower development. In particular, the best known structure-preserving cryptosystems with chosen-ciphertext (IND-CCA2) security either rely on symmetric pairings or require long ciphertexts comprised of hundreds of group elements or do not provide publicly verifiable ciphertexts. We provide a publicly verifiable construction based on the SXDH assumption in asymmetric bilinear groups e : G_1 x G_2 -> G_T, which features relatively short ciphertexts. For typical parameters, our ciphertext size amounts to less than 40 elements of G. As a second contribution, we provide a structure-preserving encryption scheme with perfectly randomizable ciphertexts and replayable chosen-ciphertext security. Our new RCCA-secure system significantly improves upon the best known system featuring similar properties in terms of ciphertext size.

Achieving better privacy for the 3GPP AKA protocol

7/04 (Monday), F202, Benjamin Richard

Proposed by the 3rd Generation Partnership Project (3GPP) as a standard for 3G and 4G mobile-network communications, the AKA protocol is meant to provide a mutually-authenticated key-exchange between clients and associated network servers. As a result AKA must guarantee the indistinguishability from random of the session keys (key-indistinguishability), as well as client- and server-impersonation resistance. A paramount requirement is also that of client privacy, which 3GPP defines in terms of: user identity confidentiality, service untraceability, and location untraceability. Moreover, since servers are sometimes untrusted (in the case of roaming), the AKA protocol must also protect clients with respect to these third parties. Following the description of client-tracking attacks e.g. by using error messages or IMSI catchers, van den Broek et al. and respectively Arapinis et al. each proposed a new variant of AKA, addressing such problems. In this paper we use the approach of provable security to show that these variants still fail to guarantee the privacy of mobile clients. We propose an improvement of AKA, which retains most of its structure and respects practical necessities such as key-management, but which provably attains security with respect to servers and Man-in-the-Middle (MiM) adversaries. Moreover, it is impossible to link client sessions in the absence of client-corruptions. Finally, we prove that any variant of AKA retaining its mutual authentication specificities cannot achieve client-unlinkability in the presence of corruptions. In this sense, our proposed variant is optimal.

Memory carving in embedded devices: separate the wheat from the chaff

6/14, F402, Thomas Gougeon

This talk will introduce memory carving techniques for embedded devices. Given that cryptographic material in memory dumps makes carving techniques inefficient, we introduce a methodology to distinguish meaningful information from cryptographic material in small-sized memory dumps. The proposed methodology uses an adaptive boosting technique with statistical tests. Experimented on EMV cards, the methodology recognised 92% of meaningful information and 98% of cryptographic material.

Assisted Identification of Mode of Operation in Binary Code with Dynamic Data Flow Slicing

5/31, F402, Pierre Lestringant

L'analyse d'implémentations en langage natif d'algorithmes cryptographiques se révèle longue et fastidieuse. De précédents travaux se sont intéressés à l'identification des primitives cryptographiques. L'objectif est aujourd'hui de proposer des solutions similaires pour les modes opératoires. Inspirée du "program slicing" la solution qui fera l’objet de la présentation, permet d’obtenir une visualisation synthétique des différents échanges de données intervenant dans l'algorithme du mode opératoire. Cette représentation se définit comme le plus petit sous graphe issu du flot de données préservant les distances pour l'ensemble des paramètres d'entrés et de sorties des primitives cryptographiques. Après avoir détaillé les différentes phases permettant l'obtention de cette représentation, je présenterai à travers de nombreux exemples son intérêt pour l’identification des modes opératoires.

Type-Based Verification of Electronic Voting Protocols

4/26, F202, Cyrille Wiedling

Les protocoles de vote électronique sont, par nature, particulièrement sensibles, et se doivent de satisfaire à d'exigentes propriétés de sécurité. Par conséquent, ils emploient souvent de nombreuses primitives cryptographiques, ce qui rend leur étude rigoureuse particulièrement difficile. Concrètement, la plupart des outils de vérification automatique actuels ne sont pas en mesure gérer toutes ces primitives (e.g. le chiffrement homomorphe ou les mix-nets), voire même les propriétés que l'on cherche à démontrer (e.g. la vérifiabilité). Cet exposé présente une nouvelle approche (NdlA : enfin pas si nouvelle que ça...), basée sur les systèmes de types, pour automatiser l'analyse des protocoles de vote électronique. Au travers de l'exemple d'Helios, nous verrons comment appliquer cette approche pour vérifier, de façon automatique, qu'un protocole de vote électronique satisfait aux principales propriétés de sécurité adéquates.

Recherche automatique de différentielles impossibles et attaques de type Demirci-Selçuk sur une grande classe de chiffres par bloc

4/12, F402, Patrick Derbez

Dans un premier temps, je présenterai les attaques de Demirci et Selçuk et ses différentes améliorations qui ont donné les meilleurs résultats connus sur les versions réduites de plusieurs systèmes de chiffrement par bloc (AES, PRINCE, ...). Je décrirai un algorithme pour rechercher automatiquement ce type d'attaques contre une large variété de chiffrements et mettrai en lumière les principales difficultés. Dans un second temps, je montrerai qu'une partie du précédent algorithme peut être utilisée pour rechercher un autre type d'attaques: les attaques par différentielle impossible. Contrairement aux précédents algorithmes qui ne servent à rechercher que les transitions impossibles couvrant un maximum de tours, notre nouvel algorithme permet de rechercher directement les meilleures attaques. Enfin, je discuterai des problèmes encore ouverts concernant les attaques de Demirci et Selçuk et de pistes de recherche.

Symmetric searchable encryption

3/09 (Wednesday), Raphaël Bost

Le chiffrement consultable tente de répondre simultanément à deux besoins opposés: comment effectuer une recherche sur une base de document stockée sur un serveur distant, et en le laissant apprendre au serveur qu’un minimum d’information sur la base ou sur les requêtes. Après avoir présenté ces systèmes et leurs contraintes, nous étudierons le cas des constructions qui restent sûre face à un adversaire malicieux (qui triche et ne suit pas les protocoles). Nous verrons aussi quelles sont les problèmes qui restent à régler et les solutions à étudier pour pouvoir utiliser en pratique ces systèmes.

Attaques par sous-espaces invariants sur les chiffrements légers

2/23, F402, Brice Minaud

Les attaques par sous-espaces invariants s'appliquent à des chiffrements légers dont le cadencement de clef est minimal (ou à des fonctions de hachage). Il n'y a que quatre attaques de ce type connues à ce jour, dont on va regarder deux en détail ; mais trois cas sur quatre produisent des attaques dévastatrices en temps pratique. On verra le schéma général de l'attaque, qui est très simple ; un outil automatique pour détecter certaines de ces attaques ; et deux exemples d'attaques, publiés à Eurocrypt 2015.

Construction d'une petite boîte S 8-bit avec branchement 3 (& applications)

2/09, F402, Pierre Karpman

Je présenterai la construction et l'implémentation d'une boîte S sur 8 bits qui a un branchement linéaire et différentiel de 3. Je montrerai une application en construisant un chiffre par bloc sur 64 bits dont la structure est très simple et basée sur l'évaluation en tranches (bitsliced) et des rotations sur mots de 8 bits. La fonction de tour de ce chiffre peut s'implémenter avec le même nombre d'instructions que celle de PRIDE sur micro-controleurs 8-bits, tout en ayant 1,5 fois plus de boîtes S actives (relativement). La boîte S que je présenterai peut aussi s'implémenter efficacement avec des instructions SIMD, a un coût faible en matériel et peut se masquer efficacement grâce au peu de portes non-linéaires nécessaires.

last modification: 02/05/18