Masking Large Keys in Hardware: A Masked Implementation of McEliece

Cong Chen, Thomas Eisenbarth, Ingo von Maurich, Rainer SteinwandtIACR ePrint 2015 · OpenReview

TL;DR

This paper presents the first hardware implementation of the McEliece cryptosystem that is resistant to side-channel attacks. By employing a novel hybrid masking approach and an on-the-fly mask generation technique, they successfully protect the large secret keys of the QC-MDPC McEliece scheme, rendering previously effective power analysis attacks infeasible.

What Problem Does This Paper Address?

The McEliece cryptosystem is a strong candidate for post-quantum cryptography due to its reliance on problems believed to be hard for quantum computers. However, practical implementations of McEliece, particularly the efficient QC-MDPC variant, are vulnerable to side-channel attacks like Differential Power Analysis (DPA). These attacks can exploit leakage in the physical implementation of the cryptosystem to recover the secret key, undermining its security. Previous work demonstrated a successful DPA attack on an unprotected FPGA implementation of QC-MDPC McEliece, recovering the full secret key. This paper addresses the critical need to secure these post-quantum candidates against such physical threats, especially for hardware implementations where side-channel leakage is a significant concern.

Methods

The core contribution of this paper is the development and implementation of a masked hardware design for the QC-MDPC McEliece decryption process. Key techniques include:

  • Hybrid Masking: A combination of Threshold Implementation (TI)-based Boolean masking for bit operations and arithmetic masking for counters is used to protect sensitive states like the key, syndrome, and intermediate values.
  • On-the-Fly Mask Generation: To efficiently mask the large bit vectors (4801 bits for the secret key), the authors employ a pseudo-random number generator (PRG) based on a Linear Feedback Shift Register (LFSR). This significantly reduces the need for external randomness compared to traditional TI implementations.
  • Masked Syndrome Computation: The linear nature of syndrome computation is exploited by splitting the parity-check matrix and syndrome into shares.
  • Masked Decoder: The non-linear operations within the decoder, specifically the AND and Hamming weight computations, are protected using a three-share TI approach for the AND operation and a secure conversion from Boolean to arithmetic masking for the Hamming weight calculation.
  • Constant-Time Implementation: The design is engineered to have a constant execution flow (except for the number of decoder iterations) to prevent timing-based side-channel attacks.

Datasets

Not discussed in the paper. The evaluation relies on simulated side-channel traces generated from the implemented hardware.

Key Insights and Ideas

  • Masking is Crucial for Post-Quantum Hardware: Even cryptosystems considered secure against theoretical quantum attacks are vulnerable in practice if their hardware implementations are not protected against physical attacks.
  • Hybrid Masking Offers Efficiency: Combining different masking techniques (Boolean and arithmetic) can provide a good balance between security and performance for complex cryptographic algorithms.
  • On-the-Fly Mask Generation is Key for Large Keys: For schemes with very large keys like McEliece, generating masks dynamically rather than pre-computing and storing them is essential for managing resource overhead and randomness requirements.
  • TI is Adaptable: Threshold Implementation, while traditionally associated with symmetric ciphers, can be effectively adapted to protect components of asymmetric cryptosystems like McEliece.
  • The Decoder is the Bottleneck for Masking: While syndrome computation is relatively straightforward to mask, the non-linear operations and control flow within the decoder require more sophisticated masking techniques.

Key Results

  • The paper presents the first masked FPGA implementation of QC-MDPC McEliece decryption.
  • The masked implementation successfully resists DPA attacks that were effective against the unprotected version. Statistical leakage detection tests (Welch's T-test) confirm the indistinguishability of traces for fixed vs. random keys.
  • The masked implementation incurs a significant hardware overhead, using approximately 7.4x more Flip-Flops, 8.2x more LUTs, and 10.5x more slices compared to the unprotected version.
  • The maximum clock frequency is reduced by a factor of 4.3 (from 318 MHz to 73 MHz) due to the increased complexity of the masked logic.
  • The number of clock cycles for syndrome computation and each decoder run remains unaffected, but the overall execution time can increase if early termination is disabled.
  • The on-the-fly mask generation significantly reduces the randomness requirement compared to other TI implementations (160 bits per decryption vs. ~8000 bits per encryption for TI-AES).

Limitations and Future Work

  • Ciphertext Masking: The paper acknowledges that the ciphertext and intermediate values like d and #upc are not masked. While argued to be key-independent, this could potentially reveal information about the error locations, leading to message recovery attacks rather than key recovery. The authors leave exploring SPA-like attacks on these values as an open question.
  • Performance Overhead: The significant increase in hardware resources and the reduction in clock frequency are notable limitations.
  • Future Work: The authors suggest exploring ways to shorten the critical path to improve clock frequency and investigating the potential for key recovery attacks based on information leakage from unmasked ciphertext-dependent variables or the number of decoding iterations.

Summary updated

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.
BibTeX
@article{chen2015masking,
  author = {Cong Chen and Thomas Eisenbarth and Ingo von Maurich and Rainer Steinwandt},
  title = {{Masking Large Keys in Hardware: A Masked Implementation of McEliece}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
  url = {https://openreview.net/forum?id=TxS5zetRt6},
}
Figure