[HN Gopher] Breaking rainbow takes a weekend on a laptop
___________________________________________________________________
Breaking rainbow takes a weekend on a laptop
Author : jack4818
Score : 141 points
Date : 2022-02-25 11:19 UTC (1 days ago)
(HTM) web link (eprint.iacr.org)
(TXT) w3m dump (eprint.iacr.org)
| jack4818 wrote:
| 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
| ototot wrote:
| 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/
| api wrote:
| 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.
| ShoveItHN wrote:
| aborsy wrote:
| How did such algorithm make it to the finalist list, passing a
| lot of steps?!
| RansomStark wrote:
| 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.
| tux3 wrote:
| 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.
| Ar-Curunir wrote:
| 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.
| sidewndr46 wrote:
| 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.
| tptacek wrote:
| 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.
| generalizations wrote:
| 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.
| aaaaaaaaaaab wrote:
| The NSA hoped noone would notice.
| bayindirh wrote:
| 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 wrote:
| 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.
| egberts1 wrote:
| Time to shorten the RekayInterval or soemthing.
| nefitty wrote:
| 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?
| Brian_K_White wrote:
| "... 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.
| gunfighthacksaw wrote:
| 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)
| ssfrr wrote:
| 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.
| hannob wrote:
| 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 wrote:
| Ah gotcha. Thank you for taking the time to clarify!
| tomcam wrote:
| I'm trying to bring back Emo and "Breaking Rainbow" will be the
| name of my group
| _yrgy wrote:
| 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.
| olliej wrote:
| 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)
| Brian_K_White wrote:
| 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.
___________________________________________________________________
(page generated 2022-02-26 23:02 UTC)