Subject: [pqc-forum] ROUND 3 OFFICIAL COMMENT: Classic McEliece From: "D. J. Bernstein" Date: Mon, 6 Jun 2022 18:20:44 +0200 To: pqc-comments@nist.gov Cc: pqc-forum@list.nist.gov Message-ID: <20220606162044.1876334.qmail@cr.yp.to> This is an official comment from the Classic McEliece team regarding a recent talk at Eurocrypt on https://eprint.iacr.org/2021/1634, a paper reporting implementations of the MMT/BJMM algorithms using about 2^60.7 cycles in total on 256 AMD EPYC 7742 CPU cores to break miniature versions of McEliece with length 1284. For comparison, when the 2021 Bellini--Esser estimator https://github.com/Crypto-TII/syndrome_decoding_estimator.git is told to ignore the cost of memory access ("memory_access=0"), it says 2^66.3 bit operations for 1989 Stern, followed by minor improvements from newer memory-intensive algorithms, such as 2^65.8 bit operations for BJMM and 2^64.6 bit operations for May--Ozerov. These numbers are larger than 2^60.7, but the units are also different: bit operations rather than CPU cycles. These algorithms were already accounted for in the Classic McEliece submission in 2017, which, regarding the recommended 6960119 parameter set, wrote "ISD variants have reduced the number of bit operations considerably below 2^256". The submission also pointed out that this ignores the cost of memory access, and stated an expectation 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." This expectation was then confirmed by subsequent analysis. For example, the Bellini--Esser estimator with "memory_access=2" reports cost 2^279.2, as noted in the Classic McEliece team email to pqc-forum in November 2021. Anyone who wants such a high security level _without_ relying on the cost of memory access can instead use the 8192128 parameter set, where the Bellini--Esser estimator with "memory_access=0" says 2^275.6 bit operations for May--Ozerov, assigning zero cost to 2^194.4 memory. The exponent here is about 10% better than attacks from the 1980s (e.g., the estimator says 2^307.4 bit operations for Dumer), but the changes in costs are much smaller if one accounts for the real cost of memory. The new paper and talk claim that some of the Classic McEliece parameter sets "fail to reach their security level by roughly 20 and 10 bit", that "McEliece Slightly Overestimates Security", etc., giving the impression of challenging the Classic McEliece security analysis and parameter selection. However, these claims are based on three serious errors. The first error is comparing the cost of a memory-intensive attack to the cost of an AES attack "on our hardware," while ignoring the fact that the machine puts a large volume of hardware into optimizing memory access and only a tiny fraction of the hardware into AES circuits. It is easy to make an AES attack sound much more expensive than it actually is if one uses a highly suboptimal AES attack machine. The second error is modeling random access to an array of size 2^80 as being as cheap as 80 bit operations. The way the paper arrives at this physically implausible model is by arguing that logarithmic cost "most accurately models our experimental data". The data points were selected from a limited range for which memory access has essentially constant cost on that machine; this is selection bias, not a valid basis for extrapolation. The third error is jumping from a comparison in this cheap-RAM model to a claim of a Classic McEliece "overestimate". The submission has always said that the number of bit operations is "considerably below 2^256"; obviously this does not reach 2^272 if one assigns merely logarithmic cost to RAM (changing the exponent by at most 8 bits). What the paper says here is matching what the submission says, not disputing it. The Classic McEliece assignment of category 5 to the 6960119 parameter set has always been explicitly based on the real cost of memory access.