9 ms·

Breaking rainbow takes a weekend on a laptop

155 points by jack4818 5y ago

jack4818 5y ago
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. [0] https://www.pqcrainbow.org https://www.pqcrainbow.org
ototot 5y ago
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. [0] https://blog.cloudflare.com/making-protocols-post-quantum/ https://blog.cloudflare.com/making-protocols-post-quantum/ [1] https://blog.cloudflare.com/post-quantum-key-encapsulation/ https://blog.cloudflare.com/post-quantum-key-encapsulation/ [2] https://blog.cloudflare.com/post-quantum-future/ https://blog.cloudflare.com/post-quantum-future/
- api 5y ago
  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.
nefitty 5y ago
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?
- hannob 5y ago
  Rainbow is a signature scheme. 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)
  - nefitty 5y ago
    Ah gotcha. Thank you for taking the time to clarify!
- gunfighthacksaw 5y ago
  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)
ShoveItHN 5y ago
aborsy 5y ago
How did such algorithm make it to the finalist list, passing a lot of steps?!
- aaaaaaaaaaab 5y ago
  The NSA hoped noone would notice.
  - bayindirh 5y ago
    After all these incidents we've gone through in the last decade, I'm not sure this is irony or just the reality. It can be either, quite frankly.
    - Brian_K_White 5y ago
      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.) It doesn't require any "aliens guy" at all.
  - olliej 5y ago
    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.
    - 5y ago
egberts1 5y ago
Time to shorten the RekayInterval or soemthing.
_yrgy 5y ago
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.
- Brian_K_White 5y ago
  I know the first thing I do when involved in a project with any kind of nda is go right on HN and say I can't talk about it.
- olliej 5y ago
  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)
tomcam 5y ago
I’m trying to bring back Emo and “Breaking Rainbow” will be the name of my group
olliej 5y ago
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
- ototot 5y ago
  Is this[0] the correct link you're mentioning? [0] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/KFgw5_qCXiI https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/KFgw...
  - olliej 5y ago
    yup! cheers for that (I get them in email, and totally forgot that they're also visible in google groups :D)

155 points by jack4818 5y ago

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. [0] https://www.pqcrainbow.org https://www.pqcrainbow.org

ototot 5y ago

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. [0] https://blog.cloudflare.com/making-protocols-post-quantum/ https://blog.cloudflare.com/making-protocols-post-quantum/ [1] https://blog.cloudflare.com/post-quantum-key-encapsulation/ https://blog.cloudflare.com/post-quantum-key-encapsulation/ [2] https://blog.cloudflare.com/post-quantum-future/ https://blog.cloudflare.com/post-quantum-future/

api 5y ago
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.

nefitty 5y ago

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?

hannob 5y ago
Rainbow is a signature scheme. 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)
- nefitty 5y ago
  Ah gotcha. Thank you for taking the time to clarify!
gunfighthacksaw 5y ago
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)

ShoveItHN 5y ago

aborsy 5y ago

How did such algorithm make it to the finalist list, passing a lot of steps?!

aaaaaaaaaaab 5y ago
The NSA hoped noone would notice.
- bayindirh 5y ago
  After all these incidents we've gone through in the last decade, I'm not sure this is irony or just the reality. It can be either, quite frankly.
  - Brian_K_White 5y ago
    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.) It doesn't require any "aliens guy" at all.
- olliej 5y ago
  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.
  - 5y ago

egberts1 5y ago

Time to shorten the RekayInterval or soemthing.

_yrgy 5y ago

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.

Brian_K_White 5y ago
I know the first thing I do when involved in a project with any kind of nda is go right on HN and say I can't talk about it.
olliej 5y ago
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)

tomcam 5y ago

I’m trying to bring back Emo and “Breaking Rainbow” will be the name of my group

olliej 5y ago

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

ototot 5y ago
Is this[0] the correct link you're mentioning? [0] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/KFgw5_qCXiI https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/KFgw...
- olliej 5y ago
  yup! cheers for that (I get them in email, and totally forgot that they're also visible in google groups :D)