Paper 2022/362
How to Backdoor (Classical) McEliece and How to Guard Against Backdoors
Alexander May and Carl Richard Theodor Schneider
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 $\boldsymbol{\delta}$ that generates via some pseudo random number generator (PRNG) the randomness that determines the secret key. Our backdoor mechanism works by encoding the encryption of $\boldsymbol{\delta}$ into the public key. Retrieving $\boldsymbol{\delta}$ then allows to efficiently recover the (backdoored) secret key. Interestingly, McEliece can be used itself to encrypt $\boldsymbol{\delta}$, thereby protecting our backdoor mechanism with strong post-quantum security guarantees. Our backdoor mechanism also works for the current Classic McEliece NIST standard proposal, and therefore opens the door for widespread maliciously backdoored implementations. Fortunately, there is a simple fix to guard (Classic) McEliece against backdoors. While it is not strictly necessary to store $\boldsymbol{\delta}$ after key generation, we show that $\boldsymbol{\delta}$ allows identifying maliciously backdoored keys. Thus, our results provide strong advice to implementers to store $\boldsymbol{\delta}$ inside the secret key (as the proposal recommends), and use $\boldsymbol{\delta}$ to guard against backdoor mechanisms.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Classic McElieceNiederreiterBackdoorSETUPPost-Quantum Cryptography
- Contact author(s)
-
research @ crtified me
alex may @ 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