I’m trying to bring back Emo and “Breaking Rainbow” will be the name of my group
Breaking rainbow takes a weekend on a laptop
21–30 of 66 posts
Re: Breaking rainbow takes a weekend on a laptop
#22How did such algorithm make it to the finalist list, passing a lot of steps?!
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.
This is pure paranoia, I'll be the first to criticize NIST and NSA for the damage they've done to standards and to their own credibility.
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.
Re: Breaking rainbow takes a weekend on a laptop
#23How did such algorithm make it to the finalist list, passing a lot of steps?!
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.
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.
Re: Breaking rainbow takes a weekend on a laptop
#24Thanks 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…
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…
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.
Re: Breaking rainbow takes a weekend on a laptop
#25This 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)
Re: Breaking rainbow takes a weekend on a laptop
#26Earlier quoted context omitted.
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.
They fooled us once; are you suggesting we let them fool us again? We have very good reason to look at NIST with suspicion from now on.
Re: Breaking rainbow takes a weekend on a laptop
#27Earlier quoted context omitted.
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.
NOBUS vulns are a fantasy, and the NSA's dual goals of strengthening and weakening security are impossible to truly resolve
Re: Breaking rainbow takes a weekend on a laptop
#28Thanks 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…
"... or is the project inherently at risk of failure due to the nature of quantum computing?" 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.
Good point. My mistake.
Re: Breaking rainbow takes a weekend on a laptop
#29Earlier quoted context omitted.
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.
NOBUS vulns are a fantasy, and the NSA's dual goals of strengthening and weakening security are impossible to truly resolve
They are, huh? Well then: what's the private key for Dual EC?
Re: Breaking rainbow takes a weekend on a laptop
#30Earlier quoted context omitted.
NOBUS vulns are a fantasy, and the NSA's dual goals of strengthening and weakening security are impossible to truly resolve
They are, huh? Well then: what's the private key for Dual EC?
What is the private key?
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.