An efficient many-core architecture for Elliptic Curve Cryptography security assessment

Elliptic Curve Cryptography (ECC) is a popular tool to construct public-key crypto-systems. The security of ECC is based on the hardness of the elliptic curve discrete logarithm problem (ECDLP). Implementing and analyzing the performance of the best known methods to solve the ECDLP is useful to assess the security of ECC and choose security parameters in practice. We present a novel many-core hardware architecture implementing the parallel version of Pollard's rho algorithm to solve the ECDLP. This architecture results in a speed-up of almost 300% compared to the state of the art and we use it to estimate the monetary cost of solving the Certicom ECCp-131 challenge using FPGAs. © 2015 Imperial College.

On the Analysis of Public-Key Cryptologic Algorithms

Andrea Miele

The RSA cryptosystem introduced in 1977 by Ron Rivest, Adi Shamir and Len Adleman is the most commonly deployed public-key cryptosystem. Elliptic curve cryptography (ECC) introduced in the mid 80's by Neal Koblitz and Victor Miller is becoming an increasingly popular alternative to RSA offering competitive performance due the use of smaller key sizes. Most recently hyperelliptic curve cryptography (HECC) has been demonstrated to have comparable and in some cases better performance than ECC. The security of RSA relies on the integer factorization problem whereas the security of (H)ECC is based on the (hyper)elliptic curve discrete logarithm problem ((H)ECDLP). In this thesis the practical performance of the best methods to solve these problems is analyzed and a method to generate secure ephemeral ECC parameters is presented. The best publicly known algorithm to solve the integer factorization problem is the number field sieve (NFS). Its most time consuming step is the relation collection step. We investigate the use of graphics processing units (GPUs) as accelerators for this step. In this context, methods to efficiently implement modular arithmetic and several factoring algorithms on GPUs are presented and their performance is analyzed in practice. In conclusion, it is shown that integrating state-of-the-art NFS software packages with our GPU software can lead to a speed-up of 50%. In the case of elliptic and hyperelliptic curves for cryptographic use, the best published method to solve the (H)ECDLP is the Pollard rho algorithm. This method can be made faster using classes of equivalence induced by curve automorphisms like the negation map. We present a practical analysis of their use to speed up Pollard rho for elliptic curves and genus 2 hyperelliptic curves defined over prime fields. As a case study, 4 curves at the 128-bit theoretical security level are analyzed in our software framework for Pollard rho to estimate their practical security level. In addition, we present a novel many-core architecture to solve the ECDLP using the Pollard rho algorithm with the negation map on FPGAs. This architecture is used to estimate the cost of solving the Certicom ECCp-131 challenge with a cluster of FPGAs. Our design achieves a speed-up factor of about 4 compared to the state-of-the-art. Finally, we present an efficient method to generate unique, secure and unpredictable ephemeral ECC parameters to be shared by a pair of authenticated users for a single communication. It provides an alternative to the customary use of fixed ECC parameters obtained from publicly available standards designed by untrusted third parties. The effectiveness of our method is demonstrated with a portable implementation for regular PCs and Android smartphones. On a Samsung Galaxy S4 smartphone our implementation generates unique 128-bit secure ECC parameters in 50 milliseconds on average.

EPFL2015

Computer Aided Cryptanalysis from Ciphers to Side Channels

Martin Vuagnoux

In this dissertation, we study the security of cryptographic protocols and cryptosystems from the mathematical definition of the primitives, up to their physical implementations in the real world. We propose a representation of the chronological design using six layers (cryptographic primitives, cryptographic protocols, implementation, computer insecurity, side channel cryptanalysis and computer human interactions). We do the assumption that these layers should not be studied independently. Indeed, many negligible security weaknesses coming from different layers can be correlated to provide devastating practical attacks on cryptosystems. However, the complexity of a complete security analysis becomes huge and interdisciplinary knowledge is needed. These limitations are probably the reasons of the lack of complete security analysis in practice. We define a novel approach, to combine and study the six layers simultaneously. We propose to follow the data flow of a system and to perform security analysis across the six layers. This technique is applied in practice to the security analysis of computer keyboards, RC4, IEEE 802.11, and e-passports. Thanks to this method, we found 34 additional exploitable correlations in RC4 and we defined the best key recovery attacks on WEP and WPA. We also identified weaknesses in the design and the implementation of e-passports. Therefore, we show that the security risk of every layer seems to be related to its level of complexity. Thus, the implementation layer, the computer insecurity layer, the side channel layer and the computer human interfaces layer are subject to cost-effective attacks in practice. Interestingly, these layers are not intensively studied in cryptography, where research stays usually focused on the two first layers (and some side channel attacks). In this dissertation, we also propose frameworks for computer aided cryptanalysis. Indeed, when the complexity of a system is too important to perform manual analysis, some tools may automatically find weaknesses. Increasing complexity in systems adds new vulnerabilities. Straightforward but automated analysis becomes relevant. Two frameworks have been developed. The first one automatically highlights linear correlation in RC4. The second framework, called Autodafé automatically detects buffer overflows in modern software, using a technique called Fuzzing by Weighting Attacks with Markers.

EPFL2010

Solving 112-bit prime ECDLP on game consoles using sloppy reduction

Joppe Willem Bos, Marcelo Kaihara, Thorsten Kleinjung, Arjen Lenstra

We describe a cell processor implementation of Pollard’s rho method to solve discrete logarithms in groups of elliptic curves over prime fields. The implementation was used on a cluster of PlayStation 3 game consoles to set a new record. We present in detail the underlying single instruction multiple data modular arithmetic.