ROUND 3 OFFICIAL COMMENT: Classic McEliece decoding failure attack

[Kirk Fleming]

The Classic McEliece submission explicitly allows a change

to decapsulation which breaks the IND-CCA2 security proof

and leaves the scheme vulnerable to decoding failure

attacks.

 

The decapsulation algorithm described in Section 2.3.3 is:

 

   1. Split the ciphertext C as (C0,C1).
   2. Set b:=1.
   3. Extract s and Gamma' from the private key.
   4. Compute e := Decode(C0,Gamma').

        If e = Fail set e:=s and b:=0.
   5. Compute C'1 := H(2,e).
   6. If C'1 != C1 set e:=s and b:=0.
   7. Compute K := H(b,e,C).
   8. Output session key K.

 

However, the discussion in the paragraphs following the

algorithm description suggests a change to Step 4 for ease

of implementation.

 

   "As an implementation note, the output of decapsulation
    is unchanged if 'e <-- s' in Step 4 is changed to assign
    something else to e. Implementors may prefer, e.g., to
    set e to a fixed n-bit string or a random n-bit string
    other than s."

 

This is not true. Using a known fixed string trivially breaks the

scheme.

 

To see why, consider decapsulation where Step 4 is changed to:

 

   4'. Compute e := Decode(C0,Gamma').

         If e = Fail set e:=0 and b:=0.

 

Let C := (C0,C1) be a ciphertext chosen so that C0 is not a
codeword and C1 := H(2,0).

 

If decoding succeeds in Step 4' then e := Decode(C0,Gamma')
and b:=1, Step 5 gives C'1 := H(2,e), the confirmation check
fails in Step 6 so gives e:=s and b:=0, and Step 7 gives the
unpredictable session key K := H(0,s,C).

 

If decoding fails in Step 4' then e:=0 and b:=0, Step 5 gives
C'1 := H(2,0), the confirmation check passes in Step 6 so
keeps e=0 and b=0, and Step 7 gives the predictable session
key K := H(0,0,C).

 

Distinguishing between these two cases gives enough

information to recover messages using a standard reaction

attack.

 

IND-CCA2 transforms are fragile. Any changes that deviate
from the security proof for ease of implementation or
efficiency reasons are potentially dangerous.

 

Kirk

 

[daniel.apon]

Hi Kirk,

"Distinguishing between these two cases gives enough information to recover messages using a standard reaction attack."

Would you describe what you mean in more detail?

Off hand, this seems like an implicit rejection vs explicit rejection issue, which raises various important issues, but doesn't seem to directly lead to a "standard reaction attack" in a straightforward manner -- to my knowledge
In particular, I don't see how to distinguish between decryption failures (of honestly generated ciphertexts) and decryption failures (of intentionally malformed ciphertexts)

Hope I'm not misunderstanding,
--Daniel

[D. J. Bernstein]

Kirk Fleming writes:
> "As an implementation note, the output of decapsulation
> is unchanged if 'e <-- s' in Step 4 is changed to assign
> something else to e. Implementors may prefer, e.g., to
> set e to a fixed n-bit string or a random n-bit string
> other than s."
> This is not true. Using a known fixed string trivially breaks the
> scheme.

For some reason Mr. Fleming omitted the next sentence in the paragraph,
which says "However, the definition of decapsulation does depend on e
being set to s in Step 6."

---Dan

[Christopher J Peikert]

This is an irrelevant and totally inadequate response to a serious issue. Fleming’s example leaves Step 6 as-is, including the “e := s” part (as required by the sentence you quoted). And it demonstrates that the output of decapsulation *does* change if Step 4 is changed as suggested by the submission, contradicting the associated claim and even apparently breaking CCA security.

Sincerely yours in cryptography,

Chris

[D. J. Bernstein]

Christopher J Peikert writes:
> This is an irrelevant and totally inadequate response to a serious issue.
> Fleming’s example leaves Step 6 as-is, including the “e := s” part (as required
> by the sentence you quoted). And it demonstrates that the output of
> decapsulation *does* change if Step 4 is changed as suggested by the
> submission, contradicting the associated claim and even apparently breaking CCA
> security.

Huh?

The specification indisputably requires e to be set to s in both failure
cases, Step 4 and Step 6.

In the case of a Step 4 failure, the computation using e in Step 5 is
irrelevant to the output, since the result is thrown away in Step 6.
This fact opens up more implementation options, using whatever e you
want in Step 5 in case of failure, _but_ you still have to set e to s in

Step 6. This is exactly what the implementation note says:

As an implementation note, the output of decapsulation is unchanged

if “e←s” in Step 4 is changed to assign something else to e.
Implementors may prefer, e.g., to set e to a fixed n-bit string, or a
random n-bit string other than s. However, the definition of

decapsulation does depend on e being set to s in Step 6.

If you maliciously misinterpret this by omitting the "but"/"However"
part then of course you get different results and a fake contradiction.

---Dan

[Christopher J Peikert]

Let's put the relevant lines of pseudocode and implementation note together, and consider the potential interpretations:

   4. Compute e := Decode(C0,Gamma').
        If e = Fail set e:=s and b:=0.
   5. Compute C'1 := H(2,e).
   6. If C'1 != C1 set e:=s and b:=0.

"As an implementation note, the output of decapsulation

is unchanged if 'e <-- s' in Step 4 is changed to assign

something else to e. Implementors may prefer, e.g., to

set e to a fixed n-bit string or a random n-bit string

other than s. However, the definition of decapsulation

does depend on e being set to s in Step 6."

A natural interpretation of this -- in my opinion, the most natural one -- is:

(a) in Step 4 you can replace "e := s" with "e := 00...0" (n bits);

(b) but in Step 6 you must preserve the "e := s".

(Notably, both "e := ..." assignments are behind conditionals, and the note says nothing about changing the logical control flow of the code. In particular, there's no instruction that the outcome of the test in Step 4 should influence the action taken in Step 6.)

Reader, do you find this to be a reasonable interpretation of the note? If so, Dan seems to think that you have "maliciously misinterpret[ed]" it. In any case, this interpretation leads to a total break of CCA security, as Fleming has demonstrated.

Now let's consider the interpretation that Dan appears to have:

(a) in Step 4 you can replace "e := s" with "e := 00...0";

(b) but for Step 6 you must change the control flow. Specifically:

   (b1) test whether e was 'Fail' in Step 4 (e has since been overwritten, but we can check if b=0);

   (b2) if so, then *unconditionally* set e:=s, regardless of whether C'1 != C1 or not;

   (b3) otherwise, do Step 6 as written above.

(It's plausible that this interpretation preserves CCA security, but I may have missed something, so no promises.)

I'll freely grant that if you know why the tests in Steps 4 and 6 are there, and why those steps set e:=s --- perhaps because you know the subtleties of the CCA security proof --- and if you intelligently use this knowledge to extrapolate from the text of the implementation note, then you can see this interpretation as being consistent with it.

But is this really the most natural interpretation? More to the point, is it one that implementors --- who may not have the above knowledge --- are likely to arrive at on their own from reading the note? I strongly doubt it. (No offense intended, implementors.)

At the very least, the note is ambiguous, and a perfectly reasonable reading of it leads to a devastating security failure. So, the specification should be updated to ensure that there is no ambiguity.

[Kirk Fleming]

Hi Daniel,

 

Daniel Apon wrote:
>
> "Distinguishing between these two cases gives enough
> information to recover messages using a standard
> reaction attack."
>
> Would you describe what you mean in more detail?

 

Let C = He for an unknown error e of weight t. Construct

 

   C' = C + H_i + H_j

 

where H_i and H_j are a pair of columns of H. This

corresponds to C' = He' where the error e' is obtained

from e by flipping the bits in positions i and j. In other

words e' = e + e_i + e_j where e_i and e_j are standard

basis vectors.

 

If C' decodes successfully then you know that e' must

also have weight t. This imples that e has a bit set in

exactly one of the positions i or j. You can recover the

full error e with at most n-1 spoofs of this form.

 

> Off hand, this seems like an implicit rejection vs
> explicit rejection issue, which raises various
> important issues, but doesn't seem to directly lead
> to a "standard reaction attack" in a straightforward
> manner -- to my knowledge
>
> In particular, I don't see how to distinguish between
> decryption failures (of honestly generated ciphertexts)
> and decryption failures (of intentionally malformed
> ciphertexts)

 

All the ciphertexts are malformed. The attack works
because you learn whether rejection happens at Step 4
because of a decoding failure (decapsulation outputs

the predictable session key) or at Step 6 because of a

confirmation failure (decapsulation outputs a different

session key).

 

Kirk

 

[D. J. Bernstein]

Christopher J Peikert writes:
>    4. Compute e := Decode(C0,Gamma').
>         If e = Fail set e:=s and b:=0.
>    5. Compute C'1 := H(2,e).
>    6. If C'1 != C1 set e:=s and b:=0.

This is an excerpt from the specification of the decapsulation function.
The specification requires e to be set to s (and b to be set to 0;
otherwise b is 1) in both failure cases, Step 4 and Step 6, producing
output H(0,s,C).

If there's a Step 4 failure then Step 6 is a no-op, since e is already s
(and b is already 0). The rest of the algorithm shows that there is no
use of C'_1 after Step 6. Consequently, in the case of a Step 4 failure,
the computation using e in Step 5 is irrelevant to the output.

This fact opens up more implementation options, using whatever e you

want in Step 5 in case of failure, _but_ you still have to set e to s in

Step 6. This, once again, is exactly what the implementation note says:

As an implementation note, the output of decapsulation is unchanged

if “e←s” in Step 4 is changed to assign something else to e.
Implementors may prefer, e.g., to set e to a fixed n-bit string, or a

random n-bit string other than s. However, the definition of
decapsulation does depend on e being set to s in Step 6.

I already wrote essentially all of this in my previous message, the
message that Dr. Peikert (1) claims to be replying to, and (2) posts
various characterizations of, but (3) does not quote. I request that he
follow the traditional email-handling practice of quoting and replying
to each point, to reduce the risk of error and to assist readers
tracking the discussions.

> A natural interpretation of this -- in my opinion, the most natural one -- is:
> (a) in Step 4 you can replace "e := s" with "e := 00...0" (n bits);
> (b) but in Step 6 you must preserve the "e := s".

This "interpretation" would replace the specified mathematical function
with a different function, contradicting

(1) the paragraph's explicit statement that "the output of
decapsulation is unchanged" and

(2) the paragraph's explicit label as an "implementation note",

not to mention that this "interpretation" would make the paragraph have
the same meaning as the paragraph _without_ the final sentence (the
sentence that Mr. Fleming omitted), begging the question of why that
sentence is there.

Even for readers who manage to miss the final sentence, this is two
direct contradictions with what's stated at the beginning of the same
paragraph. This "interpretation" is simply not correct.

> (Notably, both "e := ..." assignments are behind conditionals, and the note
> says nothing about changing the logical control flow of the code.

I don't know what Dr. Peikert thinks he means by "the logical control
flow", so the claim of a change is hard to evaluate, never mind the
question of why this is supposed to be relevant. In the end everything
is fed through standard transformations to constant-time code, so the
data flow ends up being independent of inputs.

> In
> particular, there's no instruction that the outcome of the test in Step 4
> should influence the action taken in Step 6.)

The specification indisputably requires e to be set to s in both of the
failure cases, producing a final output of H(0,s,C) in those cases. The
implementation note correctly points out the implementor's freedom to
vary an intermediate computation without affecting the final output.

> Reader, do you find this to be a reasonable interpretation of the note?

An "interpretation" that contradicts what's stated in the text is
incorrect. Repeatedly claiming that an incorrect "interpretation" is
"natural" and "reasonable" does not change the fact that it's wrong.

> If so, Dan seems to think that you have "maliciously misinterpret[ed]"
> it.

What I stated was "If you maliciously misinterpret this by omitting the

'but'/'However' part then of course you get different results and a fake

contradiction." It's of course also possible for one person maliciously
misinterpreting it to deceive other, non-malicious, people, which is an
example of why something as important as standardizing post-quantum
crypto should have evaluation procedures designed to resist attack.

> In any case, this interpretation leads to a total break of CCA
> security, as Fleming has demonstrated.

"Doctor, doctor, it hurts when I don't do what the documentation tells
me to do."

There are some types of bugs in post-quantum software that are hard to
catch with standard verification techniques. This isn't one of them.

> Now let's consider the interpretation that Dan appears to have:

Many people expect the word "interpretation" to mean that there's an
ambiguity. There's no ambiguity here.

Furthermore, most people expect the word "appears" to indicate some lack
of clarity. I see nothing unclear in the message that Dr. Peikert claims
to be replying to here. If he thinks there's a lack of clarity in
something I wrote, the normal way forward would be to quote it and ask
for clarification.

> (a) in Step 4 you can replace "e := s" with "e := 00...0";
> (b) but for Step 6 you must change the control flow. Specifically:
>    (b1) test whether e was 'Fail' in Step 4 (e has since been overwritten, but
> we can check if b=0);
>    (b2) if so, then *unconditionally* set e:=s, regardless of whether C'1 != C1
> or not;
>    (b3) otherwise, do Step 6 as written above.
> (It's plausible that this interpretation preserves CCA security, but I may have
> missed something, so no promises.)

Consider the following line of pseudocode:

   6. If C'_1 != C_1, set b:=0. If b=0, set e:=s.

Notice that this line is much more concise, and much easier to read,
than the above series of several b-b1-b2-b3 lines.

Why, one wonders, was something so short and simple stated in such an
obfuscated b-b1-b2-b3 way, using vastly more space than necessary, with
a claim of a "change" in the "control flow" etc., a scary-sounding
comment about possible losses of CCA security, etc.?

Most readers seeing this obfuscated presentation of X won't take the
time to strip away the obfuscation---they'll simply assume, incorrectly,
that X really is so complicated, and they'll tend to wonder whether a
short implementation note could really have been saying something so
complicated. This obfuscation thus contributes to the effort to convince
readers to accept a wrong "interpretation" of the implementation note,
rather than taking the implementation note to mean exactly what it says.

> I'll freely grant that if you know why the tests in Steps 4 and 6 are there,
> and why those steps set e:=s --- perhaps because you know the subtleties of the
> CCA security proof --- and if you intelligently use this knowledge to
> extrapolate from the text of the implementation note, then you can see this
> interpretation as being consistent with it.

I don't see any _overt_ errors in the statement being "freely" granted
here. However, the paragraph tries to make readers believe that one
_needs_ to go to all this work to understand a simple implementation
note. This belief is simply wrong.

I already spelled out the data-flow details that allow implementors to
vary e in this way without changing the function being computed. Those
details are entirely about the structure of the function being computed.
Again, the function is unchanged, so the question of _why_ the function
is designed this way is irrelevant, and the question made no appearance
in my explanation.

More broadly, there's an impressive circularity between

(1) repeatedly talking about CCA security to make the reader think
that the function being computed is changing, and

(2) repeatedly claiming that the function being computed is changing
to make the reader think that there's a CCA security question,

all of which is completely out of whack with the fact that this is
explicitly an _implementation note_, correctly and explicitly saying
that it computes the _same_ function.

> But is this really the most natural interpretation? More to the point, is it
> one that implementors --- who may not have the above knowledge --- are likely
> to arrive at on their own from reading the note? I strongly doubt it. (No
> offense intended, implementors.)

Again biased wording ("natural", "strongly doubt", etc.) is being used
to push an "interpretation" of a paragraph that directly contradicts
what the paragraph says.

> At the very least, the note is ambiguous, and a perfectly reasonable
> reading of it leads to a devastating security failure.

No. The claimed ambiguity is resolved by what the note says. Calling an
incorrect interpretation "perfectly reasonable" does not make it so.

> So, the specification should be updated to ensure that there is no ambiguity.

We are talking about an explicitly labeled _implementation note_ that
explicitly and correctly says that it does _not_ change the function
being computed. The explicit text is not consistent with your claimed
"interpretation". Furthermore, it's simply wrong to label a request for
a change in the note as requesting a change in the specification; we
should all be clear about the roles of specifications, reference
implementations, further implementations, and further text.

---Dan

P.S. Side question for NIST: Is it okay to be putting extra text into
the subject line of OFFICIAL COMMENTs, as in this thread? This isn't
what the official links show, but it would generally be helpful for
tracking other discussions, for example to split the discussions of
Kyber's patent issues from the discussions of Kyber-512's security.

[Greg Maxwell]

On Tue, Jan 5, 2021 at 8:18 PM D. J. Bernstein <d...@cr.yp.to> wrote:
>
> This fact opens up more implementation options, using whatever e you
> want in Step 5 in case of failure, _but_ you still have to set e to s in
> Step 6. This, once again, is exactly what the implementation note says:
>
> As an implementation note, the output of decapsulation is unchanged
> if “e←s” in Step 4 is changed to assign something else to e.
> Implementors may prefer, e.g., to set e to a fixed n-bit string, or a
> random n-bit string other than s. However, the definition of
> decapsulation does depend on e being set to s in Step 6.

I believe the implementation note is a foot-gun and should be revised.
The following "are cautioned" text does a laudable job of making the
point that the two causes of failure must not be distinguishable. But
it is easily read as only raising the concern of distinguishability
only in terms of timing, leaving open the possibility of the cases
being distinguishable by K taking on an attacker predictable value.

The note's statement about step 6 could be misread as saying "even
though you're allowed to fill e with whatever in step 4, when C1' !=
C1 you must still follow step 6 and set e=s before step 7" in other
words, only if the hash check fails. This way of reading it is
vulnerable to the attack described in Kirk's post.

In particular, if an implementation follows that logic and in step 4
sets e to some implementation specific non-secret constant, this
implementation flaw would be impossible to detect with generic test
vectors, though it could be caught by review.

I believe the note could be changed to "As an implementation note, the

output of decapsulation is unchanged if “e←s” in Step 4 is changed to

assign something else to e, so long as the comparison in Step 6. is
forced to consider C1' and C1 not equal when Decode fails."

Would that be correct?

Though even that is still a little opaque without any discussion of
_WHY_ you might want to implement it that way.

Clearly any implementation is free to implement it in whatever way
computes exactly the same function (particularly if doing so doesn't
create sidechannel vulnerabilities...), so an implementation note that
simply reminds you of that without even suggesting a concrete
optimization isn't necessarily the most useful. But my understanding
of the note is that it is actually telling you that you're allowed to
change the function so that it always fails if decoding fails, rather
than happening to pass with 1:2^256 probability when decoding fails
should the invalid input happen to guess right H(2,s). Is that
correct?

[Christopher J Peikert]

Dan, your latest reply contains a good deal of code analysis, mixed with the text of the implementation note, mixed with the words of the authors in this thread.

But the central issue is what the specification says on its own, and what implementors will do with it.

So, for the sake of concision, clarity, and precision, I suggest the following test. Please provide a modification of the original pseudocode in which:

(a) Steps 1-3 are unchanged;

(b) In Step 4, "e:=s" is changed to "e:=00...0", as allowed by the implementation note;

(c) Steps 5-?? are the result of whatever you think the note instructs the implementor to do here.

Readers can then judge for themselves whether implementors would arrive at your modified pseudocode, on their own, by reading the spec.

Kirk Fleming's original message provided such modified code based on his reading of the spec -- namely, for (c) he retained the "e:=s" in Step 6, presumably believing that to follow the instruction "However, the definition of decapsulation does depend on e being set to s in Step 6."

I believe it's likely that implementors would naturally arrive at Fleming's pseudocode, even though it is completely insecure (under CCA). That indicates an ambiguity problem with the spec as currently written.

To conclude, I would like to point out one piece of logical sleight-of-hand to readers:

On Tue, Jan 5, 2021 at 3:18 PM D. J. Bernstein <d...@cr.yp.to> wrote:

Christopher J Peikert writes:
>    4. Compute e := Decode(C0,Gamma').
>         If e = Fail set e:=s and b:=0.
>    5. Compute C'1 := H(2,e).
>    6. If C'1 != C1 set e:=s and b:=0.

This is an excerpt from the specification of the decapsulation function.
The specification requires e to be set to s (and b to be set to 0;
otherwise b is 1) in both failure cases, Step 4 and Step 6, producing
output H(0,s,C).

If there's a Step 4 failure then Step 6 is a no-op, since e is already s
(and b is already 0). The rest of the algorithm shows that there is no
use of C'_1 after Step 6. Consequently, in the case of a Step 4 failure,
the computation using e in Step 5 is irrelevant to the output.

This fact opens up more implementation options, using whatever e you
want in Step 5 in case of failure, _but_ you still have to set e to s in
Step 6. This, once again, is exactly what the implementation note says:

   As an implementation note, the output of decapsulation is unchanged
   if “e←s” in Step 4 is changed to assign something else to e.

As Kirk Fleming pointed out in his original message, the spec's claim "the output of decapsulation is unchanged...", which refers to the original pseudocode, is simply not true. Specifically, if we replace e:=s with e:=0 in Step 4, then the decapsulation output can be changed by letting C'1 = H(2,0). I don't think Dan has acknowledged this error.

I emphasize: in the spec, the "output is unchanged" claim is made *before* any suggested modifications to the code, and is used to motivate the possibility of such changes, so it must be referring to the original code.

Here is the sleight of hand: in his argument quoted above, Dan has *first* changed Step 6 to include an unconditional assignment e:=s in the case of a Step 4 failure, *then* quotes the "output is unchanged" claim as being "exactly what the implementation note says." With that change to Step 6, the claim becomes plausible -- but the claim in the spec refers to the original code, and is false.

[Christopher J Peikert]

On Tue, Jan 5, 2021 at 5:04 PM Christopher J Peikert <cpei...@alum.mit.edu> wrote:

As Kirk Fleming pointed out in his original message, the spec's claim "the output of decapsulation is unchanged...", which refers to the original pseudocode, is simply not true. Specifically, if we replace e:=s with e:=0 in Step 4, then the decapsulation output can be changed by letting C'1 = H(2,0). I don't think Dan has acknowledged this error.

Please excuse a typo here: it should be C1 = H(2,0), not C'1.

[Christopher J Peikert]

I now realize that I used the term "spec" or "specification" in some places where Dan would use the separate term "implementation note." Feel free to replace each occurrence with whatever term is best in context, or replace them all with "submission"; it won't affect the substance of my comments.

Sincerely your in cryptography,

Chris

On Tue, Jan 5, 2021 at 5:04 PM Christopher J Peikert <cpei...@alum.mit.edu> wrote:

[Mike Hamburg]

Hi Dan,

On Jan 5, 2021, at 4:18 PM, D. J. Bernstein <d...@cr.yp.to> wrote:

Christopher J Peikert writes:

...

Many people expect the word "interpretation" to mean that there's an
ambiguity. There's no ambiguity here.

...

More broadly, there's an impressive circularity between

  (1) repeatedly talking about CCA security to make the reader think
      that the function being computed is changing, and

  (2) repeatedly claiming that the function being computed is changing
      to make the reader think that there's a CCA security question,

all of which is completely out of whack with the fact that this is
explicitly an _implementation note_, correctly and explicitly saying
that it computes the _same_ function.

But is this really the most natural interpretation? More to the point, is it
one that implementors --- who may not have the above knowledge --- are likely
to arrive at on their own from reading the note? I strongly doubt it. (No
offense intended, implementors.)

Again biased wording ("natural", "strongly doubt", etc.) is being used
to push an "interpretation" of a paragraph that directly contradicts
what the paragraph says.

At the very least, the note is ambiguous, and a perfectly reasonable
reading of it leads to a devastating security failure.

No. The claimed ambiguity is resolved by what the note says. Calling an
incorrect interpretation "perfectly reasonable" does not make it so.

So, the specification should be updated to ensure that there is no ambiguity.

We are talking about an explicitly labeled _implementation note_ that
explicitly and correctly says that it does _not_ change the function
being computed.

With all due respect, horseshit.  The implementation note begins with

a perfectly clear and demonstrably false statement:

“”"

As an implementation note, the output of decapsulation is unchanged
  if “e←s” in Step 4 is changed to assign something else to e.

“””

This sentence is perfectly clear, self-contained, and ends with a full

stop.  And as Kirk pointed out, it is false: if e is assigned a fixed

string in step 4, instead of being assigned s, then there are

(C_0, C_1) for which the output of decapsulation does change.

What’s more, they are easy to compute.

There is no other plausible interpretation of your statement.  If you

meant to say that decapsulation is unchanged if, when e=bot, step 5

is replaced with

    K = H(b, something else, C)

while leaving steps 4 and 6 alone, then you could have written this

instead. Demanding that the reader replace your false statement with

a different, true statement (in which we somehow additionally branch

on b in step 6, or something?) is entirely unreasonable.  Even more

unreasonable is to call the straightforward reading of your false

statement a “fake contradiction”.  It’s not a fake contradiction.  It’s a

real contradiction. False statements are contradictions, more or less

by definition.

You might reasonably object that the false statement is transparently

false, that it is essentially a typo or an imprecision, that any reasonable

reader would understand it to mean some other, true statement.  In that

case all your critics in this thread would be picking nits.  But several

people in this thread have stated that they read your statement as

written, and I have also read it this way.

I will also support my claim that the false statement is not transparently

false or transparently a typo.  There are similar flows in in CCA transforms

where this sort of statement would be true.  Consider a generic CCA

transform from a perfectly-correct OW-CPA encryption algorithm, which

performs in part:

3: e <- Decrypt(sk, C)

4: if e = bot: e <- s and b <- 0

5: C’ <- Encrypt(pk, e)

6: if C’ != C: e <- s and b <- 0

In that case, setting e <- something else would indeed leave the

decapsulation result unchanged, because when e = bot, since Decrypt

is perfectly correct, there is no value of “something else” such that

Encrypt(pk, something else) = C.  Thus the branch on line 6 will always

be taken.  So not only is the implementation note wrong, there are

other, naturally analogous contexts in which a similar note would not

be wrong.

And indeed, Classic McEliece is based on a perfectly-correct OW-CPA

decryption algorithm. In this case, of course, the same logic does not

apply because C_1 is only part of the ciphertext.

Furthermore, one might say that the natural interpretation is

unreasonable because the specification wouldn’t demand e <- s, if

indeed any value would suffice.  But this isn’t a valid objection either,

because within that branch e=bot.  Even if Encrypt(pk, bot) is somehow

defined, it will not typically be implemented.  So in a typical

implementation, e would need to be replaced with something on that

branch.  The specification says to replace it with s, but the

implementation note claims, falsely, that any other choice would give

the same result.

The implementation note continues:

“””

 Implementors may prefer, e.g., to set e to a fixed n-bit string, or a
  random n-bit string other than s. However, the definition of
  decapsulation does depend on e being set to s in Step 6.

“””

These statements are both true.  It is also true that implementors may

prefer to use variable-time decoding algorithms, or to skip Step 7 entirely,

or to pass attacker-controlled data in backticks to a shell, or to do any

number of other insecure things.  Mentioning these in an implementation

note is transparently content-free, however, so the only reasonable

reading is to recommend that changing line 4 to “e <- something else”

would be acceptable, subject to the following that line 6 must be intact

and that side-channel leaks must be prevented.

But as Kirk has demonstrated, if an implementor changes line 4 while

leaving line 6 intact, exactly as this implementation note details, then

the resulting system is not CCA-secure.  So this statement, while

technically content-free, constitutes a footgun at the very least.

Coming back to another objection you made:

not to mention that this "interpretation" would make the paragraph have
the same meaning as the paragraph _without_ the final sentence (the
sentence that Mr. Fleming omitted), begging the question of why that
sentence is there.

The sentence is clearly there to warn implementors that the analogous

change in line 6 is forbidden and would be dangerous.  This would be a

perfectly reasonable warning, except that changing line 4 is also

dangerous.  But the reader presumably doesn’t know that because

you’ve asserted the opposite.

Your documentation (Look! I didn’t say “specification”!) is wrong, and you

really ought to fix it.

Grumble,

— Mike

[daniel.apon]

Hi Kirk,

Yes-- your attack seems correct. Well done. =)

[D. J. Bernstein]

Greg Maxwell writes:
> The note's statement about step 6 could be misread as saying "even
> though you're allowed to fill e with whatever in step 4, when C1' !=
> C1 you must still follow step 6 and set e=s before step 7"

The note about e being set to s is _not_ limited to "when C_1' != C_1".
That's an added constraint that changes the meaning, contradicts this
being an "implementation note", and contradicts this leaving the output
"unchanged". So this is indeed a misreading.

> I believe the note could be changed to "As an implementation note, the
> output of decapsulation is unchanged if “e←s” in Step 4 is changed to
> assign something else to e, so long as the comparison in Step 6. is
> forced to consider C1' and C1 not equal when Decode fails."

Sure, and then we'll have people again trying to score cheap political
points by pretending that this means something other than what it says:
e.g., pretending that "forced" is making some sort of security claim
about a modified function (rather than pointing out to the implementor
a different way to compute the _same_ function) and then attacking this
(fabricated) security claim.

Pseudocode, such as the line

   6. If C'_1 != C_1, set b:=0. If b=0, set e:=s.

in my previous message, makes misinterpretation _harder_ but doesn't
make it _impossible_. The ultimate answer is automated verification,
but this whole discussion makes zero contributions to ongoing
verification work, while actively corrupting novice evaluations of
what's safest.

> Though even that is still a little opaque without any discussion of
> _WHY_ you might want to implement it that way.

The original text says "Implementors may prefer, e.g., to set e to a
fixed n-bit string, or a random n-bit string other than s." The first
part simplifies the data flow in some types of implementations, and the
second part is worth considering as a component of side-channel
countermeasures beyond timing-attack protection.

> But my understanding
> of the note is that it is actually telling you that you're allowed to
> change the function so that it always fails if decoding fails,

If by "fails" you mean computes and outputs H(0,s,C), this isn't a
change to the specified function.

> rather than happening to pass with 1:2^256 probability when decoding
> fails should the invalid input happen to guess right H(2,s).

No, Step 6 is a no-op in the "guess right" case. There's nothing
probabilistic here.

---Dan

[Quan Thoi Minh Nguyen]

It’s puzzled me why the discussion in this thread is heated. Can we all take it easy? It's clear that all the people (Classic McEliece’s authors and critics) are knowledgeable and reputable and know what they’re doing. Is it worth arguing about the “implementation note” (which no implementers used or implemented yet) at this phase of competition? 

If we’re worried about implementations’ security then I would be more worried about multiple security bugs that Markku-Juhani O. Saarinen found in real implementations.

After the competition is concluded, is it NIST’s job to rewrite everything in a clearer manner in the standards so that implementers can follow? A similar process for IETF’s RFC standard which takes months (if not years) and multiple rounds of edit to become standard.

Cheers,

- Quan

[D. J. Bernstein]

Christopher J Peikert writes:
> Please provide a modification of the original pseudocode in which:

I already did, in exactly the message you claim to be replying to:

   6. If C'_1 != C_1, set b:=0. If b=0, set e:=s.

This meets the stated requirements of _preserving the output_ ("output
of decapsulation is unchanged") and "e being set to s in Step 6" on
failure, along with everything else that this implementation note says.

> Readers can then judge for themselves whether implementors would
> arrive at your modified pseudocode, on their own, by reading the spec.

What I wrote above is fully compliant with every detail of this
_implementation note_, correctly computing the _specified_ function.

> But the central issue is what the specification says on its own,

The _specification_ produces output H(0,s,C) in both failure cases.
The _implementation note_ correctly describes different computations
that reach the specified output in all cases.

> and what implementors will do with it.

Analyzing the ecosystem of implementations is indisputably important,
including taking account of possible errors and measures taken to
protect against errors---e.g., NIST's validation process for its current
standards, and more advanced processes that have been developed.

> Kirk Fleming's original message provided such modified code based on his
> reading of the spec -- namely, for (c) he retained the "e:=s" in Step 6,
> presumably believing that to follow the instruction "However, the definition of
> decapsulation does depend on e being set to s in Step 6."

This "interpretation" contradicts the text of the implementation note in
question. This isn't disputed.

> That indicates an ambiguity problem with the spec as currently written.

No, it doesn't.

> As Kirk Fleming pointed out in his original message, the spec's claim "the
> output of decapsulation is unchanged...", which refers to the original
> pseudocode, is simply not true.

There are multiple levels of errors in what Dr. Peikert claims here.

First, the discussion is about an explicitly labeled "implementation
note", _not_ the specification. One of the reasons this structure is
important is that it constrains the meaning of the note: the note is
_not_ changing the specified function. (Dr. Peikert posts a followup
message claiming, without analysis, that this difference "won't affect
the substance of my comments".)

Second, the claim of something being "not true" rests entirely on
pushing an "interpretation" that contradicts what the text explicitly
says, while refusing to acknowledge the existence of a statement that's
perfectly correct and matches every single detail of the text.

> Specifically, if we replace e:=s with e:=0 in Step 4, then the
> decapsulation output can be changed by letting C'1 = H(2,0).

Making _only_ that change would flunk "However, the definition of
decapsulation does depend on e being set to s in Step 6", would
contradict this being an "implementation note", and would contradict
"the output of decapsulation is unchanged".

> I don't think Dan has acknowledged this error.

There's no error.

> I emphasize: in the spec,

Wrong again. It's an implementation note.

> the "output is unchanged" claim is made
> *before* any suggested modifications to the code,

The claim is correct. This is, as it says, an implementation note about
different ways to compute _exactly the same function_.

> and is used to
> motivate the possibility of such changes, so it must be referring to
> the original code.

Not exactly. The implementation note is _starting_ from the pseudocode
used in the spec, but it is then pointing out some _different_ ways to
compute the _same_ function.

> Here is the sleight of hand: in his argument quoted above, Dan has
> *first* changed Step 6 to include an unconditional assignment e:=s in
> the case of a Step 4 failure, *then* quotes the "output is unchanged"
> claim as being "exactly what the implementation note says." With that
> change to Step 6, the claim becomes plausible

When the biased presentation ("sleight of hand" etc.) is stripped away,
this paragraph _almost_ becomes a clear admission of what the
implementation note was saying in the first place.

> -- but the claim in the spec refers to the original code, and is false.

No.

---Dan

[Kirk Fleming]

You're correct that it is NIST's responsibility to write
a clear and unambiguous standard but they will use the
submission as a basis for that. For Classic McEliece
it's not always easy to tell which parts constitute the
specification and which parts are just commentary. There
are lots of notes for implementers. Some or all of these
could be picked up by NIST and included in the standard.

 

Let's look at a different example. Section 2.2.4 of the
submission suggests that one of the checks in the
decoding subroutine can be made more efficient:

 

   "In order to test C0 = He, implementors can use any
    parity-check matrix H' for the same code."

 

   "There are various well-known choices of H' related
    to H^ that are recovered from Gamma' much more
    efficiently than MatGen, and that can be applied to
    vectors without using quadratic space."

 

What the submission fails to mention is that while H is
public other choices of H' may need to remain private.
An implementer could miss this if they're not an expert

so NIST would need to add a warning to the standard.

 

I'm not saying that things like this will necessarily
lead to problems in the standard. I'd expect NIST to
weed most of them out and hope the rest get spotted in
the review process. I'm saying that when a submission
offers so many different implementation options without
being sufficiently clear about them it makes NIST's job
much harder. I think it should be our responsibility to
help by surfacing issues as early as possible.

 

Kirk

[Kirk Fleming]

Kirk Fleming wrote:
> Let's look at a different example. Section 2.2.4 of the
> submission suggests that one of the checks in the
> decoding subroutine can be made more efficient:
>
>   "In order to test C0 = He, implementors can use any
>    parity-check matrix H' for the same code."
>
>   "There are various well-known choices of H' related
>    to H^ that are recovered from Gamma' much more
>    efficiently than MatGen, and that can be applied to
>    vectors without using quadratic space."
 

I just realized that I don't understand why the C0 = He
check is there in the first place. The pseudocode for

the decoding subroutine is:

 

   1. Extend C0 to v = (C0,0,...,0) by apppending k zeros.

 

   2. Find the unique codeword c in the Goppa code

       defined by Gamma' that is at distance <= t from v.

       If there is no such codeword, return Fail.

 

   3. Set e = v + c.

 

   4. If wt(e) = t and C0 = He, return e.

       Otherwise return Fail.

 

Let's skip over the fact that the submission doesn't actually
describe the decoder and just points to the McBits papers. I
think this expects too much of the implementer but whatever.

 

If Step 2 finds a codeword c and Step 3 sets e = v + c then
He = H(v+c) = Hv + Hc = Hv = C0 in Step 4 by construction.
The only reason you'd need to check C0 = He is if the decoder
in Step 2 wasn't guaranteed to either return a codeword or fail

but that contradicts the specification.

 

Kirk

[Ruben Niederhagen]

Hi Kirk!

On 1/7/21 3:49 AM, Kirk Fleming wrote:
> I just realized that I don't understand why the C0 = He
> check is there in the first place.

Maybe the following paragraph helps you to understand this:

"Implementors are cautioned that it is important to avoid leaking secret
information through side channels, and that the distinction between
success and failure of Decode is secret in the context of the Classic
McEliece KEM. In particular, immediately stopping the computation when
Step 2 returns Fail would reveal this distinction through timing, so it
is recommended for implementors to have Step 2 always choose some c."
(Small edits due to math symbols.)

Ruben

[Kirk Fleming]

Hi Ruben,

Choosing a random c is presumably not part of the specification
since it's only a recommendation. It also doesn't explain the
need for the check if we interpret the paragraph the way we've
been told to interpret the implementation note for decapsulation.
According to that logic if decoding fails in Step 2 and the
implementation chooses a random c then the computation of e in
Step 3 and both checks in Step 4 are irrelevant because Step 4
must always return Fail.

 

Kirk

[Ruben Niederhagen]

OK, the question why the C0 = He check is there seems to be answered.

I'll file this under 'criticism of the writing style', then.

Ruben

[Paul Hoffman]

<lurker decloaking>

Speaking as a specification writer: please don't do such filing.

The phrase "so it is recommended" leaves the implementer with three choices:
a) do what comes after the recommendation
b) do some other thing that the implementer makes up themselves
c) do what they thought was implied by the text preceding the recommendation

If you mean (a), the text needs to updated to say "so implementers must".

If you mean (b), then the specification is both incomplete and dangerous. Some implementers will pick something really smart-looking that is wrong.

If you mean (c), then the specification is both poorly-written and dangerous. Some implementers will think that what you were hinting at is something that turns out to be wrong.

I hope you meant (a); if so, you need to update the specification to say so. As far as I can tell from my mild skimming of this thread, such updates are needed in other places in this specification in order to make it clear.

It would be good for the safety of everyone if the writers **of all the specifications here** would review their submissions and, wherever there is implementation recommendations, turn them into requirements. The crypto world has the same track record as the Internet protocol world of unclear specifications that lead to security disasters.

--Paul Hoffman, going back to lurking

[Ruben Niederhagen]

On 1/7/21 4:57 PM, Paul Hoffman wrote:
> It would be good for the safety of everyone if the writers **of all
> the specifications here** would review their submissions and,
> wherever there is implementation recommendations, turn them into
> requirements.

I do not entirely agree (although I do cherish the sentiment).

The specific recommendation here (talking about the "decoding
discussion" on the C0 = He check) is about side channels.

Now, is it the task of a specification or of an implementation to
provide security against side-channel attacks?

Let's take the definition of 'side-channel attack' from Wikipedia:

"[...] a side-channel attack is any attack based on information gained
from the implementation of a computer system, rather than weaknesses in
the implemented algorithm itself [...]"

A specification provides the algorithm and tells you what to implement,
but not explicitly how to implement it; the specification is not the
implementation.

Furthermore, a specification could hardly cover all sources of side
channels. (Is it a hardware implementation? Is it a software
implementation? What is the application, what is the use case - which
side channels are relevant? ..?)

Thus, I'd say it is hardly the task for the specification to provide
side-channel protection; this burden is with the implementer.

Should a specification provide recommendations to implementers in
regards to side channels? "Yes, sure"? "No, never"? "Yes" if it helps to
increase security, "no" if it does not..? Sorry, I have no proper answer
here.

Ruben, also going back to lurking

[Rainer Urian]

> Furthermore, a specification could hardly cover all sources of side channels. (Is it a hardware implementation? Is it a software implementation? What is the application, what is the use case - which side channels are relevant? ..?)
> Thus, I'd say it is hardly the task for the specification to provide side-channel protection; this burden is with the implementer.

I totally agree. Side-channel and fault-attack countermeasures are strongly related to the device and the environment where the device is used.
For instance, they are rather different on PC and smart card devices.
Also, timing attacks cover only a very limited part of all possible side-channel attack scenarios.
So, there is never one-size-fits-all solution.

> Should a specification provide recommendations to implementers in regards to side channels? "Yes, sure"? "No, never"? "Yes" if it helps to increase security, "no" if it does not..? Sorry, I have no proper answer here.

I my opinion, the specification should take care about all points related to crypto-analytic attacks. All points related to side-channel and fault attacks shall be informative only.
According to my understanding, this is also the philosophy behind the current FIPS/NIST SP specifications.

BR,
Rainer

> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/a555c711-c54c-b4f8-4b51-f60276d138a7%40polycephaly.org.

[daniel.apon]

Hi Rainer and all,

Rainer's recent message (copied below) prompts me to re-highlight some brief informational content on NIST PQC's attitude/philosophy toward side-channel attacks.
As I haven't spoken with the team yet, I should highlight this as "speaking for myself," although I believe it's representative of the general view.


First, NIST has stated the importance of side-channel attacks and countermeasures a few times before.

For example, in the original PQC call for proposals in 2016:
"Schemes that can be made resistant to side-channel attacks at minimal cost are more desirable than those whose performance is severely hampered by any attempt to resist side-channel attacks."

For a more recent example, in the latest PQC 2nd Round Report (NISTIR 8309) in 2020:
"NIST hopes to see more and better data for performance in the third round. This performance data will hopefully include implementations that protect against side-channel attacks, such as timing attacks, power monitoring attacks, fault attacks, etc."

Second, as Rainer points out, the philosophy behind current FIPS/NIST SP specifications indeed only makes informative comments about side-channel attacks (passive or active). That is, while I suppose it's possible that NIST would choose to standardize some type of side-channel resistant PQC specification directly, this has not been the case historically, and I find it unlikely to be the case for the eventual PQC standards as well.

Nonetheless, we are certainly paying attention to side-channel attacks and their analysis, and it could be the case (all else equal) that this information directly factors into our eventual choice of this algorithm vs. that algorithm to standardize -- particularly if one algorithm/system seems to clearly lend itself to "side-channel resistance friendly implementations" more readily than another that is an otherwise close / near-indistinguishable competitor. Additionally, we certainly would not (or at least, should not) standardize an algorithm/system for which we believe side channel resistance is critical to its real-world adoption/application but where side-channel resistance appears inherently overly burdensome to come by.

So -- echoing the NIST team's prior statements on the issue: This is an important issue to think about, especially during the third round.
I sincerely appreciate everyone's earnest input to this discussion (especially, you lurkers out there :); it's very helpful.


Cheers,
--Daniel

[Kirk Fleming]

Ruben Niederhagen wrote:
>
> OK, the question why the C0 = He check is there seems to be
> answered.
>
> I'll file this under 'criticism of the writing style', then.

 

I confess. It was a leading question intended to let me complain

about interpretations of implementation notes. That was mean and
I apologize. There's still a serious point behind the question,
though. The C0 = He check really isn't needed if you trust the
decoder to either return a codeword or fail.

 

The submission recommends that when the decoder fails to find a
codeword "Step 2 chooses some vector c in (F_2)^n and continues
on to Step 3."

 

What does the submission mean by "some vector c"? Does it mean
that the implementation must choose a random c or can it set c to a
fixed value?

 

If it's intended to be read as "choose a random c" then you're
correct that you do need to check C0 = He. The wt(e) = t check
will amost surely fail but the IND-CCA2 security proof requires
the PKE scheme to be perfect. No decryption failures are allowed
no matter how negligible the probability.

 

What about using a fixed value? It's actually better to set
c = 0 when the decoder fails. In this case Step 3 sets e = v
and the check C0 = He is trivially true so can be skipped. On
the other hand the check wt(e) = t always fails since otherwise
c = 0 is the nearest codeword and would have been found by the
decoder.

 

Poorly written implementation notes are not just a problem for
security. They can also be a problem for efficiency if they stop
implementers from making changes that are genuinely safe.

 

Kirk

[Ruben Niederhagen]

On 1/8/21 3:55 PM, Kirk Fleming wrote:
> I confess. It was a leading question intended to let me complain
> about interpretations of implementation notes. That was mean and
> I apologize.

Apology accepted.

> There's still a serious point behind the question,
> though. The C0 = He check really isn't needed if you trust the
> decoder to either return a codeword or fail.
> The submission recommends that when the decoder fails to find a
> codeword "Step 2 chooses some vector c in (F_2)^n and continues
> on to Step 3."
> What does the submission mean by "some vector c"? Does it mean
> that the implementation must choose a random c or can it set c to a
> fixed value?
> If it's intended to be read as "choose a random c" then you're
> correct that you do need to check C0 = He. The wt(e) = t check
> will amost surely fail but the IND-CCA2 security proof requires
> the PKE scheme to be perfect. No decryption failures are allowed
> no matter how negligible the probability.
> What about using a fixed value? It's actually better to set
> c = 0 when the decoder fails. In this case Step 3 sets e = v
> and the check C0 = He is trivially true so can be skipped. On
> the other hand the check wt(e) = t always fails since otherwise
> c = 0 is the nearest codeword and would have been found by the
> decoder.
> Poorly written implementation notes are not just a problem for
> security. They can also be a problem for efficiency if they stop
> implementers from making changes that are genuinely safe.

I don't want to chime in here on the discussion about the quality of the
implementation notes (I am clearly biased in my opinion that the quality
of the implementation notes is impeccable ;) ).


Just as a note: The decoding algorithm used in Step 2 probably per se
computes either the unique codeword c if it exists or 'some c in
(F_2)^n'. So, in order to know if it computed the unique codeword or
some other vector, one then will need to compute something like C0 = He
anyway...

Thus, your observation is relevant only for a decoding algorithm that
'cheaply' detects its own failure; otherwise, the (C0=He)-check probably
is an efficient solution for this detection.


And maybe yet another statement: I claim that for functional
correctness, an implementer of an algorithm from a specification is
expected to ensure that his or her implementation gives the exact same
output for all possible inputs as the specified algorithm. Thus, it is
(functionally) alright to leave out steps in the algorithm that do not
alter the result (e.g., some unnecessary (C0=He)-check).
(Caution is required as usual if side-channel security comes into play.)


Basically what I am saying is that in an implementation, the C0 = He
will likely be required and efficient and if it isn't required you are
allowed to leave it out.

Ruben