ROUND 3 OFFICIAL COMMENT: Classic McEliece
325 views
Skip to first unread message
Edoardo Persichetti
Nov 19, 2021, 9:24:39 AM11/19/21
to pqc-co...@nist.gov, pqc-forum
Dear all
NIST has sent email to the Classic McEliece team requesting information
about "the concrete security of Classic McEliece's parameter sets." This
is a reply from the Classic McEliece team.
An optimized version of the latest BJMM/MMT variants in 2021 by Esser,
May, and Zweydinger, running on real hardware, is barely faster than a
2008 Stern-type attack. See the round-3 Classic McEliece talk:
https://www.nist.gov/video/third-pqc-standardization-conference-session-vii-performance-and-candidate-updates
https://csrc.nist.gov/CSRC/media/Presentations/classic-mceliece-round-3-presentation/images-media/session-7-classic-mceliece-lange.pdf
As for cryptographic sizes, the state-of-the-art cost analyses are from
a 2021 script
https://github.com/Crypto-TII/syndrome_decoding_estimator.git
by Bellini and Esser. See also https://eprint.iacr.org/2021/1243, the
accompanying paper by Esser and Bellini. Running
import sys
from sd_estimator.estimator import sd_estimate_display
for n,w in (1024,50),(3488,64),(4608,96),(6688,128),(6960,119),(8192,128):
m = 10
while 2**m < n: m += 1
k = n-w*m
sd_estimate_display(n=n,k=k,w=w,memory_access=2)
sys.stdout.flush()
outputs the tables shown below. The tables again show how small the
improvements have been after Stern's 1989 attack. The smallest costs in
the tables (not counting quantum attacks) are
2^158.6 for mceliece348864,
2^201.0 for mceliece460896,
2^278.2 for mceliece6688128,
2^279.2 for mceliece6960119, and
2^315.6 for mceliece8192128,
and footnote 11 of the paper indicates that the actual cost is higher.
Changing "memory_access" to "0" gives bit-operation counts that much
more obviously underestimate actual costs, such as 2^65.1 bit operations
for a Stern attack (using cost-0 access to megabytes of RAM) against
McEliece's original parameters, 2^141 bit operations (using cost-0
access to >2^80 RAM) for mceliece348864, and 2^246 bit operations for
mceliece6960119. (See Table 2 of https://eprint.iacr.org/2021/1243 for
more of these bit-operation counts.) This matches what Section 8.2 of
the Classic McEliece submission has always said regarding the originally
proposed mceliece6960119 size:
Subsequent ISD variants have reduced the number of bit operations
considerably below 2^256. ... 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.
This 2021 script supersedes a 2019 paper by Baldi et al. The numbers in
the 2019 paper for MMT in particular were much better than for BJMM (and
Stern)---which is impossible since BJMM structurally includes MMT, so it
was always clear that the MMT numbers had to be disregarded. NIST stated
that BJMM "is widely considered to be an improvement over MMT" and asked
"Is this analysis correct? If so, it seems like this could threaten not
just some of the McEliece parameters, but also some of the parameters of
the other code-based schemes." Kirshanova explained in
https://crypto.stackexchange.com/questions/92074/number-of-bit-operations-required-for-information-set-decoding-attacks-on-code-b
the "conclusion that BJMM algorithm is worse than MMT is incorrect
because MMT is a special case of BJMM." An MMT/BJMM calculation error in
the 2019 paper is pinpointed in https://eprint.iacr.org/2021/1243,
Appendix A. The error would also have been caught by simple consistency
checks against experiments.
The tables output by the script appear below.
==========================================================================
Complexity estimation to solve the (1024,524,50) syndrome decoding problem
==========================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+---------------+---------+
| | estimate | quantum |
+----------------+------+--------+---------+
| algorithm | time | memory | time |
+----------------+------+--------+---------+
| Prange | 84.8 | 19.3 | 49.2 |
| Stern | 73.2 | 26.1 | -- |
| Dumer | 74.1 | 26.2 | -- |
| Ball Collision | 74.2 | 26.1 | -- |
| BJMM (MMT) | 73.1 | 24.2 | -- |
| BJMM-pdw | 71.8 | 21.1 | -- |
| May-Ozerov | 70.6 | 21.1 | -- |
| Both-May | 71.5 | 21.2 | -- |
+----------------+------+--------+---------+
===========================================================================
Complexity estimation to solve the (3488,2720,64) syndrome decoding problem
===========================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 178.3 | 21.6 | 95.4 |
| Stern | 162.8 | 32.6 | -- |
| Dumer | 163.2 | 32.6 | -- |
| Ball Collision | 163.2 | 32.6 | -- |
| BJMM (MMT) | 162.2 | 30.6 | -- |
| BJMM-pdw | 160.3 | 26.8 | -- |
| May-Ozerov | 158.6 | 24.6 | -- |
| Both-May | 159.8 | 24.9 | -- |
+----------------+-------+--------+---------+
===========================================================================
Complexity estimation to solve the (4608,3360,96) syndrome decoding problem
===========================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 222.1 | 22.7 | 140.3 |
| Stern | 205.3 | 33.6 | -- |
| Dumer | 205.8 | 33.6 | -- |
| Ball Collision | 205.8 | 33.6 | -- |
| BJMM (MMT) | 204.8 | 31.6 | -- |
| BJMM-pdw | 203.4 | 28.7 | -- |
| May-Ozerov | 201.0 | 25.5 | -- |
| Both-May | 202.2 | 26.5 | -- |
+----------------+-------+--------+---------+
============================================================================
Complexity estimation to solve the (6688,5024,128) syndrome decoding problem
============================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 301.2 | 23.6 | 219.9 |
| Stern | 283.0 | 35.3 | -- |
| Dumer | 283.3 | 35.3 | -- |
| Ball Collision | 283.3 | 35.3 | -- |
| BJMM (MMT) | 282.3 | 33.3 | -- |
| BJMM-pdw | 280.4 | 29.4 | -- |
| May-Ozerov | 278.2 | 26.4 | -- |
| Both-May | 279.4 | 26.8 | -- |
+----------------+-------+--------+---------+
============================================================================
Complexity estimation to solve the (6960,5413,119) syndrome decoding problem
============================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 302.2 | 23.6 | 220.4 |
| Stern | 283.9 | 35.6 | -- |
| Dumer | 284.3 | 35.6 | -- |
| Ball Collision | 284.3 | 35.6 | -- |
| BJMM (MMT) | 283.3 | 33.6 | -- |
| BJMM-pdw | 281.4 | 29.7 | -- |
| May-Ozerov | 279.2 | 26.6 | -- |
| Both-May | 280.3 | 27.0 | -- |
+----------------+-------+--------+---------+
============================================================================
Complexity estimation to solve the (8192,6528,128) syndrome decoding problem
============================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 339.5 | 23.9 | 257.6 |
| Stern | 320.7 | 36.3 | -- |
| Dumer | 321.0 | 36.4 | -- |
| Ball Collision | 321.0 | 36.3 | -- |
| BJMM (MMT) | 320.0 | 34.4 | -- |
| BJMM-pdw | 318.6 | 31.4 | -- |
| May-Ozerov | 315.6 | 27.2 | -- |
| Both-May | 317.0 | 27.6 | -- |
+----------------+-------+--------+---------+
Best,
about "the concrete security of Classic McEliece's parameter sets." This
is a reply from the Classic McEliece team.
An optimized version of the latest BJMM/MMT variants in 2021 by Esser,
May, and Zweydinger, running on real hardware, is barely faster than a
2008 Stern-type attack. See the round-3 Classic McEliece talk:
https://www.nist.gov/video/third-pqc-standardization-conference-session-vii-performance-and-candidate-updates
https://csrc.nist.gov/CSRC/media/Presentations/classic-mceliece-round-3-presentation/images-media/session-7-classic-mceliece-lange.pdf
As for cryptographic sizes, the state-of-the-art cost analyses are from
a 2021 script
https://github.com/Crypto-TII/syndrome_decoding_estimator.git
by Bellini and Esser. See also https://eprint.iacr.org/2021/1243, the
accompanying paper by Esser and Bellini. Running
import sys
from sd_estimator.estimator import sd_estimate_display
for n,w in (1024,50),(3488,64),(4608,96),(6688,128),(6960,119),(8192,128):
m = 10
while 2**m < n: m += 1
k = n-w*m
sd_estimate_display(n=n,k=k,w=w,memory_access=2)
sys.stdout.flush()
outputs the tables shown below. The tables again show how small the
improvements have been after Stern's 1989 attack. The smallest costs in
the tables (not counting quantum attacks) are
2^158.6 for mceliece348864,
2^201.0 for mceliece460896,
2^278.2 for mceliece6688128,
2^279.2 for mceliece6960119, and
2^315.6 for mceliece8192128,
and footnote 11 of the paper indicates that the actual cost is higher.
Changing "memory_access" to "0" gives bit-operation counts that much
more obviously underestimate actual costs, such as 2^65.1 bit operations
for a Stern attack (using cost-0 access to megabytes of RAM) against
McEliece's original parameters, 2^141 bit operations (using cost-0
access to >2^80 RAM) for mceliece348864, and 2^246 bit operations for
mceliece6960119. (See Table 2 of https://eprint.iacr.org/2021/1243 for
more of these bit-operation counts.) This matches what Section 8.2 of
the Classic McEliece submission has always said regarding the originally
proposed mceliece6960119 size:
Subsequent ISD variants have reduced the number of bit operations
considerably below 2^256. ... 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.
This 2021 script supersedes a 2019 paper by Baldi et al. The numbers in
the 2019 paper for MMT in particular were much better than for BJMM (and
Stern)---which is impossible since BJMM structurally includes MMT, so it
was always clear that the MMT numbers had to be disregarded. NIST stated
that BJMM "is widely considered to be an improvement over MMT" and asked
"Is this analysis correct? If so, it seems like this could threaten not
just some of the McEliece parameters, but also some of the parameters of
the other code-based schemes." Kirshanova explained in
https://crypto.stackexchange.com/questions/92074/number-of-bit-operations-required-for-information-set-decoding-attacks-on-code-b
the "conclusion that BJMM algorithm is worse than MMT is incorrect
because MMT is a special case of BJMM." An MMT/BJMM calculation error in
the 2019 paper is pinpointed in https://eprint.iacr.org/2021/1243,
Appendix A. The error would also have been caught by simple consistency
checks against experiments.
The tables output by the script appear below.
==========================================================================
Complexity estimation to solve the (1024,524,50) syndrome decoding problem
==========================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+---------------+---------+
| | estimate | quantum |
+----------------+------+--------+---------+
| algorithm | time | memory | time |
+----------------+------+--------+---------+
| Prange | 84.8 | 19.3 | 49.2 |
| Stern | 73.2 | 26.1 | -- |
| Dumer | 74.1 | 26.2 | -- |
| Ball Collision | 74.2 | 26.1 | -- |
| BJMM (MMT) | 73.1 | 24.2 | -- |
| BJMM-pdw | 71.8 | 21.1 | -- |
| May-Ozerov | 70.6 | 21.1 | -- |
| Both-May | 71.5 | 21.2 | -- |
+----------------+------+--------+---------+
===========================================================================
Complexity estimation to solve the (3488,2720,64) syndrome decoding problem
===========================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 178.3 | 21.6 | 95.4 |
| Stern | 162.8 | 32.6 | -- |
| Dumer | 163.2 | 32.6 | -- |
| Ball Collision | 163.2 | 32.6 | -- |
| BJMM (MMT) | 162.2 | 30.6 | -- |
| BJMM-pdw | 160.3 | 26.8 | -- |
| May-Ozerov | 158.6 | 24.6 | -- |
| Both-May | 159.8 | 24.9 | -- |
+----------------+-------+--------+---------+
===========================================================================
Complexity estimation to solve the (4608,3360,96) syndrome decoding problem
===========================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 222.1 | 22.7 | 140.3 |
| Stern | 205.3 | 33.6 | -- |
| Dumer | 205.8 | 33.6 | -- |
| Ball Collision | 205.8 | 33.6 | -- |
| BJMM (MMT) | 204.8 | 31.6 | -- |
| BJMM-pdw | 203.4 | 28.7 | -- |
| May-Ozerov | 201.0 | 25.5 | -- |
| Both-May | 202.2 | 26.5 | -- |
+----------------+-------+--------+---------+
============================================================================
Complexity estimation to solve the (6688,5024,128) syndrome decoding problem
============================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 301.2 | 23.6 | 219.9 |
| Stern | 283.0 | 35.3 | -- |
| Dumer | 283.3 | 35.3 | -- |
| Ball Collision | 283.3 | 35.3 | -- |
| BJMM (MMT) | 282.3 | 33.3 | -- |
| BJMM-pdw | 280.4 | 29.4 | -- |
| May-Ozerov | 278.2 | 26.4 | -- |
| Both-May | 279.4 | 26.8 | -- |
+----------------+-------+--------+---------+
============================================================================
Complexity estimation to solve the (6960,5413,119) syndrome decoding problem
============================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 302.2 | 23.6 | 220.4 |
| Stern | 283.9 | 35.6 | -- |
| Dumer | 284.3 | 35.6 | -- |
| Ball Collision | 284.3 | 35.6 | -- |
| BJMM (MMT) | 283.3 | 33.6 | -- |
| BJMM-pdw | 281.4 | 29.7 | -- |
| May-Ozerov | 279.2 | 26.6 | -- |
| Both-May | 280.3 | 27.0 | -- |
+----------------+-------+--------+---------+
============================================================================
Complexity estimation to solve the (8192,6528,128) syndrome decoding problem
============================================================================
The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm.
The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound).
+----------------+----------------+---------+
| | estimate | quantum |
+----------------+-------+--------+---------+
| algorithm | time | memory | time |
+----------------+-------+--------+---------+
| Prange | 339.5 | 23.9 | 257.6 |
| Stern | 320.7 | 36.3 | -- |
| Dumer | 321.0 | 36.4 | -- |
| Ball Collision | 321.0 | 36.3 | -- |
| BJMM (MMT) | 320.0 | 34.4 | -- |
| BJMM-pdw | 318.6 | 31.4 | -- |
| May-Ozerov | 315.6 | 27.2 | -- |
| Both-May | 317.0 | 27.6 | -- |
+----------------+-------+--------+---------+
Best,
Edoardo
Kirk Fleming
Nov 20, 2021, 10:15:35 PM11/20/21
to pqc-...@list.nist.gov, pqc-co...@nist.gov
Edoardo wrote:
> The smallest costs in the tables (not counting
> quantum attacks) are
>
> 2^158.6 for mceliece348864,
> 2^201.0 for mceliece460896,
> 2^278.2 for mceliece6688128,
> 2^279.2 for mceliece6960119, and
> 2^315.6 for mceliece8192128,
>
> and footnote 11 of the paper indicates that the
> actual cost is higher.
> The smallest costs in the tables (not counting
> quantum attacks) are
>
> 2^158.6 for mceliece348864,
> 2^201.0 for mceliece460896,
> 2^278.2 for mceliece6688128,
> 2^279.2 for mceliece6960119, and
> 2^315.6 for mceliece8192128,
>
> and footnote 11 of the paper indicates that the
> actual cost is higher.
Footnote 11 explains that the memory access cost
uses the number of vectors instead of the number
of bits. The difference between Sqrt(vectors) and
Sqrt(memory)/2^5, the memory access cost used by
the NTRUPrime submission, is at most 1.5 bits for
May-Ozerov with these parameters.
uses the number of vectors instead of the number
of bits. The difference between Sqrt(vectors) and
Sqrt(memory)/2^5, the memory access cost used by
the NTRUPrime submission, is at most 1.5 bits for
May-Ozerov with these parameters.
In fact, the actual costs will be lower than the
figures given. The memory access cost is applied
as a fixed penalty but not all gates need a memory
access and not all memory accesses need the full
amount of memory.
figures given. The memory access cost is applied
as a fixed penalty but not all gates need a memory
access and not all memory accesses need the full
amount of memory.
This shows mceliece-4608-96 is 5 to 12 bits below
Category 3 when attacking a single ciphertext. If
you include the DOOM attack it's even worse.
Category 3 when attacking a single ciphertext. If
you include the DOOM attack it's even worse.
Kirk
Reply all
Reply to author
Forward
0 new messages