Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Arithmetic Protections Against Physical Attacks for Elliptic Curve based Cryptography – PAVOIS

Arithmetic Protections Against Physical Attacks for Elliptic Curve based Cryptography

Study and design of new arithmetic algorithms for elliptic curve cryptography (ECC) on hardware and software implementations.

Arithmetic protections

This project involves studying arithmetic solutions that combine performance efficiency and resistance to hidden channel physical attacks for crypto-based elliptic curve (ECC) systems on platforms based on FPGA or ASIC circuits and on multicore processors. An important objective is to study theoretically and practically evaluate the impact of number representations and arithmetic algorithms used to protect some ECC calculations on performance (eg, speed, throughput, latency) and the cost of (Eg silicon surface, memory required, energy consumed) for different levels of theoretical security and resistance to physical attacks by observation or disturbance (eg, simple or differential analysis, injection of Mistakes). We have studied these aspects for different finite field arithmetic used in ECC (GF (p) and GF (2)), storage and manipulation of secret keys (scalars). We have also studied the behavior of certain solutions in the framework of hyper-elliptic curve-based cryptography (HECC).

The main techniques proposed, studied, implemented, evaluated and compared are:

Proposition of arithmetic algorithms and their hardware (FPGA and ASIC) or software implementations (eg parallel on multicore processors) that integrate internal protections against certain attacks by uniformization or «randomization« of calculations in finite-field arithmetic by providing gains in efficiency over the state of the art (eg modular representations of numbers or RNS);

Use of advanced number representations that allow mathematical protection of the secret keys manipulated in the circuit / processor (while ensuring the correct behavior of the calculations), p. ex. We have used redundant representations, additions-chain representations, and multiple base representations (eg, bases (2 and 3 simultaneously) or (2, 3 and 5 simultaneously) instead of simple base 2 used in the community);

Study and development of a configurable hardware architecture at the time of conception and of its development tools for ECC and HECC which will be distributed in hardware / free software after the final version publications ASIC of our cryptoprocessor manufacturing income at foundry on January 19, 2017 after several months of delay in the foundry.

Arithmetic algorithms for ECC on multicore. The main objective is to use the multiple cores as well as possible to parallelize the usually sequential calculations and to «break« the dependency (direct or statistical) between the traces measured and the secrets.

Modular Representation of Numbers (RNS). RNS makes it possible to parallelize naturally some operations (+, -, *) by decomposing the large numbers into small elements modulo a base of moduli. But for other operations, such as modular reduction, the fact that RNS is not a positional number system complicates things substantially. We proposed a set of arithmetic algorithms and modifications of the RNS representation much more efficient than the conventional techniques.

Attacks by side channels and countermeasures. We used attacks by observation of energy consumption or electromagnetic radiation to evaluate how some arithmetic calculations behave. In particular, the RNS representation with a «randomization« of the addresses of memory seems to offer a good level of robustness.

Secure hardware layout of crypto-ECC systems. We proposed arithmetic operators which are naturally robust to certain attacks (they exhibit either uniform or random activity over time, these two aspects can even be mixed). We have also installed, for the first time, totally in hardware scalar recoding techniques.

Implementation of a hardware architecture for cryptography on hyper-elliptic curves.

Realization of an ASIC prototype of 256 bit ECC circuit. We designed, completely by ourselves, a digital integrated circuit of prototype dedicated to ECC.

The perspectives on multicore ECC implementations are to try to see how to do both parallel calculations on several cores of the calculations at the curved and finite levels and those relating to the recoding of scalars on machines with many cores (machines of type Manycore).

For RNS, and our variants of representation, we target to study the development of a large-scale hardware prototype. We think this research axis is very promising for asymmetric cryptography (and not just ECC / HECC).

The stakes are numerous for attacks and countermeasures: try to mount attacks mixing learning and templates to aim for behaviors mathematically more complex than the usual statistical dependencies; Propose algorithmic countermeasures based on the randomization of internal calculations (in non-critical paths in terms of dependencies); Propose countermeasures at architecture and circuit levels compatible with advanced arithmetic uses (algorithms and representations).

We will continue to try to find new ideas to further accelerate basic calculations in algorithms, number representations, architectures and implementations (eg multiple modular multiplications to increase the parallelism of architectural instructions). Our expertise on this subject is recognized in the community.

We have a first HECC architecture that shows about 40% better compromise time * surface compared to ECC (under the same test conditions). The work begun in the PAVOIS project is continuing in the HAH project and we hope to gain a factor of about 2 in the end. We wish to continue this work on HECC in hardware in the future.

A dedicated web page ( lists all the productions and publications of the PAVOIS project and links on their contents (publicly accessible for the vast majority). The report includes:

• 2 theses supported and financed by the PAVOIS project;

• 6 articles in leading international journals such as IEEE Transactions on Computers;

• 21 articles in renowned international conferences, some of which are major in our fields such as ARITH, AsiaCrypt, Async, CHES, ECC or ISVLSI;

• 3 articles in national conferences;

• 3 invited lectures, 2 of them international;

• 1 hardware cryptoprocessor and its development tools which will be distributed in hardware / free software;

- 1 ASIC integrated circuit of our cryptoprocessor ECC (256 bit version) unfortunately returned from foundry after the administrative end of the project.

The main objective of this proposal is the design and distribution of an open source hardware (FPGA/ASIC), together with the programming tools and
documentations, dedicated to efficient and secure curve-based cryptography. We shall study the impact of novel protection schemes against various kind of side-channel attacks, in particular we will assess the robustness of countermeasures based on non-conventional, redundant arithmetic schemes. Another ambitious objective of our proposal if the extension of our FPGA processor to handle all the arithmetic operations required for implementing the cryptosystems based on hyperelliptic curves. On the practical side, we will design innovative cryptographic hardware architectures of a specific processor based on the theoretical advancements described above to implement curve based protocols. We will target efficient and secure implementations for both FPGA an ASIC circuits. A specific part of the budget will be devoted to ASIC implementation (foundry) of the processor. After test and validation of the circuit, we plan to distribute some samples of the circuit to a few french research groups in academy and government organisations for collaborations.

Project coordinator

Monsieur Arnaud TISSERAND (CNRS / Institut de recherche en informatique et systèmes aléatoires) –

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


LIRMM - DALI Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
CNRS / IRISA CNRS / Institut de recherche en informatique et systèmes aléatoires

Help of the ANR 348,868 euros
Beginning and duration of the scientific project: August 2012 - 42 Months

Useful links

Sign up for the latest news:
Subscribe to our newsletter