ROUND 3 OFFICIAL COMMENT: Classic McEliece

693 views
Skip to first unread message

Kirk Fleming

unread,
Nov 9, 2020, 8:35:28 PM11/9/20
to pqc-co...@nist.gov, pqc-forum
There is a strong possibility that NIST intend to standardize Classic McEliece at the
end of Round 3 as a conservative option. Their Status Report on the Second Round
expressed confidence in its construction and said that they believed it could be ready
for standardization if selected. Standardizing Classic McEliece, however, also means
standardizing at least some of the parameter sets proposed by the submitters.
 
I am filing this comment to request that the Classic McEliece submitters justify the
claimed security categories for their parameters.
 
The Round 3 submission does not include any concrete analysis of the security provided
by the proposed parameter sets. There is a lot of hype about the asymptotic result from
Canto Torres and Sendrier but this is ultimately irrelevant for any finite choice of
parameters. The only firm statement contained in the submission is:
 
   "[Bernstein, Lange and Peters. 2008] reported that its attack uses 2^266.94 bit
    operations to break the (13,6960,119) parameter set. Subsequent ISD variants
    have reduced the number of bit operations considerably below 2^256."
 
The submission argues that any reduction in classical security from improved ISD attacks
will be offset by the increased memory requirements. While this may be true for some ISD
variants such as BJMM, they provide no analysis to back this up. It also ignores other
ISD variants such as Stern that need significantly less memory. In this case the finite
regime analsysis from the LEDACrypt team gives the following estimates of computational
and memory costs for the pre-merger Classic McEliece and NTS-KEM parameters:
 
     Parameter Set      Compute    Memory    Target
    
   mceliece-3488-064     152.51     34.68     143
   mceliece-4608-096     194.36     35.66     207
   mceliece-6688-128     270.46     37.48     272
   mceliece-6960-119     271.18     47.58     272
   mceliece-8192-128     306.63     67.64     272
 
   nts-kem-4096-064      166.76     35.60     143
   nts-kem-8192-080      248.01     77.63     207
   nts-kem-8192-136      313.52     67.50     272
 
By this analysis:
 
   - The mceliece-4608-096 parameters are about 13 bits below Category 3 with an attack
      that needs slightly over 6 GiB of memory.
 
   - The mceliece-6688-128 parameters are borderline Category 5 with an attack that needs
     slightly over 22 GiB of memory.
 
   - The mceliece-6960-119 parameters are borderline Category 5 with an attack that needs
     around 24 TiB of memory.
 
If Classic McEliece is to be standardized as a conservative option then the parameter sets
that are standardized with it should also be chosen conservatively. The NTS-KEM parameters
were. Three out of the five Classic McEliece parameters were not.
 
Kirk

Kirk Fleming

unread,
Nov 11, 2020, 12:20:08 PM11/11/20
to pqc-forum, pqc-co...@nist.gov
Kirk Fleming wrote: 
> In this case the finite regime analysis from the LEDACrypt team gives the following
> estimates of computational and memory costs for the pre-merger Classic McEliece
> and NTS-KEM parameters:
 
It was pointed out that my finite regime analysis reference was unclear. The figures were
taken from Tables 4 and 5 in Baldi, Barenghu, Chiaraluce, Pelosi and Santini, "A finite
regime analysis of Information Set Decoding algorithms", Algorithms 12, no. 10 (2019).
 
Kirk
 

D. J. Bernstein

unread,
Nov 19, 2020, 7:38:15 AM11/19/20
to pqc-co...@nist.gov, pqc-forum
Kirk Fleming writes:
> mceliece-3488-064 152.51 34.68 143
> mceliece-4608-096 194.36 35.66 207
> mceliece-6688-128 270.46 37.48 272
> mceliece-6960-119 271.18 47.58 272
> mceliece-8192-128 306.63 67.64 272

We agree that the second column is sometimes less than the fourth column.
However, the second column ignores the huge overheads measured by the
third column. As stated in the submission:

A closer look shows that the attack in [11] is bottlenecked by random
access to a huge array (much larger than the public key being
attacked), and that subsequent ISD variants use even more memory. The
same amount of hardware allows much more parallelism in attacking,
e.g., AES-256.

The submission goes on to state expectations regarding (e.g.) 6960119
being more expensive to break than AES-256. The numbers you quote (e.g.,
2^271.18 operations on 2^47.58 bits of RAM) are consistent with these
expectations.

The literature shows that optimized hardware for AES attacks has similar
efficiency to multipliers. The multipliers in an Intel CPU core carry
out millions of bit operations in the same time that it takes the core
to retrieve data from (say) 6GB of RAM, never mind RAM contention across
cores. GPUs and TPUs show the costs of RAM even more clearly. On a
larger scale, decades of supercomputing literature consistently fit a
square-root scaling of RAM costs, and science-fiction 3D computers
(which seem much harder to build than quantum computers) would still
have cube-root costs.

> I am filing this comment to request that the Classic McEliece submitters
> justify the claimed security categories for their parameters.

Can you please clarify how you think that the numbers already in the
literature don't already justify the assignments in the submission?

Our best guess is that you're assuming that NIST requires >=2^272
operations in a specified metric for "category 5", and that 2^271.18 is
an evaluation in this metric. But the assumption here isn't correct.
NIST has not issued clear definitions of the cost metrics for its
"categories". If at some point NIST does issue clear, stable definitions
of its cost metrics, then it should also allow all submitters to set
their "category" assignments accordingly.

Note that one can make any cryptosystem sound much easier to break by
choosing a cost metric that assigns unrealistically low cost to
operations used in attacks; RAM access is just one example. If the same
operations are not bottlenecks in attacks against AES-m or SHA-n then
this can reverse comparisons to AES-m or SHA-n respectively.

> The Round 3 submission does not include any concrete analysis of the
> security provided by the proposed parameter sets.

Not true. For example, the stated expectation to be "more expensive to
break than AES-256" is concrete, and the rationale is stated. A more
detailed analysis depends on the cost metric.

> There is a lot of hype about the asymptotic result from Canto Torres
> and Sendrier

The graph in https://video.cr.yp.to/2020/0813/video.html shows that
asymptotic lattice security levels against attacks known 10 years ago
were 42% higher than lattice security levels against attacks known today
(for otherwise unbroken lattice systems), while for McEliece's system
the change is 0%. Any thorough evaluation of security risks will take
these facts into account, along with other risk indicators.

> but this is ultimately irrelevant for any finite choice of parameters.

The submission already says, at the top of the "Information-set
decoding, concretely" section:

We emphasize that o(1) does not mean 0: it means something that
converges to 0 as n->infty. More detailed attack-cost evaluation is
therefore required for any particular parameters.

The section goes on to summarize what the literature says about concrete
cost analyses, and ends with the AES-256 comparison reviewed above.

> The submission argues that any reduction in classical security from
> improved ISD attacks will be offset by the increased memory
> requirements. While this may be true for some ISD variants such as
> BJMM, they provide no analysis to back this up.

Again, here's the critical quote from the submission:

A closer look shows that the attack in [11] is bottlenecked by random
access to a huge array (much larger than the public key being
attacked), and that subsequent ISD variants use even more memory. The
same amount of hardware allows much more parallelism in attacking,
e.g., AES-256.

The exact impact depends on the cost metric.

> It also ignores other
> ISD variants such as Stern that need significantly less memory.

No, the submission doesn't ignore this. The "attack in [11]" (see quote
above) is a Stern-type attack. The submission's comment that "subsequent
ISD variants use even more memory" (see quote above) is pretty much the
same as your comment that Stern-type attacks "need significantly less
memory".

> - The mceliece-4608-096 parameters are about 13 bits below Category 3 with
> an attack that needs slightly over 6 GiB of memory.

Evaluating such a claim would require a clear, stable definition of
"Category 3". If NIST settles on a definition to be used in NISTPQC then
submitters will be able to make "category" assignments accordingly.

See above regarding the actual costs of accessing 6GB of RAM.

> If Classic McEliece is to be standardized as a conservative option
> then the parameter sets that are standardized with it should also be
> chosen conservatively. The NTS-KEM parameters were. Three out of the
> five Classic McEliece parameters were not.

Please clarify. Are you saying anything here beyond the 2^194 vs. 2^207,
2^270 vs. 2^272, and 2^271 vs. 2^272 discussed above?

If you're concerned about 2^270 RAM operations vs. 2^272 bit operations
then you should be far more concerned about NIST dropping the targets
from 2^256 to 2^128:

* Multi-target attacks turn 2^128 into something already feasible for
large-scale attackers today. ECC is an exception to this (provably,
via a tight self-reduction), but codes and lattices and AES aren't
exceptions. See https://blog.cr.yp.to/20151120-batchattacks.html.

* Both round-1 Classic McEliece options were at the 2^256 level.
However, NIST then praised NTS-KEM for offering lower-security
options, and asked Classic McEliece for "parameter sets for other
security categories".

From this perspective, NTS-KEM and NIST were far less conservative than
Classic McEliece was. Note that general trends in networking and in CPUs
are making the high-security Classic McEliece parameter sets affordable
for more and more users.

There's also a tremendous amount to say about the dangers of unnecessary
complexity. One aspect of this is specifying more parameter sets than
necessary. Of course, NIST's request for lower-security parameter sets
was an offer that Classic McEliece couldn't refuse, but we continue to
recommend the 2^256 parameter sets. Within those parameter sets:

* The 6960119 parameter set goes back to 2008, maximizing security
for 1MB keys. This has held up just fine, and can reasonably be
viewed as the default choice.

* The new 6688128 parameter set is a slight variant that requires n
and t to be multiples of 32, which _might_ be slightly better for
formal verification, but the jury is still out on this. (Components
are being verified---see https://cr.yp.to/papers.html#controlbits
for the latest news---but this work hasn't yet reached the
components that could interact with the multiple-of-32 question.)

* The 8192128 parameter set is bigger, but the 6960119 and 6688128
parameter sets include an extra defense explained in the
submission. People paranoid enough to imagine 2^306 vs. 2^270
making a difference should also be paranoid enough to imagine this
defense making a difference.

One can easily write down even larger parameter sets. Also, the ISD
attack analyses in the literature are precise and straightforward, and
it should be easy to evaluate the security of any desired parameters in
any well-defined metric. However, the right order of events is, first,
for NIST to fully define the cost metric to be used for "categories",
and, second, for all submission teams to evaluate costs in this metric.

---Dan (on behalf of the Classic McEliece team)
signature.asc

Kirk Fleming

unread,
Nov 23, 2020, 8:01:15 PM11/23/20
to pqc-co...@nist.gov, pqc-forum
Dan Bernstein wrote:
> Kirk Fleming writes:
>>
>>    mceliece-3488-064     152.51     34.68     143
>>    mceliece-4608-096     194.36     35.66     207
>>    mceliece-6688-128     270.46     37.48     272
>>    mceliece-6960-119     271.18     47.58     272
>>    mceliece-8192-128     306.63     67.64     272
>
> We agree that the second column is sometimes less than the fourth column.
> However, the second column ignores the huge overheads measured by the
> third column.
 
No. The second column includes a logarithmic memory overhead. This is not
an accurate analysis of the cost of memory accesses but it does not ignore it.
 
> As stated in the submission:
>
>   A closer look shows that the attack in [11] is bottlenecked by random
>   access to a huge array (much larger than the public key being
>   attacked), and that subsequent ISD variants use even more memory. The
>   same amount of hardware allows much more parallelism in attacking,
>   e.g., AES-256.
 
This is the second time you've used the word "huge". Let's give it some
perspective. 2^35.66 bits is less RAM than the laptop I'm using to write
this. 2^47.58 bits is the same as Amazon EC2's u-24tb1.metal instance.
Maybe the "u" stands for 'uge.
 
> The submission goes on to state expectations regarding (e.g.) 6960119
> being more expensive to break than AES-256. The numbers you quote (e.g.,
> 2^271.18 operations on 2^47.58 bits of RAM) are consistent with these
> expectations.
 
Your submission and this reply focus almost exclusively on the
mceliece-6960-119 parameter set. What about the other four?
 
> The literature shows that optimized hardware for AES attacks has similar
> efficiency to multipliers. The multipliers in an Intel CPU core carry
> out millions of bit operations in the same time that it takes the core
> to retrieve data from (say) 6GB of RAM, never mind RAM contention across
> cores. GPUs and TPUs show the costs of RAM even more clearly. On a
> larger scale, decades of supercomputing literature consistently fit a
> square-root scaling of RAM costs, and science-fiction 3D computers
> (which seem much harder to build than quantum computers) would still
> have cube-root costs.
 
No. It's not as simple as applying a square-root overhead for memory across
the board. For an interesting (but not very rigorous) example see
http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html. The blog argues
for a square-root memory cost. If you look at the graphs this is a poor
fit in the 10 MiB to 6 GiB range.
 
Not all memory accesses are the same. The memory overhead depends on the
number of random accesses to high-latency memory. One cost model in Ray
Perlner's slides assumes that up to 2^50 bits of memory is local with
unit cost memory accesses.
 
>> I am filing this comment to request that the Classic McEliece submitters
>> justify the claimed security categories for their parameters.
>
> Can you please clarify how you think that the numbers already in the
> literature don't already justify the assignments in the submission?
 
Let's try an easier question. Can you point to the paper cited by your
submission that gives numbers for the mceliece-4608-096 parameter set
which clearly justify its assignment as category 3?
 
> Our best guess is that you're assuming that NIST requires >=2^272
> operations in a specified metric for "category 5", and that 2^271.18 is
> an evaluation in this metric. But the assumption here isn't correct.
> NIST has not issued clear definitions of the cost metrics for its
> "categories". If at some point NIST does issue clear, stable definitions
> of its cost metrics, then it should also allow all submitters to set
> their "category" assignments accordingly.
>
> Note that one can make any cryptosystem sound much easier to break by
> choosing a cost metric that assigns unrealistically low cost to
> operations used in attacks; RAM access is just one example. If the same
> operations are not bottlenecks in attacks against AES-m or SHA-n then
> this can reverse comparisons to AES-m or SHA-n respectively.
 
No. You are arguing that because NIST has not specified a single metric
no evaluation in any metric can be valid. The Call for Proposals actually
says (NIST's emphasis):
 
  "In order for a cryptosystem to satisfy one of the above security
   requirements, any attack must require computational resources
   comparable to or greater than the stated threshold, with respect
   to *all* metrics that NIST deems to be potentially relevant to
   practical security."
 
NIST gives circuit size as an example of a metric and says that AES-192 key
recovery is equivalent to 2^207 classical gates in this metric. The finite
regime analysis estimates that breaking mceliece-4608-096 with Stern takes
2^194.4 classical gates including a logarithmic overhead for memory accesses
to 6 GiB of RAM. Whether or not NIST deems this to be potentially relevant to
practical security is up to them.
 
>> The Round 3 submission does not include any concrete analysis of the
>> security provided by the proposed parameter sets.
>
> Not true. For example, the stated expectation to be "more expensive to
> break than AES-256" is concrete, and the rationale is stated. A more
> detailed analysis depends on the cost metric.
 
We have different ideas of what constitutes concrete analysis. Let's take
a look at what section 8.2 of your submission actually says. Don't worry.
It's not that long.
 
  "As an example, our parameter set mceliece6960119 takes m=13, n=6960,
   and t=119. This parameter set was proposed in the attack paper [11]
   that broke the original McEliece parameters (10,1024,50).
 
   That paper reported that its attack uses 2^266.94 bit operations to

   break the (13,6960,119) parameter set. Subsequent ISD variants have
   reduced the number of bit operations considerably below 2^256.
 
   However:
 
    - None of these analyses took into account the costs of memory
      access. A closer look shows that the attack in [11] is bottle-

      necked by random access to a huge array (much larger than the
      public key being attacked), and that subsequent ISD variants
      use even more memory. The same amount of hardware allows much
      more parallelism in attacking, e.g., AES-256.
 
    - Known quantum attacks multiply the security level of both ISD
      and AES by an asymptotic factor of 0.5 + o(1), but a closer
      look shows that the application of Grover's method to ISD
      suffers much more overhead in the inner loop.
 
   We expect that switching from a bit-operation analysis to a cost
   analysis will show that this parameter set is more expensive to
   break than AES-256 pre-quantum and much more expensive to break
   than AES-256 post-quantum."
 
That's it. No mention of the other parameter sets. No attempt to quantify
the impact of memory accesses. Just a vague statement that something
that is "considerably below 2^256" bit operations will be fine because
memory.
 
>> There is a lot of hype about the asymptotic result from Canto Torres
>> and Sendrier
>
> The graph in https://video.cr.yp.to/2020/0813/video.html shows that
> asymptotic lattice security levels against attacks known 10 years ago
> were 42% higher than lattice security levels against attacks known today
> (for otherwise unbroken lattice systems), while for McEliece's system
> the change is 0%. Any thorough evaluation of security risks will take
> these facts into account, along with other risk indicators.
>
>> but this is ultimately irrelevant for any finite choice of parameters.
 
This is the irrelevant hype I mean. You are ignoring asymptotic improvements
to half-distance decoding because McEliece uses errors with sublinear weight
yet compare it with asymptotic improvements to the exact short vector problem
even though lattice schemes depend on different variants of the problem.
 
> The submission already says, at the top of the "Information-set
> decoding, concretely" section:
>
>   We emphasize that o(1) does not mean 0: it means something that
>   converges to 0 as n->infty. More detailed attack-cost evaluation is
>   therefore required for any particular parameters.
>
> The section goes on to summarize what the literature says about concrete
> cost analyses, and ends with the AES-256 comparison reviewed above.
 
The rest of section 8.2 is quoted above in its entirety. The literature
says much more about concrete cost analyses than this "summary".
 
>> The submission argues that any reduction in classical security from
>> improved ISD attacks will be offset by the increased memory
>> requirements. While this may be true for some ISD variants such as
>> BJMM, they provide no analysis to back this up.
>
> Again, here's the critical quote from the submission:
>
>   A closer look shows that the attack in [11] is bottlenecked by random
>   access to a huge array (much larger than the public key being
>   attacked), and that subsequent ISD variants use even more memory. The
>   same amount of hardware allows much more parallelism in attacking,
>   e.g., AES-256.
>
> The exact impact depends on the cost metric.
>
>> It also ignores other
>> ISD variants such as Stern that need significantly less memory.
>
> No, the submission doesn't ignore this. The "attack in [11]" (see quote
> above) is a Stern-type attack. The submission's comment that "subsequent
> ISD variants use even more memory" (see quote above) is pretty much the
> same as your comment that Stern-type attacks "need significantly less
> memory".
>
>>   - The mceliece-4608-096 parameters are about 13 bits below Category 3 with
>>     an attack that needs slightly over 6 GiB of memory.
>
> Evaluating such a claim would require a clear, stable definition of
> "Category 3". If NIST settles on a definition to be used in NISTPQC then
> submitters will be able to make "category" assignments accordingly.
>
> See above regarding the actual costs of accessing 6GB of RAM.
 
No. The definition of category 3 is stable. Your argument is that NIST has
not specified a single metric. Evaluating the claim only needs a metric that
NIST deems practically relevant.
 
For example, the cost of breaking mceliece-4608-096 using Stern with no,
logarithmic, cube-root, or square-root memory overhead is:
 
    Parameter Set           Free    Log     Cbrt    Sqrt
  mceliece-4608-096:  189.2  194.4  200.3  204.6
 
Ray Perlner's cost model slides include almost all of these metrics. None
of them give an estimate greater than 2^207 classical gates.
 
>> If Classic McEliece is to be standardized as a conservative option
>> then the parameter sets that are standardized with it should also be
>> chosen conservatively. The NTS-KEM parameters were. Three out of the
>> five Classic McEliece parameters were not.
>
> Please clarify. Are you saying anything here beyond the 2^194 vs. 2^207,
> 2^270 vs. 2^272, and 2^271 vs. 2^272 discussed above?
>
> If you're concerned about 2^270 RAM operations vs. 2^272 bit operations
 
No, no, no. 2^189.2 classical gates does not mean 2^189.2 random memory
accesses. Not all gates involve a memory access. Not all memory accesses
are to high-latency memory. Not all high-latency memory accesses are
random. My point is that you can't just say that everything will be fine
because memory. You actually need to do the analysis.
 
> There's also a tremendous amount to say about the dangers of unnecessary
> complexity. One aspect of this is specifying more parameter sets than
> necessary. Of course, NIST's request for lower-security parameter sets
> was an offer that Classic McEliece couldn't refuse, but we continue to
> recommend the 2^256 parameter sets.
 
I assume that if Classic McEliece is chosen for standardization you will
be withdrawing the parameter sets that you don't recommend for use.
 
> One can easily write down even larger parameter sets. Also, the ISD
> attack analyses in the literature are precise and straightforward, and
> it should be easy to evaluate the security of any desired parameters in
> any well-defined metric. However, the right order of events is, first,
> for NIST to fully define the cost metric to be used for "categories",
> and, second, for all submission teams to evaluate costs in this metric.
 
No. The right order of events is, first, submit parameter sets with security
estimates in a metric that you think is practically relevant and, second,
let eveyone else spend three rounds of the NIST process evaluating those
claims. That's what most of other submissions have done.
 
> ---Dan (on behalf of the Classic McEliece team)
 
Kirk

D. J. Bernstein

unread,
Dec 7, 2020, 5:21:36 AM12/7/20
to pqc-co...@nist.gov, pqc-...@list.nist.gov
Speaking for myself in this message. As far as I can tell, the questions
specific to Classic McEliece have already been answered. There are some
broader NISTPQC process points here for NIST to address (as shown by the
inconsistent handling of different cryptosystems), and there are some
factual errors that I'll correct for the record.

As a starting point, there appears to be a misconception that NIST has
already defined metrics to be used for the NISTPQC "categories": namely,
(non-quantum and quantum) "gates" metrics, ignoring the costs of RAM.

If this were true then I would agree that all submissions have to report
security in these metrics. But it isn't true. NIST has never issued any
such definition. There are many different definitions of (non-quantum
and quantum) "gates" in the literature, with many variations (e.g.,
sometimes RAM gates, sometimes not), often producing radically different
cost numbers; NIST has never said which "gates" we're supposed to use.

The hard way to check this is to dig through the complete NISTPQC
archives and look at what NIST has written. The easy way, for people who
know some quantum algorithms, is to consider the following two facts:

* The NISTPQC call for proposals claims that known SHA3-256 collision
attacks need 2^146 "gates", with no quantum speedups.

* It's easy to find SHA3-256 collisions in only about 2^85 oracle
queries, which is in the ballpark of 2^100 quantum "gates" with the
"gates" defined in, e.g., Ambainis's famous distinctness paper and
used in many other quantum-walk papers.

To see the 2^85, apply Ambainis's algorithm to 128-bit strings
after a random prefix. Or, simpler and presumably faster, apply the
BHT (Brassard--Hoyer--Tapp) algorithm to 256-bit strings. This
means a Grover search through 170-bit inputs for hashes appearing
in a table of 2^86 hashes of other inputs.

To see the 2^100, start from the 2^85 and look at the cost of
SHA3-256 evaluation. Maybe ends up slightly over 100, but maybe
not: one can handle a large oracle cost by adjusting 170 down and
86 up. The exact number doesn't matter for anything I'll say here.

Given the gap between 2^100 and 2^146, why does the call for proposals
ignore BHT, Ambainis, etc.? Anyone who thinks that NIST has defined
"gates", and that NIST's "gates" allow free memory, will have trouble
explaining this.

It's clear how many _operations_ are used by (e.g.) BHT, but turning the
operation count into a cost number to compare to other attacks requires
defining a cost metric. Novices might think that the choice of cost
metric is a matter of "low-order details", but the gap between 2^146 and
2^100 is bigger than most of the attack advances we've seen in NISTPQC,
including advances that NIST has used to publicly justify its decisions.
It's almost as big as the gap between Kyber-768 and what the New Hope
paper calls "JarJar". It's bigger than the pre-quantum gap between
RSA-2048 and RSA-1024.

Once upon a time, NIST cited https://cr.yp.to/papers.html#collisioncost
as justification for ignoring BHT. But that paper doesn't use a "gates"
metric, so this doesn't salvage the idea that NIST has defined a "gates"
metric. That paper also takes RAM costs into account in exponents, which
is the opposite direction from treating RAM as free.

Ray Perlner claimed in August 2020 that quantum RAM gates are "much less
realistic" than non-quantum RAM gates. This sounds very wrong to me---
cost 1 for an unlimited-size array lookup is not reality, and will never
be reality, whether quantum or not---but in any case it doesn't resolve
the more basic problem of _not having a definition_.

Where's the definition that says exactly which gates are included in
NIST's "gates"? If the situation is supposed to be that NIST's "quantum
gates" exclude RAM gates while, bizarrely, NIST's "classical gates"
_include_ RAM gates, then we should all be able to confidently see this
by looking at NIST's definition. But there is no definition!

The fact that NIST has never defined a cost metric to be used in NISTPQC
is a disincentive for detailed cost evaluations. Consider the quandary
facing Caroline the Cryptanalyst:

* If Caroline does the work to analyze system S in a realistic cost
metric (e.g., 1981 Brent--Kung with appropriate parameter choices,
or a quantum variant of the same thing) then people who don't like
S will complain that Caroline is cheating and overestimating
security through the choice of metric.

* If Caroline instead picks a simpler cost metric that ignores the
costs of RAM etc. then maybe Caroline will have less work, but
people who like S will (correctly) complain that Caroline is
underestimating security.

Caroline would be able to justify an analysis by pointing to NIST's
request for a particular metric---but NIST hasn't defined a metric to
use. Is it a surprise, then, that detailed cost evaluations in NISTPQC
have been so rare? Is it a surprise that, to the extent they exist, they
don't agree on which cost metrics to use?

Simply counting the higher-level operations that naturally appear in
attacks doesn't run into these problems, but how are we supposed to
compare attacks against different systems? Or attacks against the same
system, when the underlying operations are different? (For example,
within published lattice attacks, quantum enumeration looks more
efficient than sieving in _some_ cost metrics, although in this case
there are also many unresolved questions about the higher-level
operation counts.)

Even worse, NIST has managed to make many casual observers (not the
careful observers such as Caroline!) believe that NIST _has_ defined
metrics to be used in NISTPQC. The unfortunate reality is that there's a
definitional void filled with unjustified and conflicting assumptions.
For example:

* Some people think that NIST "gates" assign low costs to memory (so
BHT uses 2^100 NIST "gates" and the call for proposals is wrong).

* Some people think that NIST "gates" assign high costs to memory
(which is why BHT doesn't beat 2^146 NIST "gates").

These incompatible beliefs end up being applied inconsistently to
different candidates, as we're seeing in discussions right now about
multiple finalists. The same lack of definitions means that nobody can
figure out the "category" boundaries, even for the small number of
submissions where operation counts in attacks are thoroughly understood.
This is a cross-cutting failure in the NISTPQC evaluation procedures.

NIST has the unique power to fix this mess by issuing a _complete_
definition of a metric (or multiple metrics if that's really needed) for
_all_ NISTPQC submissions to use. This means not just waving around
ambiguous words such as "gates", but clearly specifying _which_ gates.
We can use, say, vOW and BHT cost analyses as test cases for the clarity
of the definition, and then we can all go ahead with evaluating all
submissions in the same metric.

Will this be the "best" metric? Unlikely. Maybe it will be so poorly
chosen as to noticeably damage parameter selection. But we're starting
from major ongoing damage to the evaluation process as a direct result
of NIST's "category" boundaries not having clear definitions.

> > We agree that the second column is sometimes less than the fourth column.
> > However, the second column ignores the huge overheads measured by the
> > third column.
> No. The second column includes a logarithmic memory overhead.

Counting cost 1 for each bit of an index i is simply reading i; it is
not covering the far larger costs of retrieving x[i]. The attack is, as
the submission states, "bottlenecked by random access to a huge array";
it is not bottlenecked by inspecting the indices used for this access.
The picture to have in mind here is a RAM request moving a huge distance
down wires (or fiber or any other physical communication technology),
compared to inspecting bits locally.

In algorithm analysis, pointing to overhead beyond cost analysis X means
pointing to a cost that _isn't_ included in X. A reader who redefines
"overhead" to cover something that _is_ included in X is not correctly
presenting the original statement. This redefinition is also missing the
point in this case: what we care about are "the huge overheads" of
continual RAM access, since those are the bottlenecks in the attack.

> > As stated in the submission:
> > A closer look shows that the attack in [11] is bottlenecked by random
> > access to a huge array (much larger than the public key being
> > attacked), and that subsequent ISD variants use even more memory. The
> > same amount of hardware allows much more parallelism in attacking,
> > e.g., AES-256.
> This is the second time you've used the word "huge". Let's give it some
> perspective. 2^35.66 bits is less RAM than the laptop I'm using to write
> this.

It's also 10000 times larger than the public key. This is "a huge array
(much larger than the public key being attacked)", as the submission
says. The same circuit size "allows much more parallelism in attacking,
e.g., AES-256", as the submission says. See

https://www.sites.google.com/site/michaeljameswiener/dessearch.pdf

for an example (predating AES) of the efficiency of special-purpose
hardware for cipher attacks.

The laptop "perspective" wildly overestimates the costs of attacks, as
already established in the literature on attack hardware. The amount of
overestimation varies from one cryptosystem to another. This makes the
laptop "perspective" useless for serious security evaluation---so why
are we seeing this "perspective" appearing in NISTPQC discussions?
Answer: it's yet another random attempt to fill the void left by NIST's
failure to _define_ the NISTPQC security requirements. All sorts of
people interested in NISTPQC are being put in the position of figuring
out for themselves what the NISTPQC security levels mean, because the
only organization in a position to do the job centrally hasn't done it.

> > The submission goes on to state expectations regarding (e.g.) 6960119
> > being more expensive to break than AES-256. The numbers you quote (e.g.,
> > 2^271.18 operations on 2^47.58 bits of RAM) are consistent with these
> > expectations.
> Your submission and this reply focus almost exclusively on the
> mceliece-6960-119 parameter set. What about the other four?

The submission takes this example (using the words "as an example") to
explain the most important effects separating cost metrics in this case:
namely, the state-of-the-art attacks are "bottlenecked by random access
to a huge array (much larger than the public key being attacked)", and
quantum attacks suffer "much more overhead in the inner loop". Repeating
the same points for each parameter set, mutatis mutandis, would be
unilluminating.

Because of the unlimited variation in cost metrics, any parameter set
can be ranked anywhere from "overkill" to "too small" depending on which
cost metric is selected, as the submission spells out for this example.
The incorrect idea that this is specific to Classic McEliece was already
answered: "Note that one can make any cryptosystem sound much easier to
break by choosing a cost metric that assigns unrealistically low cost to
operations used in attacks; RAM access is just one example. If the same
operations are not bottlenecks in attacks against AES-m or SHA-n then
this can reverse comparisons to AES-m or SHA-n respectively."

I'm very much in favor of building tables of publicly verified cost
evaluations for attacks across all parameter sets in all submissions,
with AES-128, SHA-256, etc. as baselines---including how the evaluations
are changing over time, so that we can recognize attack improvements,
evaluate security stability, and evaluate maturity of analysis. However,
this process doesn't work until NIST defines a cost metric for all
NISTPQC submissions to use. Allowing cost metrics to be selected ad-hoc
for particular submissions is error-prone and subject to abuse.

> > The literature shows that optimized hardware for AES attacks has similar
> > efficiency to multipliers. The multipliers in an Intel CPU core carry
> > out millions of bit operations in the same time that it takes the core
> > to retrieve data from (say) 6GB of RAM, never mind RAM contention across
> > cores. GPUs and TPUs show the costs of RAM even more clearly. On a
> > larger scale, decades of supercomputing literature consistently fit a
> > square-root scaling of RAM costs, and science-fiction 3D computers
> > (which seem much harder to build than quantum computers) would still
> > have cube-root costs.
> No. It's not as simple as applying a square-root overhead for memory across
> the board. For an interesting (but not very rigorous) example see
> http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html. The blog argues
> for a square-root memory cost. If you look at the graphs this is a poor
> fit in the 10 MiB to 6 GiB range.

Across seven orders of magnitude of array sizes, the graphs in that blog
post are always within one order of magnitude of the square-root
prediction (and people who understand the microarchitecture already know
where the deviations come from). If you look at the supercomputing
literature you'll see the same basic scaling across further orders of
magnitude. (See, e.g., https://cr.yp.to/papers.html#nonuniform, Appendix
Q.6, comparing the records from https://sortbenchmark.org at two
different sizes for the number of 100-byte items sorted per joule.)

There's also a clear physical mechanism producing the square-root
overhead: namely, moving a bit across distance sqrt(N) consists of
sqrt(N) motions through distance 1. Each motion through distance 1
occupies a constant amount of hardware for a constant amount of time,
the same way that a bit operation occupies a constant amount of hardware
for a constant amount of time. Overall the motion through distance
sqrt(N) is occupying Theta(sqrt(N)) times more hardware (per unit time)
than a bit operation is, where Theta covers the ratios between the
relevant constants.

This basic throughput barrier is exactly what one sees in the 1981
Brent--Kung theorem, which obtains the same square root for a broad
class of plausible machine models:

https://maths-people.anu.edu.au/~brent/pd/rpb055.pdf

Fiber doesn't magically avoid this throughput barrier: the hardware is
still filled up by the data being communicated. Free-space lasers might
seem to avoid the cost of equipment in the middle, but they spread out
linearly with distance and don't end up improving scalability.

The "holographic principle" in physics says that the information in a
volume of space is actually two-dimensional. (This won't surprise
physics students who have already practiced converting three-dimensional
to two-dimensional integrals.) The numerical limits don't say that
existing technology is close to optimal, but they do say that anyone
claiming better than square-root scaling is wrong for large enough sizes
and thus has a ton of explaining to do regarding cryptographic sizes.

An easy mistake to make here is to cherry-pick some news story about a
technology improvement at some medium size, and compare it to unimproved
technology at a small size (e.g., the laptop "perspective"), while
failing to ask whether technology improvements are also following the
expected square-root curve down to small sizes.

> Not all memory accesses are the same. The memory overhead depends on the
> number of random accesses to high-latency memory.

I agree that memory accesses differ in general. However, the attacks
we're talking about here are bottlenecked by random access to a huge
array ("much larger than the public key being attacked").

Note that one can replace parallel random access with, e.g., bitonic
sorting, at which point the word "random" might seem misleading since
at a low level all accesses are through a predefined network. What
really matters, as the Brent--Kung proof clearly shows, is simply how
much data is moving across long distances.

> One cost model in Ray Perlner's slides assumes that up to 2^50 bits of
> memory is local with unit cost memory accesses.

This was already answered: "The multipliers in an Intel CPU core carry
out millions of bit operations in the same time that it takes the core
to retrieve data from (say) 6GB of RAM, never mind RAM contention across
cores."

> Can you point to the paper cited by your
> submission that gives numbers for the mceliece-4608-096 parameter set
> which clearly justify its assignment as category 3?

NIST has failed to define the metrics to be used, so there's no way for
anyone to be sure what's included in "category 3".

This isn't specific to Classic McEliece. Every submission is in the same
position of uncertainty regarding what NIST's security requirements
mean. Beyond actual security risks, this creates an artificial risk of
being criticized for allegedly not meeting someone's interpretation of
NIST's security requirements. There is no way to avoid this risk: _any_
"category" assignment of _any_ parameter set in _any_ submission can be
targeted by a metric-selection attack. The way that these criticisms are
allocated to submissions has nothing to do with security; it is a
political game of ad-hoc marketing of cost metrics.

Regarding citations, the Classic McEliece submission cites the original
attack papers. Those papers, in turn, convincingly count the operations
that they use. Each operation count corresponds to many different cost
numbers for many different choices of cost metric:

attack analysis cost metric 1
attack ---------------> operation count -------------> cost 1
\ \ \ \ \ cost metric 2
\ \ \ \ \-------------> cost 2
\ \ \ \ cost metric 3
\ \ \ \-------------> cost 3
\ \ \ cost metric 4
\ \ \-------------> cost 4
\ \ cost metric 5
\ \-------------> cost 5
\ cost metric 6
\-------------> cost 6
etc.

This correspondence is conceptually straightforward, but _which cost
metric are submitters supposed to use for NISTPQC_? Nobody knows.

There are other submissions where the operations in attacks are much
harder to count, but if we optimistically imagine this problem being
fixed then we're still faced with the same basic cost-metric question
for all submissions, as noted above.

Submitters could start from Perlner's recent "preliminary" slides, which
run through various possible features of metrics. How many metrics are
clearly defined in those slides, with a NIST commitment to treat attacks
in those metrics as being relevant? Zero. So what exactly are submitters
supposed to do? For each feature listed by Perlner, try to guess the
sanest-sounding definition of a specific metric that seems consistent
with that feature, and then work through a pile of cost evaluations in
all of these metrics, while being pretty sure that NIST will disregard
most, perhaps all, of the resulting numbers? See how crazy this is?

> You are arguing that because NIST has not specified a single metric
> no evaluation in any metric can be valid. The Call for Proposals actually
> says (NIST's emphasis):
> "In order for a cryptosystem to satisfy one of the above security
> requirements, any attack must require computational resources
> comparable to or greater than the stated threshold, with respect
> to *all* metrics that NIST deems to be potentially relevant to
> practical security."
> NIST gives circuit size as an example of a metric

No.

As a baseline, I think everyone agrees that the structure specified in
the call for proposals is as follows:

* There's a set M of metrics to be used for NISTPQC (the "metrics
that NIST deems to be potentially relevant to practical security").

* Cryptosystem X is eliminated from category 1 (and thus from
NISTPQC) if there's even _one_ metric in M saying that attacking X
costs less than AES-128 key search.

* Cryptosystem X is eliminated from category 2 if one metric in M
says that attacking X costs less than SHA-256 collision search.

* Similarly for other categories.

But what's M? Can we even point to _one_ clear example of something in
M? Unfortunately not. If you look for a NIST document that clearly
defines a metric and specifies that the metric is in this set M, you
won't find any such document!

For example, it's _not_ true that there's some clearly defined "circuit
size" metric specified to be in M, and it's not true that there's some
clearly defined "gates" metric specified to be in M. A clear definition
of NIST "gates" would let the community understand and verify the claim
in the call for proposals that known SHA3-256 attacks, such as BHT,
don't beat 2^146 NIST "gates". Right now this is unverifiable,
unfalsifiable, mathematically meaningless, since there's no definition.

> and says that AES-192 key
> recovery is equivalent to 2^207 classical gates in this metric

Unfortunately NIST never defined "this metric". See above.

> That's it. No mention of the other parameter sets. No attempt to quantify
> the impact of memory accesses.

The literature already pinpoints the number of memory accesses for
arbitrary input sizes. As soon as NIST defines a cost metric, an
analysis in that metric will be straightforward.

> Just a vague statement that something that is "considerably below
> 2^256" bit operations will be fine because memory.

The actual "will be fine" statement is "more expensive to break than
AES-256". This is not vague. It has the cost metric as a parameter, and
of course one _can_ define cost metrics that reverse the comparison by
ignoring important components of costs, but, again, having to allow
every possible metric would undermine _every_ category assignment in
_every_ submission.

Quantifying "considerably below 2^256" depends on the cost metric. The
minimum "time" in the literature is achieved by algorithms using absurd
amounts of memory, and those algorithms are optimal in metrics that allow
x[i] with cost 1, but gradually increasing the RAM cost in the metrics
(compared to other costs) shifts the optimum to different algorithms.

> This is the irrelevant hype I mean. You are ignoring asymptotic improvements
> to half-distance decoding because McEliece uses errors with sublinear weight

Carefully quantifying the application of attack ideas to a cryptosystem,
and correctly concluding that the asymptotic change in security levels
is exactly 0%, is not "ignoring" anything.

The 0% change has always been clearly and correctly labeled as being
asymptotic. This means that there's <10% change once the security level
is large enough, <1% change once the security level is large enough,
etc. Regarding the question of what "large enough" means, the submission
cites the relevant attack papers and emphasizes the importance of
concrete cost analysis.

Seeing that lattices have a worse picture here---e.g., the asymptotic
lattice security levels were 42% higher just ten years ago---is a risk
indicator. Nobody says it's the only risk indicator! Classic McEliece
has established a strong track record of observing many other risk
indicators and acting accordingly.

This is important. History suggests that identifying and monitoring risk
indicators is one of the most effective ways that system designers can
avoid disasters. There's ample evidence for this in the general
risk-management literature, and there's quite a bit of evidence in
cryptography.

Consider, for example, pre-quantum discrete-logarithm-based
cryptography. There was already a long history by 2005 of

* multiplicative groups suffering percentage losses (and sometimes
larger losses) of asymptotic security levels, including losses
avoided by elliptic curves, and

* fields with extra automorphisms suffering percentage losses of
asymptotic security levels, including losses avoided by prime
fields.

Public recommendations from cryptographers monitoring the literature
concluded that multiplicative groups were higher risk than elliptic
curves, and that fields with extra automorphisms were higher risk than
prime fields. (Of course, people desperate to paint the opposite picture
could always come up with reasons: the RSA company was still claiming
that elliptic curves hadn't been studied, for example, and there was
also an interesting story regarding "medium" fields.) Unsurprisingly, we
saw big further security losses after that for multiplicative groups
(for some highlights see https://blog.cr.yp.to/20161030-pqnist.html),
especially in the case of fields with extra automorphisms.

What does this tell us about lattices vs. McEliece? Should we be on the
alert for percentage losses of asymptotic security levels (many losses
for lattices, nothing for McEliece)? Larger losses (yes for lattices, no
for McEliece)? Unnecessary automorphisms? All of the above?

If there's a rational argument that a particular risk indicator _isn't_
helpful, the argument should be published for further analysis. Posting
one message after another labeling a risk indicator as "irrelevant hype"
doesn't move the analysis forward, and seems hard to reconcile with the
thoroughly documented discrete-log history.

> yet compare it with asymptotic improvements to the exact short vector problem
> even though lattice schemes depend on different variants of the problem.

Actually, the SVP security levels being asymptotically 42% higher in
2010 than today translates directly into the security levels of
(otherwise unbroken) lattice systems being asymptotically 42% higher in
2010 than today. Basically, the lattice attacks are bottlenecked by BKZ,
and BKZ is bottlenecked by a relatively short series of expensive
shortest-vector searches in a lower dimension (beta, the "block size"),
so if the SVP solution loses P% of its asymptotic bits of security then
the whole attack loses P% of its asymptotic bits of security.

(BKZ is one of many algorithms, and ongoing research indicates that SVP
isn't really the right interface, but these issues don't seem to affect
the exponent. A bigger issue is hybrid attacks: my message on that topic
in July outlines a way to remove another percentage from the security
level for any system with errors in, say, {-3,...,3}, so the loss for
lattice security compared to 2010 will be even larger than the SVP loss.
Some hybrid-attack details still need verification, and the percentage
hasn't been calculated yet.)

For comparison, consider https://eprint.iacr.org/2017/1139.pdf reporting
exponent 0.0465 for half-distance decoding, where Prange's algorithm
from 51 years earier was exponent 0.0576; see the paper for a survey of
intermediate results. This asymptotic 24% change corresponds to an
asymptotic 0% change in the asymptotic security level of McEliece's
system. The situation for McEliece's system has always been that the
asymptotic bits of security come primarily from a gigantic combinatorial
search through information sets.

To summarize: The graph in https://video.cr.yp.to/2020/0813/video.html
correctly compares asymptotic attack costs, as the label indicates. In
particular, the asymptotic security level of otherwise unbroken lattice
cryptosystems has dropped as dramatically as shown in the graph. (Also,
recent work, once quantified, should produce further lattice losses.)

> > The section goes on to summarize what the literature says about concrete
> > cost analyses, and ends with the AES-256 comparison reviewed above.
> The rest of section 8.2 is quoted above in its entirety. The literature
> says much more about concrete cost analyses than this "summary".

"Summary, noun: a brief statement or account of the main points of
something." I agree that the literature says much more than the summary
does.

> > Evaluating such a claim would require a clear, stable definition of
> > "Category 3". If NIST settles on a definition to be used in NISTPQC then
> > submitters will be able to make "category" assignments accordingly.
> > See above regarding the actual costs of accessing 6GB of RAM.
> No. The definition of category 3 is stable.

No, it isn't. NIST has never issued a clear, stable definition of
"Category 3". NIST has given a pseudo-definition---something that looks
at first glance like a definition but that turns out to rely on
undefined metrics. How are submitters supposed to evaluate costs in cost
metrics that haven't been defined? See above.

> 2^189.2 classical gates does not mean 2^189.2 random memory
> accesses. Not all gates involve a memory access. Not all memory accesses
> are to high-latency memory. Not all high-latency memory accesses are
> random.

It's of course true across the field of cryptanalysis that attacks vary
in how often they're randomly accessing memory. However, all of the
attacks we're discussing here are bottlenecked by random access.

> My point is that you can't just say that everything will be fine
> because memory. You actually need to do the analysis.

The attack paper [11] cited in exactly this section of the submission
already includes a detailed cost analysis of Stern's attack with many
further optimizations. The inner loop consists of picking up a number
that looks random, xor'ing it into an index i, randomly accessing x[i],
and going back to the top of the loop.

As the submission says, this attack is "bottlenecked by random access".
Newer attacks are similarly memory-bound, using even more memory.

The operation counts are clear (for this submission; again, there are
other submissions where attacks are much harder to analyze). The notion
that there's some missing analysis of how many RAM accesses there are is
simply not true. What's missing is a definition from NIST of how NISTPQC
assigns costs to x[i] and other operations.

> > There's also a tremendous amount to say about the dangers of unnecessary
> > complexity. One aspect of this is specifying more parameter sets than
> > necessary. Of course, NIST's request for lower-security parameter sets
> > was an offer that Classic McEliece couldn't refuse, but we continue to
> > recommend the 2^256 parameter sets.
> I assume that if Classic McEliece is chosen for standardization you will
> be withdrawing the parameter sets that you don't recommend for use.

Procedurally, NIST is in charge, and has always specifically reserved
the right to make its own parameter-set decisions after it consults with
the submitters and the community. See the call for proposals. Obviously
submission teams and other interested parties will provide feedback to
NIST regarding the wisdom of their decisions.

> > One can easily write down even larger parameter sets. Also, the ISD
> > attack analyses in the literature are precise and straightforward, and
> > it should be easy to evaluate the security of any desired parameters in
> > any well-defined metric. However, the right order of events is, first,
> > for NIST to fully define the cost metric to be used for "categories",
> > and, second, for all submission teams to evaluate costs in this metric.
> No. The right order of events is, first, submit parameter sets with security
> estimates in a metric that you think is practically relevant and, second,
> let eveyone else spend three rounds of the NIST process evaluating those
> claims. That's what most of other submissions have done.

No, it isn't. Let's take the Kyber submission as a case study of what
other submissions have in fact done.

The round-3 Kyber submission has an analysis concluding that attacks
against round-3 Kyber-512 are probably---accounting for the "known
unknowns"---somewhere between 2^135 and 2^167 "gates", a remarkably wide
range for a cryptosystem that claims its security is well understood.

The submission hopes that the "known unknowns" will be pinned down, and
that the final answer will be above 2^143. The submission also claims to
use a "conservative lower bound" on attack costs. Can NIST see whether
this "bound" is above or below 2^143? Can anyone else see this? Nope.

Could someone have been reviewing the analysis since the first round of
the NIST process? No. The parameter set has changed. The analysis has
changed. The problem that cryptanalysts are being asked to study has
changed! Kyber-512 used to claim that its security was based on the
MLWE problem, but, as far as I can tell, this has been dropped in round
3. Concretely, my understanding is that if someone claims an attack
against round-3 Kyber-512 by showing that MLWE for that size is easier
to break than AES-128, the official response will be that the round-3
submission does _not_ claim MLWE attacks are so hard---its security
levels are claimed only for direct IND-CPA/IND-CCA2 attacks. (I've
asked for confirmation of this in a separate thread on Kyber.)

So much for spending "three rounds of the NIST process evaluating those
claims", or, in the words of the call for proposals, "maturity of
analysis". Now let's move on to the "metric" question.

Let's say Caroline the Cryptanalyst is looking at round-3 Kyber-512.
What would be required, structurally, for Caroline to show that round-3
Kyber-512 is broken? Let's assume for simplicity that Kyber "gates" are
clearly defined and that AES-128 key search needs 2^143 Kyber "gates".
Here are two possibilities for Caroline:

* Strategy 1: Show that the best attacks considered in the submission
actually use fewer than 2^143 "gates". This is compatible with the
2^135...2^167 range claimed in the submission.

* Strategy 2: Show that attacks not considered in the submission,
such as hybrid attacks, use fewer than 2^143 "gates".

These would both be breaks, since they'd violate the minimum for
category 1, right? Nope. The submission protects itself against this by
leaving wiggle room in the cost metric. Here's the critical quote:

We do not think that [2^135] would be catastrophic, in particular
given the massive memory requirements ...

The submission is saying that 2^135 "gates" wouldn't actually be a
problem (assuming the attacks use tons of memory, which most, although
not all, lattice attacks do), since of course memory costs much more
than a "gate" count indicates.

Should Caroline expect NIST to downplay the memory requirements and
accept the attack as a break? Why?

NIST has repeatedly asked for "confidence" that the NISTPQC security
requirements are reached. I challenged the security of round-2
Kyber-512, pointing out errors in the security analysis and pointing out
reasons to believe that known attacks don't use more "gates" than
AES-128. Did NIST claim "confidence" that the attacks actually use more
"gates" than AES-128? No. Did NIST kick out that parameter set? No.
Instead NIST initiated a "preliminary", open-ended project to start
incorporating overheads into cost metrics.

Does this sound like NIST automatically kicking out any parameter set
when there's an attack below 2^143 "gates", with free RAM "gates"? No.
It sounds like NIST shifting the boundaries of "category 1" as far as
necessary to declare that Kyber-512 isn't broken, by playing games with
the cost metric. Maybe NIST has another reason for not specifying a
metric, but in any case the moving target deters cryptanalysis.

Part of recognizing security risks is recognizing the procedures that
are actually being used for designing, evaluating, and standardizing
cryptography. Cryptanalytic work is a critical part of this, and NISTPQC
is raising far more security questions than cryptanalysts can answer in
the time available. It's not as if the attack picture was stable in
2020, so why should we expect it to suddenly be stable in 2021, or in
2025? This denial-of-service attack against cryptanalysts starts from
the inherent cryptanalytic complexity of post-quantum cryptography, but
the attack is exacerbated by NIST's continued failure to clarify its
pseudo-definition of the minimum allowed NISTPQC security level.

---Dan
signature.asc

Kirk Fleming

unread,
Dec 11, 2020, 8:29:27 PM12/11/20
to pqc-forum, pqc-co...@nist.gov
Dan Bernstein (speaking for himself) wrote:
> As far as I can tell, the questions specific to Classic McEliece
> have already been answered.
 
In the formal sense that you responded, I guess. It's like asking
the time and being told that it depends on the observer's frame of
reference. Thanks Einstein. It is an answer but I still don't know
if I'm late for class.
 
Kirk Fleming wrote:
>>>> I am filing this comment to request that the Classic McEliece
>>>> submitters justify the claimed security categories for their
>>>> parameters.
 
Dan Bernstein (on behalf of the Classic McEliece team) wrote:
>>> Can you please clarify how you think that the numbers already
>>> in the literature don't already justify the assignments in the
>>> submission?
 
Kirk Fleming wrote:
>> Let's try an easier question. Can you point to the paper cited

>> by your submission that gives numbers for the mceliece-4608-096
>> parameter set which clearly justify its assignment as category 3?
 
Dan Bernstein (speaking for himself) wrote:
> NIST has failed to define the metrics to be used, so there's no
> way for anyone to be sure what's included in "category 3".
 
To be absolutely clear, you are stating that the numbers in the
literature already justify the assignments in the submission but
that you can't point to any specific numbers because there is no
way for anyone to be sure what's included in each category.
 
Okaaaay.
 
Let's try an even easier question. Why mceliece-4608-96?
 
The mceliece-6960-119 parameter set was taken from "Attacking and
defending the McEliece cryptosystem". You could have chosen the
mceliece-4624-95 parameter set from the same paper. Instead you
chose a parameter set which had "optimal security within 2^19 bytes
if n and t are required to be multiples of 32". (mceliece-4624-95
was chosen to be optimal without the restrictions on n and t)
 
mceliece-5856-64 and mceliece-4160-128 are also within 2^19 bytes.
Both of these have smaller public keys than mceliece-4608-96 and
mceliece-5856-64 has smaller ciphertexts. Please explain the metric
you used to decide which of the three parameter sets had "optimal
security".
 
Kirk

Kirk Fleming

unread,
Dec 30, 2020, 7:49:37 PM12/30/20
to pqc-forum, pqc-co...@nist.gov
I promise this is my last message on the topic. Dan has
stopped responding but I wanted to make one final point.
 
Dan Bernstein (on behalf of the Classic McEliece team) asked:

> Can you please clarify how you think that the numbers already
> in the literature don't already justify the assignments in the
> submission?
 
The only concrete security estimate given in the entire Classic
McEliece submission is:
 
  "[Bernstein, Lange and Peters. 2008] reported that its attack

   uses 2^266.94 bit operations to break the (13,6960,119)
   parameter set."
 
This is not true. Bernstein, Lange and Peters actually say:
 
  "For keys limited to 2^16, 2^17, 2^18, 2^19, 2^20 bytes, we
   propose Goppa codes of lengths 1744, 2480, 3408, 4624, 6960
   and degrees 35, 45, 67, 95, 119 respectively, with 36, 46,
   68, 97, 121 errors added by the sender. These codes achieve
   security levels 84.88, 107.41, 147.94, 191.18, 266.94 against
   our attack."
 
The 2^266.94 estimate is not for mceliece-6960-119. It's for a
different parameter set that uses list decoding to increase the
number of errors that can be corrected.
 
The submission's lack of any serious security analysis for the
five parameter sets being proposed should be cause for concern.
The team's refusal to provide any justification for their claimed
security categories when challenged should be disqualifying.
 
Kirk
 

Christopher J Peikert

unread,
May 21, 2021, 12:55:12 AMMay 21
to Kirk Fleming, pqc-forum, pqc-comments
Was there ever any response (from the Classic McEliece team or otherwise) to this comment from 30 Dec 2020? More specifically:

On Wed, Dec 30, 2020 at 7:49 PM Kirk Fleming <kpfl...@mail.com> wrote:
The only concrete security estimate given in the entire Classic
McEliece submission is:
 
  "[Bernstein, Lange and Peters. 2008] reported that its attack
   uses 2^266.94 bit operations to break the (13,6960,119)
   parameter set."
 
This is not true. Bernstein, Lange and Peters actually say:
 
  "For keys limited to 2^16, 2^17, 2^18, 2^19, 2^20 bytes, we
   propose Goppa codes of lengths 1744, 2480, 3408, 4624, 6960
   and degrees 35, 45, 67, 95, 119 respectively, with 36, 46,
   68, 97, 121 errors added by the sender. These codes achieve
   security levels 84.88, 107.41, 147.94, 191.18, 266.94 against
   our attack."
 
The 2^266.94 estimate is not for mceliece-6960-119. It's for a
different parameter set that uses list decoding to increase the
number of errors that can be corrected.

Does anyone know what effect this has on security?
 
The submission's lack of any serious security analysis for the
five parameter sets being proposed should be cause for concern.
The team's refusal to provide any justification for their claimed
security categories when challenged should be disqualifying.

Has there since been any such security analysis or justification provided for the proposed parameter sets?

Sincerely yours in cryptography,
Chris

Ruben Niederhagen

unread,
May 21, 2021, 5:09:35 AMMay 21
to Christopher J Peikert, Kirk Fleming, pqc-forum, pqc-comments
On 5/21/21 6:54 AM, Christopher J Peikert wrote:
> On Wed, Dec 30, 2020 at 7:49 PM Kirk Fleming <kpfl...@mail.com> wrote:
>
>> The only concrete security estimate given in the entire Classic
>> McEliece submission is:
>>
>> "[Bernstein, Lange and Peters. 2008] reported that its attack
>> uses 2^266.94 bit operations to break the (13,6960,119)
>> parameter set."
>>
>> This is not true. Bernstein, Lange and Peters actually say:
>>
>> "For keys limited to 2^16, 2^17, 2^18, 2^19, 2^20 bytes, we
>> propose Goppa codes of lengths 1744, 2480, 3408, 4624, 6960
>> and degrees 35, 45, 67, 95, 119 respectively, with 36, 46,
>> 68, 97, 121 errors added by the sender. These codes achieve
>> security levels 84.88, 107.41, 147.94, 191.18, 266.94 against
>> our attack."
>>
>> The 2^266.94 estimate is not for mceliece-6960-119. It's for a
>> different parameter set that uses list decoding to increase the
>> number of errors that can be corrected.
>>
>
> Does anyone know what effect this has on security?

According to the analysis in the quoted paper [Bernstein, Lange and
Peters. 2008], the difference in the security level when going from 121
errors to 119 errors while keeping the other parameters unchanged is
about 4.

Ruben
(speaking for myself)

Reply all
Reply to author
Forward
0 new messages