Subversion-resilient Authenticated key-exchange (AKE) aims to achieve the guarantees of secure AKE even in the presence of an adversary that has tampered with parts of the protocol's implementation. One way to achieve subversion-resilient AKE is the use of Reverse Firewalls (RFs), an untrusted third-party that can restore security. Recent work[17] highlights the challenges of designing RFs for practical secure channel-establishment.

Coding standards for secure programming recommend "scrubbing" sensitive data once it is no longer needed; otherwise, secrets may be recovered, as illustrated in the Heartbleed attack. Despite being an effective software-based countermeasure, zeroization, i.e., overwriting with zeroes, turns out to be challenging and error-prone. Current verification approaches suffer from scalability or precision issues when applied to production software in practice. In this paper, we put forward the GCC Static Analyzer (GSA), which is a symbolic execution engine for error finding. Specifically, we extend the GSA to build GnuZero; our automated tool that detects missing zeroization for all stack/heap variables storing sensitive data, either directly or by derivation. Our experiments confirm GnuZero efficiency and effectiveness in verifying real-world benchmarks. In particular, GnuZero passes all the relevant Juliet’s test programs, namely associated to the MITRE’s CWE-244 and CWE-226. In addition, GnuZero succeeds in identifying new vulnerabilities in open-source cryptographic modules.

We describe several algorithms for computing e-th roots of elements in a number field K, where e is an odd prime-power integer. In particular, we generalize Couveignes’ and Thomé’s algorithms originally designed to compute square-roots in the context of the General Number Field Sieve algorithm for integer factorization. Our algorithms cover most cases of e and K and their complexity is better than general root finding algorithms. Our (publicly available) Python implementation compares extremely well in performance to the implementation of these generic algorithms in well-known computer algebra softwares, allowing us to obtain reasonable timings even for large degree number fields and huge exponents e, which correspond to previously intractable cases using these softwares.

It is universally acknowledged that Wi-Fi communications are important to secure. Thus, the Wi-Fi Alliance published WPA3 in 2018 with a distinctive security feature: it leverages a Password-Authenticated Key Exchange (PAKE) protocol to protect users’ passwords from offline dictionary attacks. Unfortunately, soon after its release, several attacks were reported against its implementations, in response to which the protocol was updated in a best-effort manner.In this paper, we show that the proposed mitigations are not enough, especially for a complex protocol to implement even for savvy developers. Indeed, we present Dragondoom, a collection of side-channel vulnerabilities of varying strength allowing attackers to recover users’ passwords in widely deployed Wi-Fi daemons, such as hostap in its default settings. Our findings target both password conversion methods, namely the default probabilistic hunting-and-pecking and its newly standardized deterministic alternative based on SSWU. We successfully exploit our leakage in practice through microarchitectural mechanisms, and overcome the limited spatial resolution of Flush+Reload. Our attacks outperform previous works in terms of required measurements.Then, driven by the need to end the spiral of patch-and-hack in Dragonfly implementations, we propose Dragonstar, an implementation of Dragonfly leveraging a formally verified implementation of the underlying mathematical operations, thereby removing all the related leakage vector. Our implementation relies on HACL*, a formally verified crypto library guaranteeing secret-independence. We design Dragonstar, so that its integration within hostap requires minimal modifications to the existing project. Our experiments show that the performance of HACL*-based hostap is comparable to OpenSSL-based, implying that Dragonstar is both efficient and proved to be leakage-free.

Thanks to HTML5, users can now view videos on Web browsers without installing plug-ins or relying on specific devices. In 2017, W3C published Encrypted Media Extensions (EME) as the first official Web standard for Digital Rights Management (DRM), with the overarching goal of allowing seamless integration of DRM systems on browsers. EME has prompted numerous voices of dissent with respect to the inadequate protection of users. Of particular interest, privacy concerns were articulated, especially that DRM systems inherently require uniquely identifying information on users' devices to control content distribution better. Despite this anecdotal evidence, we lack a comprehensive overview of how browsers have supported EME in practice and what privacy implications are caused by their implementations. In this paper, we fill this gap by investigating privacy leakage caused by EME relying on proprietary and closed-source DRM systems. We focus on Google Widevine because of its versatility and wide adoption. We conduct empirical experiments to show that browsers diverge when complying EME privacy guidelines, which might undermine users' privacy. For instance, we find that many browsers gladly give away the identifying Widevine Client ID with no or little explicit consent from users. Moreover, we characterize the privacy risks of users tracking when browsers miss applying EME guidelines regarding privacy. Because of being closed-source, our work involves reverse engineering to dissect the contents of EME messages as instantiated by Widevine. Finally, we implement EME Track, a tool that automatically exploits bad Widevine-based implementations to break privacy.

Nowadays, most content providers rely on DRM (Digital Right Management) to protect media from illegal distribution. Becoming a major platform for streaming, Android provides its own DRM framework that does not comply with existing DRM standards. Thus, OTT (over-the-top) platforms need to adapt their apps to suit Android design, despite a fragmented ecosystem and little public documentation. Unfortunately, the security implications of how OTT apps leverage Widevine, the most popular Android DRM, have not been studied yet.In this paper, we report the first experimental study on the state of Widevine use in the wild. Our study explores OTT compliance with Widevine guidelines regarding asset protection and legacy phone support. With the evaluation of premium OTT apps, our experiments bring to light that most apps adopt weak and potentially vulnerable practices. We illustrate our findings by showing how to easily recover media content from many OTT apps, including Netflix.

This work describes the Mitaka signature scheme: a new hash-and-sign signature scheme over NTRU lattices which can be seen as a variant of NIST finalist Falcon . It achieves comparable efficiency but is considerably simpler, online/offline, and easier to parallelize and protect against side-channels, thus offering significant advantages from an implementation standpoint. It is also much more versatile in terms of parameter selection. We obtain this signature scheme by replacing the FFO lattice Gaussian sampler in Falcon by the “hybrid” sampler of Ducas and Prest, for which we carry out a detailed and corrected security analysis. In principle, such a change can result in a substantial security loss, but we show that this loss can be largely mitigated using new techniques in key generation that allow us to construct much higher quality lattice trapdoors for the hybrid sampler relatively cheaply. This new approach can also be instantiated on a wide variety of base fields, in contrast with Falcon ’s restriction to power-of-two cyclotomics. We also introduce a new lattice Gaussian sampler with the same quality and efficiency, but which is moreover compatible with the integral matrix Gram root technique of Ducas et al., allowing us to avoid floating point arithmetic. This makes it possible to realize the same signature scheme as Mitaka efficiently on platforms with poor support for floating point numbers. Finally, we describe a provably secure masking of Mitaka . More precisely, we introduce novel gadgets that allow provable masking at any order at much lower cost than previous masking techniques for Gaussian sampling-based signature schemes, for cheap and dependable side-channel protection.

Timing attacks are among the most devastating side-channel attacks, allowing remote attackers to retrieve secret material, including cryptographic keys, with relative ease. In principle, “these attacks are not that hard to mitigate the basic intuition, captured by the constant-time criterion, is that control-flow and memory accesses should be independent from secrets. Furthermore, there is a broad range of tools for automatically checking adherence to this intuition. Yet, these attacks still plague popular cryptographic libraries twenty-five years after their discovery, reflecting a dangerous gap between academic research and cryptographic engineering. This gap can potentially undermine the emerging shift towards high-assurance, formally verified cryptographic libraries. However, the causes for this gap remain uninvestigated. To understand the causes of this gap, we conducted a survey with 44 developers of 27 prominent open-source cryptographic libraries. The goal of the survey was to analyze if and how the developers ensure that their code executes in constant time. Our main findings are that developers are aware of timing attacks and of their potentially dramatic consequences and yet often prioritize other issues over the perceived huge investment of time and resources currently needed to make their code resistant to timing attacks. Based on the survey, we identify several shortcomings in existing analysis tools for constant-time, and issue recommendations that can make writing constant-time libraries less difficult. Our recommendations can inform future development of analysis tools, security-aware compilers, and cryptographic libraries, not only for constant-timeness, but in the broader context of side-channel attacks, in particular for micro-architectural side-channel attacks, which are a younger topic and too recent as focus for this survey.

Protocols for password-based authenticated key exchange (PAKE) allow two users sharing only a short, low-entropy password to establish a secure session with a cryptographically strong key. The challenge in designing such protocols is that they must resist offline dictionary attacks in which an attacker exhaustively enumerates the dictionary of likely passwords in an attempt to match the used password. In this paper, we study the resilience of one particular PAKE against these attacks. Indeed, we focus on the Secure Remote Password (SRP) protocol that was designed by T. Wu in 1998. Despite its lack of formal security proof, SRP has become a de-facto standard. For more than 20 years, many projects have turned towards SRP for their authentication solution, thanks to the availability of open-source implementations with no restrictive licenses. Of particular interest, we mention the Stanford reference implementation (in C and Java) and the OpenSSL one (in C).

Recently, the Dragonblood attacks have attracted new interests on the security of WPA-3 implementation and in particular on the Dragonfly code deployed on many open-source libraries. One attack concerns the protection of users passwords during authentication. In the Password Authentication Key Exchange (PAKE) protocol called Dragonfly, the secret, namely the password, is mapped to an elliptic curve point. This operation is sensitive, as it involves the secret password, and therefore its resistance against side-channel attacks is of utmost importance. Following the initial disclosure of Dragonblood, we notice that this particular attack has been partially patched by only a few implementations.

Machine learning is nowadays increasingly used in cyber-security. While intrusion detection was mainly based on human expertise in the 1990s, learning models to predict attacks are now built from data. However, a large part of the developed learning algorithms hitherto has missed real-world issues, making them unpractical. Indeed, many supervised algorithms described in the literature have been trained and tuned only on the KDD99 dataset. Besides, these algorithms are often static and are unable to automatically adapt for detecting attacks depending on the network traffic. Consequently, we are far from detecting zero-day or more general Advanced Persistent Threats (APT) since only pre-registered and well-characterized attacks can be catched. Some recent systems use unsupervised ML algorithms, but the resulting tools are overly complex: many ML components are stacked with various tuning parameters, usually making the results hard to interpret. And finally, a strong ML/DM expertise is required to set up these systems on real networks. We present netspot, a very simple network intrusion detection system (NIDS) powered by SPOT, a recent streaming statistical anomaly detector. This statistical test uses Extreme Value Theory, which is a powerful method for detecting anomalies. Unlike all the previous works, it is not an end-to-end solution aimed to detect all cyber-attacks with packet resolution. It is rather a module providing a behavioral information which can be integrated in a more general monitoring system. netspot is simple: it has few (simple) parameters, it adapts along time to the monitored network and it is as fast as current rule-based methods. But most importantly, it is able to detect realworld cyber-attacks, making it a credible practical anomaly-based NIDS.

Abstract Division property is a cryptanalysis method that proves to be very efficient on block ciphers. Computer-aided techniques such as MILP have been widely and successfully used to study various cryptanalysis techniques, and it especially led to many new results for the division property. Nonetheless, we claim that the previous techniques do not consider the full search space. We show that even if the previous techniques fail to find a distinguisher based on the division property over a given function, we can potentially find a relevant distinguisher over a linearly equivalent function. We show that the representation of the block cipher heavily influences the propagation of the division property, and exploiting this, we give an algorithm to efficiently search for such linear mappings. As a result, we exhibit a new distinguisher over 10 rounds of , while the previous best was over 9 rounds, and rule out such a distinguisher over more than 9 rounds of . We also give some insight about the construction of an S-box to strengthen a block cipher against our technique. We prove that using an S-box satisfying a certain criterion is optimal in term of resistance against classical division property. Accordingly, we exhibit stronger variants of and , improving the resistance against division property based distinguishers by 2 rounds.

In this paper, we propose a constant-time implementation of the BLISS lattice-based signature scheme. BLISS is possibly the most efficient lattice-based signature scheme proposed so far, with a level of performance on par with widely used pre-quantum primitives like ECDSA. It is only one of the few postquantum signatures to have seen real-world deployment, as part of the strongSwan VPN software suite. The outstanding performance of the BLISS signature scheme stems in large part from its reliance on discrete Gaussian distributions, which allow for better parameters and security reductions. However, that advantage has also proved to be its Achilles' heel, as discrete Gaussians pose serious challenges in terms of secure implementations. Implementations of BLISS so far have included secret-dependent branches and memory accesses, both as part of the discrete Gaussian sampling and of the essential rejection sampling step in signature generation. These defects have led to multiple devastating timing attacks, and were a key reason why BLISS was not submitted to the NIST postquantum standardization effort. In fact, almost all of the actual candidates chose to stay away from Gaussians despite their efficiency advantage, due to the serious concerns surrounding implementation security. Moreover, naive countermeasures will often not cut it: we show that a reasonable-looking countermeasure suggested in previous work to protect the BLISS rejection sampling can again be defeated using novel timing attacks, in which the timing information is fed to phase retrieval machine learning algorithm in order to achieve a full key recovery. Fortunately, we also present careful implementation techniques that allow us to describe an implementation of BLISS with complete timing attack protection, achieving the same level of efficiency as the original unprotected code, without resorting on floating point arithmetic or platform-specific optimizations like AVX intrinsics. These techniques, including a new approach to the polynomial approximation of transcendental function, can also be applied to the masking of the BLISS signature scheme, and will hopefully make more efficient and secure implementations of lattice-based cryptography possible going forward.

As messaging applications are becoming increasingly popular, it is of utmost importance to analyze their security and mitigate existing weaknesses. This paper focuses on one of the most acclaimed messaging applications: Signal. Signal is a protocol that provides end-to-end channel security, forward secrecy, and post-compromise security. These features are achieved thanks to a key-ratcheting mechanism that updates the key material at every message. Due to its high security impact, Signal's key-ratcheting has recently been formalized, along with an analysis of its security. In this paper, we revisit Signal, describing some attacks against the original design and proposing SAID: Signal Authenticated and IDentity-based. As the name indicates, our protocol relies on an identity-based setup, which allows us to dispense with Signal's centralized server. We use the identity-based long-term secrets to obtain persistent and explicit authentication, such that SAID achieves higher security guarantees than Signal. We prove the security of SAID not only in the Authenticated Key Exchange (AKE) model (as done by previous work), but also in the Authenticated and Confidential Channel Establishment (ACCE) model, which we adapted and redefined for SAID and asynchronous messaging protocols in general into a model we call identity-based Multistage Asynchronous Messaging (iMAM). We believe our model to be more faithful in particular to the true security of Signal, whose use of the message keys prevents them from achieving the composable guarantee claimed by previous analysis.

TLS (Transport Layer Security) is a widely deployed protocol that plays a vital role in securing Internet traffic. Given the numerous known attacks for TLS 1.2, it was imperative to change and even redesign the protocol in order to address them. In August 2018, a new version of the protocol, TLS 1.3, was standardized by the IETF (Internet Engineering Task Force). TLS 1.3 not only benefits from stronger security guarantees, but aims to protect the identities of the server and client by encrypting messages as soon as possible during the authentication. In this paper, we model the privacy guarantees of TLS 1.3 when parties execute a full handshake or use a session resumption, covering all the handshake modes of TLS. We build our privacy models on top of the one defined by Hermans et al. for RFIDs (Radio Frequency Identification Devices) that mostly targets authentication protocols. The enhanced models share similarities to the Bellare-Rogaway AKE (Authenticated Key Exchange) security model and consider adversaries that can compromise both types of participants in the protocol. In particular, modeling session resumption is non-trivial, given that session resumption tickets are essentially a state transmitted from one session to another and such link reveals information on the parties. On the positive side, we prove that TLS 1.3 protects the privacy of its users at least against passive adversaries, contrary to TLS 1.2, and against more powerful ones.

Abstract Besides their security, the efficiency of searchable encryption schemes is a major criteria when it comes to their adoption: in order to replace an unencrypted database by a more secure construction, it must scale to the systems which rely on it. Unfortunately, the relationship between the efficiency and the security of searchable encryption has not been widely studied, and the minimum cost of some crucial security properties is still unclear. In this paper, we present new lower bounds on the trade-offs between the size of the client state, the efficiency and the security for searchable encryption schemes. These lower bounds target two kinds of schemes: schemes hiding the repetition of search queries, and forward-private dynamic schemes, for which updates are oblivious. We also show that these lower bounds are tight, by either constructing schemes matching them, or by showing that even a small increase in the amount of leaked information allows for constructing schemes breaking the lower bounds.

In this paper, we analyze several variants of a simple method for generating prime numbers with fewer random bits. To generate a prime p less than x, the basic idea is to fix a constant q ∝ x1-ε, pick a uniformly random a <; q coprime to q, and choose p of the form a + t · q, where only t is updated if the primality test fails. We prove that variants of this approach provide prime generation algorithms requiring a few random bits and whose output distribution is close to uniform, under less and less expensive assumptions: first a relatively strong conjecture by H. Montgomery, made precise by Friedlander and Granville; then the Extended Riemann Hypothesis; and finally fully unconditionally using the Barban-Davenport-Halberstam theorem. We argue that this approach has a number of desirable properties compared with the previous algorithms, at least in an asymptotic sense. In particular: 1) it uses much fewer random bits than both the “trivial algorithm” (testing random numbers less than x for primality) and Maurer's almost uniform prime generation algorithm; 2) the distance of its output distribution to uniform can be made arbitrarily small, unlike algorithms like PRIMEINC (studied by Brandt and Damgård), which we show exhibit significant biases; and 3) all quality measures (number of primality tests, output entropy, randomness, and so on) can be obtained under standard conjectures or even unconditionally, whereas most previous nontrivial algorithms can only be proved based on stronger, less standard assumptions like the Hardy- Littlewood prime tuple conjecture. Note, however, that our analysis involves non-explicit constants, and therefore does not establish the superiority of our approach for concrete parameter sizes.

The CMAC standard, when initially proposed by Iwata and Kurosawa as OMAC1, was equipped with a complex game-based security proof. Following recent advances in formal verification for game-based security proofs, we formalize a proof of unforgeability for CMAC in EasyCrypt. A side effects of this proof are improvements of EasyCrypt libraries. This formal proof obtains security bounds very similar to Iwata and Kurosawa's for CMAC, but also proves secure a certain number of intermediate constructions of independent interest, including ECBC, FCBC and XCBC. This work represents one more step in the direction of obtaining a reliable set of independently verifiable evidence for the security of international cryptographic standards.

Understanding data distributions is one of the most fundamental research topic in data analysis. The literature provides a great deal of powerful statistical learning algorithms to gain knowledge on the underlying distribution given multivariate observations. We are likely to find out a dependence between features, the appearance of clusters or the presence of outliers. Before such deep investigations, we propose the folding test of unimodality. As a simple statistical description, it allows to detect whether data are gathered or not (unimodal or multimodal). To the best of our knowledge, this is the first multivariate and purely statistical unimodality test. It makes no distribution assumption and relies only on a straightforward p-value. Through real world data experiments, we show its relevance and how it could be useful for clustering.

Much of Internet traffic nowadays passes through active proxies, whose role is to inspect, filter, cache, or transform data exchanged between two endpoints. To perform their tasks, such proxies modify channel-securing protocols, like TLS, resulting in serious vulnerabilities. Such problems are exacerbated by the fact that middleboxes are often invisible to one or both endpoints, leading to a lack of accountability. A recent protocol, called mcTLS, pioneered accountability for proxies, which are authorized by the endpoints and given limited read/write permissions to application traffic. Unfortunately, we show that mcTLS is insecure: the protocol modifies the TLS protocol, exposing it to a new class of middlebox-confusion attacks. Such attacks went unnoticed mainly because mcTLS lacked a formal analysis and security proofs. Hence, our second contribution is to formalize the goal of accountable proxying over secure channels. Third, we propose a provably-secure alternative to soon-to-be-standardized mcTLS: a generic and modular protocol-design that care- fully composes generic secure channel-establishment protocols, which we prove secure. Finally, we present a proof-of-concept implementation of our design, instantiated with unmodified TLS 1.3, and evaluate its overheads.

Although postquantum cryptography is of growing practical concern, not many works have been devoted to implementation security issues related to postquantum schemes. In this paper, we look in particular at fault attacks against implementations of lattice-based signatures and key exchange protocols. For signature schemes, we are interested both in Fiat-Shamir type constructions (particularly BLISS, but also GLP, PASSSign, and Ring-TESLA) and in hash-and-sign schemes (particularly the GPV-based scheme of Ducas-Prest-Lyubashevsky). For key exchange protocols, we study the implementations of NewHope, Frodo, and Kyber. These schemes form a representative sample of modern, practical lattice-based signatures and key exchange protocols, and achieve a high level of efficiency in both software and hardware. We present several fault attacks against those schemes that recover the entire key recovery with only a few faulty executions (sometimes only one), show that those attacks can be mounted in practice based on concrete experiments in hardware, and discuss possible countermeasures against them.

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for postquantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to microcontrollers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more traditional side-channel analysis, and describe several attacks that can yield a full key recovery.

The Transport Layer Security (TLS) protocol is designed to allow two parties, a client and a server, to communicate securely over an insecure network. However, when TLS connections are proxied through an intermediate middlebox, like a Content Delivery Network (CDN), the standard endto- end security guarantees of the protocol no longer apply. In this paper, we investigate the security guarantees provided by Keyless SSL, a CDN architecture currently deployed by CloudFlare that composes two TLS 1.2 handshakes to obtain a proxied TLS connection. We demonstrate new attacks that show that Keyless SSL does not meet its intended security goals. These attacks have been reported to CloudFlare and we are in the process of discussing fixes. We argue that proxied TLS handshakes require a new, stronger, 3-party security definition. We present 3(S)ACCEsecurity, a generalization of the 2-party ACCE security definition that has been used in several previous proofs for TLS. We modify Keyless SSL and prove that our modifications guarantee 3(S)ACCE-security, assuming ACCE-security for the individual TLS 1.2 connections. We also propose a new design for Keyless TLS 1.3 and prove that it achieves 3(S)ACCEsecurity, assuming that the TLS 1.3 handshake implements an authenticated 2-party key exchange. Notably, we show that secure proxying in Keyless TLS 1.3 is computationally lighter and requires simpler assumptions on the certificate infrastructure than our proposed fix for Keyless SSL. Our results indicate that proxied TLS architectures, as currently used by a number of CDNs, may be vulnerable to subtle attacks and deserve close attention.

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 according to Chandola, Banerjee and Kumar.

Differential power analysis (DPA) is a side-channel attack in which an adversary retrieves cryptographic material by measuring and analyzing the power consumption of the device on which the cryptographic algorithm under attack executes. An effective countermeasure against DPA is to mask secrets by probabilistically encoding them over a set of shares, and to run masked algorithms that compute on these encodings. Masked algorithms are often expected to provide, at least, a certain level of probing security. Leveraging the deep connections between probabilistic information flow and probing security, we develop a precise, scalable, and fully automated methodology to verify the probing security of masked algorithms, and generate them from unprotected descriptions of the algorithm. Our methodology relies on several contributions of independent interest, including a stronger notion of probing security that supports compositional reasoning, and a type system for enforcing an expressive class of probing policies. Finally, we validate our methodology on examples that go significantly beyond the state-of-the-art.

This paper studies the security of efficient pairing implementations with compressed and standard representations against fault attacks. We show that these attacks solve the Fixed Argument Pairing Inversion and recover the first or second argument of the pairing inputs if we can inject double-faults on the loop counters. Compared to the first attack of Page and Vercauteren on supersingular elliptic curves in characteristic three, these are the first attacks which address efficient pairing implementations. Most efficient Tate pairings are computed using a Miller loop followed by a Final Exponentiation. Many papers show how it is possible to invert only the Miller loop and a recent paper of Lashermes et al. at CHES 2013 shows how to invert only the final exponentiation. During a long time, the final exponentiation was used as a countermeasure against the inversion of the Miller loop. However, the CHES attack cannot be used to invert this step on efficient and concrete implementations. Indeed, the two first steps of the Final Exponentiation use the Frobenius map to compute them efficiently. The drawback of the CHES 2013 attack is that it only works if these steps are implemented using very expensive inversions, but in general, these inversions are computed by using a conjugate since elements at the end of the first exponentiation are unicity roots. If this natural implementation is used, the CHES 2013 attack is avoided since it requires to inject a fault so that the faulted elements are not unicity roots. Consequently, it is highly probable that for concrete implementations, this attack will not work. For the same reasons, it is not possible to invert the Final Exponentiation in case of compressed pairing and both methods (conjugate and compressed) were proposed by Lashermes et al. as countermeasures against their attack. Here, we demonstrate that we can solve the FAPI-1 and FAPI-2 problems for compressed and standard pairing implementations. We demonstrate the efficiency of our attacks by using simulations with Sage on concrete implementations.

Abstract 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.

Softwares use cryptographic algorithms to secure their communications and to protect their internal data. However the algorithm choice, its implementation design and the generation methods of its input parameters may have dramatic consequences on the security of the data it was initially supposed to protect. Therefore to assess the security of a binary program involving cryptography, analysts need to check that none of these points will cause a system vulnerability. It implies, as a first step, to precisely identify and locate the cryptographic code in the binary program. Since binary analysis is a difficult and cumbersome task, it is interesting to devise a method to automatically retrieve cryptographic primitives and their parameters.

Fault attacks are attacks in which an adversary with physical access to a cryptographic device, say a smartcard, tampers with the execution of an algorithm to retrieve secret material. Since the seminal Bellcore attack on modular exponentiation, there has been extensive work to discover new fault attacks against cryptographic schemes and develop countermeasures against such attacks. Originally focused on high-level algorithmic descriptions, these efforts increasingly focus on concrete implementations. While lowering the abstraction level leads to new fault attacks, it also makes their discovery significantly more challenging. In order to face this trend, it is therefore desirable to develop principled, tool-supported approaches that allow a systematic analysis of the security of cryptographic implementations against fault attacks.

We give three new algorithms to solve the “isomorphism of polynomial” problem, which was underlying the hardness of recovering the secret-key in some multivariate trapdoor one-way functions. In this problem, the adversary is given two quadratic functions, with the promise that they are equal up to linear changes of coordinates. Her objective is to compute these changes of coordinates, a task which is known to be harder than Graph-Isomorphism. Our new algorithm build on previous work in a novel way. Exploiting the birthday paradox, we break instances of the problem in time q 2n/3 (rigorously) and q n/2 (heuristically), where q n is the time needed to invert the quadratic trapdoor function by exhaustive search. These results are obtained by turning the algebraic problem into a combinatorial one, namely that of recovering partial information on an isomorphism between two exponentially large graphs. These graphs, derived from the quadratic functions, are new tools in multivariate cryptanalysis.

Hash functions are the swiss army knife of cryptographers. They are used to generate unique identifiers in hash-and-sign signatures, as one-way functions for one-time-password, to break the structure of the input in key derivation functions and also for authentications. We propose a formal analysis of domain extenders for hash functions in the in differentiability framework. We define a general model for domain extenders and provide a unified proof of their security in the form of a generic reduction theorem. Our general model captures many iterated constructions such as domain extenders, modes of operation of symmetric cryptography such as CBC-MAC or block ciphers based on Feistel networks. Its proof has been carried out using the Computational Indistinguishability Logic of Barthe et al.. The theorem can help designers of hash functions justifying the security of their constructions: they only need to bound the probability of well-defined events. Our model allows to consider many SHA-3 finalists and is instantiated on two well-known constructions, namely Chop-MD and Sponge. Finally, the in differentiability bounds which we prove are convincing since they match previous proofs and the application of our result on the sponge construction (underlying the Keccak design) highlights the lack of an additional term in the bound provided by Bertoni et al., as was anticipated but not justified by Bresson et al..

The Camellia block cipher has a 128-bit block length, a user key 128, 192 or 256 bits long and a total of 18 rounds for a 128-bit key and 24 rounds for a 192 or 256-bit key. It is a Japanese CRYPTREC-recommended e-government cipher, a European new European schemes for signatures, integrity and encryption (NESSIE) selected cipher and an ISO international standard. In this study, the authors describe a flaw in the approach used to choose plaintexts or ciphertexts in certain previously published square-like cryptanalytic results for Camellia and give two possible approaches to correct them. Finally, by taking advantage of the early abort technique and a few observations on the key schedule of Camellia, the authors present impossible differential attacks on 10-round Camellia with the FL/FL−1 functions under 128 key bits, 11-round Camellia with the FL/FL−1 functions under 192 key bits, 14-round Camellia without the FL/FL−1 functions under 192 key bits and 16-round Camellia without the FL/FL−1 functions under 256 key bits.

The majority of current attacks on reduced-round variants of block ciphers seeks to maximize the number of rounds that can be broken, using less data than the entire codebook and less time than exhaustive key search. In this paper, we pursue a different approach, restricting the data available to the adversary to a few plaintext/ciphertext pairs. We argue that consideration of such attacks (which received little attention in recent years) improves our understanding of the security of block ciphers and of other cryptographic primitives based on block ciphers. In particular, these attacks can be leveraged to more complex attacks, either on the block cipher itself or on other primitives (e.g., stream ciphers, MACs, or hash functions) that use a small number of rounds of the block cipher as one of their components. As a case study, we consider the Advanced Encryption Standard (AES)-the most widely used block cipher. The AES round function is used in many cryptographic primitives, such as the hash functions Lane, SHAvite-3, and Vortex or the message authentication codes ALPHA-MAC, Pelican, and Marvin. We present attacks on up to four rounds of AES that require at most three known/chosen plaintexts. We then apply these attacks to cryptanalyze an AES-based stream cipher (which follows the leak extraction methodology), and to mount the best known plaintext attack on six-round AES.

In this paper, we study the security of Schnorr based identification and signature schemes. Like the carry attack of Fouque et al. at CHES last year, we exploit the carry knowledge from fault attack on other public-key schemes like DSA and other ECDSA signature scheme, Schnorr and GPS authentication and signature schemes. These attacks can be used to recover very efficiently the secret key and it is worth noticing that the complexity of the attack depends on the equation involving the secret key. We also present different techniques to learn the carry leakage using fault analysis.

In this paper, we study the security of a practical randomness extractor and its application in the TLS standard. Randomness extraction is the first stage of key derivation functions since the secret shared between the entities does not always come from a uniformly distributed source. More precisely, we wonder if the Hmac function, used in many standards, can be considered as a randomness extractor? We show that when the shared secret is put in the key space of the Hmac function, there are two cases to consider depending on whether the key is larger than the block-length of the hash function or not. In both cases, we provide a formal proof that the output is pseudo-random, but under different assumptions. Nevertheless, all the assumptions are related to the fact that the compression function of the underlying hash function behaves like a pseudo-random function. This analysis allows us to prove the TLS randomness extractor for Diffie-Hellman and RSA key exchange. Of independent interest, we study a computational analog to the leftover hash lemma for computational almost universal hash function families: any pseudo-random function family matches the latter definition.

In this paper, we present a new fault attack on elliptic curve scalar product algorithms. This attack is tailored to work on the classical Montgomery ladder method when the $y$-coordinate is not used. No weakness has been reported so far on such implementations, which are very efficient and were promoted by several authors. But taking into account the twist of the elliptic curves, we show how, with few faults (around one or two faults), we can retrieve the full secret exponent even if classical countermeasures are employed to prevent fault attacks. It turns out that this attack has not been anticipated as the security of the elliptic curve parameters in most standards can be strongly reduced. Especially, the attack is meaningful on some NIST or SECG parameters.

The aim of electronic voting schemes is to provide a set of protocols that allow voters to cast ballots while a group of authorities collect the votes and output the final tally. In this paper we describe a practical multi-candidate election scheme that guarantees privacy of voters, public verifiability, and robustness against a coalition of malicious authorities. Furthermore, we address the problem of receipt-freeness and incoercibility of voters. Our new scheme is based on the Paillier cryptosystem and on some related zero-knowledge proof techniques. The voting schemes are very practical and can be efficiently implemented in a real system.