This is truly an incredible result. I want to adopt some PQC to my own stuff recently and considering Rainbow as one of my choice.
I also know that Cloudflare is now trying to adopt these PQC protocols[0][1], so I checked the Cloudflare blog post after seeing this attack. Then, I found out a blog mentioning this attack[2], lol.
The KEX schemes that seem to have received the most cryptanalysis are SIKE (SIDH that permits key reuse) and NTRU. They seem solid but I’d only use them in the real world in a hybrid scheme where the key is hashed with the result of a conventional ECC exchange. That way you get that security if the PQ algorithm ends up broken.
The signature schemes seem dodgy to me except for Sphincs and it’s variants and those have big keys and signatures. The keys are not impractically big for many uses but would be tough for things like block chains.
This is an incredible result from Ward Beullens, who has practically broken the 3rd round NIST PQ candidate "Rainbow"[0]
Paper Abstract:
This work introduces new key recovery attacks against the Rainbow signature scheme, which is one of the three finalist signature schemes still in the NIST Post-Quantum Cryptography standardization project. The new attacks outperform previously known attacks for all the parameter sets submitted to NIST and make a key-recovery practical for the SL 1 parameters. Concretely, given a Rainbow public key for the SL 1 parameters of the second-round submission, our attack returns the corresponding secret key after on average 53 hours (one weekend) of computation time on a standard laptop.
Thanks to the informative resources linked to by jack4818 and ototot I was able to slightly wrap my head around this. I'll share my barely informed, naive understanding in the hopes that it'll help others in a similar position build on it. Please correct me if any of what I share is mistaken!
Quantum computers have special properties that make them capable of breaking commonly used encryption schemes. We're dependent on those schemes for secure communication, like logging into a bank website. Due to this, the organization NIST has been working on finding encryption schemes that would be diffcult to break with a quantum computer.
NIST was at the stage of this project where they felt reasonably confident that three specific encryption schemes met the requirements. This is after review of many candidates. Rainbow made it to the top three. Ward Buellens essentially managed to break Rainbow, thereby making it ineligible for use in a quantum computer-powered future.
I assume this puts the two remaining candidates' eligibility into question. Were the requirements lacking, or is the project inherently at risk of failure due to the nature of quantum computing?
Generally it seems the encryption side of post quantum is a bit easier than the signature side. All signature schemes proposed have significant downsides.
(though this result raises very serious questions about the whole process - if it's possible that a promising candidate which probably would've been standardized very soon can be broken so severely it questions whether we know enough about these technologies to standardize them yet)
Quantum computers are good at solving the hidden subgroup problem, which generalizes RSA and Diffie Hellman.
The reason they do well in this area is that you can implement a Fourier transform with exponentially fewer quantum logic gates than classical logic gates.
Post quantum involves implementing a cryptosystem which can not be reduced to a hidden subgroup problem, but I’m still not sure if this is sufficient (QIP might solve other classes of problems easily)
Do you have a good reference on the relationship between quantum computers and Fourier transforms? I’m a DSP researcher by day and this is the first time I’ve heard about this, so my interest is piqued.
There is an excruciating amount of papers, but at least it has a sensible name: you can google “quantum Fourier transform” and go down the rabbit hole of suffering from there :D
The rainbow team just posted to the pqc development list acknowledging the attack and thanking the authors.
They’ve increased the parameter sets to compensate, implying that the maths I don’t understand doesn’t create a systemic failure but rather a sufficiently meaningful reduction in attack complexity
The same way Dual_EC_DRBG became a NIST standard, the NSA pulls the strings.
You can't expect a government department to provide robust security to the masses when the rest of the government is trying the prevent that exact situation.
At this point anything, cryptography related, coming from NIST should be considered compromised.
A risible argument. NSA wants NOBUS vulnerabilities: the kind they can exploit, but nobody else can, because NIST cryptography gets used on the kinds of systems NSA doesn't want exploited in a weekend with a laptop.
If a cryptographically relevant quantum computer is built - then everyone with a CRQC can recover the secret key for the Q parameter. Not a very good NOBUS plan if CRQC are expected to be built as NIST and NSA have made clear by their desire for pq crypto standards.
A pertinent question comes to mind: do you suggest NSA hasn’t and could not have stolen the private key that is relevant for the Juniper Q parameter swap?
I wouldn’t find such a claim reasonable and NSA would have it if they want it.
One presumes that the Chinese still have a copy of that other private key for their swapped out Q parameter. Maybe they keep it with their copy of the OPM data that they took. Maybe they use the OPM data for leverage on the actual secret key holders to get the original private key for the original Q parameter. Maybe they don’t care because swapping Q was better and easier. If you think this Dual EC design is a success…
NSA outclasses every other intelligence service on earth but they too have insiders who leave with more than is allowed.
Furthermore, NSA has also been willing to deploy LFSR designs which are still being broken by a single digit number of persons such as the recent PX-1000cr break. Do you know if NSA considered that NOBUS?
If NSA considered the LFSR design in the DES replacement cipher in the PX-1000cr NOBUS, their claim of NOBUS was wrong. If they didn’t consider it NOBUS, then on what ground do you claim that they only want to deploy NOBUS backdoors?
Either way, we can observe just from public cases that their backdoor strategy isn’t limited to only deploying NOBUS backdoors. To claim they only want NOBUS is an NSA PR talking point from Vanee’ Vines herself at the NSA press office. It is not only wrong, it’s blatantly ahistorical. NSA wants plaintext and that means they don’t only deploy and push NOBUS backdoors.
There are other examples that aren’t public yet and definitely aren’t NOBUS.
It's tricky to get a bead on what it is people think I'm arguing here. My argument is simple and narrow: if it's an attack discovered independently that can break a cryptosystem with realistic parameters over a weekend on a laptop, it's not an NSA backdoor. NSA backdoors are trivially exploitable by NSA, but not trivially exploitable by anyone with the relevant mathematics background.
It appears that you’re saying that PX-1000cr isn’t an example NSA backdoor or that the article breaking the cipher in the PX1000cr is incorrect?
It seems like you’re either very aware of how NSA backdoors work and you’re misleading people for some reason or you don’t know what you’re talking about, you’re being hopeful and you are ignoring the evidence that NSA inserts backdoors which can be broken by others. Assuming the latter in good faith, I’m afraid to inform you that you’re simply incorrect.
Do you dispute that the secret key for the Q Parameter in Dual EC may be recovered by anyone with a CRQC? This is assuming that they exist, and if they don’t or won’t exist, why does NSA concern themselves with pq crypto? I agree that someone stealing the key is a different effort but either could have answered your question of what the key is - so the technique is largely irrelevant, but I take your more narrow point and will engage it.
If NSA isn’t misleading us to deploy broken crypto with their pq standardia push, then they probably don’t consider the Q parameter in Dual EC to be a NOBUS backdoor. After all, by your argumentation NOBUS is forever, isn’t it?
There are other backdoored systems pushed by NSA and some are still in use. I assure you, they can be broken in a weekend by someone with the relevant computer science and mathematical background. The trick for finding it is to realize your core assumption is wrong.
One system NSA built was purpose built to trick a community of interest, and it worked. The core break is in the RNG - the RNG only generates keys from a small subset of all possible keys. The users of this system have no clue.
Do you really suggest that this kind of NSA backdoor doesn’t exist and that evidence of it means that it isn’t NSA who did it? It again seems ahistorical of you.
It seems like you’re either very aware of how NSA backdoors work and you’re misleading people for some reason or you don’t know what you’re talking about
I am explaining that I see two options and I pick the second in good faith. I believe I am participating according to the rules, or at least I am attempting to do so in good faith.
One is innuendo, the second one is an insult. In good faith or not, neither is 'participating according to the rules' since both are explicitly mentioned there as things not to do.
I respectfully disagree. It certainly isn’t intended as an insult!
One looks like astroturfing performed without a valid basis against cited examples shared in good faith, the other appears to be a mistake in analysis which I am pointing out in good faith. It’s probably an honest mistake, the history here is intentionally obscured by large-scale adversaries.
I do believe that the second is just a mistake and I do not intend it as an insult. I would appreciate it if you could please assume good faith with my responses and additionally hear me when I say it is in good faith a mistake of analysis. I think that his analysis is simply wrong, and my citations are evidence for why I think this is so.
You don't have to agree but you can't call people NSA shills and you can't tell people they don't know what they're talking about. That's just how this forum works - don't put that kind of thing in your comments. It's not a high or difficult bar to meet.
I did not intend, nor do I think I called the parent an NSA shill. If it comes across as that, I apologize.
The parent clearly says that it is hard to get a bead on what he is arguing. I tried to explain what people may hear or see and I do believe that some people might not be able to see the latter but only the former, fair or not, but I only endorsed the latter.
I guess I should make clear that I think the parent is simply mistaken and that I don’t think he is a shill. It’s not intended as an insult to say there is a mistake of analysis, as I said the topic is very difficult and also often very contentious.
I’m saying this in response to the parents claim of it being hard to get a bead on what he is arguing. I’m answering that as two possible ways to read it and I emphasize the latter. I did not accuse, I tried to explain what I think people take from his argumentation.
My words included two options, one of which includes those words — and I disowned the first option. Please read it again and then read his comment again. Selective quoting won’t change that I was providing a reflection of two possible reads of his comments, and I endorsed the latter in good faith. If you think my first option is unreasonable as a characterization to write down, I’m not sure how I can more clearly express that this is a reading that someone can fairly arrive at - I just think it’s wrong. I provided these two options because he could rephrase his comments to avoid the first one entirely to sharpen his argument. If the parent hadn’t expressed that it was “hard to get a bead” I wouldn’t have provided the first option as feedback to try to express the possible “beads” in question.
If you don’t think there are people who are actively misleading people on this topic or that a comment can’t be read that way, I think we should agree to disagree. People will read a lot of things in this area in bad faith and they are also often wrong because there is intentional obfuscation by large-scale adversaries.
Look, dude, I don't care about this NSA shill stuff, and you're not doing your arguments any favors trying to super-duper-duper explain what you really meant by dropping innuendo into the thread. Just stop talking about it and move on. Now you know that HN is super picky about "shillage" arguments. We can be done talking about it.
I'm having trouble even following what you're saying here. A cryptographically-relevant quantum computer breaks all conventional elliptic curve cryptography, not just NSA's backdoor. Everything we're talking about is irrelevant if NSA can break curves with quantum computers.
The point is that if the RNG didn’t artificially add elliptic curves in the form of a back door, even a CRQC wouldn’t be able to break the RNG. Grover can be assumed to reduce the security by roughly ~N/2. A design with a sufficiently large N isn’t going to fall to a CRQC generally. The design of Dual EC which includes a backdoor is strictly worse than a design without a low hanging Q to attack.
NSA expects and is pushing the idea that there will be a CRQC. NSA does not say they will be the only people with a CRQC, and so their hold on a monopoly to exploit Dual EC isn’t forever and will someday be in the domain of a person with a laptop (and access to a CRQC).
I think your entire argument boils down to "there's no such thing as a NOBUS backdoor because practical quantum computing breaks Dual EC". OK. Super interesting point.
I pointed out two specific cryptographic backdoors. One follows from your premise - a regular person can’t just bust Dual EC because it is based on a hard problem. That’s true for now but it’s also the exception as far as I can tell. Other backdoors by NSA don’t all share that property.
The other example of an NSA backdoor is the DES replacement known as the PX-1000cr cipher. It is claimed also to be a backdoor from NSA but by your framing, it can’t be an NSA backdoor because it was broken by Stef on his laptop without much of a budget. Your framing suggests that because someone found it and broke it, it can’t be an NSA NOBUS backdoor. But as I pointed out even the Dual EC backdoor has limits and so your standard seems unreasonable.
Then there is DES itself which was intentionally weakened by NSA. IBM wanted 64 bits, NSA wanted fewer bits and at the time, Hellman said DES should have twice the bits. Between Hellman and NSA, I guess we know who won.
NSA doesn’t only want NOBUS backdoors. They want almost anything that gets them plaintext first in a reliable manner, and things related to long term security come a far distant second, if at all, as we see in the analysis of the PX-1000cr research.
Also yeah, having a quantum computer will give everyone the secret key for the Q in Dual EC. Recording that traffic now will probably have pay off for non NSA adversaries later if a CRQC is really coming. Who knows if that will happen, but we know NSA is exploiting fear of that happening to push for new cryptography that isn’t a hybrid design including some kind of ECC.
This is a very reasonable take. The people at NIST are in a bind. Many of them are good people with positive intentions, but they cannot speak freely about NSA and they say so openly at cryptography conferences when asked.
It’s all good. I take it respectfully. Let me try again and I mean this entirely in good faith. I don’t think you’re an NSA shill as I think my other comments were taken by random readers. I do think you’re just mistaken and like many Americans (myself included) we want to believe in our institutions. You seem like a reasonable person, and I meant no slight towards you.
My read is that you asked what is the secret key with the implication that if they have it they should reveal it. No one who has it would do that to settle an argument. Well maybe someone would but it seems like an unreasonable ask. Absence of evidence isn’t evidence of absence (of the theft of the secret key for the q parameter for Dual EC), right?
If Dual EC didn’t have a backdoor, no could steal the secret key that NSA uses to exploit it. One is more secure than the other, and I take your comment as requiring the secret key for the corresponding Q to leak for that design to be a bad idea that is insecure. Again, I don’t think that is a reasonable standard of evidence. We know people steal stuff from NSA and we cannot expect that they will drop the secret key on hacker news to decide that it was a bad idea in the first place.
NOBUS is a fantasy idea - is there even a reasonable proposal that isn’t less secure than the same system without a backdoor? Even with ECDLP in play, if a CRQC is really in our future, Dual EC isn’t a forever NOBUS backdoor. If we knew how to do public key cryptography that could last 100+ years and we thought it was also post-quantum, maybe a backdoor wouldn’t weaken the system overall. But that’s a lot of maybes…
The argument you're making doesn't even cohere. If quantum computers break conventional cryptography, they moot backdoors in conventional public key cryptography. But they can simply be re-established in PQ public key cryptography. The idea behind a PKRNG backdoor is simple!
Huh, okay. I will try to clarify, apologies if I’m being incoherent. The argument I’m making is that the evidence doesn’t support your original claim or your follow up ask for a secret key.
NSA isn’t trying to (only) make NOBUS backdoors where the NOBUS is forever. If it isn’t forever, it’s not secure in the “Nobody but US(A)” sense implied by NOBUS as thrown around.
NOBUS is a fantasy of a very large security claim because even with a PKRNG, the keys can be stolen. However in the Dual EC case the current PKRNG again will also fall to a CRQC in addition to key theft. Both cases are strictly worse than a purely CSPRNG without a backdoor. The damage done by this kind of sabotage is hard to measure.
The evidence about backdoors points to NSA malfeasance and not towards NSA wanting something that is never insecure as is very strongly implied by the common framing of NOBUS as a concept.
The parallel that matters is that NSA is documented as being inclined to design, allow, and promote backdoors like Dual EC to be standardized by NIST. They have no obligation to break and publish the break as Ward has done here. It’s not that the authors of rainbow are suspect, it’s that the result of the process isn’t telling us what we hope it tells us. NIST must consult with NSA by law but the law does not require NSA to help. It certainly does not require NSA to save NIST from standardizing a broken system. The Dual EC backdoor is a documented act of strategic sabotage by NSA and NIST, though we extend the benefit of the doubt to NIST.
What stands between us and additional standardized backdoors is effectively a very small number of smart academics who relative to NSA are underfunded and under resourced. Thankfully we have people like Ward breaking systems and publishing it openly. Unfortunately we have NSA funded people pushing things as well, Dragonfly and IETF come to mind here as well.
NIST standardization does not mean NSA can’t break it. Historically, we know from the Dual EC standardization that they can break it by their own design, and they let the world deploy and use Dual EC to NSA’s own advantage.
An apt comparison for the NIST standardization process would be the World Wrestling Entertainment. Except Vince McMahon just likes making money, whereas the NSA has the objective of interecepting all communications, forever.
There is no indication that that’s what happened in this case. This stuff is just non-trivial to cryptanalyze , and there’s not that many people who can do it.
NSA is regularly claimed to be the employer of the largest number of mathematicians in the world.
The reason we don’t know about the NSA analysis is that the law doesn’t require NSA to analyze the winners and then make the results public.
If Ward can do it and make it public, that’s wonderful and we should thank him. Thank you Ward!
We can’t say the same about NSA. This is really a problem and we should be able to rely on NSA to break such schemes and to deliver the result openly to NIST. It’s unbelievable that this isn’t the case and rather we have to rely on some nice guy with a weekend of laptop time.
They authors acknowledged on the list that they didn’t think of the attack, and have appropriately scaled the parameters.
Cryptography is hard - there have been numerous NTRU optimizations that withstood years of analysis before someone worked how to break them. Not everything is an NSA conspiracy. The dual-EC bullshit was even confusing to other cryptographers at the time, but at that time good faith was still being assumed.
The attack the NSA used on the standardization process can’t be repeated in anyway now, because no protocols are accepted that don’t demonstrate how the various constants are determined. Of course there’s also much less trust in US gov, and more importantly us gov adjacent cryptographers.
At the time some cryptographers said it looked like a backdoor and they were largely dismissed by the public until Snowden related evidence came to light. Further reporting exposed the $10m bribe to RSA. To wax poetic: It was not a note in isolation but a note in a much larger song.
It is important to remember that NSA is continuing to do this kind of thing and they try from every angle. It is literally their job. Consider that the Dragonfly issues at the IETF are after Dual EC.
There are backdoored systems which are deployed and have not yet been revealed.
We must be on the lookout for them, and we must consider that NSA supposedly employs the most mathematicians in the world.
Ward’s work is amazing. Wouldn’t it be amazing if NSA actually tried to help? Do we suppose NSA didn’t also have a break on it? If not, we should really hope Ward keeps working in public. If NSA actually wanted to help and did help by breaking the remaining systems, it might win some points in public and especially if they advance the state of the art in cryptanalysis.
They were largely dismissed by "the public" --- and dismissive themselves --- because nobody believed anybody would actually use an expensive, janky PKRNG when far simpler, more performant CSPRNGs were already universally available in operating systems and standard C libraries. The revelation in the BULLRUN leaks wasn't that Dual EC was suspicious --- it had always been suspicious --- but rather that companies were actually using it, because NSA suborned RSA Security into making BSAFE use it.
(Prior to BULLRUN, I'd have been equally dismissive of the idea that people were still using BSAFE, either, but, no, as it turns out, the industry is a whole lot dumber than any of us expected it is).
NSA does actually try to help; it's ostensibly half of their mission (nobody seriously believes the IAD mission gets anything close to 50% of the resources).
This comment is great and gets to the heart of the dispute. Thanks for making it.
I have spoken with one of the authors who found it and he did not dismiss it, so I don’t know why you frame it as it they did? Maybe this would be a useful citation?
I do not believe that this was the only surprise in BULLRUN. I was horrified (as an American) that NSA weakened cryptography to their advantage even including against American businesses. This is still going on today and it isn’t just BSAFE. The NSA also “enables” other products including hardware to their advantage.
I agree that IAD has an important positive goal for work, I’m not really in a position to know if they are trying to help but the goal seems solid. I agree that they do not get anything close to 50% of the funding and I think this should be solved by breaking them out from NSA entirely. They should probably be made into a transparent group which never ever gives NSA an advantage as the first time did so much damage that we are still discussing it today.
And it doesn't even matter. It's almost a distraction to even think about conspiracy theories or worrying about sounding like a conspiracy kook.
By now it doesn't matter if there is a conspiracy or not.
The totally boring unimaginative hard nosed practical conclusion is you do not accept cryptographic advice from this source. (NIST, or the US government at large, or any other government either, or really even any large corporation.)
This isn’t the first time I’ve seen something billed as “post quantum” that is completely broken on conventional computers. I wish I could say more about that.
A lot of the problem seems to be in making practical PQC algorithms. There are a few algorithms that have provable security guarantees (at least as I understand it), such as McEliece. Somewhat hilarious McEliece is actually faster than existing DLP systems. The problem is that the key size is very large, enough to make it impractical in the real world.
There are also systems like learning with errors. shortest vector, ... but I don't understand them well enough to know if they've been proven safe at a basic technique level.
The problem is that there have been many attempts to reduce the actual key size, and they keep being found to have ended up breaking the security of the underlying scheme.
I feel like that's what has happened here with rainbow.
(as a note to the "NSA conspiracy" folk: The NSA or what have you wants schemes that they can break by knowing some secret value. Schemes that simply break outright aren't useful to them because it means (1) anyone can break it, and (2) as a byproduct of (1) they cannot use it safely. In an ideal world what they want is something so secure that they could use it for communication themselves - which would reduce suspicion - but also be able to decrypt everything)
I also know that Cloudflare is now trying to adopt these PQC protocols[0][1], so I checked the Cloudflare blog post after seeing this attack. Then, I found out a blog mentioning this attack[2], lol.
[0] https://blog.cloudflare.com/making-protocols-post-quantum/
[1] https://blog.cloudflare.com/post-quantum-key-encapsulation/
[2] https://blog.cloudflare.com/post-quantum-future/