Breaking rainbow takes a weekend on a laptop
eprint.iacr.org
eprint.iacr.org
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/
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.
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.
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)
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)
You already and automatically know it's not that, because the article was not about breaking the encryption with a quantum computer.
It was broken with trivial hardware and in trivial time.
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
[0] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/KFgw...
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 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…
https://eprint.iacr.org/2016/376.pdf
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?
https://www.cryptomuseum.com/crypto/philips/px1000/
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 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.
you can't talk at people like that here, see
https://news.ycombinator.com/newsguidelines.html
and take it down five notches
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.
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.
Hard to coerce that into a "good faith".
Accusations of astroturfing are not allowed here.
Just stop.
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.
https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
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 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.
It is a private key probably still stored in a hardware module controlled by NSA CES, isn’t it?
This isn’t a problem: Just ask for decrypts by the usual FISA CES API and you don’t need the private key directly.
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…
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.
But don't over-correct. You can't just call anyone who submits to NIST an NSA puppet. There is zero parrallel with the Dual EC backdoor.
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.
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.
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.
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.
(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).
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.
It can be either, quite frankly.
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.)
It doesn't require any "aliens guy" at all.
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)