How to Backdoor (Classic) McEliece and How to Guard Against Backdoors

Tobias Hemmert; Alexander May; Johannes Mittmann; Carl Richard Theodor Schneider

Paper 2022/362

How to Backdoor (Classic) McEliece and How to Guard Against Backdoors

Tobias Hemmert, Bundesamt für Sicherheit in der Informationstechnik (BSI)

Alexander May

, Ruhr University Bochum

Johannes Mittmann

, Bundesamt für Sicherheit in der Informationstechnik (BSI)

Carl Richard Theodor Schneider

, Ruhr University Bochum

Abstract

We show how to backdoor the McEliece cryptosystem such that a backdoored public key is indistinguishable from a usual public key, but allows to efficiently retrieve the underlying secret key. For good cryptographic reasons, McEliece uses a small random seed 𝛅 that generates via some pseudo random generator (PRG) the randomness that determines the secret key. Our backdoor mechanism works by encoding an encryption of 𝛅 into the public key. Retrieving 𝛅 then allows to efficiently recover the (backdoored) secret key. Interestingly, McEliece can be used itself to encrypt 𝛅, thereby protecting our backdoor mechanism with strong post-quantum security guarantees. Our construction also works for the current Classic McEliece NIST standard proposal for non-compressed secret keys, and therefore opens the door for widespread maliciously backdoored implementations. Fortunately, our backdoor mechanism can be detected by the owner of the (backdoored) secret key if 𝛅 is stored after key generation as specified by the Classic McEliece proposal. Thus, our results provide strong advice for implementers to store 𝛅 inside the secret key and use 𝛅 to guard against backdoor mechanisms.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. PQCrypto 2022
DOI: 10.1007/978-3-031-17234-2_2
Keywords: Classic McEliece Niederreiter Backdoor SETUP Post-Quantum Cryptography
Contact author(s): tobias hemmert @ bsi bund de
alex may @ rub de
johannes mittmann @ bsi bund de
carl schneider @ rub de
History: 2022-09-29: last of 3 revisions; 2022-03-18: received; See all versions
Short URL: https://ia.cr/2022/362
License: CC BY

BibTeX

@misc{cryptoeprint:2022/362,
      author = {Tobias Hemmert and Alexander May and Johannes Mittmann and Carl Richard Theodor Schneider},
      title = {How to Backdoor (Classic) McEliece and How to Guard Against Backdoors},
      howpublished = {Cryptology ePrint Archive, Paper 2022/362},
      year = {2022},
      doi = {10.1007/978-3-031-17234-2_2},
      note = {\url{https://eprint.iacr.org/2022/362}},
      url = {https://eprint.iacr.org/2022/362}
}