Re: Kyber security level?
D. J. Bernstein
> 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
John Mattsson
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231004001232.1377274.qmail%40cr.yp.to.
D. J. Bernstein
> The important thing is that ML-KEM-512 is approximately as hard to
> break as AES-128 in practice.
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
Mike Ounsworth
+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
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB96786B8CB2D5A115109FB64789CDA%40GVXPR07MB9678.eurprd07.prod.outlook.com.
Blumenthal, Uri - 0553 - MITLL
On Oct 10, 2023, at 16:34, 'Mike Ounsworth' via pqc-forum <pqc-...@list.nist.gov> wrote:
This Message Is From an External SenderThis message came from outside the Laboratory.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB57390CFFDFDAFF612C50965A9FCDA%40CH0PR11MB5739.namprd11.prod.outlook.com.
D. J. Bernstein
> – “ML-KEM-512 is useful” is more important than “we can’t quite agree
> on how to count its bits of security”.
model" is a calculation error on a much larger scale than readers would
expect from the word "quite".
---D. J. Bernstein
Daniel Apon
-----
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231010221741.1888791.qmail%40cr.yp.to.
Loganaden Velvindron
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB96786B8CB2D5A115109FB64789CDA%40GVXPR07MB9678.eurprd07.prod.outlook.com.
Moody, Dustin (Fed)
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
John Mattsson
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
> 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."
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
Perlner, Ray A. (Fed)
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.
D. J. Bernstein
Within the posting that I've challenged as a major error in evaluating
the Kyber-512 security level, NIST wrote "approximately 40 bits of
Where does NIST claim the NTRU Prime submission says what this text
attributes to the submission? Full quote, please.
---D. J. Bernstein
John Mattsson
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.
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
> 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."
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
John Mattsson
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231013104157.2073315.qmail%40cr.yp.to.
Christopher J Peikert
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
Perlner, Ray A. (Fed)
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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CACOo0Qg1DvqZJOp8wf8NRt-ChPkNRxVLdjaaAEDG0QDt09xu4Q%40mail.gmail.com.
Brent Kimberley
What’s the current definition of massive? 1KG of DNA?
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB48556B24CDC340A80CACB9B19CD2A%40DM6PR09MB4855.namprd09.prod.outlook.com.
John Mattsson
Hi,
I saw that the New Scientist article about this thread also managed to include conspiracy theories about mobile networks and GEA1.
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>
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB48556B24CDC340A80CACB9B19CD2A%40DM6PR09MB4855.namprd09.prod.outlook.com.
D. J. Bernstein
'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
submission? Full quote, please."
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.
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
Christopher J Peikert
- You say "Presumably NIST obtained 40 in the following easy way: ... subtract the 129 from the 169."
- In your caricature of "agency desperation, revisited", step 4 has the implicit assumption that NIST simply said "Add '40 bits of additional security'..."
--
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/20231014190154.88197.qmail%40cr.yp.to.
John Mattsson
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 miscalculation” are 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?
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CACOo0QjaSkWoBEU4tQ-hScatLYZqYs0R3%3D4zQR2Y3to%2B-RkYoQ%40mail.gmail.com.
Daniel Apon
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
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
Christopher J Peikert
- 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 miscalculation” are unfounded.
mtthe...@gmail.com
Daniel Apon
Well done, Matt.
Watson Ladd
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 miscalculation” are 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.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB9678A95F4F666E2555CD973489D0A%40GVXPR07MB9678.eurprd07.prod.outlook.com.