Re: Kyber security level?

11,847 views
Skip to first unread message

D. J. Bernstein

unread,
Oct 3, 2023, 8:13:00 PM10/3/23
to pqc-...@list.nist.gov
'Perlner, Ray A. (Fed)' via pqc-forum writes:
> 40 bits of security more than would be suggested by the RAM model
[ ... ]
> approximately 40 bits of additional security quoted as the "real cost
> of memory access" by the NTRUprime submission

This is (1) not plausible and (2) not what the NTRU Prime submission
says. It is, in context, NIST exaggerating the Kyber-512 security level.

For example, if we rewind to the 2020-vintage attacks considered in the
latest Kyber documentation:

* The Kyber documentation reports that "Core-SVP" is 2^118 for
Kyber-512. "Core-SVP" is a simplified estimate of the number of
attack iterations.

* The documentation also reports an estimate of 2^151 for the number
of bit operations in attacks against Kyber-512. This number is what
NIST calls security in "the RAM model".

* NIST's imaginary "40 bits of security more than would be suggested
by the RAM model" then gives an unsupported estimate of 2^191.

For comparison, when attacks are scaled up from Kyber-512 to sntrup653,
the NTRU Prime documentation reports 2^129 for the "Core-SVP" estimate
of the number of attack iterations, and reports an estimate of memory
accesses as having cost equivalent to 2^169 bit operations. Down at the
Kyber-512 level, an analogous estimate is 2^154 bit operations.

Both 151 and 154 leave very little margin for Kyber-512 compared to
NIST's "floor" of 143. These could be underestimates but they could also
be overestimates. The analyses are complicated and inadequately tested.
There have also been attack improvements since 2020.

I am thus deeply skeptical of claims that Kyber-{512,768,1024} are as
hard to break as AES-{128,192,256} by known attacks, never mind the
risks from future attacks. I recommend that NIST withdraw those claims.
Furthermore, given the considerable risk of Kyber-512 being weaker than
AES-128, I recommend terminating standardization of Kyber-512. See
https://blog.cr.yp.to/20231003-countcorrectly.html for further comments.

---D. J. Bernstein
signature.asc

John Mattsson

unread,
Oct 10, 2023, 4:33:24 AM10/10/23
to D. J. Bernstein, pqc-...@list.nist.gov

Hi,

We think it is excellent that NIST has specified ML-KEM-512. If ML-KEM-512 is slightly above or below the security level of AES-128 is practically completely irrelevant. The important thing is that ML-KEM-512 is approximately as hard to break as AES-128 in practice. We believe ML-KEM-512 offer a significant security margin for many applications, especially if used in hybrid mode with Curve25519. The risk that both ML-KEM-512 and Curve25519 would be practically broken in the next decades seems very small.

 

The maximum transmission unit (MTU) is typically just around 1300 bytes. The encapsulation key and ciphertext are 800 and 768 bytes in ML-KEM-512 versus 1184 and 1088 bytes in ML-KEM-768. The size difference means that when using ML-KEM-512, a lot more additional information can be sent in the same packet. This significantly reduces latency, which is very important in many applications. We believe that the availability of ML-KEM-512 will increase the adoption rate of quantum-resistant cryptography. We believe most implementations will support all three security levels (in fact we think NIST should encourage this) so applications should be able to quickly change the security level if needed.

Correct the stated complexity numbers for ML-KEM-512 if needed, adjust the definition of security category 1 if needed, but make sure to standardize ML-KEM-512.

Cheers,
John

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

 

D. J. Bernstein

unread,
Oct 10, 2023, 10:32:33 AM10/10/23
to pqc-...@list.nist.gov
John Mattsson writes:
> The important thing is that ML-KEM-512 is approximately as hard to
> break as AES-128 in practice.

I presume you're relying here on NIST's November 2022 claim that
Kyber-512 is "likely" as hard to break as AES-128 when memory-access
costs are taken into account.

The argument that NIST eventually gave for this doesn't hold up to
scrutiny. See my previous message.

If you're relying on something else, please clarify.

---D. J. Bernstein
signature.asc

Mike Ounsworth

unread,
Oct 10, 2023, 4:33:35 PM10/10/23
to John Mattsson, D. J. Bernstein, pqc-...@list.nist.gov

+1 to John!

 

– “ML-KEM-512 is useful” is more important than “we can’t quite agree on how to count its bits of security”.

 

---

Mike Ounsworth

Any email and files/attachments transmitted with it are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

Blumenthal, Uri - 0553 - MITLL

unread,
Oct 10, 2023, 5:05:30 PM10/10/23
to Mike Ounsworth, pqc-...@list.nist.gov
+1 to John and Mike. 

Regards,
Uri

On Oct 10, 2023, at 16:34, 'Mike Ounsworth' via pqc-forum <pqc-...@list.nist.gov> wrote:


+1 to John! – “ML-KEM-512 is useful” is more important than “we can’t quite agree on how to count its bits of security”. --- Mike Ounsworth From: 'John Mattsson' via pqc-forum <pqc-forum@ list. nist. gov> Sent: Tuesday, October 10, 2023
ZjQcmQRYFpfptBannerStart
This Message Is From an External Sender
This message came from outside the Laboratory.
 
ZjQcmQRYFpfptBannerEnd

D. J. Bernstein

unread,
Oct 10, 2023, 6:19:18 PM10/10/23
to pqc-...@list.nist.gov
'Mike Ounsworth' via pqc-forum writes:
> – “ML-KEM-512 is useful” is more important than “we can’t quite agree
> on how to count its bits of security”.

NIST's "40 bits of security more than would be suggested by the RAM
model" is a calculation error on a much larger scale than readers would
expect from the word "quite".

---D. J. Bernstein
signature.asc

Daniel Apon

unread,
Oct 10, 2023, 8:02:51 PM10/10/23
to pqc-...@list.nist.gov
Did DJB's PQC-Forum posts get so long that they had to be moved into blog format?

-----

I declare a Gish Gallop. Accordingly, I will employ Wikipedia's suggested strategy:

1. Because there are too many falsehoods to address, it is wise to choose one as an example. Choose the weakest, dumbest, most ludicrous argument that your opponent has presented and tear this argument to shreds (also known as the weak point rebuttal).
2. Do not budge from the issue. Don't move on until you have decisively destroyed the nonsense and clearly made your point.
3. Call it out: name the strategy. "This is a strategy called the 'Gish Gallop'. Do not be fooled by the flood of nonsense you have just heard."


In the blog post, the claim is made: "NIST chose to deemphasize the bandwidth graph by using thinner red bars for it."

As a part of my Weak Point Rebuttal, I claim that this is the weakest, dumbest, most ludicrous argument I could find in the blog post (in a 2 minute scan).
I claim it is an obviously stupid point, with no additional support or evidence required, and that the burden is on the creator of the blog post to substantiate the specific "Thinner Red Bars" claim.

Cheers,
--Daniel

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

Loganaden Velvindron

unread,
Oct 10, 2023, 11:35:26 PM10/10/23
to John Mattsson, D. J. Bernstein, pqc-...@list.nist.gov


On Tue, Oct 10, 2023, 12:33 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:

Hi,

We think it is excellent that NIST has specified ML-KEM-512. If ML-KEM-512 is slightly above or below the security level of AES-128 is practically completely irrelevant. The important thing is that ML-KEM-512 is approximately as hard to break as AES-128 in practice. We believe ML-KEM-512 offer a significant security margin for many applications, especially if used in hybrid mode with Curve25519. The risk that both ML-KEM-512 and Curve25519 would be practically broken in the next decades seems very small.

 

The maximum transmission unit (MTU) is typically just around 1300 bytes. The encapsulation key and ciphertext are 800 and 768 bytes in ML-KEM-512 versus 1184 and 1088 bytes in ML-KEM-768. The size difference means that when using ML-KEM-512, a lot more additional information can be sent in the same packet. This significantly reduces latency, which is very important in many applications. We believe that the availability of ML-KEM-512 will increase the adoption rate of quantum-resistant cryptography. We believe most implementations will support all three security levels (in fact we think NIST should encourage this) so applications should be able to quickly change the security level if needed.


Could nist also look into picking up other candidates for key exchange ? Ntruprime is being used by default for openssh ...

Moody, Dustin (Fed)

unread,
Oct 11, 2023, 1:46:17 PM10/11/23
to Loganaden Velvindron, John Mattsson, D. J. Bernstein, pqc-forum
Loganaden,

There are still KEMs being evaluated in the 4th round.  At the conclusion of the 4th round, it is likely we will select 1 or 2 for standardization.  

Dustin

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Loganaden Velvindron <loga...@gmail.com>
Sent: Tuesday, October 10, 2023 11:34 PM
To: John Mattsson <john.m...@ericsson.com>
Cc: D. J. Bernstein <d...@cr.yp.to>; pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Re: Kyber security level?
 

Daniel Apon

unread,
Oct 11, 2023, 4:15:35 PM10/11/23
to pqc-forum, Loganaden Velvindron, D. J. Bernstein, pqc-...@list.nist.gov, John Mattsson
This sounds like a good reason for the community writ-large to re-open discussion at other SDOs like IETF on SSH, rather than leaving it as an orphaned protocol.

John Mattsson

unread,
Oct 12, 2023, 1:15:23 AM10/12/23
to D. J. Bernstein, pqc-...@list.nist.gov

Hi,

 

I have not looked into the lastest discussions between you and Ray but the last statement from the whole team seems to be:

 

"It is clear that in the gate-count metric it is a very close call and that in this metric the pre-quantum security of Kyber-512 may be a few bits below the one of AES-128. However, the best known attacks against Kyber-512 require huge amounts of memory and the real attack cost will need to take the cost of (access to) memory into account."

 

If ML-KEM-512 falls slightly short of AES-128 or not does not seem practically relevent to me as the attacks require unpractical amounts of memory. I assume the attacks discussed here are lattice sieve algorithms like the one by Becker et. al.

 

The statements in FIPS 203 (Draft) that attacks on ML-KEM-512 requires resources comparable to AES-128 seems correct to me. ML-KEM-512 seems practically secure and very useful.

 

Cheers,

John

D. J. Bernstein

unread,
Oct 12, 2023, 2:59:52 AM10/12/23
to pqc-...@list.nist.gov
'John Mattsson' via pqc-forum writes:
> I have not looked into the lastest discussions between you and Ray but
> the last statement from the whole team seems to be:
> "It is clear that in the gate-count metric it is a very close call and
> that in this metric the pre-quantum security of Kyber-512 may be a few
> bits below the one of AES-128. However, the best known attacks against
> Kyber-512 require huge amounts of memory and the real attack cost will
> need to take the cost of (access to) memory into account."

For the first sentence, the underlying numbers (1) leave a _much_ wider
uncertainty range than you'd expect from "close call"; see, e.g., the
latest Kyber documentation---and (2) are obsolete; see, e.g., Appendix D
of https://cat.cr.yp.to/cryptattacktester-20230614.pdf.

Regarding the second sentence, NIST specifically claimed that the NTRU
Prime team estimates that memory access adds "40 bits of security more
than would be suggested by the RAM model", and used this as part of
drawing NIST's conclusion that, despite the uncertainties, Kyber-512 was
not "terribly likely" to fall below the AES-128 security level.

But that claim is a major calculation error by NIST, not something the
NTRU Prime team said. See my first message in this thread. One can view
the error as confusing "Core-SVP" with "the RAM model"; the Kyber
documentation estimates a 33-bit gap between those for Kyber-512, plus
or minus 16 bits in either direction.

---D. J. Bernstein
signature.asc

Perlner, Ray A. (Fed)

unread,
Oct 12, 2023, 4:21:46 PM10/12/23
to D. J. Bernstein, pqc-forum
Dear all,

Dan Bernstein has recently (on the current email thread) accused us of making a basic arithmetic error, in an email we sent to the forum about 10 months ago during a discussion of Kyber512’s security margin (See the relevant thread here https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/-1Ja0ZYyAQAJ). Dan is incorrect on this point, and in any event the supposed error only concerns our interpretation of one of several possible methods we cited from published literature for estimating memory access costs in lattice attacks. We stand by our previous statement that to the best of our knowledge, in realistic models of computation, the cost of breaking Kyber512, Kyber768, and Kyber1024, using known techniques, is higher than the cost of breaking respectively AES128, AES192, and AES256.

The estimation method in question is that of the 3rd round NTRUprime submission to the NIST-PQC standardization process (https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf), of which Dan is a coauthor. In particular, we interpreted NTRUprime’s security analysis to be making assumptions that would imply that Kyber512 has about 40 bits of additional security margin, if memory access costs are taken into account. To support his accusation that this resulted from a basic arithmetic error, he recently quoted two numbers 151 and 154 as estimates of the security of Kyber, respectively excluding and including memory access costs. However, we don’t see these numbers as directly comparable. The 151 is Kyber’s security “beyond-core-SVP” estimate from section 5.2.1 of the Kyber spec https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf . This estimate excludes memory access costs, but it includes sizeable subexponential factors that affect concrete complexity. The 154 number is extrapolated from table 2 in the NTRUprime spec. This estimate includes memory costs, but excludes subexponential factors. The directly comparable number, without either memory costs or subexponential factors would be 118. Note that 154-118=36, which is well within the range of “about 40.”

Perhaps Dan is claiming that the subexponential factors from Kyber’s estimates would affect the number of bit operations, but not memory access costs, but this does not seem plausible to us. A number of the subexponential factors accounted for by Kyber’s estimate obviously and straightforwardly apply multiplicatively to memory access costs in the same way as computational costs (in particular refined block sizes for BKZ, number of SVP oracle calls in BKZ, dimensions for free, progressivity overheads.) Some further subexponential cost factors come from an analysis of the cost of AllPairSearch in https://eprint.iacr.org/2019/1161.pdf . Adapting this analysis to memory access cost is less straightforward, but we don’t expect the subexponential factors that would result to be all that different. The subexponential factors could even turn out to be larger, since in addition to the factors relevant to computational cost, there are significant subexponential factors that should be included in the size of the memory being accessed (e.g. it takes more than 1 bit to store a lattice point during sieving), which in the NTRUprime model would induce an increase in the cost per bit to access memory. While we have not done a full analysis of what would happen to the NTRUprime estimates if these subexponential factors were included, we are quite certain that the resulting estimate would be significantly larger than the 154 number Dan gives.

We emphasize that we are not claiming that 2^191 bit operation equivalents (or any similar number derived from adjusting NTRUprime's analysis to include subexponential factors) is an accurate estimate of the security of Kyber512. As noted earlier in this email, we only quoted NTRUprime’s analysis as one of several imperfect estimates of memory costs for lattice attacks in the literature. We’ve said in the past that NTRUprime’s estimate of the cost per bit to access a memory of a given size in the relevant range is probably a bit of an overestimate. Moreover, the formulae in the NTRUprime spec seem to be modeling a version of lattice attacks optimized to minimize computational cost when memory access is free. It’s likely that there are better tradeoffs available in the real world where memory access is expensive (e.g. using a larger bucket size to make memory access more local, at the cost of needing to do more computation.) Nonetheless, we expect Kyber to still have adequate security margin, even accounting for these considerations. We continue to encourage research refining security estimates for Kyber512 and the other parameter sets and will do our best to respond quickly and appropriately should anything arise from such research that changes our assessment.

Best,
Ray Perlner (NIST PQC)

-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of D. J. Bernstein
Sent: Thursday, October 12, 2023 2:59 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Re: Kyber security level?

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231012065904.1988759.qmail%40cr.yp.to.

D. J. Bernstein

unread,
Oct 12, 2023, 7:35:45 PM10/12/23
to pqc-...@list.nist.gov
Okay, let's try this in even smaller steps.

Within the posting that I've challenged as a major error in evaluating
the Kyber-512 security level, NIST wrote "approximately 40 bits of
additional security quoted as the 'real cost of memory access' by the
NTRUprime submission".

Where does NIST claim the NTRU Prime submission says what this text
attributes to the submission? Full quote, please.

---D. J. Bernstein
signature.asc

John Mattsson

unread,
Oct 13, 2023, 4:50:49 AM10/13/23
to D. J. Bernstein, pqc-...@list.nist.gov

Hi Dan,

 

Trying with a quote from you instead:

 

Dan Bernstein wrote Thursday, June 4, 2020:

"Kyber-512, fall slightly short of their respective claims of NIST security level."

 

I assume you still think that you were correct.

 

That would still be perfectly fine for me. Even if ML-KEM-512 fall short of the theoretical target level in some way, I still very very much want ML-KEM-512. I cannot see that any discussed attacks would be anywhere near realistic. When using crypto over actual real-world networks, the sizes of public keys and ciphertexts are often much more important for latency and energy consumption than CPU cycles.

 

As I wrote in a comment early in the competition:

 

"while standardized algorithms should have a reasonable high security margin to hopefully

withstand also future attacks, there is no point in having absurdly high security margins for memory,

like protecting against attacks requiring planet sized memory units, or circuits with depths requiring

eons of time to calculate."

 

A lot of standards in the past has focused a bit too much on unrealistic attack models equating memory and time, offline and online attacks, width and height of circuits. Nobody is brute forcing P-256 and RSA-2048, instead the attacks that actually happens in practice are implementations not verifying curve points, side-channel attacks, nonce reuse, etc.

 

Cheers,

John

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

D. J. Bernstein

unread,
Oct 13, 2023, 6:43:27 AM10/13/23
to pqc-...@list.nist.gov
'John Mattsson' via pqc-forum writes:
> Trying with a quote from you instead:
> Dan Bernstein wrote Thursday, June 4, 2020:
> "Kyber-512, fall slightly short of their respective claims of NIST security level."

No, I didn't write that, nor does that address the much more recent NIST
calculation error and misattribution that I've challenged in this thread
(NIST writing "40 bits of security more than would be suggested by the
RAM model ... approximately 40 bits of additional security quoted as the
'real cost of memory access' by the NTRUprime submission").

---D. J. Bernstein
signature.asc

John Mattsson

unread,
Oct 13, 2023, 7:05:08 AM10/13/23
to D. J. Bernstein, pqc-...@list.nist.gov

Sorry, my mistake. I see now that the quote was written by the The Kyber team in a mail to you. I got confused by a "D. J. Bernstein" <d...@cr.yp.to> wrote:” at the top of the mail from the Kyber team.

 

Cheers,

John

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

Christopher J Peikert

unread,
Oct 13, 2023, 11:56:47 AM10/13/23
to Perlner, Ray A. (Fed), D. J. Bernstein, pqc-forum
Dear Ray and NIST, thank you for the additional elaboration for how you estimated Kyber512's security level, and for pointing out why the cited 151 and 154 numbers are not comparable.

From this it is clear to me that the central assertion from Dan Bernstein's blog post -- that NIST's calculation "was a severe and indefensible miscalculation" that "boils down to nonsensically multiplying two costs that should have been added" -- is categorically incorrect.

In my understanding, the key point on this matter is this (my emphasis):

On Thu, Oct 12, 2023 at 4:21 PM 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov> wrote:
A number of the subexponential factors accounted for by Kyber’s estimate obviously and straightforwardly apply multiplicatively to memory access costs in the same way as computational costs

In other words, the total memory-access cost grows multiplicatively, not additively, with the relevant memory-bound computations -- and sieving-based attacks are highly memory bound.

As a simple example: if an algorithm does 2^10 bit operations on 2^9 bits, but retrieving those bits from memory costs 2^6 operations per bit, then the memory-access cost is the product 2^9 * 2^6 = 2^15. Moreover, underestimating the number of bit operations -- and hence the number of bits to be retrieved -- as (say) 2^4 yields a multiplicative (not additive) underestimate of 2^4 * 2^6 = 2^10 for the memory-access cost. [Note that we have underestimated by a factor of 2^5, not 2^6, because that's how much the memory access was underestimated, and that's what dominates here.]

The internals of a sieving iteration are vastly more complicated than this example, but large portions of its computations are similarly memory bound. So, as above, multiplying the relevant costs yields a sensible estimate, and severely underestimating the computational cost (e.g., as Core-SVP implicitly does) would result in a multiplicative underestimate of the real cost.

I think one fundamental mistake in the blog post is a false assumption about how NIST estimated the ~20-40 bits of additional security due to memory-access costs: "Presumably NIST obtained 40 in the following easy way: ... subtract the 129 from the 169."

Sincerely yours in cryptography,
Chris

Perlner, Ray A. (Fed)

unread,
Oct 13, 2023, 3:24:12 PM10/13/23
to Christopher J Peikert, D. J. Bernstein, pqc-forum

Hi Dan and Chris,

 

In addition to what Chris said, we would like to add the following quote:

 

"Sieving algorithms in the literature typically use a massive database, size 2^(0.2075...β+o(β)) (and often even larger). This multiplies the real cost of the algorithms by 2^(0.1037...β+o(β)); see Section 6.6." -p65 NTRU Prime spec. https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf

 

This seems like a pretty clear endorsement by the NTRUprime team of the position that a factor, somewhere in the ballpark of 2^40 for Kyber512, should be multiplied, not added.

 

Since no one other than Dan seems to see a significant error in our analysis 10 months ago, and since our current assessment of Kyber512’s security is what really matters, NIST will not engage further in this thread.  The full text of the email from 10 months ago that Dan is drawing quotes from can be found at https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBurXr58Rs/m/xHojUDCaBAAJ , and our current assessment remains that to the best of our knowledge, in realistic models of computation, the cost of breaking Kyber512, Kyber768, and Kyber1024, using known techniques, is higher than the cost of breaking respectively AES128, AES192, and AES256.

 

Best,

Ray  Perlner (NIST PQC)

 

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Christopher J Peikert
Sent: Friday, October 13, 2023 11:57 AM
To: Perlner, Ray A. (Fed) <ray.p...@nist.gov>
Cc: D. J. Bernstein <d...@cr.yp.to>; pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Re: Kyber security level?

 

Dear Ray and NIST, thank you for the additional elaboration for how you estimated Kyber512's security level, and for pointing out why the cited 151 and 154 numbers are not comparable.

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

Brent Kimberley

unread,
Oct 13, 2023, 3:37:46 PM10/13/23
to Perlner, Ray A. (Fed), Christopher J Peikert, D. J. Bernstein, pqc-forum

What’s the current definition of massive?  1KG of DNA?

THIS MESSAGE IS FOR THE USE OF THE INTENDED RECIPIENT(S) ONLY AND MAY CONTAIN INFORMATION THAT IS PRIVILEGED, PROPRIETARY, CONFIDENTIAL, AND/OR EXEMPT FROM DISCLOSURE UNDER ANY RELEVANT PRIVACY LEGISLATION. No rights to any privilege have been waived. If you are not the intended recipient, you are hereby notified that any review, re-transmission, dissemination, distribution, copying, conversion to hard copy, taking of action in reliance on or other use of this communication is strictly prohibited. If you are not the intended recipient and have received this message in error, please notify me by return e-mail and delete or destroy all copies of this message.

John Mattsson

unread,
Oct 14, 2023, 6:50:17 AM10/14/23
to pqc-forum, Matthew Sparkes, ALAN.W...@surrey.ac.uk

Hi,

 

I saw that the New Scientist article about this thread also managed to include conspiracy theories about mobile networks and GEA1.

 

https://www.newscientist.com/article/2396510-mathematician-warns-us-spies-may-be-weakening-next-gen-encryption/

 

Here is what I wrote about that a few years ago:

 

"The second generation (2G or GSM) mobile networks have quite low security by today‘s standards. But GSM was actually the first mass-market communication system to use cryptography, which was both revolutionary and controversial. At the time, export of cryptography was heavily restricted and GSM had to be designed with this in mind. The encryption algorithms A5/1 and A5/2 are LFSR-based stream ciphers supporting 64-bit key length. A5/2 is a so-called export cipher designed to offer only 40-bit security level. Usage of export ciphers providing weak security was common at that time and other standards like TLS also supported export cipher suites.”

 

To further align with export control regulations, the key generation algorithms COMP128-1 and COMP128-2 decreased the effective output key length to 54 bits by setting 10 bits the key to zero. While A5/1 and A5/2 mostly met their design criteria, COMP128-1 was a very weak algorithm and was soon replaced by COMP-128-2 and COMP128-3. When packet-switched data was introduced with GPRS, slightly different algorithms GEA1 and GEA2 were introduced. Similar to A5/1 and A5/2, GEA1 and GEA2 are LFSR-based stream ciphers supporting 64-bit key length, where GEA1 was the export cipher. The export ciphers A5/2 and GEA1 are forbidden to support in phones since many years and COMP128-1 is forbidden to support in both networks and SIM cards. None of the original 2G algorithms were officially published anywhere as they were intended to be kept secret, which was quite common practice at the time. But all were reverse engineered by researchers in academia nearly a decade after their development.

 

https://www.ericsson.com/en/blog/2021/6/evolution-of-cryptographic-algorithms

 

That A5/2 and GEA1 are 40-bit export ciphers have always been well-known to everyone working with crypto in the mobile industry and I don't think that has ever been secret.

 

I think the main problem with GSM is that it is still alive. GSM was designed to have a lifetime of 10 years. In a historic perspective you could write a lot of positive things about GSM. It was the first mass-market use of encryption and authentication, something we today take for granted. Many security agencies in the 80-ies hated the idea of mass market encryption in GSM and tried to stop it.

 

Cheers,

John Preuß Mattsson

 

From: 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov>


Date: Friday, 13 October 2023 at 21:26
To: Christopher J Peikert <cpei...@alum.mit.edu>

D. J. Bernstein

unread,
Oct 14, 2023, 3:02:20 PM10/14/23
to pqc-...@list.nist.gov
I have two short yes/no clarification questions.

'Perlner, Ray A. (Fed)' via pqc-forum writes:
> "Sieving algorithms in the literature typically use a massive
> database, size 2^(0.2075...β+o(β)) (and often even larger). This
> multiplies the real cost of the algorithms by 2^(0.1037...β+o(β)); see
> Section 6.6." -p65 NTRU Prime spec.
> https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf

In a separate branch of the thread, I quoted NIST writing "approximately
40 bits of additional security quoted as the 'real cost of memory
access' by the NTRUprime submission". I then asked "Where does NIST
claim the NTRU Prime submission says what this text attributes to the
submission? Full quote, please."

Yes or no: Is NIST giving the above o(β) quote as an answer to that
question, i.e., claiming that the above o(β) quote says what the above
40-bits quote attributes to the NTRU Prime submission?

> This seems like a pretty clear endorsement by the NTRUprime team of
> the position that a factor, somewhere in the ballpark of 2^40 for
> Kyber512, should be multiplied, not added.

Yes or no: When NIST writes "multiplied" here, does it mean multiplying
by the security level in "the RAM model", as in another NIST quote "40
bits of security more than would be suggested by the RAM model"?

---D. J. Bernstein
signature.asc

Christopher J Peikert

unread,
Oct 15, 2023, 12:02:35 PM10/15/23
to pqc-...@list.nist.gov
Dan, you initiated this thread with a link to your blog post in which you made a very serious accusation: that NIST made "a severe and indefensible miscalculation" that "boils down to nonsensically multiplying two costs that should have been added" (your emphasis).

The responsible thing would be to have the facts right, and not rely on unsupported and incorrect assumptions (see below), before making such a major accusation.

While that ship has sailed, the second-most responsible thing would be to withdraw the accusation, now that you know your assumptions and caricature are incorrect. Will you do so?

(This matters because the accusations have traction: e.g., the lede of this article repeats the allegation that "NIST has made errors – either accidental or deliberate – in calculations describing the security of the new standards." And several of the comments here simply take for granted that NIST made the alleged "nonsensical" calculation error.)

Details: your argument in support of the accusation rests on at least two key assumptions:
  1. You say "Presumably NIST obtained 40 in the following easy way: ... subtract the 129 from the 169."
  2. In your caricature of "agency desperation, revisited", step 4 has the implicit assumption that NIST simply said "Add '40 bits of additional security'..."
The post doesn't give any evidence to support either assumption. And as we have seen, neither one holds up.

Moreover, we have also seen that there is a perfectly sensible reason to multiply much of the lower-order cost of sieving iterations with the cost of memory access per iteration.

So, neither the "severe and indefensible miscalculation" nor "nonsensically multiplying" charges hold water.

Sincerely yours in cryptography,
Chris
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

John Mattsson

unread,
Oct 15, 2023, 6:07:40 PM10/15/23
to pqc-...@list.nist.gov

I have now read the whole of Dan’s extensive blog post. Some reflections:

 

- The blog would have benefited from an upfront disclosure that the author is an author of  multiple competing algorithms in the NIST competition.

 

- Professor Peikert's strong endorsement of NIST's calculations makes it quite apparent that the accusations characterizing this as a "fiasco", “stupid”, “obvious”, “immediately be caught”, “indefensible miscalculationare unfounded.

 

- The blog overlooks the crucial aspect that the discussed attacks necessitate impractical amounts of memory. ML-KEM-512 seems to offer substantial practical security. The theoretical discussion about memory complexity does not seem practically important to me.

 

- There seems to be nothing substantiating the claim that the NSA is actively undermining the security of ML-KEM. ML-KEM was designed by the Kyber Team, ML-KEM-512 seems to offer substantial practical security, and I struggle to comprehend why NSA would put U.S. corporations and government bodies at risk from foreign entities.

 

- It strikes me as rather strange to accuse NIST of lacking openness and transparency while simultaneously engaging in standardization in ISO, where even the final standards aren't made publicly available. My view is that cryptographic algorithm standards hidden behind paywalls, such as ISO, present significant security risks and should be avoided.

 

- The statement, "In the call for submissions, it was crystal clear that cryptosystems had to be at least as hard to break as AES-128," doesn't appear accurate. The call for proposals states "comparable to rather than insisting on a strict equivalence to AES-128.

 

- While opinions may differ, I have actively advocated for NIST to allow updates to algorithms and revise requirements when deemed necessary throughout the course of the standardization project.

 

- A concise scientifically written paper submitted to IACR eprint would have been sooooo much better.

 

In my view, the NIST PQC project has been very positive overall. Standardizing ML-KEM-512, ML-KEM-768, and ML-KEM-1024 is a good choice, but I would also been happy with Saber, NTRU, NTRU Prime, or NewHope. I have the impression that NIST listens to received comments. I strongly think NIST should standardize ML-KEM-512. I think standardizing exactly one structured lattice KEM with 3 security levels is perfect. Several standardized structure lattice KEMs is bad for everybody. NIST’s plan to standardize 1-2 code-based KEMs make sense to me. I hope that we in the future will also see a full Diffie-Hellman replacement with very small messages such as CSIDH standardized.

 

Cheers,

John Preuß Mattsson

Expert Cryptographic Algorithms and Security Protocols, Ericsson

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Christopher J Peikert <cpei...@alum.mit.edu>
Date: Sunday, 15 October 2023 at 18:08
To: pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Re: Kyber security level?

Daniel Apon

unread,
Oct 16, 2023, 2:23:19 AM10/16/23
to pqc-forum, John Mattsson, Matthew Sparkes, ALAN.W...@surrey.ac.uk
In view of https://www.newscientist.com/article/2396510-mathematician-warns-us-spies-may-be-weakening-next-gen-encryption/ ....

Has anyone here considered the possibility (just my idle speculation crawling out) that in his role as a public figure, Daniel J. Bernstein is a multi-decade shill for the NSA?

(Yes, yes. Bear with me.)

It's a well known fact that Dan Bernstein and Art Driscol (a senior cryptographer at the NSA) were roommates while in grad school at the University of California, Berkeley. (This, of course, precedes the events related to the major U.S.-national / Supreme Court cases where DJB first made his name - arguing for a free speech relaxation of export control of cryptography.) Does this provide DJB the opportunity and - especially - the motive? Has anyone taken the time to question the authenticity of this narrative?

For all of the "apparent" mathematical subtleties around "adding or multiplying" various numbers in an incredibly complicated analysis of lattice reduction attacks (which this email thread has now clearly shown to be FALSE - via PUBLIC and "academic" analyses), how much easier would it be to instead influence public cryptography standards by using a long-running false flag operation?

I've heard it claimed many times that the NSA generates FUD in many communication channels to thwart the progress of academic cryptographers. And I've seen public commentary on the newscientist article, like: https://science.slashdot.org/story/23/10/13/2233207/mathematician-warns-us-spies-may-be-weakening-next-gen-encryption
[Dear lawyers that DJB might hire to attack me, I hereby publicly claim Dan's contribution to public news articles, minimally, make him a "public figure" with respect to Libel Law within the United States of America.]

A casual glance by any serious cryptographer should immediately leave you with the impression that the vast majority of people in such social media discussions aren't conversational in the details of PQC standards or lattice-based cryptography technical matter. However, they'll readily gobble up the hyped commentary.

And -- Of course they will. Every time I take a flight on an airplane, I rely on the judgements of an entire, diverse community of technical experts. I'm being shot up to 30,000 feet in a metal tube by an infernal combustion process. In modern society, everyone relies - incredibly frequently - on the voices of others (the experts) to explain things that they can't specialize in.

But in the case of lattice cryptography (and on the subject of NTRU Prime), hasn't DJB's entire role for the past ~7 years to be a "spoiler" -- attacking academically- and publicly-developed lattice-based cryptography? He hasn't essentially published in the field through peer-review for years, until he brought his scheme to the NIST competition. (Sure - he posted on many Google Groups forums saying whatever he says.)

In the first round of the NIST PQC competition, DJB's original NTRU Prime submission *woefully* over-estimated the security of lattice-based cryptography by *significantly over-estimating* the cost of memory in lattice reduction attacks.

Specifically, the original "claimed Category 5 parameters" (256-bit secure) actually worked out to be closer to Category 1 strength (128-bit secure). MANY candidates have been removed from the NIST PQC standardization process for losing half of their bits of security; but NTRU Prime was given HUGE leeway to re-adjust their lattice-parameter selection much higher.

Some many years later, now Dan has claimed that memory-access costs of lattice reduction essentially costs NOTHING (and been shown wrong).

It seems like Dan changes his point of view -- inconsistently with himself -- and never "retracts" misinformation that he has published.

What could be the reason for this? I've come up with three thoughts:

1) Daniel J. Bernstein is so incredibly egotistic, that scientific truth doesn't matter to him.
2) Daniel J. Bernstein is acting on behalf of a foreign (to the U.S.) intelligence agency, with the aim to undermine the work of NIST in the long run.
3) Daniel J. Bernstein is a shill for the NSA

Well -- to me -- (2) seems not so likely. In such a scenario, surely the NSA would throw its weight around to stave off such a threat.

So, it seems to me, there are two likely cases:
Either DJB is an independent actor with no regard for the truth (only to satisfy his own ego), or DJB is acting on behalf of the NSA to subvert public cryptographic standards.

Just some thoughts / my two cents,
--Daniel



P.S. Note that actively and intentionally promoting / instigating toxicity on the PQC Forum -- with the goal of undermining the integrity of a scientific community -- is a natural outcome of either (1) or (3). The more that a public forum based on science is undermined, the better either objective would be served.

P.P.S. Are the above arguments easily destroyed or blatantly unbelievable? Wow - amazing! Welcome to performance art. Maybe some pop-sci journalist will write an article about this post.

Oscar Smith

unread,
Oct 16, 2023, 10:29:25 AM10/16/23
to pqc-forum, Christopher J Peikert
The key point is that the multiplication should be between sieving iterations and cost of memory access per iteration, not between gate complexity and  the cost of memory per iteration. As I understand it, the claimed iteration count of Kyber is 2^118 with a claimed 2^25 gates per iteration. As such, a memory cost of 2^30 per iteration would yield a total cost of 2^118*(2^25+2^30) which means that the memory, while being a bottleneck, only adds 5 bits of security.

If these numbers are wrong, I would appreciate a clarification from either DJB or NIST as to what the actual iteration count, cpu gates per iteration, and memory access cost per iteration is.

Bobby McGee

unread,
Oct 16, 2023, 11:18:11 AM10/16/23
to pqc-forum
I look forward to reading "A comparison of complexity models for lattice algorithms with applications to concrete security estimates for lattice-based post-quantum cryptography."  Is it so difficult to produce a list of the form "solving Problem X with Algorithm Y under model Z requires resources W?"  Maybe hundreds of these papers exist and everyone is satisfied by the results, but to a non-expert, this discussion gives the appearance that no such consensus exists.

Generally speaking, I appreciate Prof. Bernstein's efforts towards honesty, transparency, and rigor, although his methods may occasionally be counterproductive.

Christopher J Peikert

unread,
Oct 16, 2023, 11:42:31 AM10/16/23
to John Mattsson, pqc-...@list.nist.gov
On Sun, Oct 15, 2023 at 6:07 PM 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:

- Professor Peikert's strong endorsement of NIST's calculations makes it quite apparent that the accusations characterizing this as a "fiasco", “stupid”, “obvious”, “immediately be caught”, “indefensible miscalculationare unfounded.


To be clear, I fully endorse NIST's key point that "A number of the subexponential factors accounted for by Kyber’s estimate obviously and straightforwardly apply multiplicatively to memory access costs in the same way as computational costs," and that this has a significant effect on the real security margin. I'm not aware of any knowledgeable controversy on this point.

And yes, from this it follows that those accusations, along with the NIST-multiplied-when-it-should-have-added one, are unfounded and should be withdrawn.

I haven't seen detailed calculations that precisely quantify the effect (it would be good if these were released to the community). But the announced conclusions about Kyber512's security margin against known attacks look plausible to me.

mtthe...@gmail.com

unread,
Oct 19, 2023, 7:49:23 PM10/19/23
to pqc-forum, Daniel Apon, John Mattsson, Matthew Sparkes, ALAN.W...@surrey.ac.uk

Well, if we want to entertain those thoughts we should also consider the following.

Dan Bernstein is currently trying to block the standardization of ML-KEM/Kyber in an upcoming amendment to ISO/IEC 18033-2  using questionable tactics.

This is a remarkable development that shouldn't go unnoticed.

Sincerely,
Matt

Daniel Apon

unread,
Oct 19, 2023, 8:15:53 PM10/19/23
to mtthe...@gmail.com, pqc-forum, John Mattsson, Matthew Sparkes, ALAN.W...@surrey.ac.uk
How incredibly timely.

Well done, Matt.

Watson Ladd

unread,
Oct 19, 2023, 8:22:18 PM10/19/23
to John Mattsson, pqc-...@list.nist.gov


On Sun, Oct 15, 2023, 3:07 PM 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:

I have now read the whole of Dan’s extensive blog post. Some reflections:

 

- The blog would have benefited from an upfront disclosure that the author is an author of  multiple competing algorithms in the NIST competition.

 

- Professor Peikert's strong endorsement of NIST's calculations makes it quite apparent that the accusations characterizing this as a "fiasco", “stupid”, “obvious”, “immediately be caught”, “indefensible miscalculationare unfounded.

 

- The blog overlooks the crucial aspect that the discussed attacks necessitate impractical amounts of memory. ML-KEM-512 seems to offer substantial practical security. The theoretical discussion about memory complexity does not seem practically important to me.

 

- There seems to be nothing substantiating the claim that the NSA is actively undermining the security of ML-KEM. ML-KEM was designed by the Kyber Team, ML-KEM-512 seems to offer substantial practical security, and I struggle to comprehend why NSA would put U.S. corporations and government bodies at risk from foreign entities.


How did that logic work out for Juniper and OPM?
To view this discussion on the web visit