New decoding record: length-1347 McEliece challenge solved

[D. J. Bernstein]

A Eurocrypt 2022 paper announced solutions to the length-1223 and
length-1284 challenges from https://decodingchallenge.org/goppa. I'm
pleased to announce a solution to the length-1347 challenge.

This new record does not come from new algorithmic improvements. On the
contrary, I simply ran the ISD attack software from the following 2008
paper: Daniel J. Bernstein, Tanja Lange, and Christiane Peters,
"Attacking and defending the McEliece cryptosystem", PQCrypto 2008.

There have been only slight speedups in ISD algorithms since 2008. The
fact that 15-year-old attack software remains competitive with the
latest attack software in setting records is a remarkable testament to
the stability of the McEliece attack picture.

See https://isd.mceliece.org/1347.html for further information.

---D. J. Bernstein

P.S. For lattice-based cryptography, has anyone tried taking the best
2008 attack software (I guess this means NTL 5.4.2) and measuring how
many orders of magnitude faster today's attack software is in solving
lattice challenges?

[Andre]

Dan,

Congratulations on obtaining the new record.

However, as we discussed recently here on the mailing list, our paper always
supported the good stability of McEliece security
(https: //groups. google. com/a/list. nist. gov/g/pqc-forum/c/ldAzu9PeaIM/m/yE4qSYPoB
AAJ). Also, in this discussion, I corrected your interpretation of us claiming
*huge* speedups over previous algorithms, like Dumer / Stern, on mid-sized
instances (e. g. , Challenges 1284 and 1347): We claimed roughly an order of
magnitude over *available* implementations. Note that your code was (despite a
promise in the original 2008 paper) not available online until *after* our
recent record computations...

In this discussion, you then provided benchmarks that your Stern implementation
performs roughly on par with our MMT / BJMM on *mid-sized instances*. I remarked
that your implementation is highly optimized for these challenge-sized instances
by allowing only for a very specific configuration of the algorithm. Precisely,
a configuration that is non-optimal for large McEliece instances, i.e., for
security-relevant instances.

Overall, your record does not uncover any new findings, but is (no offense) part
of a Classic McEliece marketing campaign.

Further, your record does of course *not* imply that algorithmic improvements of
the last decades for *cryptographic-sized* instances have been minor. It either
means that the break-even point to those algorithms lies beyond code length 1347
or is already reached and you simply used more computational power.

Honestly, I don't understand why you promote those weak security arguments for a
scheme known as secure as McEliece. It is already well understood by the
cryptographic community and especially by NIST that in terms of security,
McEliece is a prime candidate. NIST's round 3 report starts the overall
assessment of McEliece with "NIST is confident in the security of Classic
McEliece [... ]" and justifies deciding against McEliece with "[... ] it is unclear
whether Classic McEliece represents the best option for enough applications to
justify standardizing it at this time. ".

Therefore, listing real-world applications seems to be more fruitful than using
weak security arguments when pushing for the standardization of a scheme whose
security is not in doubt.

-Andre (speaking for myself)

[D. J. Bernstein]

Andre writes:
> Congratulations on obtaining the new record.

Thank you.

> However, as we discussed recently here on the mailing list, our paper
> always supported the good stability of McEliece security

Here I'm confused: "however" sounds like there's a contradiction, but
"good stability of McEliece security" sounds compatible with my message
("There have been only slight speedups in ISD algorithms since 2008").

> Also, in this discussion, I corrected your interpretation of us claiming
> *huge* speedups over previous algorithms, like Dumer / Stern, on mid-sized
> instances (e. g. , Challenges 1284 and 1347):

Sorry, I'm having trouble matching this up to the previous discussion.
If I said something wrong, please give an exact quote and explain the
issue with the quote so I can issue an appropriate erratum.

The actual claim at issue here is as follows. Regarding what the 2022
paper calls "modern ISD", that paper claims to "demonstrate that these
algorithms lead to significant speedups for practical cryptanalysis on
medium-sized instances (around 60 bit)": https://eprint.iacr.org/2021/1634

The evidence accumulated against this claim includes

* a new record from the 2008 software on the series of challenges
selected in the 2022 paper;

* https://cr.yp.to/software/lowweight-20220616.tar.gz, a head-to-head
comparison showing that the 2008 software is _faster_ than the 2022
software for the challenges selected in the 2022 paper, on exactly
the CPUs selected in the 2022 paper; and

* identification of previous algorithmic speedups (e.g., Omura's
random walks) that the 2022 paper appears to have omitted from its
baseline---tilting the 2022 comparison in favor of "modern ISD",
since (as quantified in the 2008 paper) these speedups have much
more impact on the baseline than on "modern ISD".

Structurally, a claim to demonstrate algorithmic speedups has to be
backed by a direct comparison to the best previous algorithm, but the
2022 paper compared to a worse algorithm.

> We claimed roughly an order of
> magnitude over *available* implementations.

I agree that page 4 of the 2022 paper states a comparison to "available
implementations". However, this comparison of implementations doesn't
justify the paper's highlighted claim of better _algorithms_ ("these
algorithms lead to significant speedups for practical cryptanalysis on
medium-sized instances (around 60 bit)").

A careful reader finds page 10 of the 2022 paper saying "we refrain from
further optimizations of this step, as introduced in [7, 17]". There's a
preceding argument on page 10 that this specific speedup is small. In
fact, there is a synergy between this speedup and other speedups that
are explained in the 2008 paper, such as the use of 2^l-bit tables with
a choice of l that fits into cache.

The fundamental technical point here is that small amounts of memory are
much less expensive to access than large amounts of memory. This rewards
ISD algorithms that squeeze into small amounts of memory. For those ISD
algorithms, one easily sees the impact of reducing linear-algebra costs,
for example using Omura's random walks and the 2008 improvements.

> Note that your code was (despite a promise in the original 2008 paper)
> not available online until *after* our recent record computations...

The speedups used in the software were explained in detail in the 2008
paper. Furthermore, many people received copies of the software as part
of carrying out the record computation in 2008. I don't recall the
authors of the 2022 paper ever asking for a copy for comparison.

As for "promise": No, there was no such promise. The paper said "plan"
("We plan to publish our attack software"). A delay of plans, even a
complete change of plans, is not a broken promise. Words have meanings.

> In this discussion, you then provided benchmarks that your Stern
> implementation performs roughly on par with our MMT / BJMM on
> *mid-sized instances*.

I guess you're referring here to the first message in that thread, in
which the 2008 authors wrote "Our PQCrypto 2008 ISD algorithm is faster
than the Eurocrypt 2022 ISD algorithm, on the CPUs selected in the new
paper, for the challenges selected in the new paper, according to a
direct comparison of (1) our measurements of the 2008 software (the 2+2
case of the 2008 algorithm) and (2) the speeds reported in the new paper
for that paper's software."

> I remarked that your implementation is highly optimized for these
> challenge-sized instances

The 2022 paper omits, from its comparison baseline, various speedups
that had appeared in the previous literature. These speedups are not
specific to "challenge-size instances".

Meanwhile the 2022 software uses 256-bit vector intrinsics that Intel
introduced in 2013. (Vector intrinsics are manual effort to compensate
for compilers having limited understanding of vectorization.) Obviously
the 2008 software doesn't. So which software is "highly optimized"?

I agree with the general point that one needs to be careful in using
software performance as a proxy for algorithm performance. There's a
general warning in the 2008 paper that "optimizing CPU cycles is
different from, and more difficult than, optimizing the simplified
notion of 'bit operations' " used in the algorithm analysis; and the
details in the 2008 paper refer to performance of a particular CPU.

I don't see any such warnings in the 2022 paper. On the contrary, the
2022 paper extrapolates algorithm performance for cryptographic sizes
starting from the statement that "a logarithmic access cost most
accurately models our experimental data". The 2022 paper reaches this
statement from observations of how software timings vary across sizes.

Content-wise, the 2022 observations appear to all have been at the same
level of the CPU's cache hierarchy, in part because the 2022 paper
didn't use the 2^l-bit tables from the 2008 algorithm (see Section 6 of
the 2008 paper) and in part because the 2022 paper considered only a
limited range of problem sizes. It isn't physically plausible that the
costs of RAM scale logarithmically, and serious graphs such as

https://i0.wp.com/chipsandcheese.com/wp-content/uploads/2022/06/image-4.png
https://i0.wp.com/chipsandcheese.com/wp-content/uploads/2022/06/image-1.png

immediately show the slowdowns of moving from, e.g., L1 cache to L2
cache to L3 cache. One doesn't see these slowdowns if measurements are
limited to a single cache level.

> by allowing only for a very specific configuration of the algorithm.

It's correct that the software focuses on the case of 2+2 errors. This
is for code simplicity. The speedups in question are not limited to this
case.

> Precisely, a configuration that is non-optimal for large McEliece
> instances, i.e., for security-relevant instances.

No, this is a circular argument:

* The 2022 paper's claim that one should use high-memory parameters
for cryptographic attacks relies on its claim of logarithmic
scaling of costs of RAM.

* The 2022 paper obtains the claim of logarithmic scaling from
observations of the 2022 software.

* The 2022 software doesn't take advantage of the extra speed of
fitting into small amounts of RAM.

* Ergo, it's circular to argue that this speedup should be ignored on
the basis of its alleged irrelevance to cryptographic sizes.

Serious attackers will instead take advantage of the better performance
obtained by ASICs running many low-memory ISD computations in parallel.

> Overall, your record does not uncover any new findings,

Now I'm puzzled. If new records aren't new findings, then why is a new
record highlighted in the title of the 2022 paper?

> but is (no offense) part of a Classic McEliece marketing campaign.

No. I agree that the long-term stability of attacks against the McEliece
cryptosystem is a central argument for using that cryptosystem; I don't
agree that you've identified any errors, let alone the sort of sustained
errors that would justify the pejorative terminology here. (As a side
note, it's interesting how one-sided NIST's tone policing is.)

The 2022 paper and https://www.youtube.com/watch?v=tSGe1atsKAI _claim_
to identify mistakes in the Classic McEliece security analysis---

This ISD algorithm, due to Prange [18], is the main tool for
estimating the security of code-based cryptography such as McEliece
and BIKE/HQC. ... Both the BIKE/HQC and McEliece teams use the
asymptotic formula from Equation (2) to analyze their bit-security
... in McEliece’s (large) weight regime the speedups are so
significant that they indeed lead to measurable security losses ...
McEliece Slightly Overestimates Security.

... And unfortunately the works were not taking newly experimented,
experimental data created or existing one together with estimates to
extrapolate the hardness of the instances. No, they were taking the
asymptotic run time formula from Prange. ... So I know I'm drawing a
quite bad picture here.

---but alert observers will notice that neither of these sources quotes
the submission. Anyone who takes the time to check what the submission
actually says (see my email dated 14 Jun 2022 06:05:31 +0200) sees that,
no, the submission had always explicitly recognized and avoided exactly
these mistakes.

Let me suggest issuing a clear erratum for the record regarding the
claim that the Classic McEliece submission uses Prange for concrete
security estimates. It would also be useful, in the future, to use exact
quotes to reduce risks of misattribution.

> Further, your record does of course *not* imply that algorithmic
> improvements of the last decades for *cryptographic-sized* instances
> have been minor.

All of the improvements change the exponent by only a 1+o(1) factor
asymptotically. Certainly the literature says that a closer look at
performance for concrete sizes detects differences among different ISD
variants. This has always been emphasized in the Classic McEliece
submission, and was again noted in https://isd.mceliece.org/1347.html:
"It is also important to note that different algorithms can scale
differently. The best algorithm for a challenge is not necessarily the
best algorithm for a larger challenge. Algorithm analyses are used to
predict cryptographic security levels; scaled-down computations are used
as a double-check on the analyses."

> It either means that the break-even point to those algorithms lies
> beyond code length 1347 or is already reached and you simply used more
> computational power.

"More computational power" is ambiguous: what's the baseline?

One interpretation is that the baseline is what would have happened with
the 1347 record using the 2022 software. The 2008 software is faster
than the 2022 software for 1284, so if the 2022 software is faster than
the 2008 software for 1347 then it would be by such a small margin as to
require careful benchmarking.

A different interpretation is that the baseline is the 1284 record.
Certainly the 1347 record used more computational power than the 1284
record. For these parameter shapes, each extra error makes attacks
roughly 5x harder. The 2008 software certainly isn't gaining 5x, and the
random searches weren't unusually lucky.

As for "break-even point", that's a scientifically problematic concept
when the curves in question have similar shapes, because a small change
in the curves can easily produce a large change in the break-even point.

> Honestly, I don't understand why you promote those weak security arguments
> for a scheme known as secure as McEliece.

Similar question to the above: If new records are "weak" arguments, then
why is a new record in the title of the 2022 paper?

> It is already well understood by the
> cryptographic community and especially by NIST that in terms of security,
> McEliece is a prime candidate. NIST's round 3 report starts the overall
> assessment of McEliece with "NIST is confident in the security of Classic
> McEliece [... ]"

Sure, but NIST's concept of "confidence" is a low bar. For example:

* NIST's round-2 report mentioned NIST's "confidence in
better-performing signature algorithms" than SPHINCS+.

* NIST's 21 January 2021 email appeared to indicate that new attacks
against Rainbow and GeMSS were examples of shaking this
"confidence".

* NIST's round-3 report says NIST is "confident" in lattice
algorithms.

I think long-term security should be the top goal, but I don't see
where the facts regarding security stability---for example, the fact
that lattices have lost much more security since (e.g.) 2008 than the
McEliece system has---are reflected in any of NIST's reports. Instead
NIST seems to be under the impression that the only reason to use
McEliece is its small ciphertexts.

Perhaps this is because the security-stability facts are inadequately
documented. For people who aren't immersed in the attack literature, an
ISD paper claiming to gain a few bits sounds a lot like a lattice paper
claiming to gain a few bits, and it's hard to see the big picture of
McEliece attacks being much more stable than lattice attacks.

Now everyone can see 15-year-old attack software remaining competitive
and setting new records, and can ask for a comparison to how much
lattice-attack speed has changed in the past 15 years.

> and justifies deciding against McEliece with "[... ] it is
> unclear
> whether Classic McEliece represents the best option for enough applications
> to
> justify standardizing it at this time. ".
> Therefore, listing real-world applications seems to be more fruitful

Certainly listing real-world applications is useful. Note that there has
already been quite a bit of this activity.

> than using weak security arguments when pushing for the
> standardization of a scheme whose security is not in doubt.

Hmmm. I'm having trouble reconciling this with "I know I'm drawing a
quite bad picture here".

---D. J. Bernstein