Classic McEliece on the ARM Cortex-M4

Ming-Syan Chen⋆, Tung ChouIACR 2021 · DOI

TL;DR

This paper presents the first constant-time implementation of the Classic McEliece post-quantum cryptography scheme on the resource-constrained ARM Cortex-M4 microcontroller. By cleverly storing the large public key in flash memory, they achieve surprisingly efficient performance, outperforming other schemes like FrodoKEM significantly.

What Problem Does This Paper Address?

The advent of quantum computers poses a significant threat to current public-key cryptography (like RSA and ECC). To counter this, the National Institute of Standards and Technology (NIST) is standardizing post-quantum cryptography (PQC) algorithms. Classic McEliece is a leading candidate, known for its strong security guarantees derived from its code-based construction. However, a major hurdle for its adoption, especially in embedded systems, is its notoriously large public key size. The target platform, an STM32F4-Discovery board, has very limited SRAM (192 KB), which is insufficient to even store the smallest Classic McEliece public keys. This paper tackles the challenge of making Classic McEliece practical on such constrained devices.

Methods

The core of the paper is a highly optimized, constant-time implementation of Classic McEliece for the ARM Cortex-M4. Key techniques include:

  • Flash Memory Storage: Recognizing the SRAM limitation, the authors store the public key in the larger flash memory (1 MB) available on the STM32F4-Discovery board. This is a crucial adaptation for embedded deployment.
  • Constant-Time Implementation: To prevent side-channel attacks (like timing attacks), all operations are designed to take a predictable amount of time, regardless of the input data. This is achieved by avoiding secret-dependent memory accesses and using techniques like sorting networks for permutations.
  • Optimized LUP Decomposition: For key generation, they employ an optimized LUP decomposition algorithm, adapted from previous work, to efficiently compute the public key matrix.
  • Matrix Multiplication Optimizations: Techniques like "blocking" (dividing matrices into smaller sub-matrices) and specialized assembly functions are used to speed up matrix operations, which are central to the McEliece algorithm.
  • Bitsliced and Radix-16 Representations: For field arithmetic (essential for decoding), they explore and optimize two representations: bitsliced and radix-16, choosing the most efficient for different operations.
  • Berlekamp-Massey Algorithm Optimization: They compare different versions of the Berlekamp-Massey decoder and select the most performant one, further optimizing it for the Cortex-M4.

Datasets

Not discussed in the paper. The paper focuses on implementing and benchmarking an existing cryptographic algorithm rather than training or evaluating on a dataset.

Key Insights and Ideas

  • Flash Memory is Key for Embedded PQC: The paper demonstrates that by creatively utilizing flash memory for public key storage, even schemes with massive keys can become viable on resource-constrained embedded systems. This opens doors for PQC on a wider range of devices.
  • Constant-Time is Non-Negotiable: The emphasis on constant-time implementation highlights its critical importance for security in embedded environments, where side-channel attacks are a significant concern.
  • Micro-optimizations Matter: The detailed breakdown of optimizations for matrix operations, field arithmetic, and the Berlekamp-Massey algorithm shows that significant performance gains can be achieved through careful, low-level tuning for specific architectures like the Cortex-M4.
  • Trade-offs in PQC Implementations: The paper implicitly shows that there are often trade-offs between different implementation choices (e.g., bitsliced vs. radix-16 representations, Massey vs. Xu's BM algorithm), and the optimal choice can depend on the target hardware and performance goals.

Key Results

The paper reports impressive performance figures for Classic McEliece on the STM32F4-Discovery board:

  • Level-1 Parameters (mceliece348864*):
    • Encapsulation: 582,199 cycles
    • Decapsulation: 2,706,681 cycles
  • Level-3 Parameters (mceliece460896*):
    • Encapsulation: 1,081,335 cycles
    • Decapsulation: 6,535,186 cycles
  • Performance Comparison: Compared to FrodoKEM (level-1), their encapsulation is over 80x faster, and decapsulation is over 17x faster.
  • Key Generation: They successfully implemented key generation for level-1 parameter sets.
  • Decapsulation: They can also perform decapsulation for level-5 parameter sets.

Limitations and Future Work

  • Limited Parameter Set Support: While they implemented key generation for level-1 and decapsulation for level-5, full support for all parameter sets (especially key generation for higher levels) is limited by the platform's SRAM and flash constraints.
  • Platform Specificity: The optimizations are tailored for the STM32F4-Discovery board. While the techniques are expected to be useful for other Cortex-M4 devices, direct porting might require adjustments.
  • Future Work: The authors suggest that their techniques are applicable to other "Giant Gecko" microcontrollers with larger memory. They also note that further optimizations are possible, and their implementation is available as open-source for others to build upon. They also mention that the time to write data to flash memory seemed to vary, which warrants further investigation.

Summary updated

Abstract

This paper presents a constant-time implementation of Classic McEliece for ARM Cortex-M4. Specifically, our target platform is stm32f4-Discovery, a development board on which the amount of SRAM is not even large enough to hold the public key of the smallest parameter sets of Classic McEliece. Fortunately, the flash memory is large enough, so we use it to store the public key. For the level-1 parameter sets mceliece348864 and mceliece348864f, our implementation takes 582 199 cycles for encapsulation and 2 706 681 cycles for decapsulation. Compared to the level-1 parameter set of FrodoKEM, our encapsulation time is more than 80 times faster, and our decapsulation time is more than 17 times faster. For the level-3 parameter sets mceliece460896 and mceliece460896f, our implementation takes 1 081 335 cycles for encapsulation and 6 535 186 cycles for decapsulation. In addition, our implementation is also able to carry out key generation for the level-1 parameter sets and decapsulation for level-5 parameter sets on the board.
BibTeX
@inproceedings{chen2021classic,
  author = {Ming-Syan Chen⋆ and Tung Chou},
  title = {{Classic McEliece on the ARM Cortex-M4}},
  booktitle = {IACR},
  year = {2021},
  doi = {10.46586/tches.v2021.i3.125-148},
}
Figure