Paper 2022/362
How to Backdoor (Classic) McEliece and How to Guard Against Backdoors
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}, url = {https://eprint.iacr.org/2022/362} }