Home ::Publications and project dissemination

Publications and project dissemination

  • Post-quantum cryptography: NATO project at the FEI
  • This contribution clearly sends the message about the importance of post-quantum cryptography in a world-wide scale along with concise description of state of the art in the particular field. The article published in the Slovak University of Technology journal informs readers about the involvement of the Institute of Computer Science and Mathematics (Slovak University of Technology) in the NATO research project. It also promotes all participating parties involved in the joint efforts to address the problem of development of security mechanisms resistant against computational power of quantum computers. Latest developments in the field have proven the significance of this topic, thereby direct application of achieved results in the real world is of the project's primary concern.

 

List of publications 

  1. A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log2 n)​
  2. Polynomial structures in code-based cryptography​
  3. RSA Key Extraction​ via Low-Bandwidth Acoustic Cryptanalysis 
  4. A new approach towards the Golomb–Welch conjecture
  5. McEliece PKC Calculator​
  6. Get your hands off my laptop: physical side-channel key-extraction attacks on PCs ​
  7. McEliece PKC Implementation
  8. A note on quantum related-key attacks
  9. Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves
  10. Efficient Software Implementations of Code-based Hash Functions and Stream-Ciphers
  11. Circuits resilient to additive attacks with applications to secure computation
  12. Post-quantum cryptography: NATO project at the FEI
  13. Differential Power Analysis of a McEliece Cryptosystem
  14. Correlation Power Analysis using Measured and Simulated Power Traces based on Hamming Distance Power Model – Attacking 16-bit Integer Multiplier in FPGA
  15. Improving CPA Attack Against DSA and ECDSA
  16. Masking Large Keys in Hardware: A Masked Implementation of McEliece
  17. New GPT cryptosystem based on the (u|u+v)-construction codes
  18. NP-completeness of the coset weight problem for quasi-dyadic codes
  19. Stealing keys from PCs using a radio: cheap electromagnetic attacks on windowed exponentiation
  20. Acoustic cryptanalysis
  21. Get your hands off my laptop: physical side-channel key-extraction attacks on PCs (extended version)
  22. Countermeasure against the SPA Attack on an Embedded McEliece Cryptosystem
  23. A Side-Channel Attack Against the Secret Permutation on an Embedded McEliece Cryptosystem
  24. Weaknesses In Two RFID Authentication Protocols
  25. Applying Grover’s algorithm to AES: quantum resource estimates
  26. Note On Modular Reduction In Extended Finite Fields And Polynomial Rings For Simple Hardware
  27. Computing pth roots in extended finite fields of prime characteristic p ≥ 2
  28. SBS : A Fast and Provably Secure Code-Based Stream Cipher
  29. A Pseudorandom Number Generator Based on Worst-Case Lattice Problems
  30. Extended Security Arguments for Signature Schemes
  31. Critical attacks in code-based cryptography
  32. A Secure Code-Based Authentication Scheme for RFID Systems
  33. Improved RFID Authentication Protocol based on Randomized McEliece Cryptosystem
  34. DPA on the Secure Bit Permutation in the McEliece PKC
  35. CacheBleed: a timing attack on OpenSSL constant time RSA
  36. ECDH key-extraction via low-bandwidth electromagnetic attacks on PCs
  37. Practical Implementation of McEliece Cryptosystem on Android
  38. On Generation of Error Vectors
  39. Physical key extraction attacks on PCs
  40. CacheBleed: a timing attack on OpenSSL constant time RSA
  41. Side Channels in SW Implementation of the McEliece PKC
  42. Overview of the McEliece Cryptosystem and its Security
  43. Quantum circuits for F2n - multiplication with subquadratic gate count
  44. Horizontal and Vertical Side Channel Analysis of a McEliece Cryptosystem
  45. Improved Timing Attacks against the Secret Permutation in the McEliece PKC
  46. On lower bounds for Information Set Decoding over Fq and on the effect of Partial Knowledge

 

  1. A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log2 n)​

Martin Roetteler, Rainer Steinwandt 

Quantum Information & Computation, vol. 14, pp. 888-900, 2014

Abstract  - Improving over an earlier construction by Kaye and Zalka, Maslov et al. describe an implementation of Shor's algorithm which can solve the discrete logarithm problem on binary elliptic curves in quadratic depth O(n^2). In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth O(log^2 n). As technical tools we introduce quantum circuits for GF(2^n) multiplication in depth O(log n) and for GF(2^n) inversion in depth O(log^2 n).

​​​Available at: [http://arxiv.org/abs/1306.1161]

  1. Polynomial structures in code-based cryptography​

Vlad Dragoi, Pierre-Louis Cayrel , Brice Colombier and Tania Richmond

Abstract  - In this article we discus a probability problem applied in the code based cryptography. It is related to the shape of the polynomials with exactly t different roots. We will show that the structure is very dense and the probability that this type of polynomials has at least one coefficient equal to zero is extremelly low. We treated this issue in our research of natural countermeasures to a timing attack against the polynomial evaluation.

​​​Available at: [http://hal.inria.fr/docs/00/86/53/55/PDF/2013_-_Polynomial_structures_in_code-based_cryptography.pdf]

  1. RSA Key Extraction​ via Low-Bandwidth Acoustic Cryptanalysis ​

Daniel Genkin, Adi Shamir, Eran Tromer

Advances in Cryptology - CRYPTO 2014/1 pp. 444-461

Abstract  - Many computers emit a high-pitched noise during operation, due to vibration in some of their electronic components. These acoustic emanations are more than a nuisance: they can convey information about the software running on the computer, and in particular leak sensitive information about security-related computations. In a preliminary presentation, we have shown that different RSA keys induce different sound patterns, but it was not clear how to extract individual key bits. The main problem was that the acoustic side channel has a very low bandwidth (under 20 kHz using common microphones, and a few hundred kHz using ultrasound microphones), many orders of magnitude below the GHz-scale clock rates of the attacked computers. Here, we describe a new acoustic cryptanalysis key extraction attack, applicable to GnuPG's current implementation of RSA. The attack can extract full 4096-bit RSA decryption keys from laptop computers (of various models), within an hour, using the sound generated by the computer during the decryption of some chosen ciphertexts. We experimentally demonstrate that such attacks can be carried out, using either a plain mobile phone placed next to the computer, or a more sensitive microphone placed 4 meters away. Beyond acoustics, we demonstrate that a similar low-bandwidth attack can be performed by measuring the electric potential of a computer chassis. A suitably-equipped attacker need merely touch the target computer with his bare hand, or get the required leakage information from the ground wires at the remote end of VGA, USB or Ethernet cables.

​​​Media coverage of the paper [DOC, PDF]

Available at: [PDF, Web]

  1. A new approach towards the Golomb–Welch conjecture ​

Peter Horak, Otokar Grošek

Abstract  - The Golomb–Welch conjecture deals with the existence of perfect e-error correcting Lee codes of word length n, PL(n, e) codes. Although there are many papers on the topic, the conjecture is still far from being solved. In this paper we initiate the study of an invariant connected to abelian groups that enables us to reformulate the conjecture, and then to prove the non-existence of linear PL(n,2) codes for n ≤ 12. Using this new approach we also construct the first quasi-perfect Lee codes for dimension n = 3, and show that, for fixed n, there are only finitely many such codes over Z.

​​​Available at: [http://dx.doi.org/10.1016/j.ejc.2013.10.010]

  1. McEliece PKC Calculator​

Marek Repka

Journal of Electrical Engineering, 2014, Vol. 65, No. 6, p. 342-348

Abstract  - The original McEliece PKC proposal is interesting thanks to its resistance against all known attacks, even using quantum cryptanalysis, in an IND-CCA2 secure conversion. Here we present a generic implementation of the original McEliece PKC proposal that provides test vectors (for all important intermediate results), and also in which a measurement tool for side-channel analysis is employed. To our best knowledge, this is the first such an implementation. This Calculator is valuable in implementation optimization, in further McEliece/Niederreiter like PKCs properties investigations, and also in teaching. Thanks to that, one can, for example, examine side-channel vulnerability of a certain private key, or one can find out and test particular parameters of the cryptosystem in order to make them appropriate for an efficient hardware implementation. This implementation is available here.

Available at: [http://iris.elf.stuba.sk/JEEEC/data/pdf/6_114-03.pdf]​

  1. Get your hands off my laptop: physical side-channel key-extraction attacks on PCs ​

Daniel Genkin, Itamar Pipman and Eran Tromer

CHES 2014, pp. 242-260

Abstract  - Many computers emit a high-pitched noise during operation, due to vibration in some of their electronic components. These acoustic emanations are more than a nuisance: they can convey information about the software running on the computer, and in particular leak sensitive information about security-related computations. In a preliminary presentation (Eurocrypt'04 rump session), we have shown that different RSA keys induce different sound patterns, but it was not clear how to extract individual key bits. The main problem was the very low bandwidth of the acoustic side channel (under 20 kHz using common microphones, and a few hundred kHz using ultrasound microphones), many orders of magnitude below the GHz-scale clock rates of the attacked computers.

In this paper we describe a new acoustic cryptanalysis key extraction attack, applicable to GnuPG's current implementation of RSA. The attack can extract full 4096-bit RSA decryption keys from laptop computers (of various models), within an hour, using the sound generated by the computer during the decryption of some chosen ciphertexts. We experimentally demonstrate that such attacks can be carried out, using either a plain mobile phone placed next to the computer, or a more sensitive microphone placed 4 meters away.

Beyond acoustics, we demonstrate that a similar low-bandwidth attack can be performed by measuring the electric potential of a computer chassis. A suitably-equipped attacker need merely touch the target computer with his bare hand, or get the required leakage information from the ground wires at the remote end of VGA, USB or Ethernet cables.

​​​Available at: [http://www.cs.tau.ac.il/~tromer/handsoff]

  1. McEliece PKC Implementation

Bitpunch team

Abstract  - Implementation of McEliece PKC by students from FEI STU led by Pavol Zajac. The full code compiles with gcc, there is a makefile available. It depends on openssl (SHA-512 required for paddings). Source code is available here.

  1. A note on quantum related-key attacks

Martin Roetteler and Rainer Steinwandt

Information Processing Letters, vol. 115, no. 1, pp. 40-44, 2015

Abstract  - In a basic related-key attack against a block cipher, the adversary has access to encryptions under keys that differ from the target key by bit-flips. In this short note we show that for a quantum adversary such attacks are quite powerful: if the secret key is (i) uniquely determined by a small number of plaintext-ciphertext pairs, (ii) the block cipher can be evaluated efficiently, and (iii) a superposition of related keys can be queried, then the key can be extracted efficiently.

Available at: [http://www.sciencedirect.com/science/article/pii/S0020019014001719]

  1. Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves

P. Budhathoki and R. Steinwandt

Abstract  - When designing quantum circuits for Shor’s algorithm to solve the discrete logarithm problem, implementing the group arithmetic is a cost-critical task. We introduce a software tool for the automatic generation of addition circuits for ordinary binary elliptic curves, a prominent platform group for digital signatures.The resulting circuits reduce the number of T-gates by a factor 13/5 compared to the best previous construction, without increasing the number of qubits or T-depth. The software also optimizes the (CNOT) depth for GF(2)-linear operations by means of suitable graph colorings.

Available at:

    1. Efficient Software Implementations of Code-based Hash Functions and Stream-Ciphers 

    P.-L. Cayrel, M. Meziani, O. Ndiaye et  Q. Santos

    Proceedings of WAIFI 2014, LNCS xxxx, pages xxx-xxx, Springer-Verlag, 2014

    Abstract  - In this work, we present a survey on software implementations of two families of cryptographic primitives based on the syndrome decoding problem: hash functions and stream ciphers. We have studied dierent algorithms, namely, FSB, SFSB, RFSB, SYND, 2SC and XSYND, and tried to improve their performances as software implementations which are done in C language by Using XMM registers from Streaming SIMD Extensions (SSE). We provide a fair comparison of the implementations of those primitives in the same platform and also give links to the codes we have developed. Although we did not reach the speed given in the paper in some cases, we managed to beat the results of the reference implementations when they are available.

    Available at: [https://docs.google.com/file/d/0B4Cy03-L745ZVkFsRDdrTXh1NFE/edit]

    1. Circuits resilient to additive attacks with applications to secure computation

    Daniel Genkin, Yuval Ishai, Manoj M. Prabhakaran, Amit Sahai, Eran Tromer

    2014 ACM Symposium on Theory of Computing, STOC '14, ACM, 2014, pp. 495-504

    Abstract  -  We study the question of protecting arithmetic circuits against additive attacks, which can add an arbitrary fixed value to each wire in the circuit. This extends the notion of algebraic manipulation detection (AMD) codes, which protect information against additive attacks, to that of AMD circuits which protect computation.

    We present a construction of such AMD circuits: any arithmetic circuit C over a finite field F can be converted into a functionally-equivalent randomized arithmetic circuit • C of size O(|C|) that is fault-tolerant in the following sense. For any additive attack on the wires of C, its effect on the output of C can be simulated, up to O(|C|/|F|) statistical distance, by an additive attack on just the input and output. Given a small tamper-proof encoder/decoder for AMD codes, the input and output can be protected as well.

    We also give an alternative construction, applicable to small fields (for example, to protect Boolean circuits against wire-toggling attacks). It uses a small tamper-proof decoder to ensure that, except with negligible failure probability, either the output is correct or tampering is detected.

    Our study of AMD circuits is motivated by simplifying and improving protocols for secure multiparty computation (MPC). Typically, securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries. We observe that in simple passive-secure MPC protocols for circuit evaluation, the effect of any active adversary corresponds precisely to an additive attack on the original circuit's wires. Thus, to securely evaluate a circuit C in the presence of active adversaries, it suffices to apply the passive-secure protocol to C. We use this methodology to simplify feasibility results and attain efficiency improvements in several standard MPC models.

    Available at: [PDF]

    1. Post-quantum cryptography: NATO project at the FEI 

    ​Pavol Marák

    SPEKTRUM, Journal of Slovak University of Technology, Academic year 2014/2015, Volume XXI., Issue 5

    This contribution clearly sends the message about the importance of post-quantum cryptography in a world-wide scale along with concise description of state of the art in the particular field. The article published in the Slovak University of Technology journal informs readers about the involvement of the Institute of Computer Science and Mathematics (Slovak University of Technology) in the NATO research project. It also promotes all participating parties involved in the joint efforts to address the problem of development of security mechanisms resistant against computational power of quantum computers. Latest developments in the field have proven the significance of this topic, thereby direct application of achieved results in the real world is of the project's primary concern.

    Available at: [http://www.stuba.sk/new/docs//stu/informacie_o/diani_na_stu/spektrum/2015/201505.pdf] [page 10]

    1. Differential Power Analysis of a McEliece Cryptosystem

    ​Cong Chen, Thomas Eisenbarth, Ingo von Maurich, Rainer Steinwandt

    The paper has been accepted for publication in ACNS 2015 proceedings.

    Abstract  - This work presents the first differential power analysis of an implementation of the McEliece cryptosystem. Target of this side-channel attack is a state-of-the-art FPGA implementation of the efficient QC-MDPC McEliece decryption operation as presented at DATE 2014. The presented cryptanalysis succeeds to recover the complete secret key after a few observed decryptions. It consists of a combination of a differential leakage analysis during the syndrome computation followed by an algebraic step that exploits the relation between the public and private key.

    Available at: [https://eprint.iacr.org/2014/534.pdf] 

    1. Correlation Power Analysis using Measured and Simulated Power Traces based on Hamming Distance Power Model – Attacking 16-bit Integer Multiplier in FPGA

    ​Marek Repka, Michal Varchola

    International Journal of Computer Network and Information Security, Vol. 7, No. 6, May 2015, pp. 10-16

    Abstract  - In many cases side channel attacks complexity are estimated by considering attack simulations only. Regarding this estimations, parameters of cryptographic devices are set so the attack is infeasible. This work shows that this approach to secure cryptographic equipment can be dangerous because real attacks can be much better than expected according to simulations. This observation is presented on very generic Correlation Power Attack using Hamming Distance Power Model. This attack is aimed against integer multiplier implemented in FPGA. In cryptography, an integer multiplier power consumption can sometimes be exploited to reveal a secret. Very often it is in asymmetric cryptography that is used in PKI as a fundamental building block. As an example, there are DSA and its various derivations.

    Available at: [http://www.mecs-press.org/ijcnis/ijcnis-v7-n6/IJCNIS-V7-N6-2.pdf] 

    1. Improving CPA Attack Against DSA and ECDSA

    ​Marek Repka, Michal Varchola and Miloš Drutarovský

    Journal of Electrical Engineering, Vol. 66, No. 3, 2015, pp. 159-163

    Abstract  - In this work, we improved Correlation Power Analysis (CPA) attack against Digital Signature Algorithm (DSA) and its various derivations, such as Elliptic Curve Digital Signature Algorithm (ECDSA). The attack is aimed against integer multiplication with constant secret operand. We demonstrate this improvement on 16-bit integer multiplier in FPGA. The improvement makes it possible to guess more blocks of key, and the improvement also eliminates errors of simulated attacks what is very important when approximating attack success rate and complexity based on simulated attacks. We also discus a possible efficient countermeasure. 

    Available at: [http://iris.elf.stuba.sk/JEEEC/data/pdf/3_115-06.pdf] 

     

    1. Masking Large Keys in Hardware: A Masked Implementation of McEliece

    ​Cong Chen, Thomas Eisenbarth, Ingo von Maurich and Rainer Steinwandt

    22nd International Conference on Selected Areas in Cryptography (SAC 2015)

    Abstract  - Instantiations of the McEliece cryptosystem which are considered computationally secure even in a post-quantum era still require hardening against side channel attacks for practical applications. Recently, the first differential power analysis attack on a McEliece cryptosystem successfully recovered the full secret key of a state-of-the-art FPGA implementation of QC-MDPC McEliece. In this work we show how to apply masking countermeasures to the scheme and present the first masked FPGA implementation that includes these countermeasures. We validate the side channel resistance of our design by practical DPA attacks and statistical tests for leakage detection.

    Available at: [SAC 2015 preproceedings]

    1. New GPT cryptosystem based on the (u|u+v)-construction codes

    ​H. Moufek, R. Mahdjoubi, P.-L. Cayrel and K. Guenda

    ICCC 2015, to appear

    Abstract  - In this paper, we construct a new variant of the GPT public key cryptosystem (PKC) to increase the security level. Our cryptosystem is based on a hard problem; the rank syndrome decoding (RSD). This variant presents a construction of matrix-product code by two different types of codes, LRPC (Low Rank Parity Check) codes and PUM (Partial Unit Memory) convolutional codes. Our encryption scheme is with a smaller public key compared to the McEliece variants and some GPT variants.

    Available at: []

     

    1. NP-completeness of the coset weight problem for quasi-dyadic codes

    ​P.-L. Cayrel, K. Diagne and C. T.Gueye

    ICCC 2015, to appear

    Abstract  - Since 1978, the Syndrome Decoding Problem (SDP) was proven to be N P-complete, since then the security of certain cryptographic applications relies on its hardness. In 2009, Matthieu Finiasz has extended this result demonstrating the N P-completeness of certain sub-classes of the SDP. In this paper, we prove the N P-completeness of the Coset Weight Problem for a specific family of codes: the quasi-dyadic codes.

    Available at: []

     

    1. Stealing keys from PCs using a radio: cheap electromagnetic attacks on windowed exponentiation

    Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer

    CHES 2015

    Abstract  -  We present new side-channel attacks on RSA and ElGamal implementations that use the popular sliding-window or fixed-window (m-ary) modular exponentiation algorithms. The attacks can extract decryption keys using a very low measurement bandwidth (a frequency band of less than 100 kHz around carrier under 2 MHz) even when attacking multi-GHz CPUs. We demonstrate the attacks’ feasibility by extracting keys from GnuPG, in a few seconds, using a nonintrusive measurement of electromagnetic emanations from laptop computers. The measurement equipment is cheap and compact, uses readily-available components (a Software Defined Radio USB dongle or a consumer-grade radio receiver), and can operate untethered while concealed, e.g., inside pita bread. The attacks use a few non-adaptive chosen ciphertexts, crafted so that whenever the decryption routine encounters particular bit patterns in the secret key, intermediate values occur with a special structure that causes observable fluctuations in the electromagnetic field. Through suitable signal processing and cryptanalysis, the bit patterns and eventually the whole secret key are recovered.​

    Available at: [PDF, Web]

    1. Acoustic cryptanalysis

    Daniel Genkin, Adi Shamir, Eran Tromer

    Journal of Cryptology, to appear

    Abstract  - Many computers emit a high-pitched noise during operation, due to vibration in some of their electronic components. These acoustic emanations are more than a nuisance: they can convey information about the software running on the computer, and in particular leak sensitive information about security-related computations. In a preliminary presentation (Eurocrypt'04 rump session), we have shown that different RSA keys induce different sound patterns, but it was not clear how to extract individual key bits. The main problem was the very low bandwidth of the acoustic side channel (under 20 kHz using common microphones, and a few hundred kHz using ultrasound microphones), several orders of magnitude below the GHz-scale clock rates of the attacked computers. In this paper we describe a new "acoustic cryptanalysis" key extraction attack, applicable to GnuPG's implementation of RSA. The attack can extract full 4096-bit RSA decryption keys from laptop computers (of various models), within an hour, using the sound generated by the computer during the decryption of some chosen ciphertexts. We experimentally demonstrate such attacks, using a plain mobile phone placed next to the computer, or a more sensitive microphone placed 10 meters away.

    Available at: []

    1. Get your hands off my laptop: physical side-channel key-extraction attacks on PCs (extended version)

    Daniel Genkin, Itamar Pipman, Eran Tromer

    Journal of Cryptographic Engineering, to appear

    Abstract  - We demonstrate physical side-channel attacks on a popular software implementation of RSA and ElGamal, running on laptop computers. Our attacks use novel side channels, based on the observation that the “ground” electric potential, in many computers, fluctuates in a computation-dependent way. An attacker can measure this signal by touching exposed metal on the computer’s chassis with a plain wire, or even with a bare hand. The signal can also be measured at the remote end of Ethernet, VGA or USB cables. Through suitable cryptanalysis and signal processing, we have extracted 4096-bit RSA keys and 3072-bit ElGamal keys from laptops, via each of these channels, as well as via power analysis and electromagnetic probing. Despite the GHz-scale clock rate of the laptops and numerous noise sources, the full attacks require a few seconds of measurements using Medium Frequency signals (around 2 MHz), or one hour using Low Frequency signals (up to 40 kHz). ​

    Available at: [PDF, Web]

    1. Countermeasure against the SPA Attack on an Embedded McEliece Cryptosystem

    M. Petrvalsky, T. Richmond, M. Drutarovsky, P.-L. Cayrel and V. Fischer.

    Proceedings of MAREW 2015, to appear, IEEE, 2015

    Abstract  - In this paper, we present a novel countermeasure against a simple power analysis based side channel attack on a software implementation of the McEliece public key cryptosystem. First, we attack a straightforward C implementation of the Goppa codes based McEliece decryption running on an ARM Cortex-M3 microprocessor. Next, we demonstrate on a realistic example that using a “chosen ciphertext attack” method, it is possible to recover the complete secret permutation matrix. We show that this matrix can be completely recovered by an analysis of a dynamic power consumption of the microprocessor. Then, we estimate the brute-force attack complexity reduction depending on the knowledge of the permutation matrix. Finally, we propose an efficient software countermeasure having low computational complexity. Of course, we provide all the necessary details regarding the attack implementation and all the consequences of the proposed countermeasure especially in terms of power consumption.

    Available at: [PDF]

    1. A Side-Channel Attack Against the Secret Permutation on an Embedded McEliece Cryptosystem

    T. Richmond, M. Petrvalsky and M. Drutarovsky

    TRUDEVICE 2015, Grenoble (France), Mars 2015.

    Abstract  - In this paper, based on a thorough analysis of the state of the art, we point out a missing solution for embedded devices to secure the syndrome computation. We show that this weakness can open the door to a side-channel attack targeting the secret permutation. Indeed, brute-force attack iterations are dramatically decreased when the secret permutation is recovered. We demonstrate the feasibility of this attack against the McEliece cryptosystem implemented on an ARM Cortex-M3 microprocessor using Goppa codes. We explain how to recover the secret permutation on a toy example. Finally, we propose a promising countermeasure, which can be implemented in embedded devices to prevent this attack.

    Available at: [PDF]

    1. Weaknesses in Two RFID Authentication Protocols

    N. Chikouche, F. Cherif, P.-L. Cayrel and M. Benmohammed

    Proceedings of C2SI 2015, LNCS 9084 pages 162-172, LNCS, Springer-Verlag, 2015

    Abstract  - One of the most important challenges related to Radio Frequency Identification (RFID) systems is security. In this paper, we analyze the security and performance of two recent RFID authentication protocols based on two different code-based cryptography schemes. The first one, proposed by Malek and Miri, is based on randomized McEliece cryptosystem. The second one, proposed by Li et al., is based on Quasi Cyclic-Moderate Density Parity Check (QC-MDPC) McEliece cryptosystem. We provide enough evidence to prove that these two RFID authentication protocols are not secure. Furthermore, we propose an improved protocol that eliminates existing weaknesses in studied protocols.

    Available at: [Springer Link]

    1. Applying Grover’s algorithm to AES: quantum resource estimates

    Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt

    Accepted at PQCrypto 2016

    Abstract  - We present quantum circuits to implement an exhaustive key search for the Advanced Encryption Standard (AES) and analyze the quantum resources required to carry out such an attack. We consider the overall circuit size, the number of qubits, and the circuit depth as measures for the cost of the presented quantum algorithms. Throughout, we focus on Clifford+T gates as the underlying fault-tolerant logical quantum gate set. In particular, for all three variants of AES (key size 128, 192, and 256 bit) that are standardized in FIPS-PUB 197, we establish precise bounds for the number of qubits and the number of elementary logical quantum gates that are needed to implement Grover's quantum algorithm to extract the key from a small number of AES plaintext-ciphertext pairs.

    Available at: [to be announced]

    1. Note On Modular Reduction In Extended Finite Fields And Polynomial Rings For Simple Hardware

    Marek Repka

    Journal of Electrical Engineering, Vol. 67 (2016), No. 1, 56-60

    Abstract  - Modular reduction in extended finite fields and polynomial rings is presented, which once implemented works for any random reduction polynomial without changes of the hardware. It is possible to reduce polynomials of whatever degree. Based on the principal defined, two example RTL architectures are designed, and some useful features are noted furthermore. The first architecture is sequential and reduce whatever degree polynomials, taking 2 cycles per term. The second architecture is parallel and designed for reduction of polynomials of 2(t-1) degree at most, taking 1 cycle per the whole reduction.

    Available at: [PDF]

    1. Computing pth roots in extended finite fields of prime characteristic p ≥ 2

    Marek Repka

    Electronics Letters, Volume 52, Issue 9, p. 718 –719, DOI:  10.1049/el.2015.4141

    Abstract  - Direct computation of pth roots in extended finite fields of characteristic p ≥ 2 is introduced, wherein the reduction polynomial is irreducible and can be even random. Proposed method works in any case of p ≥ 2 and finite field extension. This method is the most efficient, it is even more efficient than the method, which is widely used, based on inversion of squaring matrix utilised in the case of p = 2. This method is more efficient regarding the computation and storing of the matrix as well as the computation of the roots.

    Available at: [PDF, Online]

    1. SBS : A Fast and Provably Secure Code-Based Stream Cipher

    P.-L. Cayrel, M. Meziani and O. Ndiaye

    ICCC 2015, pages 137-149

    Abstract  - We propose a new synchronous stream cipher, called SBS, based on iterating a set of Niederreiter’s functions. Our proposal is characterized by a high software performance. Its speed is comparable to the AES encryption in counter mode. It runs at 7.8 cycles per byte. We have performed detailed security analysis, in particular, we prove that the security of SBS is reducible to the syndrome decoding problem. More precisely, we show that distinguishing the keystream generated by SBS is hard as solving an instance of the regular syndrome decoding problem.

    Available at: []

    1. A Pseudorandom Number Generator Based on Worst-Case Lattice Problems

    P.-L. Cayrel, M. Meziani, O. Ndiaye, R. Lindner and R. Silva

    ICCC 2015 and to appear in Applicable Algebra in Engineering, Communication and Computing, 2016

    Abstract  - In this paper we construct a pseudorandom number generator using only worst-case hardness assumptions for standard lattice problems. With a common technique, we can then build a stream cipher by combining the generated pseudorandom sequence with the plaintext. Moreover, as an option to gain efficiency both in terms of speed and memory, we suggest the use of ideal lattices in the construction. Currently, there is no known attack that could exploit this choice. Our implementation for Graphics Processing Units (GPUs) leverages from the parallelism inherent in lattice schemes and reaches performances comparable to the fastest known constructions that enjoy security proofs.

    Available at: []

    1. Extended Security Arguments for Signature Schemes

    Ö. Dagdelen, D. Galindo, P. Véron, M. El Yousfi Alaoui and P.-L. Cayrel 

    Designs, Codes and Cryptography, pages 441-461, 2016

    Abstract  - The well-known forking lemma by Pointcheval and Stern has been used to prove the security of the so-called generic signature schemes. These signature schemes are obtained via the Fiat-Shamir transform from three-pass identification schemes. A number of five-pass identification protocols have been proposed in the last few years. Extending the forking lemma and the Fiat-Shamir transform would allow to obtain new signature schemes since, unfortunately, these newly proposed schemes fall outside the original framework. In this paper, we provide an extension of the forking lemma in order to assess the security of what we call n-generic signature schemes. These include signature schemes that are derived from certain (2n  + 1)-pass identification schemes. We thus obtain a generic methodology for proving the security of a number of signature schemes derived from recently published five-pass identification protocols, and potentially for (2n + 1)-pass identification schemes to come.

    Available at: []

    1. Critical attacks in code-based cryptography

    P.-L. Cayrel, C. T. Gueye, O. Ndiaye and R. Niebuhr

    International Journal of Information and Coding Theory, Vol. 3, No. 2, pages 158-176, 2015

    Abstract  - Code-based cryptographic schemes are promising candidates for post-quantum cryptography since they are fast, require only basic arithmetic, and have a well understood security. While there is strong evidence that cryptosystems like McEliece and Niederreiter are secure, they have certain weaknesses when used without semantic conversions. Critical attacks generally can't be avoided by increasing the key size of several code-based cryptosystems. In this paper we present a survey on critical attacks in code-based cryptography and we propose a specific conversion with a smaller redundancy of data than Korara's et al. and which protects against CCA2. Our purpose is to evaluate three cryptosystems: McEliece, Niederreiter and HyMES. We analyse their security against several models such as: Broadcast, Known Partial plaintext, Message-resend, Related-message, Chosen ciphertext, Lunchtime, Reaction attack and Malleability. Our work follows a first work done by Imai and Kobara 2001 which does not cover the whole known attacks and does not deal with the HyMES scheme.

    Available at: []

    1. A Secure Code-Based Authentication Scheme for RFID Systems 

    N. Chikouche, F. Cherif, P.-L. Cayrel and M. Benmohammed

    International Journal of Computer Network and Information Security, pages 1-9, 2015.

    Abstract  - Two essential problems are still posed in terms of Radio Frequency Identification (RFID) systems, including: security and limitation of resources. Recently, Li et al.'s proposed a mutual authentication scheme for RFID systems in 2014, it is based on Quasi Cyclic-Moderate Density Parity Check (QC-MDPC) McEliece cryptosystem.This cryptosystem is designed to reducing the key sizes.In this paper, we found that this scheme does not provide untraceability and forward secrecy properties. Furthermore, we propose an improved version of this scheme to eliminate existing vulnerabilities of studied scheme. It is based on the QC-MDPC McEliece cryptosystem with padding the plaintext by a random bit-string. Our work also includes a security comparison between our improved scheme and different code-based RFID authentication schemes. We prove secrecy and mutual authentication properties by AVISPA (Automated Validation of Internet Security Protocols and Applications) tools. Concerning the performance, our scheme is suitable for low-cost tags with resource limitation.

    Available at: []

    1. Improved RFID Authentication Protocol based on Randomized McEliece Cryptosystem  

    N. Chikouche, F. Cherif, P.-L. Cayrel and M. Benmohammed

    International Journal of Network Security, Vol.17, No.4, pages 413-422, 2015.

    Abstract  - Among the embedded systems which were quickly developed during the last years and that were used in various domains (e.g. access control, health, ...) we can cite radio frequency identification (RFID). In this paper, we propose an improved mutual authentication protocol in RFID systems based on the randomized McEliece cryptosystem. The McEliece cryptosystem is not only very fast, but it is resistant to quantum computing and it does not require any crypto-processor. Our work includes a comparison between the improved protocol and different existing protocols based on error-correcting codes in terms of security and performance. Security and privacy properties are proved, and the performance of the proposed authentication protocol is analysed in terms of storage requirement, communication cost and computational cost.

    Available at: []

    1. DPA on the Secure Bit Permutation in the McEliece PKC   

    M. Petrvalsky, T. Richmond, M. Drutarovsky, P.-L. Cayrel and V. Fischer

    RADIOELEKTRONIKA 2016, IEEE, to appear

    Abstract  - The segment of post-quantum cryptography rises its importance with increasing improvements in the quantum computing. Cryptographic post-quantum algorithms have been proposed since 1970s. However, side-channel attack vulnerabilities of these algorithms are still in focus of the recent research. In this paper, we present a differential power analysis attack on the McEliece public-key cryptosystem. We demonstrate that a part of a private key, permutation matrix, can be recovered using the power analysis. We attack a software implementation of a secure bit permutation that was proposed by Strenzke et al. at PQCrypto 2008. The cryptosystem is implemented on a 32-bit ARM based microcontroller. We provide details of the attack and results using power consumption measurements of the device. In addition, we outline a novel countermeasure against the introduced attack. The countermeasure uses properties of the linear codes and does not require large amount of random bits which can be profitable for low-cost embedded devices.

    Available at: []​

    1. CacheBleed: a timing attack on OpenSSL constant time RSA 

    Yuval Yarom, Daniel Genkin, Nadia Heninger

    Cryptology ePrint Archive: Report 2016/224

    Abstract  - The scatter-gather technique is a commonly-implemented approach to prevent cache-based timing attacks. In this paper we show that scatter-gather is not constant-time. We implement a cache timing attack against the scatter-gather implementation used in the modular exponentiation routine in OpenSSL version 1.0.2f. Our attack exploits cache-bank conflicts on the Sandy Bridge microarchitecture. We have tested the attack on an Intel Xeon E5-2430 processor. For 4096-bit RSA our attack can fully recover the private key after observing 16,000 decryptions.

    Available at: [online]​

    1. ECDH key-extraction via low-bandwidth electromagnetic attacks on PCs

    Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer

    Proc. RSA Conference Cryptographers' Track (CT-RSA) 2016, LNCS 9610, 219-235, Springer, 2016

    Abstract  -  We present the first physical side-channel attack on elliptic curve cryptography running on a PC. The attack targets the ECDH public-key encryption algorithm, as implemented in the latest version of GnuPG's Libgcrypt.

    Available at: [online]​

    1. Practical Implementation of McEliece Cryptosystem on Android

    Andrej Boledovič and Juraj Varga

    16th Central European Conference on Cryptology (CECC 2016), June 22-24, Piešťany, Slovakia

    Abstract  -  Mobile operating system Android is the most commonly used mobile OS in the world. Since the first version of this OS, Android contains embedded cryptographic library to use by the developers. However, this library does not contain ciphers belonging to so called post-quantum cryptography (PQC). In our work we implemented McEliece algorithm as a representative of PQC in messenger application in OS Android.

    Available at: [online]​

    1. On Generation of Error Vectors

    Otokar Grošek and Viliam Hromada

    16th Central European Conference on Cryptology (CECC 2016), June 22-24, Piešťany, Slovakia

    Available at: [online]​

    1. Physical key extraction attacks on PCs

    Daniel Genkin, Lev Pachmanov, Itamar Pipman, Adi Shamir, Eran Tromer, Yuval Yarom

    Communications of the ACM, vol. 59 no. 6, 70-79, 2016

    Abstract  -  Cryptography is ubiquitous. Secure websites and financial, personal communication, corporate, and national secrets all depend on cryptographic algorithms operating correctly. Builders of cryptographic systems have learned (often the hard way) to devise algorithms and protocols with sound theoretical analysis, write software that implements them correctly, and robustly integrate them with the surrounding applications. Consequentially, direct attacks against state-of-the-art cryptographic software are getting increasingly difficult.

    Available at: [online]​

    1. CacheBleed: a timing attack on OpenSSL constant time RSA

    Yuval Yarom, Daniel Genkin, Nadia Heninger

    proc. Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2016, to appear

    Abstract  -  The scatter-gather technique is a commonly-implemented approach to prevent cache-based timing attacks. In this paper we show that scatter-gather is not constant-time. We implement a cache timing attack against the scatter-gather implementation used in the modular exponentiation routine in OpenSSL version 1.0.2f. Our attack exploits cache-bank conflicts on the Sandy Bridge microarchitecture. We have tested the attack on an Intel Xeon E5-2430 processor. For 4096-bit RSA our attack can fully recover the private key after observing 16,000 decryptions.

    Available at: [online]​

    1. Side Channels in SW Implementation of the McEliece PKC

    Marek Klein

    INFOCOMMUNICATIONS JOURNAL 8.1 (2016): 10-16.

    Abstract  -  The McEliece cryptosystem is considered secure in the presence of quantum computers because there is no known quantum algorithm to solve the problem this cryptosystem is built on. However, naive implementation of the cryptosystem can open side channels, which can be used to gather information about the message or the secret key. In this paper we present results of chosen timing attacks on straightforward implementation of this cryptosystem. Furthermore, we present practical countermeasures and evaluate their efficacy.

    Available at: [PDF]​

    1. Overview of the McEliece Cryptosystem and its Security

    Marek Repka and Pavol Zajac

    Tatra Mt. Math. Publ. 60 (2014), 57–83​

    Abstract  -  McEliece cryptosystem (MECS) is one of the oldest public key cryptosystems, and the oldest PKC that is conjectured to be post-quantum secure. In this paper we survey the current state of the implementation issues and security of MECS, and its variants. In the first part we focus on general decoding problem, structural attacks, and the selection of parameters in general. We summarize the details of MECS based on irreducible binary Goppa codes, and review some of the implementation challenges for this system. Furthermore, we survey various proposals that use alternative codes for MECS, and point out some attacks on modified systems. Finally, we review notable existing implementations on low-resource platforms, and conclude with the topic of side channels in the implementations of MECS.

    Available at: [PDF]​

    1. Quantum circuits for F2n - multiplication with subquadratic gate count

    S. Kepley and R. Steinwandt

    Quantum Information Processing, vol. 14, no. 7, pp. 2373-2386

    Abstract  -  One of the most cost-critical operations when applying Shor’s algorithm to binary elliptic curves is the underlying field arithmetic. Here, we consider binary fields F2n in polynomial basis representation, targeting especially field sizes as used in elliptic curve cryptography. Building on Karatsuba’s algorithm, our software implementation automatically synthesizes a multiplication circuit with the number of T-gates being bounded by 7· nlog2(3) for any given reduction polynomial of degree n = 2N. If an irreducible trinomial of degree n exists, then a multiplication circuit with a total gate count of O(nlog2(3)) is available.

    Available at: [online]​

    1. Horizontal and Vertical Side Channel Analysis of a McEliece Cryptosystem

    C. Chen, T. Eisenbarth, I. von Maurich, and R. Steinwandt

    IEEE Transactions on Information Forensics and Security, vol. 11, no. 6, 1093-1105, 2016

    Abstract  -  This paper presents horizontal and vertical side channel analysis techniques for an implementation of the McEliece cryptosystem. The target of this side-channel attack is a state-of-the-art field-programmable gate array (FPGA) implementation of the efficient quasi-cyclic moderate-density parity-check McEliece decryption operation, as presented at Design, Automation and Test in Europe (DATE) 2014. The presented cryptanalysis succeeds to recover the complete secret key after a few observed decryptions. It consists of a combination of a differential leakage analysis during the syndrome computation followed by an algebraic step that exploits the relation between the public key and the private key.

    Available at: [online]​

    1. Improved Timing Attacks against the Secret Permutation in the McEliece PKC

    D. Bucerzan, P. - L. Cayrel, V. Dragoi and T. Richmond

    Inter. Journal of Computers Communications & Control, 12(1), 7-25, 2016

    Abstract  -  In this paper, we detail two side-channel attacks against the McEliece public-key cryptosystem. They are exploiting timing differences on the Patterson decoding algorithm in order to reveal one part of the secret key: the support permutation. The first one is improving two existing timing attacks and uses the correlation between two different steps of the decoding algorithm. This improvement can be deployed on all error-vectors with Hamming weight smaller than a quarter of the minimum distance of the code. The second attack targets the evaluation of the error locator polynomial and succeeds on several different decoding algorithms. We also give an appropriate countermeasure.

    Available at: []​

    1. On lower bounds for Information Set Decoding over Fq and on the effect of Partial Knowledge

    R.Niebuhr, E. Persichetti, P. - L. Cayrel, S. Bulygin and J. Buchmann

    Inter. Journal of Information and Coding Theory, 2016.

    Abstract  -  In this paper, we detail two side-channel attacks against the McEliece public-key cryptosystem. They are exploiting timing differences on the Patterson decoding algorithm in order to reveal one part of the secret key: the support permutation. The first one is improving two existing timing attacks and uses the correlation between two different steps of the decoding algorithm. This improvement can be deployed on all error-vectors with Hamming weight smaller than a quarter of the minimum distance of the code. The second attack targets the evaluation of the error locator polynomial and succeeds on several different decoding algorithms. We also give an appropriate countermeasure.

    Available at: [online]​