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.
Daniel Apon
I hereby call for the public cryptographic reseaerch community (acting through NIST) to formally ban Daniel J. Bernstein from the PQC Forum for life, as well as enforce a lifetime ban on him from all NIST Cryptography standardization processes.
Daniel Apon
Paul Hoffman
--Paul Hoffman
Wrenna Robson
More technical content and less posturing, please. (Bonus points for technical content that the below-average half of us on the list can at least partially understand.)
--Paul Hoffman
--
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/2DF63E87-19C3-489F-8A97-9C59BBAB748C%40icann.org.
Steven Jambert
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANuKc3h7kB0y%3DRzRNw9ZoNCtFh-gzzph7Sjix16TUD06HkugkA%40mail.gmail.com.
John Mattsson
Hi Steven,
There are numerous significant problems with paywalled security standards and the SDOs that produce them:
- Non-public standards have a much higher risk of both intentional and non-intentional security vulnerabilities. It is well-known that security agencies from different countries participate in standardization and development of security products with the explicit goal of sabotaging security to enhance their surveillance capabilities. This is much easier in closed SDOs. The "public" review is not very public. There are many security agencies globally and they often hide their identity [1].
- Security vulnerabilities in paywalled standards are much less likely to be found. Paywalls strongly discourages security researchers from examining and reasoning about standards and interactions between standards. Open access is very important for security specifications as history has showed over and over again that lack of analysis often lead to significant weaknesses. People has argued that paywalls were a major reason why the serious Wi-Fi “KRACK” vulnerability [2], which allowed anyone to get onto a secure network, was undiscovered for so long. People have even been arguing that “paywalls drive mass surveillance.” [3].
- Paywalled standards lead to significantly more implementation vulnerabilities. Just as paywalled standards strongly discourages security researchers from evaluating the standards, it also strongly discourages developers to actually read the standards. There are many examples where developers implemented from freely available sources such as Wikipedia and academic articles instead of the paywalled standard. In the best case this just leads to interoperability problems, but often it also leads to security vulnerabilities. One example is XTS which if implemented from publicly available sources easily do completely unsecure things like reusing the same tweak [4]. This also illustrated the point why negative test vectors are equally important as positive test vectors.
- In 2023 there have been several court verdicts in the EU and US [5][6] stating that all technical standards referenced by laws must be freely available. I think that should be even broader. I think it is a democratic right to know the details of all security specifications that governments recommend even if not referenced by law.
- In two excellent articles [7][8], Anthony Rutkowski analyses the practice of paywall standards and how it creates security vulnerabilities incompatible with the cybersecurity objective:
”Referencing a paywall standard by a standards body or government agency effectively makes them a sales promotion agent.”
“The continued use of ICT standards hidden behind sales point paywalls using glacial development processes is a cyber security vulnerability.”
“It is long past due for the practice to stop and stop enabling it as “a business model”—that is so obviously antithetical to the cybersecurity objective.”
- As discussed in a recent CFRG thread [9], ISO is also questionable for other reasons. ISO policy prohibits public speculation and ISO is systematically commit copyfraud. Copyfraud is a huge problem. Unfortunately, authorities mostly ignore this crime.
Cheers,
John
[1] Wikipedia, “Security agency”
https://en.wikipedia.org/wiki/Security_agency
[2] Matthew Green, “Falling through the KRACKs”
https://blog.cryptographyengineering.com/2017/10/16/falling-through-the-kracks/
[3] Rick Falkvinge, “The recent catastrophic Wi-Fi vulnerability was in plain sight for 13 years behind a corporate paywall”
[4] StackExchange, “An XTS penguin
https://crypto.stackexchange.com/questions/58871/an-xts-penguin
[5] Anthony Rutkowski, “EU Standards Must Be Freely Available”
https://circleid.com/posts/20230623-eu-standards-must-be-freely-available
[6] Anthony Rutkowski, “The Standards Paywalls Fall: Everyone Benefits”
https://circleid.com/posts/20230913-the-standards-paywalls-fall-everyone-benefits
[7] Anthony Rutkowski, “Monumental Cybersecurity Blunders”
https://circleid.com/posts/20220513-monumental-cybersecurity-blunders
[8] Anthony Rutkowski, “Global Standards Collaboration: Is It Possible?”
https://circleid.com/posts/20230203-global-standards-collaboration-is-it-possible
[9] CFRG, "Classic McEliece"
https://mailarchive.ietf.org/arch/msg/cfrg/ADMtHuMgG20XTFM989ECtCYB1YQ/
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPpUMuPVT9fdbWbEp4vSjA90CJOiC5dVobTBPi1%2BnfTDxaXSjA%40mail.gmail.com.
Daniel Apon
Thank you for your email! (My position on DJB's accusations has been made well enough clear now. =) I plan to let this round rest..)
That said -- I wholeheartedly support a return to the science!
Speaking of the science, here is my take on what's going on (from a broader level):
1- Across the global population of human beings, the intersection A \cap B \cap C of the three sets..
A := {People Who Fully Understand Lattice Reduction & BKZ In All Its Gory Details} and
B := {People Who Fully Understand High Performance Computing And Its Future Possibilities In All Its Gory Details} and
C := {People Who Publish In The Public Scientific Space}
..is APPROXIMATELY the empty set. (Optimistically, it's not ZERO people, but it appears to me that it's very likely you could count the number of all such humans on your fingers.)
2- During the past 7-8 years (or longer), multiple groups (primarily as authors/co-authors on NIST PQC specification documents in Rounds 1, 2, and 3) have attempted a variety of different "memory-cost modelings" in order to argue about the concrete security of their various proposals.
3- Most of those memory-costing attempts disagree at some layer of abstraction. While there do seem to be some points of agreement, there is (clearly!) not community consensus on the full memory-costing argument from top to bottom -- aside from a general feeling of ennui that this is an incredibly complicated analysis in Measurement Science that certainly has SOME effect, but analytical precision has not yet been achieved nor agreed upon.
4- Most of the discussion thus far has, thus, ruled out hot takes on the topic that seem "very far out" from the most probable ground truth -- but naturally, leaves a lot of uncertainty and wiggle room 'in the middle' where people can truthfully disagree.
5- The topic itself has been emotionally/politically inflamed. This sadly dis-incentivizes public research efforts into the topic -- public research efforts being the most natural remedy to the situation.
6- There is no comprehensive 'starting point' document that even details (survey-style) the various viewpoints conjectured thus far. This ALSO sadly dis-incentivizes public research efforts into the topic -- public research efforts being the most natural remedy to the situation.
7- So, there is a SIGNIFICANT NEED for at least a single, neutral-voice reference point for science to progress in the area. (Without this, researchers would naturally feel hesitant to wade into the topic, for fear of missing an important key concept / reference, and being blasted by one side or the other.)
8- To wit, a fresh research paper on this topic that is (somehow!) i) comprehensive, ii) technically thorough, and iii) convincing to experts in adjacent areas of science (but who don't want to wade into BKZ + HPC issues themselves) should obviously be a very high impact scientific contribution -- likely, in my opinion, meriting a Best Paper award at some IACR conference, were it to rise above the current situation of this claim/counter-claim cycle (a cycle which feels, to me, much like the design/break/patch cycle of historical cryptography as an art rather than modern cryptography as a science).
9- And finally, note that people in the High Performance Computing community are still writing fresh PhD theses about the underlying technical matter intersecting this topic even within the last decade. For example (citing someone entirely unrelated to the cryptographic community as an example): https://dr.lib.iastate.edu/server/api/core/bitstreams/90eb0c04-5c36-40cb-bc34-e3a8b6fb7324/content
---
I will see if it's possible to simply go back and catalogue the various views (or at least, the majority of significant views) on memory-modeling in a future forum post -- my time permitting.
If even doing that seems to necessitate an ePrint paper post (or an "SoK-style" conference submission, etc.), there might be more of a delay. (It's unclear how big the job will end up being until I get started.)
And that said -- I strongly encourage anyone else interested in this issue to consider doing the same cataloguing / information-synthesizing exercise! (Even if I go back and write a survey, it's not obvious that having only one viewpoint on how to arrange the "information thus far" is optimal.)
Best regards,
--Daniel
Daniel Apon
Paul specifically requested " technical content that the below-average half of us on the list can at least partially understand ", and I realize now that my previous post used the phrase "memory-costing" without defining the term, or explaining what's going on here.
I will attempt to remedy that in this email.
Toward that end, in what follows -- I am going to use blue highlighting to denote when I am giving some number as an example to illustrate the basic point without claiming (in view of the technical experts / above-average half of the list) that these numbers are in any manner technically precise or a hard claim that I'm willing to defend. That is, I expect the real numbers are perhaps a little lower or a little higher, but the numbers I give in this email -- like 2^69 (nice.) -- are morally correct in the sense that I use them. It is possible that the numbers highlighted in blue that I give are way off; I hope not.
This is an email for the "below-average half of us on the list" sent with love from me. =)
-----
When the term "memory-costing" is used in these discussions, it's (mostly) being used in the context of the "canonical attack" against lattice-based cryptography: i.e. the BKZ algorithm (the "Block Korkine-Zolotarev" algorithm), specifically using some sieving subroutine, in the format of a Primal attack.
Historically, the BKZ algorithm has also been considered with an alternative subroutine, called "enumeration" (instead of "sieving"). Recently, it's seemed to be the case that BKZ-with-enumeration tends to perform better at very low dimensions (lattices of dimension 60 or below), and BKZ-with-sieving performs better when once hits the "asymptotic regime" of lattices with dimension 60 or above. Note that practical / real-world lattice cryptosystems tend to use dimensions in the range 500 to 2000.
In the past couple of years, a post on this forum by MATZOV (a mathematics group of the Israeli Defense Force) claimed a speed-up for the Dual attack ("Dual" as opposed to "Primal" methodologies), which surpassed the speed of the best Primal attacks. That claim is being debated, and follow-up research is ongoing.
So, for the sake of this email, I'll focus only on the BKZ-with-sieving Primal attack algorithm (with the reader's understanding that issues external to this discussion -- e.g. sieving-vs-enumeration, primal-vs-dual, completely new insights, etc. -- could change which specific algorithm is the most important to focus on, and necessitate a complete re-do of any such "memory-costing" analysis).
-----
At a high level, the BKZ algorithm attempts to perform a key-recovery attack against an instance of a lattice cryptosystem with parameters (dimension, modulus, noise rate) = (n, q, \eta) by first choosing a block size \beta as a function of (n, q, \eta).
\beta specifically should be the smallest integer above Neumaier's "reducedness parameter" lower bound; e.g. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6743704/pdf/10623_2016_Article_273.pdf.
If \beta is below Neumaier's threshold, then the lattice reduction algorithm will fail to produce the shortest vector in the relevant (Bai-Galbraith embedded) lattice, which is the secret key of the lattice cryptosystem.
If \beta is above Neumaier's threshold, then you're wasting work.
(Sometimes there has been disagreement over the exact value of \beta for a given instance of a lattice cryptosystem, but this is typically within +- 1 to 3.)
But for the sake of estimating the order of the cost of breaking a lattice cryptosystem (via secret key recovery), everyone essentially agrees on what \beta should be.
-----
Given a choice of block size \beta (and an associated "Bai-Galbraith" lattice basis, which is a simple arrangement of terms in a matrix from the public key and ciphertext material of an instance of a lattice cryptosystem), the BKZ algorithm performs a polynomial number of "tours" performing a sieving subroutine (with various optimizations possible -- like "Dimensions for Free" -- and minor extra book-keeping required between each sieving subroutine call).
A tour means you go from the top-left to bottom-right "\beta by \beta" submatrices of the original Bai-Galbraith-embedded matrix (say, about 2n by 2n). For each submatrix, you make a call to the sieving subroutine in dimension \beta. The total number of tours is a small polynomial.
To be conservative in estimating the concrete security of some instance of a lattice cryptosystem, the "Core SVP" model recommends to only include the costs of a single sieving subroutine in dimension \beta. (If an attacker can sieve once on a \beta by \beta matrix, you give them the win.)
So, the real question becomes: How much does it cost to sieve in dimension \beta?
-----
There is a long list of literature on how best to sieve. Recent work by Kirshanova & Laarhoven claims this line of work in sieving doesn't get much better than we currently know. The Jessica / G6K machine by Albrecht, Ducas, Herold, Kirshanova, Postlewaite, & Stevens and the Tensor Core Sieving implementations by Ducas, Stevens, & van Woerden provide two recent points of data at the frontier of the science.
A sieving algorithm attempts to find the shortest basis in a given lattice (very close to the cost of finding the shortest vector in a given lattice). It takes a matrix as input (treating it as a basis for a lattice), and attempts to "geometrically reduce" this matrix into another, much shorter, nicer matrix acting as a basis for the same lattice -- but which allows to easily answer hard questions about the associated lattice's geometry.
The known sieving algorithms are better than "naive brute force" approaches, but not by a lot. (If they were significantly better than brute force, lattice cryptography as a whole would be dead!)
At a very high / abstract level, a sieving algorithm uses a matrix (a lattice basis) as input, samples many random integer-vectors, and computes 'lattice-point vectors' by multiplying the input-matrix with these randomly-sampled integer-vectors.
Each such 'lattice-point vector' is a point in the lattice / element of the lattice, and with high probability, each such 'lattice-point vector' will be about about the same length (emanating from the origin, (0, 0, ..., 0)).
The idea, though, is to take addition/subtractions of each pair of 'lattice-point vectors' to generate a new list of 'candidate vectors.'
The 'candidate vectors' will also be in the lattice, but the hope is that you might find some vector in the list of 'candidate vectors' that is shorter than the list of all lattice-vectors you have so far.
It is a very rare event that a 'candidate vector' will be usefully shorter, so this step requires a Lot Of Brute-Force Work.
After obtaining enough 'candidate vectors' that are shorter than previously known, the procedure 'resets' -- arranging these vectors in a matrix, and repeating the above procedure -- until eventually the shortest vectors in the entire dimension-\beta (sub)lattice are found. (Then, the overall BKZ tour proceeds on further.)
-----
Memory-Costing:
The idea with 'memory-costing' is that within each iteration of the sieve, one needs to generate an extremely large list of 'lattice-point vectors' (consuming system entropy and memory size) and store them persistently for some Very Long Time. Since each such random vector is useful to add/subtract with other future random vectors -- that is, you are doing (potentially) some "All-Pairs" style of computation -- you end up generating a huge database of randomly-sampled data from the original, very short matrix used as input to that iteration-step..
Modern analyses count two things towards cost (in a fairly clean way):
1) The maximum number of vectors you're expected to have to store in memory at once.
2) The maximum number of arithmetic operations you're expected to have to perform until the iteration completes.
For simplicity for the "below-average half of us on this list" (with many apologies to the "above-average half of us in this list"),
let's say that the calculation you need to perform involves 2^115 arithmetic operations and storing 2^70 integers.
(One might ask -- wow, that's a HUGE memory already! Is there a lower-memory alternative? Possibly -- but current analyses indicate the time-vs-memory trade-off is BAD: i.e. lowering memory from current BKZ-sieving analyses seems to cause an extreme increase in running time.)
Now, we arrive at "memory-costing" -- finally.
Fundamentally, the number of cores / processors in any realistic Very Large Supercomputer is likely to be much less than the storage of this device.
As a result, you don't only need to consider..
1) How many operations need to be performed to succeed in expectation, and
2) How many 'memory cells' need to be occupied to succeed in expectation,
..but also..
3) How much delay/lag is there involved with moving memory around between memory-storage and processing-units?
At a high level, Claim: Intra-System Communication is more costly than the System's Overall Computation in such an algorithm's execution.
-----
To conclude this email (sheesh), let's take a simple example, with lots of blue highlighted numbers.
Suppose each CPU in the system can perform 1 arithmetic operation per clock cycle out of the 2^115.
Now, calculate some number of nanometers in between each possible storage point per integer in the system's memory (using the denest future memory-storage technology you can imagine this next century).
This allows you to derive a minimum physical storage radius in meters / kilometers for the entire memory of this algorithm's execution. (Here, I'm assuming that memory is tiled as a 2D array, perhaps as a Very Big square, or a rectangle, or a circle. I will posit some small constant number of z-axis tilings for memory-communication wires and redundant memory, etc. There has also been discussion of a "Death Star" 3D-tiling of memory in orbit of the planet, but that seems unrealistic...)
Based on the speed of light and the minimum storage radius in meters / kilometers for the entire memory, you can derive a delay/lag for two integers to be brought together -- on average / in expectation -- between any two points at physical distance in this large memory. Let's say it's 0.01 seconds on average.
Further, let's assume that typical nodes in the computing system run at around 1.0 GHz -- i.e. about 1 billion clock cycles / arithmetic operations per second per node.
Then, clearly, the 0.01 seconds on average delay to move memory into the compute-nodes is many orders of magnitude greater than the processing power of individual nodes! (This is where any additional 'memory-costing' calculations arise from.)
-----
The above is already a difficult enough problem to reason about, but further -- you need to consider that a sufficiently sophisticated adversary will custom-design a Very Large Scale supercomputer (and perhaps -- have many further optimizations / speed-ups that are not published in public).
The only, simple, remaining question is:
Can you provide a concrete/comprehensive, speed-of-light-based lower bound for the additional costs of memory accesses during the execution of a Primal Attack using BKZ-with-sieving against Kyber-512?
Best regards,
--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/ae918ed4-908c-4fdd-b7e4-63452aa0fd8dn%40list.nist.gov.
Daniel Apon
Matt Henrick
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANuKc3h7kB0y%3DRzRNw9ZoNCtFh-gzzph7Sjix16TUD06HkugkA%40mail.gmail.com.
michal.r.a...@gmail.com
John Mattsson
Thanks Daniel,
I think this is a good summary of the current situation. I agree that papers in this area would be very welcome. As you write, even a survey-style paper documenting the viewpoints conjectured thus far would be very useful.
But just as with performance, theoretical models and calculations only take you so far. In addition to theoretical models, I would like to see increased focus on challenges. I think a lot more government funding should go to creating and breaking challenges such as [1-5]. In the end, the important practical things are time and cost, not various theoretical complexities. For performance, I love the always updated eBACS (ECRYPT Benchmarking of Cryptographic Systems) [6]. I would also like to see more funding for such activities.
With actual cost and time numbers from challenges and performance measurements you can make quite good estimates even of secret capabilities. Security agencies use the same supercomputers, FPGAs, and ASIC processes as everybody else. Sometimes the exact number of FLOPS is even public [7]. Budgets and energy consumption are limiting resources for everybody.
My understanding is that the current discussion revolve around a theoretical debate regarding whether ML-KEM-512 surpasses or falls short of AES-128 in one of the memory-cost models. ML-KEM-512 appears to provide a substantial degree of practical security. Maybe having 5 security levels is too much. The complexities of AES-128 and AES-256 are just arbitrarily chosen magic numbers. I like the standardization of Curve25519 and Curve448 [8] where it was decided that Curve448 is a good curve and 448 bits is good enough. In practice, the complexity differences between attacks on Curve448 and P-521 does not matter much. Both offer very high security (if implemented with point validation, which is unfortunately often missing in practice). At this point in the project, the original 2017 call of proposals [9] is quite irrelevant.
Cheers,
John
[1] https://www.latticechallenge.org/
[2] https://www.mqchallenge.org/
[3] https://crowdchallenge.tii.ae/mceliece-challenges/index.php
[4] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
[5] https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html
[7] https://en.wikipedia.org/wiki/National_Defence_Radio_Establishment
[8] https://www.rfc-editor.org/rfc/rfc7748.html
--
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/ae918ed4-908c-4fdd-b7e4-63452aa0fd8dn%40list.nist.gov.
Wrenna Robson
John Mattsson
Hi Wrenna,
A recent discussion about European recommendations can be found here:
https://mailarchive.ietf.org/arch/msg/cfrg/ADMtHuMgG20XTFM989ECtCYB1YQ/
In addition to NIST, ML-KEM (Kyber) is also recommended by at least The Netherlands, France (ANSSI), and CNSA 2.0. While The Netherlands have stopped recommending FrodoKEM and Classic McEliece, ANSSI recommends also including FrodoKEM where performance is not a problem.
My guess would be that most countries in a few years will recommend ML-KEM and ML-DSA for general use. I hope all countries will do that. Global standards are very good for everyone.
Cheers,
John
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Wrenna Robson <wren....@gmail.com>
Date: Monday, 23 October 2023 at 10:46
To: Matt Henrick <mtthe...@gmail.com>
Cc: Paul Hoffman <paul.h...@icann.org>, pqc-forum <pqc-...@list.nist.gov>
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANuKc3hL2EK7hQHvZ%2BAVo%3D6BaO9n9Bsfw_ED7KtnZT%3Dir4_q3Q%40mail.gmail.com.
Wrenna Robson
William Whyte
Hi Matt – thanks for the info. How is ISO managing the risk that NIST might end up standardizing something subtly different from the current Kyber spec? Is the plan to delay publication of 18033-2 until the NIST standard is out, or to publish 18033-2 when it’s ready and update if necessary after the NIST standard?
Cheers,
William
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov>
On Behalf Of Matt Henrick
Sent: Monday, October 23, 2023 12:26 AM
To: Wrenna Robson <wren....@gmail.com>
Cc: Paul Hoffman <paul.h...@icann.org>; pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [Ext] [pqc-forum] Re: Kyber security level?
WARNING: This email originated from outside of Qualcomm. Please be wary of any links or attachments, and do not enable macros.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAFhiExv%2B2DtPeWUAYET3d4RHiRnxRehODrnPBFimaJ_W0yoU-A%40mail.gmail.com.
Mike Hamburg
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/c752d059-46a0-4874-bf94-3bf3c64a4c56n%40list.nist.gov.
Daniel Apon
Very well could be!
Related: Thanks Michal for linking your paper -- people ought to cite it more!
Let me list a few, natural metrics / data points to consider (regarding cost of memory & memory access):
i) energy cost of the memory access (as Mike points out)
ii) cost of manufacture/installation of the large memory (not free in the real world)
iii) heat dissipation in overly dense memory configurations with large energy draw
iv) memory bus configuration limitations (there are no e.g. 2^69-to-1 data buses that I'm aware of); routing/scheduling at scale must be hierarchical in some manner
v) reasonable physical fault tolerance for each component of the overall compute system
Also, All-- my personal thanks especially for the many, off-list calculations that a large variety of researchers are actively engaged in suddenly; I take this as a huge success. =)
Cheers,
--Daniel
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/5B6626EE-6FC6-41B1-91E8-0D488EB677AF%40shiftleft.org.
D. J. Bernstein
clarification questions regarding recent security claims from NIST.
NIST hasn't answered those questions. Procedurally, this stonewalling
can't be allowed to stop security review. Content-wise, I think the
"yes" answers are the most obvious interpretations of what NIST wrote.
If I don't see a clarification soon from NIST one way or another then
I'll respond under the assumption that the "yes" answers are correct.
---D. J. Bernstein
D. J. Bernstein
> My understanding is that the current discussion revolve around a
> theoretical debate regarding whether ML-KEM-512 surpasses or falls
> short of AES-128 in one of the memory-cost models.
The point of post-quantum cryptography is to protect against big quantum
computers that future attackers seem increasingly likely to have. Future
attackers will have big non-quantum computers in any case.
How many years of security should we expect Kyber-512 to provide if it
already falls short of AES-128 by some unspecified amount against known
attacks? 5? 10? Is there a risk analysis backing this up?
The latest Kyber documentation says that the Kyber-512 security level
measured by "gates" could be anywhere between 8 bits below AES-128 and
22 bits above. That was written years ago. There have been many papers
on lattice attacks since then. Is there documentation presenting and
justifying updated uncertainty intervals?
NIST claimed that Kyber-512 was "unlikely" to be less secure than
AES-128 when the costs of memory access were taken into account. The
foundation of this claim was NIST incorrectly multiplying the "real cost
of memory access" by "the RAM model"---assigning the cost of a full
memory access to each bit operation. What makes this error _really_
dangerous is that it's missing the analysis that any large-scale
attacker will carry out: clearly specify a realistic cost model, and
then optimize attack subroutines and parameters for that model. Is there
literature doing this for Kyber-512?
Is there _any_ clearly defined non-withdrawn quantitative security claim
for Kyber-512, so that if the claim is wrong then it can be falsified?
Where? Sure, if Kyber-512 attacks improve enough for academics to
demonstrate them then that's the end of the story, but are we supposed
to ignore attacks carried out by attackers with vastly larger resources?
If you think these questions don't matter because "applications should
be able to quickly change the security level if needed", what do you say
to the users whose encrypted data has been given away to attackers? Is
the objective here to advertise post-quantum support, or to actually
solve the security problem at hand?
> Security agencies use the same supercomputers, FPGAs, and ASIC
> processes as everybody else.
equipment anywhere else."
https://web.archive.org/web/20230430105513/https://www.nsa.gov/portals/75/documents/news-features/declassified-documents/nsa-early-computer-history/6586785-nsa-key-role-in-major-developments-in-computer-science.pdf
---D. J. Bernstein
Daniel Apon
I would like to cite your own analyses.
I bring your attention, first, to the NTRU Prime Round 1 specification document, found in the NTRU Prime ZIP file at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions
Readers can distinguish this PDF as labeled with the numbers "20171130" at the top of the PDF.
On page 28, Section 8.1, paragraph labeled "Parameter set kem/sntrup4581761," we find the text:
"Category 5. [..] we expect that further analysis [..] of memory and communication costs, will show that this parameter set is much more expensive to break than AES-256."
I bring your attention, second, to the NTRU Prime Round 3 specification document, found in the NTRU Prime ZIP file at https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions
Readers can distinguish this PDF as labeled with the numbers "20201007" at the top of the PDF.
On page 83, Section 8.2, paragraph labeled "Parameter set kem/sntrup761," we find the text:
"Category 2."
Again in the Round 3 specification, PDF labeled "20201007," we find on page 103, Table 2, the text:
"Warnings: Memory is not free."
In this same table, we see multiple examples of "free memory cost" vs "real memory cost" increasing bits of security (by your own estimation) for hybrid and non-hybrid attacks for enumeration and sieving attacks by nearly 40 bits of security.
Perhaps it is best - at last - to let others in the public fora perform their own independent analyses..
--Dan A
Oscar Smith
Daniel Apon
The algorithm being considered for memory-access cost is not different between cryptosystem A vs cryptosystem B.
It is the same attack algorithm for both cryptosystems.
If you have an attack algorithm that noticeably distinguishes between Kyber and NTRU Prime in its approach, the entire world would very much love to hear about it...
Best,
--Daniel
Daniel Apon
Alexander May
We would like to draw your attention to our Bochum Challenges.
Our page was set up this summer, currently provides Kyber Challenges, and we plan to regularly update with new challenges (e.g. featuring Dilithium and McEliece within the next months).
We would be very happy to see more cryptanalysis of our challenges, with the goal to foster confidence in PQ parameter selection.
All the best,
Alex
(on behalf of the Bochum Challenge team with Julian Nowakowski,
Carl Richard Theodor Schneider, and Luca Witt)
D. J. Bernstein
> In this same table, we see multiple examples of "free memory cost" vs "real
> memory cost" increasing bits of security (by your own estimation) for
> hybrid and non-hybrid attacks for enumeration and sieving attacks by nearly
> 40 bits of security.
case, the increase is from the Core-SVP iteration count: e.g., for
sntrup653, this estimate is 2^169, whereas the 2^129 is Core-SVP.
Core-SVP is not "the RAM model". Every bit operation adds 1 to cost in
"the RAM model". The NIST calculation at issue ("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") is multiplying
* the "real cost of memory access" by
* cost in "the RAM model",
so it's counting a full memory access for every bit operation; that's
(1) wrong and (2) not what the NTRU Prime documentation says.
Quantitatively, the NTRU Prime cost metric says that looking up n bits
in a T-bit table has the same cost as n*T^0.5/2^5 bit operations. If an
attack iteration has this lookup and then B bit operations, the total
cost of the iteration in this metric is n*T^0.5/2^5 _plus_ B.
Meanwhile the cost of an iteration in "the RAM model" is B for the
attacks in question (plus a negligible extra cost for memory "gates"),
so NIST is taking n*T^0.5/2^5 _times_ B.
For the Kyber-512 attacks in question, saying that the NTRU Prime
documentation estimated memory-access cost as 2^40 isn't far off
(although Kyber-512 is smaller than sntrup653, and "approximately"
downplays the explicit warnings in the documentation). What I've
challenged here is something different: NIST inflating costs by taking
all of the bit operations counted in "the RAM model" and multiplying
those by the memory-access cost.
See https://blog.cr.yp.to/20231023-clumping.html for an analysis, from
first principles, of two simple attack components, first in "gate"
counts, then in the NTRU Prime cost metric, then in NIST's inflated
metric.
---D. J. Bernstein
D. J. Bernstein
> 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
My blog post already said this ("Multiplying the new iteration count by
the cost of memory access per iteration makes perfect sense"), while
carefully distinguishing this from the actual topic of dispute. Here are
formulas for the actual dispute:
* The correct calculation is memcost + bitopscost, i.e.,
(memcost/iter + bitopscost/iter) * iter.
* NIST's inflated calculation is memcost/iter * bitopscost, i.e.,
(memcost/iter * bitopscost/iter) * iter.
The dispute is not about multiplications by iter, or about various
factors contributing to iter. The dispute is about NIST multiplying
memcost/iter by bitopscost/iter, instead of correctly adding those.
The NIST quote that I explicitly challenged was "40 bits of security
of additional security quoted as the 'real cost of memory access' by the
access" by costs in "the RAM model", and thus counting a memory access
for every bit operation; that's fundamentally wrong.
---D. J. Bernstein
Wrenna Robson
(memcost/iter * bitopscost/iter) * iter", presumably that latter expression should just have bitopscost rather than bitopscost/iter just to be consistent with yourself? (Also seems to make the units make more sense.)
--
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/20231024114552.794501.qmail%40cr.yp.to.
D. J. Bernstein
> I presume that NIST obtained 40 in the following easy way: look at the
> security-level table on page 103 of the source; observe that pre-quantum
> sieving for sntrup653 at the top is listed as 169 and 129 for "real" and
> "free" respectively; subtract the 129 from the 169.
Christopher J Peikert writes:
> 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."
Christopher J Peikert writes:
> You say "Presumably NIST obtained 40 in the following easy way: ...
> subtract the 129 from the 169."
[ ... ]
> The post doesn't give any evidence to support either assumption. And
> as we have seen, neither one holds up.
Daniel Apon writes:
> in the Round 3 specification, PDF labeled "20201007," we find on page
> 103, Table 2
> increasing bits of security (by your own estimation) for hybrid and
> non-hybrid attacks for enumeration and sieving attacks by nearly 40
> bits of security.
---D. J. Bernstein
D. J. Bernstein
> Quick question - in your last, when you said "NIST's inflated calculation
> is memcost/iter * bitopscost, i.e.,
> (memcost/iter * bitopscost/iter) * iter", presumably that latter
> expression should just have bitopscost rather than bitopscost/iter just to
> be consistent with yourself?
the algorithm. Typically the algorithm is structured as a series of
identical iterations, and the analysis looks at the number of iterations
(call this "iter") and the bit operations in each iteration (that's
bitopscost/iter); multiplying those gives
bitopscost = bitopscost/iter * iter.
The cost for memory access is similarly memcost = memcost/iter * iter.
The total cost of memory access and bit operations is
memcost + bitopscost = (memcost/iter + bitopscost/iter) * iter.
When NIST says "the RAM model", it's counting each bit operation as cost
1, but instead of a realistic memcost it has cheapmemcost, meaning cost
just 1 per memory-access operation. Usually cheapmemcost is negligible,
so "the RAM model" says basically bitopscost = bitopscost/iter * iter.
When NIST says "approximately 40 bits of additional security quoted as
the 'real cost of memory access' by the NTRUprime submission", it's
taking estimates for memcost/iter numbers, such as 2^40 coming from an
estimated memcost = 2^169 and an estimated iter = 2^129.
(Ultimately those estimates come from the NTRU Prime documentation
saying "we estimate the cost of each access to a bit within N bits of
memory as the cost of N^{0.5}/2^5 bit operations", along with estimates
for the amount of memory access incurred by "primal" lattice attacks.
See the NTRU Prime documentation for important warnings about
underestimates, overestimates, and instabilities in those numbers.)
When NIST says "40 bits of security more than would be suggested by the
RAM model", it's multiplying "real cost of memory access" by cost in
"the RAM model", giving memcost/iter * (cheapmemcost + bitopscost),
which is basically memcost/iter * bitopscost.
This is an inflated formula for the algorithm cost. What the above
"i.e." is saying is that this inflated formula is equal to
memcost/iter * bitopscost/iter * iter; that's simply plugging in the
equation bitopscost = bitopscost/iter * iter.
See https://blog.cr.yp.to/20231023-clumping.html for an illustrative
example of analyzing an algorithm where each iteration does one memory
lookup and then thousands of bit operations. The memory cost dominates
once the table sizes are large enough, so the total cost is basically
memcost = memcost/iter * iter, while NIST's inflated cost estimate
memcost/iter * bitopscost is too high by a factor bitopscost/iter.
If you're looking for a cost definition that can be given to a proof
system, see Section 2.1 of https://cat.cr.yp.to/papers.html. That
definition doesn't account for long-distance communication costs, so it
ends up assigning unrealistically low costs to batches of memory
accesses---but still not cost 1; you can trace how the memory-access
costs show up in the analyses using that definition. If you look at,
e.g., isd1_cost then you'll see that one of the costs involves sorting,
which is an example of an operation on a large volume of memory; that
cost is added to other bit operations; the sum is multiplied by iter;
something extra is added for preprocessing and postprocessing outside
the iterations. The resulting cost tally perfectly matches costs
observed for full algorithm executions in a circuit simulator.
---D. J. Bernstein
Wrenna Robson
--
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/20231024142248.803003.qmail%40cr.yp.to.
Daniel Apon
Matt Henricksen
Daniel Apon
(Ad hominem needling of both NIST and IACR aside,) thanks for the mostly technical nature of these posts. I'll take a look.
--Daniel
D. J. Bernstein
> I bring your attention, first, to the NTRU Prime Round 1 specification
> It's utter nonsense to assume that the memory cost analysis from one
> algorithm translates equivalently to an unrelated algorithm.
First, the cited 2017 document says that "the best attack algorithms
known today are much better than the best attack algorithms known a few
years ago, so it is unreasonable to expect that the algorithms have
stabilized"; and there have indeed been many advances in lattice attacks
since 2017.
(For readers not familiar with the overall attack trends, here's an easy
way to check: look at 2010 Lindner--Peikert claiming that dimension 256
offers "security levels at least matching those of AES-128"; then look
at FrodoKEM saying it's an "instantiation and implementation" of 2010
Lindner--Peikert and recommending dimension 640 for "category 1".)
Second, the cited 2017 document highlights a massively parallelizable
limited-memory attack algorithm (and explains why this is important),
whereas NIST's claims regarding the Kyber-512 security level are instead
focusing on a memory-intensive algorithm, one that was designed to
minimize "gates" without regard to communication costs.
So, no, it's very much not the same attack algorithm.
---D. J. Bernstein
Matt Henrick
John Mattsson
Hi Dan,
Dan Bernstein wrote (https://blog.cr.yp.to/20231023-clumping.html):
> Some of the followups to my message were obviously off-topic, such as ad-hominem
> attacks, praise for Kyber-512's efficiency, and praise for NIST manipulating its minimum
> criteria to allow Kyber-512 (seriously: "adjust the definition of security category 1 if
> needed, but make sure to standardize ML-KEM-512").
It seems clear that we don’t agree whether NIST should standardize ML-KEM-512 and if the 2017 call of proposals is important anymore but I have a hard time seeing that my comments were off-topic at all. Your email and blog post talk a lot about whether NIST should standardize ML-KEM-512, the importance and definition of security category 1, and non-security properties. Some examples:
“So I recommend eliminating Kyber-512”
”I recommend terminating standardization of Kyber-512”
”manipulating the qualification criteria”
”it was crystal clear that cryptosystems had to be at least as hard to break as AES-128 in every "potentially relevant" cost metric”
”applications that have limited sizes for public keys and/or ciphertexts”
My comment that NIST should standardize ML-KEM-512, that the sizes of public keys and ciphertexts are very important, that the 2017 call of proposal is quite irrelevant at this point, and that ”at least as hard as” is incorrect seem very much on-topic.
Assuming you talk about me, I don’t think I have praised ML-KEM-512 efficiency at all. I pointed that sizes for public keys and ciphertexts are very important for performance. I have made the same comment several times during the project. I would likely have been happy with NTRU-509 as well but that it quite irrelevant at this point.
I think there is a lot to learn from the SHA-3 standardization. I think the decision to stick to the original requirements was a big mistake. The adoption of SHA-3 was hurt by the perception that it is slow, not the lack of trust. As we can see, the fast SHAKE functions are much more used than the slow fixed-length SHA-3 functions, and a lot of people see TurboSHAKE with half the number of rounds as the future. The fixed-length SHA-3 functions offer meaninglessly high pre-image security significantly hurting their performance.
https://github.com/emanjon/NIST-comments/blob/main/2023%20-%20FIPS%20202%20and%20SP%20800-185.pdf
Cheers,
John Prueß Mattsson
D. J. Bernstein
> standardize ML-KEM-512, the importance and definition of security
> category 1, and non-security properties.
to focus on the security claims for Kyber. I quoted a security-level
calculation by NIST, challenged the calculation as being (1) wrong and
(2) a misrepresentation of NIST's claimed source, gave an example of a
quantitative sanity check flunked by that calculation, recommended that
NIST withdraw the Kyber claims that it had explicitly based upon this
calculation, and, given the considerable risk of Kyber-512 being weaker
than AES-128, recommended terminating standardization of Kyber-512.
If you would like to comment on topics beyond the Kyber security level
(certainly there are many interesting non-security topics, and my blog
is not limited to security topics), as illustrated by your "a lot more
additional information can be sent in the same packet" comments, please
start a separate email thread to make it easier for readers to track the
messages that are focusing on the security level.
---D. J. Bernstein
Daniel Apon
1) I'm exceedingly hesitant to litigate, support in part or full, or criticize in part or full the research paper pre-print cited in your blog post before it has undergone blind peer review and accepted for publication in a respected conference's proceedings. Scientific publication processes exist for many reasons, and 'live/online' peer-review on a public forum is not the proper process. (For a variety of related and unrelated reasons, I had to sit and think a while before writing this very email as well.)
2) Conditioned on the above limitations, I have two simple clarifying questions about the matter in the blog post itself:
i) Would you please formally, technically, and unambiguously define what an "iteration" (i.e. "iter") is?
ii) You've introduced a brand new costing model and argued that it changes the estimation of the cost of AES-128. This raises a red flag for me: that a sleight of hand is occurring in the rhetoric.
For example, perhaps I can introduce another new costing model. Maybe I will allow for a hardware model that can efficiently evaluate discrete approximations up to bit-precision 'k' of a sinusoidal function in 'one gate' / one specialized hardware operation. Now, I want to consider machine-learning style attacks against AES, and cost it using this specialized hardware model.
The point of fixing a model and being consistent, is that it allows straightforward apples-to-apples comparisons. Note, of course, the odd effect that -- by reducing the "gate-cost of attacking AES-128" with a model-switch, you've (paradoxically) increased bits of security -- ceteris paribus -- for all cryptosystems considered against that model. Then, of course, one should consider enhanced algorithms in the new model for the multitude of algorithms under consideration, causing a chaotic relative-scoring effect on any security review. Rhetorical question: Is this somehow still reasonable? Sure. But it's certainly a research question in the small handful of months (or days) after beginning the line of discussion, and it's too soon to expect the entire community to draw authoritative conclusions (see my comment under (1)).
Actual question here: The circuit gate model is very well-defined. There are 2 bits into a gate and 1 out, so there are 2^2^2 =16 gates. Would you please make your argument in this model, or consider what changes?
3) Regarding your reply to my reply to Oscar:
i) 2010 Lindner-Peikert was a research paper, not a submission as a standardization candidate for NIST.
ii) that the NTRU Prime 2017 document -- which was the specification document of a submission as a standardization candidate for the formal NIST process -- woefully miscalculates the expect bits of security of its proposed parameters is not a minor problem.
---
In summary:
I remain unconvinced by the ad-hominem accusations.
I also remain unconvinced by the new technical claims.
Sadly, we may not come to agreement on these issues -- but this thread's gone on long enough (probably far too long), and I need to get back to my day job.
Best regards,
--Daniel
Dan Brown
Wrenna Robson writes:
> Quick question - in your last, when you said "NIST's inflated calculation
> is memcost/iter * bitopscost, i.e.,
> (memcost/iter * bitopscost/iter) * iter", presumably that latter
> expression should just have bitopscost rather than bitopscost/iter just to
> be consistent with yourself?
When I write "bitopscost", I mean the total cost of bit operations in
the algorithm. Typically the algorithm is structured as a series of
identical iterations, and the analysis looks at the number of iterations
(call this "iter") and the bit operations in each iteration (that's
bitopscost/iter); multiplying those gives
---D. J. Bernstein
D. J. Bernstein
> research paper
https://blog.cr.yp.to/20231023-clumping.html is much shorter than the
paper and gives a self-contained description of (1) the xor-and-popcount
operation, (2) the algorithm for that operation in the Asiacrypt 2020
paper (which says this is its "primary optimisation target", and is the
source of Kyber's "gate" count for "AllPairSearch"); and (3) how
clumping solidly beats the 2020 paper in the 2020 paper's metric.
This is from first principles---things taught to first-year CS students.
It's simple enough that students should be able to follow it without
trouble. If you have a question about some step, feel free to ask.
> Would you please formally, technically, and unambiguously define
> what an "iteration" (i.e. "iter") is?
iteration is "xor-and-popcount".
> brand new costing model
No. The blog post analyzes each algorithm three ways: using the cost
metric in the Asiacrypt 2020 paper; using the memory-cost metric from
the 2020 NTRU Prime documentation; and using an inflated calculation
that NIST introduced in 2022 and misattributed to NTRU Prime.
> Actual question here: The circuit gate model is very well-defined. There
> are 2 bits into a gate and 1 out, so there are 2^2^2 =16 gates. Would you
> please make your argument in this model, or consider what changes?
quote the text from the blog post that you don't find clear. I don't
know what "argument" you're referring to here, nor do I know why
switching to another cost metric is supposed to be relevant.
Each of the three types of calculations in the blog post has good
reasons to be there. The Asiacrypt 2020 metric is the source of the
"gate" counts in the Kyber documentation. NIST's (mis)calculation is the
source of NIST's claim that, given memory-access costs, Kyber-512 is
"unlikely" to be easier to break than AES-128. The NTRU Prime metric is
numerically in between and is what NIST incorrectly claimed to be using.
> the NTRU Prime 2017 document
> proposed parameters
and how do you claim this is relevant to the Kyber security level?
The documentation obtains 2^248 (page 28) for sntrup4591761 from the
2015 Hoffstein--Pipher--Schanck--Silverman--Whyte--Zhang estimate (cited
and quoted on page 24) of the cost of enumeration. Are you claiming the
2015 paper "woefully miscalculates" that cost? If so, why are you not
properly naming the source of the calculation, and what's your
justification for claiming that it was a woeful miscalculation?
The 2017 NTRU Prime documentation explains why its analysis of known
attacks doesn't include numbers for sieving, given "the absence of any
realistic analyses of sieving cost for large β". In context, "realistic"
includes the costs of memory access; this is Section 6.7 of the 2017
documentation. Are you claiming that there _was_ a realistic analysis of
sieving cost for large β in 2017? If so, where?
(As a side note, in 2022 you characterized sieving against Kyber-512 as a
Death Star "small-moon-sized cryptanalytic device" involving "importing
matter from other solar systems". Surely 2017-vintage sieving against
sntrup4591761 would need an even larger device; did I miss where you
spoke up to object to people considering those attacks? Anyway, the NTRU
Prime documentation wasn't arbitrarily dismissing big-memory attacks; it
was asking for quantification of memory-access costs. If you claim that
this was quantified for large-β sieving in 2017: Citation needed.)
As for the overall security level, are you claiming that taking numbers
for enumeration was ("woefully") miscalculating the costs of attacks
known in 2017? If so, what's your evidence for this claim?
Or are you claiming that _newer_ attacks against sntrup4591761 are far
below 2^248? If so, what's your evidence for this claim, and why do you
claim this contradicts something in the 2017 NTRU Prime documentation?
Note that the documentation explicitly says it's analyzing _known_
attacks (as an analogy, 2010 Lindner--Peikert said that dimension 256
was "currently" at least as hard to break as AES-128), while warning
that "it is unreasonable to expect that the algorithms have stabilized".
This is perfectly consistent with, and even predicts, newer algorithms
being faster.
---D. J. Bernstein
John Mattsson
Hi,
Future attackers will certainly have big non-quantum computers, but I think we can expect AES-128 to resist single-key attacks from even the most powerful adversaries for decades. I have not seen any realistic cost-time calculations indicating otherwise. I agree with NIST that “AES 128 will remain secure for decades to come”. The practically important security question to ask is how much cost (in dollars) and time (in years) breaking ML-KEM-512 requires.
When 128-bit keys become possible to brute force (which will not be with Grover’s algorithm), attacks will focus on keys or ciphertexts of particular interest. If you have less interesting information, you will be safe for a longer time. Practically, the more relevant questions are often “is it worth attacking?” and “is cryptography the weakest link?” rather than “can it be attacked?”.
https://xkcd.com/538/ (CC BY-NC 2.5 Deed)
If you want protection against nation state attackers 50 years from now, you should definitely use AES-256 and ML-KEM-1024 (or FrodoKEM or Classic McEliece). For many other use cases I think ML-KEM-512 + Curve25519 provide plenty of security. Multi-key attacks are a different story. Multi-key attacks on AES-128 might already be practically possible but are much less interesting for attackers. I don’t know the complexity of multi-key attacks on ML-KEM + Curve25519.
I think the most important thing right now is to quickly get standardized quantum-resistant cryptography deployed on a large scale, and a very important aspect of that is performance/sizes. NIST has previously done a very good job with security levels and when to phase them out.
> "NSA's computers almost always were well in advance of data processing
> equipment anywhere else."
The article also says that NSA like other security agencies in the 1960s and 1970s transitioned from developing their own computers to buying commercially developed computers. The article also states that in 1983 the commercially available Cray XMP-24 was ”arguably the most powerful computer in the world”.
Cheers,
John Preuß Mattsson
--
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/20231024002414.759971.qmail%40cr.yp.to.
D. J. Bernstein
> I think we can expect AES-128 to resist single-key attacks from even
> the most powerful adversaries for decades.
unspecified amount against known attacks? 5? 10? Is there a risk
analysis backing this up?"
> 1960s and 1970s transitioned from developing their own computers to
> buying commercially developed computers.
"in addition to building its own units". It then says that NSA "has a
great demand for microchips". It leaves the details of this demand
classified.
---D. J. Bernstein
Oscar Smith
Dear Dan "potential NSA spy" Bernstein,
"It leaves the details of this demand classified."
How terrible that, like the NSA, I can't FOIA your email inbox <3
D. J. Bernstein
> totalcost (breaking AES-128) : totalcost (breaking ML-KEM-512)?
(listed in the underlying Asiacrypt 2020 paper as "NOT, AND, OR, XOR,
LOAD, STORE"), was, given "known unknowns", somewhere between 2^-22 and
2^8 for the "primal" attacks considered in the Kyber documentation. The
analysis hasn't been updated for newer attack papers, including some
undisputed speedups and some disputed speedups.
The current thread is about something much simpler: whether the total
cost of memory access in an algorithm is
* (right:) cost per memory access times the number of memory accesses
or
* (wrong:) cost per memory access times the total number of "gates",
where "gates" include not just memory accesses but also further bit
operations.
To see that NIST used the wrong answer in obtaining its claim that
Kyber-512 was "unlikely" to be cheaper to break than AES-128, look at
NIST's words multiplying the "real cost of memory access" by costs in
"the RAM model" ("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"), and look
at page 80 of NIST IR 8413 saying that in "the RAM model" the "cost of
an attack is determined by counting operations that act on a fixed
number of bits, including reading or writing to memory".
For a low-end example of how much this mistake shifts security levels,
look at Section 4.2 of the Asiacrypt paper, which counts about 6n bit
operations next to 1 memory access; for that particular subroutine, the
error inflates costs by 12 bits. The actual security difference will be
larger than this and requires research to pin down. Algorithm designers
who are charged a trillion bit operations for each memory access will
happily consider more sophisticated algorithms that spend billions of
bit operations making better use of each item retrieved from memory, but
then the same calculation error claims costs billions of times larger
than the actual costs.
There's still no erratum from NIST for this miscalculation, or for the
misattribution of this calculation to the NTRU Prime documentation.
---D. J. Bernstein
John Mattsson
Hi Dan,
>That doesn't answer the question: "How many years of security should we
>expect Kyber-512 to provide if it already falls short of AES-128 by some
>unspecified amount against known attacks? 5? 10? Is there a risk
>analysis backing this up?"
Well, the answer to your question containing “if it already falls short of AES-128 by some unspecified amount” is unspecified. As you acknowledge with “if”, there is no consensus that ML-KEM-512 falls short of AES-128. I try to answer both possibilities:
- Assuming NIST is correct in 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 answer is strictly more years than AES-128, so several decades.
- Assuming you are correct in that ML-KEM-512 falls short of AES-128 in some computational model, the fact that lattice sieving attacks requires huge amount of memory, which practically is a much more expensive resource than operations, my estimate would still be several decades.
You asked before what I meant with “theoretical”. What I would like to see is a realistic practical calculation of how much it would cost and how long time it would take to break ML-KEM-512. Some questions for you:
- Using the best current algorithms and commercial CPUs, FPGAs, and ASIC processes. How many billion dollars would it cost (CAPEX, OPEX) and how many million years would it take today to recover a single ML-KEM-512 decapsulation key? With such a calculation you can estimate the “years of security” for different types of information.
- In your blog you talk about multi-key attacks on AES-128, giving the impression that multi-key attacks on ML-KEM-512 might be a problem. What are the complexities of multi-key attacks on ML-KEM-512 and ML-KEM-512+Curve25519? I think using ML-KEM together with Curve25519 will be very common.
Some more questions for you:
- One of my collogues spent time doing complexity calculations. My collogue does not agree with you but does not want to comment in the PQC forum out of fear of being publicly labeled as stupid. Do you understand that your aggressive personal attacks are severely limiting the open scientific discussion, especially for young researchers?
- How can someone who is so often talking about openness and transparency be heavily involved in ISO, which is not only the opposite of that but also clearly a cybersecurity risk?
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VOzy0wz_E/m/6pgf5tFaAAAJ
- Do you understand that your unfounded claims that the NSA is actively undermining the security of ML-KEM is agreeing perfectly with the narrative of Russia and China? IETF, IEEE, and W3C are for good reasons heavily relying on NIST algorithms and will likely continue to do so.
https://www.newscientist.com/article/2396510-mathematician-warns-us-spies-may-be-weakening-next-gen-encryption/
https://foreignpolicy.com/2023/08/25/china-wants-to-run-your-internet/
“Beijing is trying to shift the development of the internet standards from the multistakeholder, collaborative, voluntary consensus system of the IETF, IEEE or W3C towards a multilateral, nation-state driven forum”
Cheers,
John Preuß Mattsson
--
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/20231026214149.972405.qmail%40cr.yp.to.
Oscar Smith
John Mattsson
> Isn't this the wrong metric? If you want an algorithm to last for 50 years
As I wrote before “If you want protection against nation state attackers 50 years from now, you should definitely use AES-256 and ML-KEM-1024 (or FrodoKEM or Classic McEliece)”. Just like algorithms have different security lifetimes, information does as well.
>surely the thing that matters is the algorithms and commerical cpus 40 years from now. We obviously don't know what those are, but on the hardware side at least, it's possible to make a pretty reasonable estimate.
Yes. For future attack algorithms you need to make an educated guess and determine how large margin you want.
Cheers,
John
From:
Oscar Smith <oscard...@gmail.com>
Date: Saturday, 28 October 2023 at 05:24
To: pqc-forum <pqc-...@list.nist.gov>
Cc: John Mattsson <john.m...@ericsson.com>, D. J. Bernstein <d...@cr.yp.to>
Subject: Re: [Ext] [pqc-forum] Re: Kyber security level?
D. J. Bernstein
> as I understand it, the Theta(sqrt(n)) cost of memory access is
> intended to model the energy cost of accessing memory, rather than the
> time cost. This is because accessing memory requires sending (and
> routing) a signal to and/or from memory, and communicating over a
> longer distance is more energy-intensive.
A more basic rationale for assigning cost d to sending a bit over a
length-d wire is that there are d length-1 components of the wire, each
of which is occupied by that bit for a constant amount of time. This
rationale doesn't depend on whether the segments are used serially; as
https://maths-people.anu.edu.au/~brent/pd/rpb055.pdf puts it, the lower
bounds "do not need to assume that the propagation time increases with
the length of the wire".
Fundamentally, the attacker is limited by the available hardware and the
available time. For example, 10 units of hardware running for 5 units of
real time carry out at most 50 separate actions, which you can visualize
as follows in space-time:
* Time 0: 0123456789
* Time 1: 0123456789
* Time 2: 0123456789
* Time 3: 0123456789
* Time 4: 0123456789
Sending a bit through a length-d wire consumes d of those actions. For
comparison, d bit operations also consume d of those actions.
The above description ignores constant factors. A hardware gate is
physically more complicated than a similar length of wire and takes
longer to settle down. The NTRU Prime documentation looks at energy
numbers published by Intel to estimate that retrieving a bit from N bits
of memory has the same cost as sqrt(N)/2^5 bit operations. It should
also be possible to come up with a constant by directly looking at the
hardware mass and time consumption for bit operations and for wires.
(For a really precise estimate, one should account for different types
of bit operations: e.g., XOR is more expensive than NAND.)
Here's one reason that it's good to keep more than energy in mind.
Focusing exclusively on energy makes the idea of "run at lower and lower
clock speeds to save energy" (to the extent that this is feasible) sound
like it gains more and more for the attacker. The reality, however, is
that energy is just another budget item for the attacker---maybe just
another type of hardware investment, such as solar cells and batteries.
If energy is a big part of the total budget then the attacker will look
at ways to reduce it (see https://blog.cr.yp.to/20230609-turboboost.html
for some numbers), but the attacker _won't_ be trying to push it as
close to 0 as possible---that would get less and less done in the same
amount of time for the same total investment in attack hardware. Saving
the environment probably isn't a high priority for the attacker.
One can object to the appearance of wires in the above rationale:
switching to free-space lasers might seem to communicate across distance
d _without_ the attacker having to pay for d units of intermediate
hardware. But, oops, free-space lasers spread out over distance. Of
course, there are more technologies to consider, and there's a long
history of inadequate security margins being broken by technological
advances even when those are "just" advances in normal circuit design.
A better-documented objection is that the corner of the cryptanalytic
literature paying attention to communication costs usually succeeds in
optimizing attack _algorithms_ to drastically reduce those costs. The
details and results depend on the attack. Three pre-quantum examples:
* Sorting: Heapsort has "operation" exponent 1+o(1) but much worse
area-time exponent. Mesh sort (e.g., Schnorr--Shamir or Schimmler)
reduces the area-time exponent to 1.5+o(1).
* Discrete logs: Baby-step-giant-step has "operation" exponent
0.5+o(1) but much worse area-time exponent. Pollard's rho method
reduces the area-time exponent to 0.5+o(1).
* Factorization: Traditional NFS (or TWINKLE) has "operation"
exponent 1.901...+o(1) but much worse area-time exponent.
https://cr.yp.to/papers.html#nfscircuit reduces the area-time
exponent to 1.975...+o(1).
The "operation"-vs.-area-time change in exponent ended up as 50%, 0%,
and 4% in these examples. Discrete logs and factorization ended up with
much smaller penalties than the sorting subroutine because the attacks
were modified to communicate less. In each case, it would be a serious
mistake to simply use an attack algorithm optimized for "operations".
---D. J. Bernstein
Daniel Apon
A gentle technical quibble:
The linked paper https://maths-people.anu.edu.au/~brent/pd/rpb055.pdf cites earlier work C.D. Thompson 1979: https://dl.acm.org/doi/pdf/10.1145/800135.804401.
C.D. Thompson defines the VLSI model of complexity theory (Section 2.; page 3, left column, paragraph "Words.") as having words of $\lceil log N \rceil$ bits.
But when I go back to (say) https://blog.cr.yp.to/20231023-clumping.html, I see discussion of (correct me if I'm way off..) extracting 5 bits from a table.
I don't think 5-bit tables reasonably constitute a word in C.D. Thompson's model.
---
Moreover, this isn't just a technicality. It really has impacts in modern cryptography. For example, see the modern ORAM (Oblivious RAM literature), where massaging word-sizes can greatly influence what is possible "asymptotically."
Dan, is it possible for you to clarify this point (without me digging deeper on my own time)?
D. J. Bernstein
> Dan, is it possible for you to clarify this point (without me digging
> deeper on my own time)?
clarification of, and identify the point that you don't find clear?
---D. J. Bernstein
D. J. Bernstein
> Using the best current algorithms and commercial CPUs, FPGAs, and
> ASIC processes. How many billion dollars would it cost (CAPEX, OPEX)
> and how many million years would it take today to recover a single
> ML-KEM-512 decapsulation key?
> ML-KEM-512+Curve25519?
is Bitcoin, which did roughly 2^111 bit operations last year. That's the
equivalent of a few billion dollars of mass-market Bitcoin-mining
machines running for a year. A large-scale attacker will be able to
reach similar economies of scale and has a much larger yearly budget.
Recovering an AES-128 key, out of a billion target keys encrypting a
known plaintext, takes roughly that number of bit operations, so it's
feasible for a large-scale attacker.
(The attacker obviously won't use commercial CPUs or FPGAs for such a
large computation. See the five-order-of-magnitude gap analyzed in
https://cat.cr.yp.to/cryptattacktester-20231020.pdf#subsection.F.11.)
Recovering a Curve25519 key, out of any number of target keys, takes
about 2^145 bit operations: i.e., billions of times more difficult. This
_does not_ mean that an attacker with billions of dollars to spend won't
be able to break Curve25519 for billions of years: computer technology
is continuing to become more and more cost-effective, and I wouldn't bet
against this giving another 2^30 within the foreseeable future. But
quantum computers look like they'll easily win this race.
(One can always find optimists claiming that chip improvement has come
to an end and that quantum computing will fail. However, risk management
requires looking at the bad scenarios. This is why we're working on
post-quantum cryptography _before_ seeing demonstrations of anything
useful being accomplished by quantum computers.)
For Kyber-512, the latest Kyber documentation had a security analysis
from 2020 ending up with a very wide uncertainty range for the costs of
high-probability single-target "primal" attacks: between 2^135 and 2^165
bit operations, not counting costs of memory access. Optimists then say
that
* there won't be improved single-target attack algorithms,
* multi-target attacks won't do better than single-target attacks,
* attacks against Kyber won't do better than these MLWE/MLWR attacks,
* the costs of memory access will add a lot to the 135, and
* 135, as the low end, has negligible chance of occurring anyway.
However:
* There are already undisputed improvements (plus some disputed
improvements), the easiest being clumping, which by itself moves
the entire [135,165] range down by nearly 10 bits. The issue here
isn't simply that the range for known attacks needs to be updated;
the big issue is that lattice attacks are complicated and haven't
stabilized. This needs to be factored into risk analyses.
* There's an ACM CCS 2021 paper briefly outlining a proof that
one-out-of-many attacks for MLWE are as hard as single-target
attacks, but the proof has a flaw pointed out and exploited in
https://cr.yp.to/papers.html#lprrr. The main analysis in the latter
paper is asymptotic; quantifying the concrete impact on Kyber-512
will take more research. This is also something where better
attacks should be expected---within limits, since a 2^40-target
attack can't drop security levels by more than 40 bits, but those
limits aren't comforting for Kyber-512.
* Even if QROM IND-CCA2 security is assumed to cover all IND-CCA2
attacks (which isn't necessarily the case, as discussions of a
recent NSA proposal illustrate), current proofs don't rule out the
possibility of Kyber's QROM IND-CCA2 security being much easier to
break than the underlying MLWE/MLWR problems. The Kyber security
analysis relies on hope that this proof gap doesn't matter, rather
than on cryptanalysis.
* The only quantified claim regarding the costs of memory access in
Kyber-512 attacks comes from NIST incorrectly multiplying the cost
of each memory access by the number of bit operations in an attack.
A correct analysis instead multiplies the cost of each memory
access by the number of memory accesses (a number that doesn't
appear in NIST's analysis), and searches for attacks optimizing the
total cost. This is something else where more research is required.
* I'm not aware of attempts to quantify probabilities for the
components of the uncertainty range in the Kyber documentation, so
there's no way to derive a quantitative conclusion regarding the
probability of the low end occurring---never mind the question of
whether a 25% or 10% or 5% chance of disaster is acceptable.
Some of the alarm bells going off here are already recognized in NIST's
general statements regarding procedures. For example, NIST said that
breaking a single AES-128 key (this is closer to the Curve25519 example
than to the one-out-of-a-billion-AES-128-keys example) is a "floor" for
security, said that a replacement for gate counts "must at minimum"
ensure (among other things) that "all known attacks have been optimized
with respect to the proposed metric", and said that "submitters of
algorithms where the complexity of the best known attack has recently
decreased significantly, or is otherwise poorly understood, should be
especially conservative" in "category" assignments.
> * One of my collogues spent time doing complexity calculations. My
> PQC forum out of fear of being publicly labeled as stupid. Do you
> understand that your aggressive personal attacks are severely limiting
> the open scientific discussion, especially for young researchers?
but are scared to comment given that I'm the victim of frequent personal
attacks. This description might sound like what you're saying with roles
reversed---but people who look for the supporting evidence find that I'm
criticizing _government_ actions, while various replies are using
personal attacks to avoid responding to the content. NIST benefits from
the attacks and doesn't take any real action to bring the attacks under
control; readers who are interested in the thread topic---Kyber's
security level---have to wade through more and more off-topic material.
> * How can someone who is so often talking about openness and
> opposite of that but also clearly a cybersecurity risk?
times in https://nist.pqcrypto.org/foia/index.html talking about
openness and transparency, and which is heavily involved in ISO? This
understanding of "someone" would require erroneously conflating people
with organizations, but that line seems to have been crossed already.
> * Do you understand that your unfounded claims that the NSA is
> the narrative of Russia and China?
should be transparently and verifiably following clear public rules so
that we don't need to worry about their motivations.
---D. J. Bernstein
Daniel Apon
--
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/20231101153327.1303015.qmail%40cr.yp.to.
D. J. Bernstein
> > > deeper on my own time)?
> > Sorry, can you please quote the specific text that you're asking for
> > clarification of, and identify the point that you don't find clear?
Citing a blog post isn't quoting the specific text that you're claiming
is unclear, nor is it pinpointing what's allegedly unclear about that
text. I also have no idea how your "technical quibble" is supposed to be
disputing anything that I wrote. If you have a question or comment about
something specific I wrote, please quote it and identify the issue.
---D. J. Bernstein
Brent Kimberley
Year one:
New rig:
50 watts yields +200 Tops, an effective workload of 100 x 10^12 ops, 2^46.5 ops.
An availability of one nine. i.e., 328.72 days, 28.4 E+6 sec or 2^24.76 seconds.
Rounding up, the system yields 2^71.2 ops.
Year two:
Previous:
2^71.2 ops.
New rig:
+50 watts yields +288 Tops, an effective workload of 144 x 10^12 ops, 2^47 ops.
An availability of one nine. i.e. 328.72 days, 28.4 E+6 sec or 2^24.76 seconds.
Rounding up, the system yields 2^71.7 ops in year one.
Combined:
2^71 (2^.2+2^.7) = 2^72.4 ops
Year Three:
Previous:
2^72.4 ops
New rig:
2^72.2 ops.
Combined:
2^72 (2^.4+2^.2) = 2^73.3 ops
And so on...
Assume the operational life of a rig is no more than six years.
According to Shor's law, RSA-2048 has a bit strength of ~ 56 bits. (112bits /2 = 56 bits)
We believe we can do better.
Now, let's make the outrageous claim that we can complete SQA in one op. (I can't.)
Year one
71.2 - 56 = 2^15.2
Keys discovered: 2^15.2 RSA-2048 keys
Total sunk cost $4k
The total sunk cost per key is $9.40
Year two
72.4 -56 = 16.4
Keys discovered: 2^16.4 RSA-2048 keys
Total sunk cost $8k
The total lifetime sunk cost per key is $10.81 per key
Year three
73.3 - 56 = 13.3
Keys discovered: 2^17.3 RSA-2048 keys
Total sunk cost $12k
The total lifetime sunk cost per key is $13.45 per key.
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.
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.
Jim Goodman
I think you've got your cost calculations inverted as you're computing:
metric = <# of keys> / <cost>
which gives you keys per dollar not dollars per key. So your numbers
would end up being:
Year One: 9.40 keys per dollar (10.62 cents per key)
Year Two: 10.81 keys per dollar ( 9.25 cents per key)
Year Three: 13.45 keys per dollar ( 7.43 cents per key)
Take care.
Jim
Brent Kimberley
-----Original Message-----
From: Jim Goodman <ji...@crypto4a.com>
Sent: Friday, November 3, 2023 8:29 AM
To: Brent Kimberley <Brent.K...@Durham.ca>; 'D. J. Bernstein' <d...@cr.yp.to>; pqc-...@list.nist.gov
Subject: RE: [pqc-forum] Re: energy consumption and attack cost
> .cr.yp.to%2F20231023-clumping.html&data=05%7C01%7CBrent.Kimberley%40du
> rham.ca%7C74b25790598643d3fa7808dbdc686dd9%7C52d7c9c2d54941b69b1f9da19
> 8dc3f16%7C0%7C0%7C638346113299352830%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiM
> C4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C
> %7C&sdata=uYQvDZg55%2BT3nNUYxaFgzRVrTbbYqsMV5TUMX6BVAsY%3D&reserved=0
D. J. Bernstein
approximately 40 bits of additional security quoted as the 'real cost of
and (2) not what the NTRU Prime documentation says.
(A correct calculation of the total cost of memory access and bit
operations in an attack is as follows: multiply the number of memory
accesses by the average cost of each memory access, and then add the
total cost of the bit operations. NIST is instead multiplying the "real
cost of memory access" by cost in "the RAM model", and in particular by
the number of bit operations; that's wrong.)
In email dated 13 Oct 2023 01:34:24 +0200, I asked "Where does NIST
claim the NTRU Prime submission says what this text attributes to the
submission? Full quote, please."
In email dated 13 Oct 2023 19:24:04 +0000, NIST quoted the following
two sentences from the NTRU Prime submission: "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."
In this message, I'll go step by step through what this quote says, and
compare that to NIST's misrepresentations of what the quote says. I
request that NIST promptly issue appropriate errata.
1. The definition of o(β)
The first important point to understand is that saying o(β) is _not_
saying 0. It doesn't _exclude_ 0, but it's rarely 0, and it's rarely in
any particular range around 0.
o(β) is standard mathematical notation for any sublinear function of β;
i.e., any f(β) such that the ratio f(β)/β converges to 0; i.e., any f(β)
such that |f(β)/β| is below 0.1 for all large enough β, and |f(β)/β| is
below 0.01 for all large enough β, and so on.
sqrt(β) is an example of o(β). Obviously it isn't 0 (assuming β > 0).
1000 sqrt(β) is another example of o(β). This isn't 0. It's much bigger
than β when β is small, and stays bigger than β until β reaches 1000000.
1000 β/log(β) is another example of o(β). This isn't 0. It stays bigger
than β until β reaches exp(1000).
-1000 β/log(β) is another example of o(β); note the minus sign here.
There's no requirement of o(β) being nonnegative.
The o() notation was introduced more than 100 years ago---
https://archive.org/details/handbuchderlehre01landuoft/page/60/mode/2up
---and is used pervasively in many areas of mathematics and computer
science. Saying that an algorithm has been sped up from N^(2+o(1))
operations to N^(1+o(1)) operations---here o(1) means something that
converges to 0 as N increases---is often much easier than figuring out
more precise formulas (e.g., 2N^2 vs. N log N or N exp(sqrt(log N)) or
something even more complicated). The disadvantage of this simplicity is
that this doesn't say what the speedup is for any particular N. There
can even be a slowdown! AKS sorting uses N (log N)^(1+o(1)) comparisons
while Batcher sorting uses N (log N)^(2+o(1)) comparisons, but a closer
look shows that Batcher beats AKS for every reachable value of N.
Page 66 of the NTRU Prime documentation reiterates the definition of
o(β) and includes the following warning: "Readers often think---or
hope---that o(β) can be ignored, i.e., replaced with 0. However,
ignoring o() in asymptotics can lead to misstating security levels by an
unlimited number of bits: e.g., claiming 2^100 'operations' or 2^300
'operations' for an attack that actually uses 2^200 'operations'."
2. NIST's misrepresentations of o(β)
No matter what value of β NIST has in mind, it's wrong for NIST to leap
from 0.1037...β+o(β) to 40, or to "approximately 40", or to "somewhere
in the ballpark of 40".
The issue here isn't the level of precision of "approximately" or
"somewhere in the ballpark of". Imagine, for example, that
* NIST's "ballpark" concept is so big as to mean "between 10 and 70"
(never mind the question of what this does to NIST's conclusions
about the Kyber-512 security level) and
* NIST is claiming that 0.1037...β+o(β) is in this "ballpark",
between 10 and 70, for, say, β = 406.
This claim is false if, e.g., the o(β) is -0.5 β/log(β). There's nothing
in this o(β) quote ruling out that possibility. Ergo, it's wrong for
NIST to attribute a between-10-and-70 conclusion to this quote.
Right after giving the o(β) quote, NIST made exactly this mistake:
> 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.
In fact, contrary to NIST's claim here, the o(β) quote neither says nor
implies anything "in the ballpark of 2^40"---no matter how the
"ballpark" is quantified. (As for "multiplied, not added", see below.)
Beyond that, NIST didn't _explicitly_ claim that the o(β) quote was
answering my request for a full quote backing up NIST's "approximately
* NIST gave the o(β) quote shortly after I had issued the request,
and I think that the most obvious interpretation is that NIST was
giving the o(β) quote as an (alleged) answer to that request.
* NIST didn't answer when I asked for clarification on this point
(email dated 14 Oct 2023 21:01:54 +0200). NIST also didn't answer
when I said that stonewalling can't be allowed to stop security
review and said that if NIST didn't clarify one way or the other
then I would respond assuming this interpretation (email dated 24
Oct 2023 00:14:21 +0200).
So, for this message, I'll assume that NIST is claiming that the o(β)
quote says what NIST attributed to the NTRU Prime submission when NIST
wrote "40 bits of security more than would be suggested by the RAM model
That claim is false. NIST is leaping from 0.1037...β+o(β) and some
unspecified value of β to some unquantified "approximately 40" range. No
matter what the value of β is, and no matter what the range is,
0.1037...β+o(β) does not justify that conclusion, and it's wrong for
NIST to attribute this conclusion to this o(β) quote. This is the same
mathematical error by NIST once again.
(Another way that NIST is misrepresenting its claimed source---the "RAM
model" part---is covered below.)
As a side note, how can NIST say that this 40 was "quoted as the 'real
cost of memory access' by the NTRUprime submission", and then point to
NTRU Prime text that doesn't say 40 and doesn't contain the exact words
"real cost of memory access"? What NIST wrote in the first place was
indicating, falsely, that NIST was simply copying from the original NTRU
Prime submission. The issue here is separate from NIST's mathematical
error; even if NIST (incorrectly) believes that the original statement
_implies_ NIST's conclusions, why is NIST claiming that the original
source _stated_ those conclusions?
As another side note, NIST's original "40 bits of security more than
would be suggested by the RAM model" text was accompanied by NIST
writing "For NTRUprime's estimates see section 6.11 of
https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf"---but the o(β)
quote wasn't in Section 6.11! Is NIST ever going to give a straight
answer to the simple question of where it obtained the 40 in the first
place? (Section 6.11 also doesn't say 40, and doesn't say "real cost of
memory access".)
3. The cost of sieving
2015 Becker--Ducas--Gama--Laarhoven obtains a "heuristic time complexity
for solving SVP in dimension n of (3/2)^(n/2+o(n)) ≈ 2^(0.292n+o(n))". I
won't keep repeating the word "heuristic"; all of the attack costs here
rely on heuristics.
Typical attacks against Kyber etc. involve 2^(o(β)) calls to SVP in
dimension β. Each call takes "time" 2^(0.2924...β+o(β)), so the total
attack "time" is also 2^(0.2924...β+o(β)). Various post-2015 speedups
(e.g., "dimensions for free") save 2^(o(β)) factors, again producing
overall "time" 2^(0.2924...β+o(β)).
The previous paragraph relies on the lemma that the sum of sublinear
functions is sublinear: if f(β) is sublinear and g(β) is sublinear then
f(β)+g(β) is also sublinear. In short, o(β)+o(β) is also o(β). So
multiplying 2^(0.2924...β+o(β)) by 2^(o(β)) gives 2^(0.2924...β+o(β)).
Similarly, dividing that by 2^(o(β)) gives 2^(0.2924...β+o(β)).
These "time" calculations are considering bit operations while ignoring
the costs of memory access. Now let's switch over to accounting for the
costs of memory access using the following estimate from the NTRU Prime
documentation: accessing a bit within an N-bit array has the same cost
as sqrt(N)/2^5 bit operations. Specifically, let's consider the
following attack features:
* T = attack "time" (number of bit operations, ignoring memory access);
* M = number of memory accesses in the attack;
* N = number of bits of memory being accessed.
In the NTRU Prime metric, the cost of each memory access is sqrt(N)/2^5,
so the total cost of all memory accesses is M*sqrt(N)/2^5, so the total
cost of the algorithm is T+M*sqrt(N)/2^5. (For algorithms using multiple
arrays, the total cost is T+M_1*sqrt(N_1)/2^5+M_2*sqrt(N_2)/2^5+...)
For the 2015 algorithm,
* T is 2^(0.2924...β+o(β));
* M is also 2^(0.2924...β+o(β)); and
* N is 2^(0.2075...β+o(β)).
Then sqrt(N) is 2^(0.1037...β+o(β)), so sqrt(N)/2^5 is also
2^(0.1037...β+o(β)), so M*sqrt(N)/2^5 is 2^(0.396...β+o(β)), so
T+M*sqrt(N)/2^5 is also 2^(0.396...β+o(β)).
Notice that, compared to the T cost ignoring memory accesses,
T+M*sqrt(N)/2^5 is larger by a factor 2^(0.1037...β+o(β)).
The NTRU Prime submission correctly summarizes this as follows: "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."
4. NIST's miscalculation of the cost
When NIST multiplies costs in "the RAM model" (i.e., T+M) by the "real
cost of memory access" (in the NTRU Prime metric), NIST is computing an
indefensible
(T+M)*sqrt(N)/2^5
instead of the correct
T+M*sqrt(N)/2^5.
In other words, instead of correctly computing the total cost of memory
access in an attack as the number of accesses times the (average) cost
of each access, NIST is inflating this to the number of _bit operations_
in the attack times the cost of each access.
In the common situation of T/M being far above 1 but below sqrt(N)/2^5,
NIST's miscalculation is inflating costs by a factor very close to T/M,
which can be thousands or millions or billions, depending on the attack
variant in question.
What does this do to the o(β) formulas? For the 2015 attack, nothing!
NIST's inflation factor for that attack is subexponential: it adds
something sublinear to the exponent. At the level of detail of the o(β)
quote, it is impossible to see this difference.
Specifically, remember that T is 2^(0.2924...β+o(β)) and that M is also
2^(0.2924...β+o(β)), so T+M is 2^(0.2924...β+o(β)), so NIST's
miscalculation gives 2^(0.396...β+o(β)), which is larger than T by a
factor 2^(0.1037...β+o(β)).
The o(β) quote from the NTRU Prime documentation is thus consistent with
NIST's miscalculation. But the o(β) quote is also consistent with (and
in fact comes from) the correct calculation. So NIST is simply wrong in
claiming that the o(β) quote states NIST's calculation.
Saying that T/M is only 2^(o(β)) for this attack doesn't mean that T
equals M: subexponential factors can be critical. It also doesn't mean
that T/M is 2^(o(β)) for all attacks; "enumeration" is a counterexample.
More broadly, it's terribly dangerous to be drawing conclusions about
how small T+M*sqrt(N)/2^5 can be when there haven't been serious efforts
to optimize attacks for that metric. One of the things that I find
baffling about NIST's appeal to the NTRU Prime documentation is that the
NTRU Prime documentation prominently warns readers about the instability
of lattice attacks, whereas NIST suppresses these warnings and draws
comforting conclusions about Kyber-512. But the more basic point here is
that NIST is miscalculating memory-access costs---and misattributing
Daniel Apon
You wrote:
"Citing a blog post isn't quoting the specific text that you're claiming is unclear"
--Daniel
D. J. Bernstein
> You wrote:
> "Citing a blog post isn't quoting the specific text that you're claiming is
> unclear"
text from me that you're claiming is unclear. You also claimed to have a
"technical quibble"; please quote the specific text from me that you're
claiming is inaccurate. Thanks in advance.
---D. J. Bernstein
Brent Kimberley
It will be interesting to see what architectures are popular in 2035 when RSA is retired.
-----Original Message-----
From: Brent Kimberley
Sent: Friday, November 3, 2023 8:06 AM
To: D. J. Bernstein <d...@cr.yp.to>; pqc-...@list.nist.gov
Brent Kimberley
Daniel Apon
The blog post writes
"As a small example, say we want to add 7 bits a,b,c,d,e,f,g. Instead of spending 20 "gates" on bit operations as above, we can spend just 1 "gate" on a table lookup indexed by (a,b,c,d,e,f,g). The table has 27 entries, each with a 3-bit output."
The blog post writes
"For example, let's say we take a table of size 262, mapping two 31-bit inputs to the 5-bit sum of bits of the xor of the inputs. This is what I'm calling "31-bit clumping"."
The values that are being retrieved via the approach in your blog post are, apparently, "5-bit sum"s. However, C.D. Thompson's model (https://dl.acm.org/doi/pdf/10.1145/800135.804401) allows for "The basic chunk of information considered in this paper is a word of \ceil{log N} bits."
Are you sure that you haven't mis-calculated (compared apples to oranges) when your approach appears to be retrieving 5 bits from tables of size 2^{50} and 2^{62}?
In C.D. Thompson's model, I ought to be able to retrieve (say) 62 bits at once from a 2x 31-bit look-up -- or even 7 bits from a table of size 2^7 (not 3).
The block sizes ("The basic chunk of information" a la C.D. Thompson) don't match in size. It may be very easy to plug in differing block sizes for input index-queries and output bits retrieved, then substitute this ratio into someone else's calculation (e.g. the Kyber specification document) derived in a different manner, and then manipulate a final number by a few dozens in the exponent.
I'm not going to spend the time to work through and fix this technical glitch for you... But if you clearly know the answer, then that's okay -- great by me even -- and it's really not a big deal (i.e. a "gentle technical quibble"); I would love to learn the answer.
Complicated ideas have fallen apart by smaller problems than this though, so it's not unwarranted to dig into the weeds here.
And on a related point: Part of the reason for hosting this conversation through established scientific processes (like blind peer review) is to intentionally 'crowd-source' the answer to the broader research community. I still believe that is the best approach to resolve these many questions.
Daniel Apon
To be conservative for security analysis, you should give the hypothetical attacker every advantage possible.
In this case, small output-retrievals against AES may mis-calculate the correct "gate cost" of breaking various AES levels, and result in a chaotic relative security scoring.