13 ms·
Debunking NIST's calculation of the Kyber-512 security level
- deleted 3y ago[deleted]
- nmitchko 3y agoUnfortunately, the NSA & NIST most likely is recommending a quantum-proof security that they've developed cryptanalysis against, either through high q-bit proprietary technology or specialized de-latticing algorithms . The NSA is very good at math, so I'm be thoroughly surprised if this analysis was error by mistake rather than error through intent.
- deleted 3y ago[deleted]
- jrochkind1 3y agoThe NSA also has a mission-based interest in _breaking_ other people's crypto though, which is generally known. Which is generally known, so I'm surprised by your argument. Even if the NSA knows more than they are telling us, this doesn't result in most of us feeling less worried, as their ends may not be strengthening the public's cryptography!
- yung-africas 3y ago[flagged]
- rideontime 3y agowhat do you have against dodo birds
- garba_dlm 3y agoI just find it sad that it's things like these that make it impossible for the layman to figure out what is going on with, for example, Mochizuki's new stuff I have no reason to doubt that a lot of math has been made more difficult than necessary just because it is known to give a subtle military advantage in some cases, but this isn't new;
- cosmojg 3y agoIsn't that what the person you're replying to said?
- jrochkind1 3y agoIt's clear to me now that it is! Either I misread it, or maybe they edited it to make it more clear!
- aaomidi 3y agoYes: https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG Also, we still to this day do not know where the seed for P256 and P384 came from. And we're using that everywhere. There is a non-zero chance that the NSA basically has a backdoor for all NIST ECC curves, and no one actually seems to care.
- sweis 3y agoNIST P-256 curve seed came from the X9.62 specification drafted in 1997. It was provided by an NSA employee, Jerry Solinas, as an example seed among many other seeds, including those provided by Certicom. Read this for more details: https://eprint.iacr.org/2015/1018 https://eprint.iacr.org/2015/1018
- brohee 3y agoOr you find it somewhat credible but still use them because fending off the NSA is not something you want to spend energy on, and you are confident in the fact that NSA think no one else can find the backdoor.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- tptacek 3y ago"Specialized de-latticing algorithms"?
- sweis 3y ago"High q-bit proprietary technology" and "specialized de-latticing algorithms" are made up terms that nobody uses.
- tptacek 3y agoI'm stuck on trying to work out what it would mean to de-lattice something. Would that transform a lattice basis into a standard vector space basis in R or something, or, like MOV, would it send the whole lattice to an element of some prime extension field? In my mind's eye, it's cooler: it's like, you render the ciphertext as a raster image, and then "de-lattice" it to reveal the underlying plaintext, scanline by scanline.
- garba_dlm 3y agoi'm still working on understanding lattices better but i can imagine, based on my own ignorance, creativity, and lack of correct understanding, would be some kind of factorization. as I think while trying to better know what's a lattice, I imagine a lattice like a coordinate pair, but instead of each coordinate existing on a line, they exist on a binary tree (or some other directed graph explored from a root outwards without cycles) which means you have two such binary-trees (not necessarily binary, but it's just easier to work with them seemingly) and then you combine these into ONE lattice. so then, to de-lattice means to recover the binary trees. but when I say binary tree I'm thinking about rational numbers (because stern broccott trees)
- tptacek 3y agoA lattice is like a vector space, but with exclusively integer coefficients. It's not a coordinate pair. If you think of vectors as coordinate pairs, a vector space is a (possibly unbounded) set of coordinate pairs. If you haven't done any linear algebra, a decent intuition would be mathematical objects like "the even numbers" or "the odd numbers", but substituting vectors (fixed-sized tuples of numbers) for scalars.
- deleted 3y ago
- bsder 3y ago> through high q-bit proprietary technology Somebody would leak or steal that as it would be a GIGANTIC leap forward in our engineering skill at the quantum level. Getting more than a handful of qubits to stay coherent and not collapse into noise is a huge research problem right now, and progress has been practically non-existent for almost a decade.
- perihelions 3y agoRelated thread from last year, with 443 comments: https://news.ycombinator.com/item?id=32360533 https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
- jeffrallen 3y agoSomething I've learned from a career of watching cryptographer flame wars: Don't bet against Bernstein, and don't trust NIST.
- nonrandomstring 3y agoLove the narrative style of this writing second-guessing the erroneous thought processes. Are they deceptive? Who knows. What worries me is that it's neither malice nor incompetence, but that a new darker force has entered our world even at those tables with the highest stakes.... dispassion and indifference. It's hard to get good people these days. A lot of people stopped caring. Even amongst the young and eager. Whether it's climate change, the world economic situation, declining education, post pandemic brain-fog, defeat in the face of AI, chemicals in the water.... everywhere I sense a shrug of slacking off, lying low, soft quitting, and generally fewer fucks are given all round. Maybe that's just my own fatigue, but in security we have to vigilant all the time and there's only so much energy humans can bring to that. That's why I worry that we will lose against AI. Not because it's smarter, but because it doesn't have to _care_, whereas we do.
- r3trohack3r 3y agoBad systems beat good people. There are a lot of symptoms to distract yourself with. Focus on the game instead. A society full of good people will sort out the rest.
- bdamm 3y agoThis apathy is an interesting phenomenon, let's not ignore it. The Internet has brought us a wealth of knowledge but it has also shown us how truly chaotic the world really is. And negativity is a profitable way to drive engagement, so damn near everyone can see how problematic our society is. And when the algorithm finds something you care to be sad about, it will show you more, more, and ever more all the way into depression. This is the lasting legacy of the Internet, now. Not freedom for all to seek and learn, but freedom for the negativity engines to seek out your brain and suck you into personal obliteration. A society of good people? Nobody really cares any more. And I do agree with the gp; if you look, you can see it everywhere. What is this going to become? Collective helplessness as we eek out what little bits of personal fulfillment we can get in between endless tragedy and tantalizing promise?
- 3y ago
- fefe23 3y agoIf you have never heard of Bernstein, this may look like mad ramblings of a proto-Unabomber railing against THE MAN trying to oppress us. However, this man is one of the foremost cryptographers in the world, he has basically single-handedly killed US government crypto export restrictions back in the days, and (not least of all because of Snowden) we know that the NSA really is trying to sabotage cryptography. Also, he basically founded the field of post-quantum cryptography. Is NIST trying to derail his work by standardizing crappy algorithms with the help of the NSA? Who knows. But to me it does smell like that. Bernstein has a history of being right, and NIST and the NSA have a history of sabotaging cryptographic standards (google Dual_EC_DRBG if you don't know the story).
- ignoramous 3y agoAn interesting set of comments (by tptacek) from a thread in 2022 (I wonder if they still hold the same opinion in light of this latest post on NIST-PQC by djb): > The point isn't that NIST is trustworthy. The point is that the PQC finalist teams are comprised of academic cryptographers from around the world with unimpeachable reputations, and it's ludicrous to suggest that NSA could have compromised them. The whole point of the competition structure is that you don't simply have to trust NIST; the competitors (and cryptographers who aren't even entrants in the contest) are peer reviewing each other, and NIST is refereeing. > What Bernstein is counting on here is that his cheering section doesn't know the names of any cryptographers besides "djb", Bruce Schneier, and maybe, just maybe, Joan Daemen. If they knew anything about who the PQC team members were, they'd shoot milk out their nose at the suggestion that NSA had suborned backdoors from them. What's upsetting is that he knows this, and he knows you don't know this, and he's exploiting that. --- > I spent almost 2 decades as a Daniel Bernstein ultra-fan --- he's a hometown hero, and also someone whose work was extremely important to me professionally in the 1990s, and, to me at least, he has always been kind and cheerful... I know what it's like to be in the situation of (a) deeply admiring Bernstein and (b) only really paying attention to one cryptographer in the world (Bernstein). > But talk to a bunch of other cryptographers --- and, also, learn about the work a lot of other cryptographers are doing --- and you're going to hear stories. I'm not going to say Bernstein has a bad reputation; for one thing, I'm not qualified to say that, and for another I don't think "bad" is the right word. So I'll put it this way: Bernstein has a fucked up reputation in his field. I am not at all happy to say that, but it's true. --- > What's annoying is that [Bernstein is] usually right, and sometimes even right in important new ways. But he runs the ball way past the end zone. Almost everybody in the field agrees with the core things he's saying, but almost nobody wants to get on board with his wild-eyed theories of how the suboptimal status quo is actually a product of the Lizard People. (https://news.ycombinator.com/item?id=32365259 https://news.ycombinator.com/item?id=32365259, https://news.ycombinator.com/item?id=32368598 https://news.ycombinator.com/item?id=32368598, https://news.ycombinator.com/item?id=32365679 https://news.ycombinator.com/item?id=32365679)
- codeflo 3y agoThat's more of a diary than an article -- jargony, disorganized, running in circles, very hard to follow. But the information might be important regardless. There's a strong implication that NIST with help of the NSA intentionally standardized on a weak algorithm. We all know that's possible. But can someone who follows some of this stuff more closely explain what the play would be? I always assumed that weakening public cryptography in such a way is a risky bet, because you can't be sure that an attacker doesn't independently find out what you know. You can keep a secret backdoor key (that was the accusation when they released Dual_EC_DRBG), but you can't really hide mathematical results. Why would they be willing to risk that here?
- aaomidi 3y ago> Why would they be willing to risk that here? Certain types of attacks basically make it so you need to have a specific private key to act as a backdoor. That's the current guess on what may be happening with the NIST ECC curves. If so, this can be effectively a US-only backdoor for a long, long time.
- tptacek 3y agoI don't believe that is anybody's guess on what may be happening with the NIST ECC curves. Ordinarily, when people on HN say things like this, they're confusing Dual EC, a public key random number generator, known to be backdoored, with the NIST curve standards.
- aaomidi 3y agoYeah I've noticed people mixing them up. They happened around the same time, so I can excuse it a bit. The problem with the NIST ECC curves are that we still do not know where the heck that seed came from and why that seed specifically.
- tptacek 3y agoSee Koblitz and Menenzes: https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf
- neonate 3y agohttp://web.archive.org/web/20231003195013/https://blog.cr.yp.to/20231003-countcorrectly.html http://web.archive.org/web/20231003195013/https://blog.cr.yp... https://archive.ph/NrOG6 https://archive.ph/NrOG6
- jcranmer 3y agoNotwithstanding DJB's importance to cryptography, and the fact that I'm ignorant of a large number of details here, there was a point where he lost a lot of credibility with me. Specifically, when he gets to the graphs, he says "NIST chose to deemphasize the bandwidth graph by using thinner red bars for it." That is just not proven by his evidence, and there is a very plausible explanation for it. The graph that has the thinner bars is a bar chart that has more data points than the other graph. Open up your favorite charting application, and observe the difference in a graph that has 12 data points versus one with 9... of course the one with 12 data points has thinner lines! At this point, it feels quite strongly to me that he is trying to interpret every action in the most malicious way possible. In the next bullet point, he complains that they're not using a log scale for the graph... where everything is in the same order of magnitude. That doesn't sound like a good use case for log scale, and I'm having a hard time trying to figure out why it might be justified in this case. Knowing that DJB was involved in NTRU, it's a little hard to shake the feeling that a lot of this is DJB just being salty about losing the competition.
- aaomidi 3y ago> Knowing that DJB was involved in NTRU, it's a little hard to shake the feeling that a lot of this is DJB just being salty about losing the competition. There isn't a lot of people in the world with the technical know-how for cryptography. It's clear that competitors in this space are going to be reviewing eachothers work.
- ziddoap 3y ago>At this point, it feels quite strongly to me that he is trying to interpret every action in the most malicious way possible. Given the long and detailed history of various governments and government agencies purposefully attempting to limit the public from accessing strong cryptography, I tend to agree with the "assume malice by default" approach here. Assuming anything else, to me at least, seems pretty naive.
- tptacek 3y agoAn important detail you really want to understand before reading this is that NIST (and NSA) didn't come up with these algorithms; they refereed a competition, in which most of the analysis was done by competitors and other academics. The Kyber team was Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, and also Peter Schwabe, a collaborator of Bernstein's.
- wnevets 3y agoCorrect me if I'm wrong, everything is also being done out in the open for everyone to see. The NIST aren't using some secret analysis to make any recommendations.
- tptacek 3y agoYou don't really know, but you can be reasonably sure that they didn't sabotage the submissions themselves.
- pclmulqdq 3y agoThere is a final standardization step where NIST selects constants, and this is done without always consulting with the research team. Presumably, these are usually random, but the ones chosen for the Dual-EC DRBG algorithm seem to have been compromised. SHA-3 also had some suspicious constants/padding, but that wasn't shown to be vulnerable yet.
- tptacek 3y agoThe problem with Dual EC isn't the sketchy "constants", but rather the structure of the construction, which is a random number generator that works by doing a public key transformation on its state. Imagine CTR-DRBG, but standardized with a constant AES key. You don't so much wonder about the provenance of the key so much as wonder why the fuck there's a key there at all. I don't know of any cryptographer or cryptography engineer that takes the SHA3 innuendo seriously. Do you? Additional backstory that might be helpful here: about 10 years ago, Bernstein invested a pretty significant amount of time on a research project designed to illustrate that "nothing up my sleeves" numbers, like constants formed from digits of pi, e, etc, could be used to backdoor standards. When we're talking about people's ability to cast doubt on standards, we should keep in mind that the paragon of that idea believes it to be true of pi. I'm fine with that, for what it's worth. Cryptography standards are a force for evil. You can just reject the whole enterprise of standardizing cryptography of any sort, and instead work directly from reference designs from cryptographers. That's more or less how Chapoly came to be, though it's standardized now.
- greggsy 3y agoIt would be interesting to see Signal Sciences response to this Bernstein’s post
- barsonme 3y agoWho is Signal Sciences?
- greggsy 3y agoActually, I meant Open Whisper, the company behind Signal. Got my wires crossed.
- ignoramous 3y agonit: Open Whisper Systems (who built WhisperCore, an encryption layer; WhisperMonitor, a firewall; TextSecure, a messenger; and RedPhone, a voice call service) exited to Twitter back in the day [1]. Signal is apparently marketed and developed by Signal Messenger LLC [2]. [0] https://archive.is/IRYTQ https://archive.is/IRYTQ [1] https://news.ycombinator.com/item?id=3286530 https://news.ycombinator.com/item?id=3286530 [2] https://archive.is/ZI7G1 https://archive.is/ZI7G1
- feurenard 3y agoSignal seems to use Kyber-1024, which does meet the NIST contest's security criteria. I wrote some more details here: https://community.signalusers.org/t/signal-blog-quantum-resistance-and-the-signal-protocol/55765/14 https://community.signalusers.org/t/signal-blog-quantum-resi...
- thadt 3y agoThe unfortunate reality of this is that while he may be right, it is difficult to classify the responses (or non-response) from the NIST people as deceptive vs just not wanting to engage with someone coming from such an adversarial position. NIST is staffed by normal people who probably view aggressively worded requests for clarification in the same way that most of us have probably fielded aggressively worded bug reports. Adding accusatory hyperbolic statements like: "You exposed three years of user data to attackers by telling people to use Kyber starting when your patent license activates in 2024, rather than telling people to use NTRU starting in 2021!" doesn't help. Besides the fact that nobody is deploying standalone PQ for some time, there were several alternatives that NIST could have suggested in 2021. How about SIKE? That one was pretty nice until it was broken last year. Unfortunately, NIST doesn't have a sterling reputation in this area, but if we're going to cast shade on the algorithm and process, a succinct breakdown of why, along with a smoking gun or two would be great. Pages and pages of email analysis, comparison to (only) one other submission, and accusations that everyone is just stalling so data can be vacuumed up because it is completely unprotected makes it harder to take seriously. If Kyber-512 is actually this risky, then it deserves to be communicated clearly.
- hn_throwaway_99 3y agoEdit: Just realized the author is djb, Daniel Bernstein, which I guess is semi-ironic for me because I was recently praising him on HN for an old, well-read blog post on ipv6. Thus, I guess I may take back a bit of what I said below, or least perhaps it would be better to say that I can better understand the adversarial tone given djb's history with NIST recommendations (more info at https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptography https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp...). > The unfortunate reality of this is that while he may be right, it is difficult to classify the responses (or non-response) from the NIST people as deceptive vs just not wanting to engage with someone coming from such an adversarial position. Couldn't agree with this more. I don't like to harp on form over substance, but in this case the form of this blog post was so bad I had difficulty evaluating whether the substance was worthwhile. I'm not in the field of cryptography, so I'm not qualified to assess on the merits, but my thoughts reading this were: 1. All the unnecessary snark and disparagement made me extremely wary of the message. It seemed like he was making good points, but the overall tone was similar to those YouTube "WhaT ThE ElITe DoN'T WanT YoU TO KnoW!!" videos. Frankly, the author just sounds like kind of an asshole, even if he is right. 2. Did anyone actually read this whole thing?? I know people love to harp on "the Internet has killed our attention spans", and that may be true, but the flip side is we're bombarded with so much info now that I take a very judicious approach to where I'll spend my time. On that point, if you're writing a blog post, the relevant details and "executive summary" if you will should be in the first couple paragraphs, then put the meandering, wandering diary after. Don't expect a full read if important tidbits are hidden like Where's Waldo in your meandering diary.
- loondri 3y agoThe NIST standardization process, appears to have a grey area particularly around the selection of constants. The skepticism around standardization, advocating instead for direct adoption from cryptographers, sheds light on potential shortcomings in the current system. There is definitely a need for a more transparent or open scrutiny in algorithm standardization to ensure security objectives are met.
- literarylover 3y ago[dead]
- laughriot101 3y ago[dead]
- 10g1k 3y agoRelated note: Government employees (including military, intel) are just people, and worse, bureaucrats. They aren't magical wizards who can all do amazing things with mathematics and witchcraft. If they were good at what they do, they wouldn't need ever increasing funding and projects to fix things.
- ethbr1 3y agoCryptanalysis and encryption are somewhat of an exception to this. There are some extremely smart people who work in these areas for the government, precisely because funding and application is on a different scale.
- lazide 3y agoVery few folks except the gov’t have real existential need for best in breed crypto, frankly.
- sneak 3y ago> Discovering the secret workings of NISTPQC. I filed a FOIA request "NSA, NIST, and post-quantum cryptography" in March 2022. NIST stonewalled, in violation of the law. Civil-rights firm Loevy & Loevy filed a lawsuit on my behalf. As much as I generally loathe djb personally, professionally he will always have my support as he’s been consistently willing to take the federal government to task in court. It brings me great joy to see he’s still at it.
- SoylentOrange 3y agoWhy do you dislike him personally?
- vGPU 3y agoMight be because he’s a bit of a “Linus” in crypto with the same ego and temper. However, the man has done so much to advance privacy and cryptography I think he’s earned the right to be a bit snippy, especially when he’s discussing something so complex 99% of the comments are “too long to read” and “I read it but I still don’t understand it”.
- sneak 3y agohttps://news.ycombinator.com/item?id=13891900 https://news.ycombinator.com/item?id=13891900
- 1vuio0pswjnm7 3y ago"Security is supposed to be job #1. So I recommend eliminating Kyber-512."
- 0xDEAFBEAD 3y agoAssuming djb is correct and the current process is broken... is trying to expose it and then fix it through FOIA requests really the best approach? If your codebase is hairy enough, and the problem to be solved is fundamentally fairly simple, sometimes it's better to rewrite than refactor. Doubly so if you believe a clever adversary has attempted to insert a subtle backdoor or bugdoor. What would a better crypto selection process look like? I like the idea of incorporating "skin in the game" somehow... for example, the cryptographer who designs the scheme could wager some cash that it won't be broken within a particular timeframe. Perhaps a philanthropist could offer a large cash prize to anyone who's able to break the winning algorithm. Etc.
- OkayPhysicist 3y agoTaking money from the cryptographers offers the exact opposite incentive that you want it to: your NSA black budget slush fund has orders of magnitude more spending power than anybody honest could hope to acquire.
- JoachimS 3y agoMy takeaway (impression) from the DJB post is that the evaluation by the NISTPQC seems not to provide algorithms with a firm level of security. That the evaluation is not clear cut, and not provide a good, conservative lower bound for the security provided by the algorithms selected.
- capitainenemo 3y agoMinor typo. "How can NIST justify throwing NIST-509 away?" should be "How can NIST justify throwing NTRU-509 away?"
- jasmas 3y agoI'm not sure N(IST)SA has any credibility left. Polularity of curve 25519 over their P curves is encouraging and it would be great to see the community continue this direction and largely ignore them going forward. The government shouldn't be leading or deciding, it would be better organized around gathering current consensus and following when it comes to FIPS, regulation, etc.
- _8j50 3y agoScorpions and frogs as usual.
- martinralbrecht 3y agoNIST responded: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO...
- Garbleflorp 3y ago[dead]