6
$\begingroup$

Suppose a challenger creates a McEliece encryption system where there is a public key consisting of a matrix $G$ representing some linear code, and a number $t$ for the number of errors.

Then the adversary takes two messages $m_0$ and $m_1$ and uses the public key matrix $G$ to find $c_0=Gm_0$ and $c_1=Gm_1$. Then the adversary sends $m_0$ and $m_1$ to the challenger.

Then the challenger picks $b$ at random and creates $c=Gm_b+e$, and $e$ has at most $t$ errors. Then they send $c$ to the adversary. The adversary calculates: $$e_0=c-c_0=Gm_b+e-Gm_0=G(m_b-m_0)+e$$ $$e_1=c-c_1=Gm_b+e-Gm_1=G(m_b-m_1)+e$$ Since $m_b$ is one of the two messages, then either $e_0=e$ or $e_1=e$. The adversary knows when this happens because $e$ has $t$ or fewer non-zero terms. Further, the other $e_i$ will consist of a non-zero codeword plus the error. Since the minimum distance of the code is greater than or equal to $2t+1$, then this codeword will have at least $2t+1$ non-zero terms; when $e$ is subtracted from this, there will be at least $t+1$ non-zero terms, so the adversary is sure that this was not the message. Hence, the adversary has a 100% chance of correctly guessing $b$.

Does this attack work? Is there some other aspect to the McEliece system that I don't know about that stops this attack?

Improve this question
$\endgroup$
2
  • $\begingroup$ This indeed looks like a valid attack that has already published been 2008 (PDF) with a counter measure to make McEliece IND-CPA: randomly pad the message and ignore the defined amount of trailing bits. $\endgroup$
    – SEJPM
    Commented Mar 4, 2016 at 16:12
  • $\begingroup$ Thanks, that's exactly what I was looking for! I'll accept this as an answer if you post it as such. $\endgroup$
    – Sam Jaques
    Commented Mar 5, 2016 at 17:10

1 Answer 1

Reset to default
5
$\begingroup$

Does this attack work?

Yes, it works.
However, "textbook" McEliece was never claimed to be IND-CPA.
In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF).

They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many random bits and later simply ignore those bits at decryption.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Funfact: I found the linked paper in the german Wikipedia entry for McEliece and it does not appear in the english version. $\endgroup$
    – SEJPM
    Commented Mar 5, 2016 at 19:34
  • $\begingroup$ I'm certainly no expert on McEliese, but why would one use a random prefix when you could have a strong random permutation instead? That's like reinventing the PKCS#1v1.5 RSA padding. $\endgroup$
    – CodesInChaos
    Commented Mar 17, 2016 at 16:46
  • $\begingroup$ @CodesInChaos a) you wouldn't use McEliece like this anyways (it's not IND-CCA secure) b) this is the simplest way to make McEliece IND-CPA (not necessarily the best) C) merely applying a PRP (or something like that) wouldn't make McEliece IND-CPA because it's lacking randomness and the PRP won't change that. $\endgroup$
    – SEJPM
    Commented Mar 17, 2016 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.