Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A Key-Recovery Side-Channel Attack on Classic McEliece Implementations

Guo, Qian LU ; Johansson, Andreas LU and Johansson, Thomas LU orcid (2022) In IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) 2022(4). p.800-827
Abstract
In this paper, we propose the first key-recovery side-channel attack on Classic McEliece, a KEM finalist in the NIST Post-quantum Cryptography Standardization Project. Our novel idea is to design an attack algorithm where we submit special ciphertexts to the decryption oracle that correspond to cases of single errors. Decoding of such ciphertexts involves only a single entry in a large secret permutation, which is part of the secret key. Through an identified leakage in the additive FFT step used to evaluate the error locator polynomial, a single entry of the secret permutation can be determined. Iterating this for other entries leads to full secret key recovery. The attack is described using power analysis both on the FPGA reference... (More)
In this paper, we propose the first key-recovery side-channel attack on Classic McEliece, a KEM finalist in the NIST Post-quantum Cryptography Standardization Project. Our novel idea is to design an attack algorithm where we submit special ciphertexts to the decryption oracle that correspond to cases of single errors. Decoding of such ciphertexts involves only a single entry in a large secret permutation, which is part of the secret key. Through an identified leakage in the additive FFT step used to evaluate the error locator polynomial, a single entry of the secret permutation can be determined. Iterating this for other entries leads to full secret key recovery. The attack is described using power analysis both on the FPGA reference implementation and a software implementation running on an ARM Cortex-M4. We use a machine-learning-based classification algorithm to determine the error locator polynomial from a single trace. The attack is fully implemented and evaluated in the Chipwhisperer framework and is successful in practice. For the smallest parameter set, it is using about 300 traces for partial key recovery and less than 800 traces for full key recovery, in the FPGA case. A similar number of traces are required for a successful attack on the ARM software implementation. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)
volume
2022
issue
4
pages
800 - 827
publisher
Ruhr-University of Bochum
external identifiers
  • scopus:85137103250
ISSN
2569-2925
project
Securing Quantum-Safe Signatures
Lightweight Cryptography for Autonomous Vehicles
language
English
LU publication?
yes
id
9ffe6b5a-7c00-4987-bde5-c328d374cc7c
date added to LUP
2022-08-30 11:54:28
date last changed
2023-11-21 07:05:52
@article{9ffe6b5a-7c00-4987-bde5-c328d374cc7c,
  abstract     = {{In this paper, we propose the first key-recovery side-channel attack on Classic McEliece, a KEM finalist in the NIST Post-quantum Cryptography Standardization Project. Our novel idea is to design an attack algorithm where we submit special ciphertexts to the decryption oracle that correspond to cases of single errors. Decoding of such ciphertexts involves only a single entry in a large secret permutation, which is part of the secret key. Through an identified leakage in the additive FFT step used to evaluate the error locator polynomial, a single entry of the secret permutation can be determined. Iterating this for other entries leads to full secret key recovery. The attack is described using power analysis both on the FPGA reference implementation and a software implementation running on an ARM Cortex-M4. We use a machine-learning-based classification algorithm to determine the error locator polynomial from a single trace. The attack is fully implemented and evaluated in the Chipwhisperer framework and is successful in practice. For the smallest parameter set, it is using about 300 traces for partial key recovery and less than 800 traces for full key recovery, in the FPGA case. A similar number of traces are required for a successful attack on the ARM software implementation.}},
  author       = {{Guo, Qian and Johansson, Andreas and Johansson, Thomas}},
  issn         = {{2569-2925}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{800--827}},
  publisher    = {{Ruhr-University of Bochum}},
  series       = {{IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)}},
  title        = {{A Key-Recovery Side-Channel Attack on Classic McEliece Implementations}},
  volume       = {{2022}},
  year         = {{2022}},
}