Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Breaking rainbow takes a weekend on a laptop

eprint.iacr.org

Post reply on HN
Print view View original

1–10 of 66 posts

Re: Breaking rainbow takes a weekend on a laptop

#2

Post by jack4818 »

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

Re: Breaking rainbow takes a weekend on a laptop

#3

Post by ototot »

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/

[1] https://blog.cloudflare.com/post-quantum-key-encapsulation/

[2] https://blog.cloudflare.com/post-quantum-future/

Re: Breaking rainbow takes a weekend on a laptop

#4

Post by nefitty »

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?

Re: Breaking rainbow takes a weekend on a laptop

#5

Post by hannob »

nefitty wrote: post #4

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…

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)

Re: Breaking rainbow takes a weekend on a laptop

#6

Post by nefitty »

hannob wrote: post #5
nefitty wrote: post #4

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…

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…

Ah gotcha. Thank you for taking the time to clarify!
Post reply on HN