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
Preprint.
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-08-15: last of 2 revisions
2022-03-18: received
See all versions
Short URL
https://ia.cr/2022/362
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2022/362}},
      url = {https://eprint.iacr.org/2022/362}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.