logo CNRS
logo Cybersecurity Institute
Workshop WRAC'H Workshop on Randomness and Arithmetics for Cryptography on Hardware
logo ANR
Roscoff, France. April 15-19, 2019.
logo Sorbonne
logo UGA

Talks List

Cécile Dumas

TRNG - Evaluation & certification

Abstract: Secure components like smart-cards often include a true random number generator (TRNG) for security needs, in particular cryptography. Evaluating this secure element is an important challenge in the context of products certification, and the evaluation methodology is constantly evolving in last fifteen years.

Today an evaluator has to validate the TRNG physical model provided by the developer; to do so a specific tests suite has to be implemented and the results analysis has to bring to a deep understanding of the stochastic model behavior.

The role of the evaluator is also to highlight the TRNG defects by pushing the target to environmental limits and to verify the product resists to state-of-the-art side-channel and fault injection attacks.
Patrick Haddad

Random number generators: the point of view of a semiconductor company

Abstract: Generation of physical random numbers is a major concern for IOT manufacturers and electronic devices suppliers. When designing and marketing random number generators, manufacturer of electronic components faces 3 challenges.

The most important is to ensure that the output of the generator is unpredictable and contains enough entropy. Thus, the designer shall estimate the amount of disorder contained in the generated number sequence and must ensure that this quantity is sufficient during the full life cycle of the circuit. There are different standardized approaches available in the literature to perform such estimation. These standards are commercial arguments and represent the different criteria of a circuit manufacturer.

The second challenge is to implement the generator in a simple way. Indeed, a random number generator should ideally use the same design and integration process as any other part of a circuit. In addition, in order to optimize their integration with the surrounding components, generator should occupy the smallest possible area and consume low power.

The final objective for a manufacturer of electronic components is to ensure the robustness of the generator against physical attacks by observation or perturbation. It must ensure that the generated numbers cannot be linked with a side channel such as the power consumption or electromagnetic emissions of the circuit. Moreover, the manufacturer must ensure that an attacker cannot thermally or electrically perturb the generator and thus take control of the numbers.

During this presentation, we will present the means, constraints and research axes of a semiconductor company such as STMicroelectronics to meet those 3 main challenges.
Marie-Angela Cornélie

VHDL design of a crypto-processor for elliptic curves

Abstract: The hardware implementation of elliptic curves arithmetic on FPGA must meet performance criteria but also it must take into account the countermeasures for side-channel attacks. In the literature, it is possible to distinguish the different implementations regarding the supporting curves (NIST, generic, Jacobi Quartic, Edwards, ...), the devices (small or big capacity), the computation units used (slices or DSPs).

One possible countermeasure against side-channel attacks is to work with curves where addition and doubling can be performed with the same formulae. In this way, the analysis of the execution of the scalar multiplication does not directly reveal the processed operations. One solution is to work with Jacobi Quartic curves.

In order to increase the performance of the design, the most critical operation has to be optimized. For elliptic curves defined on finite fields, the operation rely on the modular arithmetic of the base field. According to the chosen representation, the most costly operation is either the multiplication or the division. Moreover, the performances are also mainly influenced by the way the finite field elements are represented.

Apart from the classical elliptic curves operation (addition, doubling, scalar multiplication), the pairings also involve modular computations. However, they are performed on extensions of the base field. In some cases, the conversion from Weierstrass form to Jacobi Quartic form is only possible on a cubic extension. Therefore, the design has to take into account the optimization of the extensions implementations.

In this context, we present implementations on FPGA of a fast modular arithmetic using DSPs. Our design exploits the parallelization of all implemented algorithms in order to have a fast execution even when working on extension fields.
Eleonora Cagli

Improved Deep-Learning Side-Channel Attacks using Normalization layers

Abstract: Cryptographic integrated circuits may be vulnerable to attacks based on the observation of information leakages conducted during the cryptographic algorithms' executions, the so-called Side-Channel Attacks. Nowadays the presence of several countermeasures may lead to the acquisition of signals which are at the same time highly noisy, forcing an attacker or a security evaluator to exploit statistical models, and highly multi-dimensional, letting hard the estimation of such models. In this talk we reformulate a Side-Channel Attack as a classification problem, for which the deep learning literature is flourish. Deep artificial neural networks are powerful tools that allow to extract significant features and estimate useful models from potentially huge datasets of high-dimensional, highly noisy data. We apply deep learning techniques to attack cryptographic implementations that are protected by jitter-based countermeasures, implying acquired signals that are not synchronous. In this context we exploit Convolutional Neural Networks to perform the attack, showing that the obtained strategy is effective even in presence of desynchronization. Moreover, we equip the training with some specialized Data Augmentation techniques to reduce the overfitting phenomenon and raise the attack performances.
Annelie Heuser

Profiled side-channel analysis revisited

Abstract: The core problem faced in side-channel analysis can be translated into common problems given in classical tasks for machine learning. It is therefore natural to use and exploit standard machine learning techniques to reveal sensitive data using side-channel information. In this talk, we will discuss recent advances made in the field of side-channel analysis using machine learning and deep learning techniques. This includes reshaping the underlying side-channel scenario with semi-supervised techniques, discussing evaluation metrics, and enhancing side-channel classification techniques. Finally, in this talk, we will discuss if the commonly used evaluation framework is actually suitable given attacks from machine learning and we will propose another strategy to evaluate profiled side-channel analysis.
Houssem Maghrebi

A recent line of research has investigated new profiling technique based on deep learning as an alternative to the well-known template attack.

Abstract: The advantage of this new profiling approach is twofold: (1) the approximation of the information leakage by a multivariate Gaussian distribution is relaxed (leading to a more generic approach) and (2) the pre-processing phases such as the traces realignment or the selection of the Points of Interest (PoIs) are no longer mandatory, in some cases, to succeed the key recovery (leading to a less complex security evaluation roadmap).

The related published works have demonstrated that deep learning based profiled attacks were very efficient when targeting cryptographic implementations protected with the most common side-channel countermeasures such as masking, jitter and random delays insertion.

In this paper, we tried to assess the efficiency of this new profiled attack under different realistic and practical scenarios.

First, we studied the impact of the noise, the dimensionality of the attack's area of interest and the complexity of the leakage function on the robustness of the attack.

We demonstrated that the deep learning techniques are sensitive to these parameters and we proposed some practical recommendations that can be followed to enhance the profiling and the key recovery phases.

Second, we targeted a more complex masking scheme based on Shamir's secret sharing and proved that this new profiling approach performs well.

Finally, we conducted a security evaluation of a batch of several combinations of side-channel protections using simulations and real traces captured on real devices.

The experimental results confirmed that deep learning based attack is a very efficient alternative to the state-of-the-art profiling attacks.
Damien Robissout

Improved Deep-Learning Side-Channel Attacks using Normalization layers.

Abstract: Recent papers used deep neural networks to improve profiled side-channel attacks. The networks were efficient even in the presence of countermeasures such as masking and de-synchronization. Nevertheless, tuning networks to perform specific tasks is difficult and there is still room for improvement. One of such improvements takes the form of normalization. Batch normalization is a well-known technique in the machine learning community to prevent the network from overfitting. In our work, using the ASCAD database, we test the addition of batch normalization layers and compare the results against the existing networks. Our experimental results cleary show that we significantly improve the attacks by reducing the number of traces needed to retrieve the key to about 1000 no matter the de-synchronization.
Ramtine Tofighi

Using Machine Learning to defeat software protection
Guenael Renault

ROCA Returns ! Where Entropy is Not the Only Problem To Consider!
Werner Schindler

Security Evaluation of Physical RNGs
pdf available here
Jean-Luc Danger and Sylvain Guilley

Analysis of Mixed PUF-TRNG Circuit Based on SR-Latches in FD-SOI Technology

Abstract: An SR-latch can be regarded as primitive to build a True Random Number Generation (TRNG) or Physically Unclonable Function (PUF). Indeed, when the SR inputs of the latch are tied together and go from an unknown state (i.e. S=R=1) to a memory state (i.e. S=R=0), the behaviour depends on the balance between the NAND or NOR gates composing the latch. With the process mismatch, there is a great chance that the latch converges towards the same state, thus creating a PUF equivalent to a SRAM-PUF or latch-PUF.

However, if the latch is well-balanced, it can enter a metastable state and converges to a stable state depending on the input noise, thus making a TRNG. In order to make sure some latches are able to behave like a TRNG, and some like a PUF, we consider a set of latches driven by the same SR signal. A test-chip in 28nm UTBB-FD-SOI technology has been designed with 1024 latches in order to analyze the behavior. The FD-SOI technology enables easy change of the performances of gates using the body biasing, which consists in applying a specific body voltage to each gate. Hence, the two NOR gates composing the SR-latch can be tuned individually to get the optimality, i.e. the maximum entropy, for both PUF and TRNG.

The results show that the optimal point is the same for both PUF and TRNG, and that the proposed structure can generate concurrently a PUF with high reliability, and a TRNG with high speed.
Nicolas Bruneau, Sylvain Guilley and Adrien Facon

Automatic derivation of optimal side-channel attacks rounded at a given order

Abstract: Masking countermeasure against side-channel attacks consists in randomly sharing sensitive variables. Therefore, such protections consume a lot of randomness (which must be balanced, independent, etc.). Today, many masking protections are constructively designed to be dth-order secure. The parameter d0 is a design security metric whereby each tuple of strictly less than d shares is independent from the clear sensitive variables.

For masking schemes such as Ishai-Sahai-Wagner (CRYPTO 2003) or Rivain-Prouff (CHES 2010), the security proof is based on composability: it is possible to design widgets for basic operations, e.g., field addition and multiplication, forming a universal set. Subsequently, combining them allows to build arbitrary computations.

Reuse of variables shall be dealt with cautiously. In practice, reused variables usually benefit from refresh.

There is one venue of research which consists in checking a complete implementation (Barthe et al., EUROCRYPT 2015). Since the combinatorics of verification is large, the proof employs heuristics taylored for the masking scheme.

Now, in practice, the attacker must perform a dth-order attack. But the attacker will maximize its advantage, and so she is not expected to be satisfied by one combination of d shares. Here we face a paradox: the larger the order d, the more possible combinations, hence it is relevant to study whether in practice, the security level in terms of data complexity (number of traces to recover the key) is still increasing with parameter d.

In this paper, we show how to compute optimal attacks, with tradeoffs regarding data and computational complexities (as in Bruneau et al., J. of Cryptology 2018). We aim at analyzing real-world implementations, irrespective of the source language they are coded in. Moreover, we want to consider optimized code. For this reason, we analyze the intermediate representation generated by a compiler, and generate the formula for the multivariate high-order distinguisher after having simplified the terms.

Results show that monovariate high-order attacks are underestimating the security level by orders of magnitude, especially when the noise level is high.

pdf available here
Timo Zijlstra, Karim Bigou and Arnaud Tisserand

Countermeasures against physical attacks on ring-LWE encryption schemes

Abstract: In 2016 the NIST launched a standardization project for post quantum public key encryption and digital signatures. More than half of the PKE/KEM submissions that made it to the second round are based on the hardness of lattice problems such as Learning with Errors (LWE) and NTRU. We consider the ring-LWE based encryption scheme and discuss the robustness of its decryption function against adversaries that exploit side channel observations. An attacker may try to recover the secret key by correlating power measurements with hypotheses on secret key values. To prevent these side channel attacks, several countermeasures have been proposed. Randomization of input ciphertexts and secret keys can be used to reduce the correlation between the side channel observations and the secret key.

There are various techniques to obtain such a randomization. Examples include the masking scheme by Reparaz et al. and shifting and blinding methods proposed by Saarinen. We also discuss the use of redundant number representation to randomize the computations.
Aurore Guillevic

A comparison of pairing-friendly curves at the 192-bit security level

Abstract: Pairings on elliptic curves are involved in signatures, NIZK, and recently in blockchains (ZK-SNARKS). These pairings take as input two points on an elliptic curve E over a finite field, and output a value in an extension of that finite field. Usually for efficiency reasons, this extension degree is a power of 2 and 3 (such as 12,18,24), and moreover the characteristic of the finite field has a special form. The security relies on the hardness of computing discrete logarithms in the group of points of the curve and in the finite field extension.

In 2013-2016, new variants of the function field sieve and the number field sieve algorithms turned out to be faster in certain finite fields related to pairing-based cryptography. Now small characteristic settings (with GF(2(4n)), GF(3(6m))) are discarded, and the situation of GF(pk) where p is prime and k is small (in practice from 2 to 54) is unclear.

The asymptotic complexity of the Number Field Sieve algorithm in finite fields GF(pk) (where p is prime) and its Special and Tower variants is given by an asymptotic formula of the form A(c+o(1)) where A depends on the finite field size (log pk), o(1) is unknown, and c is a constant between 1.526 and 2.201 that depends on p, k, and the choice of parameters in the algorithm.

In this talk, we adapt to higher k previous works that refine the approaches of Menezes-Sarkar-Singh and Barbulescu-Duquesne to estimate the cost of a hypothetical implementation of the Special-Tower-NFS in GF(pk) for small k. We consider the 192-bit security level and update the parameter sizes for pairing-based cryptography with k in {12,16,18,24}. Then we compare the pairing efficiency on these curves. If time allows it, we will also consider embedding degrees 15, 21, 27.

pdf available here
Laurent Imbert

Faster cofactorization with ECM using mixed representations

pdf available here
Vincent Zucca

Application of RNS in the context of homomorphic encryption
Nicolas Meloni

Euclidean Addition Chains Scalar Multiplication on Curves with Efficient Endomorphism
Thomas Espitau

Physical Attacks on Lattice based Signature
Jerome Courtois

Evaluation of Resilience of randomized RNS implementation
Antoine Joux

Fully homomorphic encryption modulo Fermat numbers
Thomas Plantard

SPA resistant Exponentiation based on Brun's GCD algorithm
Paulo Martins and Leonel Sousa

Building Algorithm-Hiding FHE Systems from Exotic Number Representations

Abstract: Cloud computing providers maintain shared high-performance servers that are used by their clients as necessary. However, as attacks such as Meltdown and Spectre have shown, traditional isolation mechanisms are not sufficient to guarantee neither the secrecy of data nor the privacy of processing algorithms. With Fully Homomorphic Encryption (FHE), data may be processed encrypted in the cloud, making any leaked information look random to an attacker. While there has also been research on ensuring the confidentiality of the processing algorithm, this type of systems tries to emulate a computer architecture homomorphically, leading to impractical results. Rather than considering that FHE should offer the properties of a general-purpose processor, the most adequate number representations and their properties are herein investigated to achieve efficient domain-specific processors.

More concretely, stochastic number representations and fixed-point arithmetic are considered, each with its own characteristics. Based on these representations, systems are proposed that allow to approximate a wide range of functions in a generic way, producing an encrypted description of them. In particular, we focus on functions whose approximation may be efficiently evaluated in an homomorphic manner, namely multivariate continuous functions, which might even be non-analytic, thus going beyond traditional Taylor series-based approaches. When processing the encrypted function descriptions, the homomorphic evaluator is not able to infer anything from the function except for how precisely it is being approximated.

By having a larger number of functions that can be supported, security is being improved, since the amount of possibilities for the function that is being processed is also large. Moreover, since the algorithm inputs are encrypted, data disclosure is also prevented. As a byproduct, we achieve a mechanism to automatically translate the user code to the encrypted approximated descriptions. The translation treats the function in a black-box approach, which means that the user does not need to change his typical development flow, and that he or she can call other functions, use complex control flows, etc. Finally, a prototype of the system is presented, its applicability is verified in practice for commonly used applications, including image processing and machine learning, and the two aforementioned number representations are thoroughly compared.

pdf available here
Christophe Nègre

Regular Modular Exponentiation and Scalar Multiplication over Hyperelliptic Curves using Base Splitting

Abstract: Public key cryptosystems like RSA or (H)ECC can be threaten by side channel analysis when they are implemented on an embedded device. Such attacks monitor either the computation time, the power consumption or the electromagnetic emanation in order to extract part of the secret key. For example in the simple power analysis (SPA), the attacker can decompose the power trace into a the sequence power trace of operations in the underlying group. If these sequence of operations are correlated to the key the attacker can deduce part of the the secret key.

The basic approach to render an exponentiation immune to SPA analysis consists to have a sequence of operations uncorrelated to the secret key. In this talk we will present some recent improvements on such regular exponentiation for RSA and scalar multiplication on hyperelliptic curve. These approaches use a splitting of the base element into two equal parts, and then take advantage of this splitting to reduce the cost of the square-and-multiply-always (resp. double-and-add-always) approach for regular exponentiation in RSA (resp. scalar multiplication on hyperelliptic curve).
Jean-Marc Robert, Christophe Negre and Thomas Plantard

Enhanced Digital Signature using Splitted Digit Exponent Representation

Abstract: Digital Signature Algorithm (DSA) involves modular exponentiation, of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers. However, due to the cost of the memory, to its small size and to the latency of access, previous research sought for minimization of the storage.

In this paper, taking into account the modern processor features and the growing size of the cache memory, we improve the storage/efficiency trade-off, by using a RNS Digit exponent representation. We then propose algorithms for modular exponentiation. The storage is lower for equivalent complexities for modular exponentiation computation.

The implementation performances show significant memory saving, up to 3 times for the largest NIST standardized key sizes compared to state of the art approaches. This work has been presented at WAIFI 2016 conference. We extend this approach to the Elliptic Curve Scalar Multiplication with another multiplicative digit approach we call R-splitting, providing side-channel resistance.

pdf available here
Viktor Fischer

(New) challenges in random number generation for cryptography

Abstract: In this talk, we will discuss the main research problems to be solved in the domain of random number generation in logic devices, which are commonly used for implementation of cryptographic systems in hardware.

Starting with the discussion about "good" and "bad" sources of randomness in logic devices, we will compare the most common methods of randomness extraction: sampling of random signals vs counting of random events. Next, we will discuss importance of stochastic models of sources of randomness and of the generator itself in the context of security guarantees. Security will be leading evaluation criterion also in the remaining parts of the talk in which we will discuss the choice of embedded statistical tests. We will stress importance of evaluation of functionality and efficiency of the proposed embedded statistical tests. We will underline necessity of testing of the whole generator datapath, which is not explicitly required by current standards.

All along the talk, we will analyze the above mentioned problems from the point of view of the two current security standards in this domain: BSI AIS20/31 and NIST SP 800-90B.
Titouan Coladon, Ph. Elbaz-Vincent, Etienne Marcatel, Cyril Hugounenq

Hermitian fplll and applications
Titouan Coladon, Philippe Elbaz-Vincent and Cyril Hugounenq

MPHELL: a fast and robust library with unified arithmetic for elliptic curves cryptography

Abstract: We propose a new versatile ECC library based on unified arithmetics with a focus on protection against simple power analysis and an abstract layer for easy customisations. It has been extensively tested on x86-64, ARM 32bits and STM32 architectures and also in real-world applications.

Our library has the advantage to propose standard elliptic curves (all those from fips186-4) but gives also the possibility to use curves in different settings such as Weierstrass form in co-Z coordinates, Jacobi quartic or Edwards forms (as well as their associated conversions functions).

The number arithmetic used in MPHELL is inherited from GMP and has some improvement using Montgomery representation and windowing techniques.

Part of this library and the mathematics behind it were described in the thesis of Cornelie.

We present some comparative ECDSA signatures timings for different elliptic curves without taking into account specificity of the curves in our library (as opposed to OpenSSL for instance).

To illustrate the abstraction layer for ground fields and curves, we will also show implemantations based on randomized arithmetic.

Our library will be released under LGPL v3 This work is supported by ANR-15-IDEX-02, ANR ARRAND (ANR-15-CE39-0002) and SECURIOT-2-AAP FUI 23.

pdf available here
Philippe Elbaz-Vincent, Cyril Hugounenq and Sebastien Riou

SPAE: An authenticated encryption algorithms for low-cost embedded systems

Abstract: We propose a new block-cipher mode of operation, called SPAE, for authenticated encryption with associated data (AEAD). This mode is specifically designed toward embedded systems and industrial applications but is nevertheless patent-free. The algorithm has been developped to address the needs of a growing trend in IoT systems: storing an application processor's code and data on a low cost flash memory. Existing AEAD algorithms, such as OCB, GCM, CCM, EAX, SIV, provide the required functionality however in practice each of them suffer from various drawbacks for this particular use case.

SPAE is a generic construction around a block cipher providing both authentication and privacy in a single pass. We present also security statements that apply to this scheme responding to some industrial needs (in particular nonce misuse resistance). The cipher AES was used for concrete implementations and timings for several low-cost hardware platforms used in IoT industry show that AES-SPAE is over two times faster than AES-GCM.

pdf available here
Lucas Barthelemy

Binary Permutation Polynomial Inversion and Application to Obfuscation Techniques
Damien Vergnaud

Secure Outsourcing of Group Exponentiations

Abstract: Cryptographic operations are performed everywhere, from standard laptop to smart cards. Some devices computational resources can be very limited and it is natural to delegate costly operations to another device capable of carrying out cryptographic algorithms. In this setting, it is obviously important to ensure the limited device that the computation is carried out correctly and that the powerful device does not learn anything about what it is actually computing (including the secret inputs and outputs).

In this talk, we review the recent advances on secure outsourcing of group exponentiation (in groups of known prime order as well as in groups of unknown order). We notably present recent efficient constructions, cryptanalytic results and efficiency lower bounds.
Nadia El Mrabet

Randomness as countermeasures against Side Channel Attacks
Yssouf Dosso

Efficient and secure modular operations using the Polynomial Modular Number System, Part 1
Jeremy Marrez

Efficient and secure modular operations using the Polynomial Modular Number System, Part 2
Ph. Elbaz-Vincent and Mohamed Traoré

Generating RSA keys the wrong way!