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
dand#upcare 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