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

31–40 of 66 posts

Re: Breaking rainbow takes a weekend on a laptop

#31

Post by secretkeyholder »

tptacek wrote: post #20
RansomStark wrote: post #11

Earlier 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.

If a cryptographically relevant quantum computer is built - then everyone with a CRQC can recover the secret key for the Q parameter. Not a very good NOBUS plan if CRQC are expected to be built as NIST and NSA have made clear by their desire for pq crypto standards.

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.

Re: Breaking rainbow takes a weekend on a laptop

#32

Post by olliej »

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

Re: Breaking rainbow takes a weekend on a laptop

#33

Post by olliej »

aaaaaaaaaaab wrote: post #9
aborsy wrote: post #8

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

The NSA hoped noone would notice.

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.

Re: Breaking rainbow takes a weekend on a laptop

#34

Post by olliej »

ssfrr wrote: post #24
gunfighthacksaw wrote: post #14

Earlier quoted context omitted.

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.

There is an excruciating amount of papers, but at least it has a sensible name: you can google “quantum Fourier transform” and go down the rabbit hole of suffering from there :D

Re: Breaking rainbow takes a weekend on a laptop

#35

Post by tptacek »

secretkeyholder wrote: post #30
tptacek wrote: post #29

Earlier quoted context omitted.

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.

I don't think you're following the actual dispute on this subthread.

Re: Breaking rainbow takes a weekend on a laptop

#36

Post by tptacek »

secretkeyholder wrote: post #31
tptacek wrote: post #20

Earlier 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.

If a cryptographically relevant quantum computer is built - then everyone with a CRQC can recover the secret key for the Q parameter. Not a very good NOBUS plan if CRQC are expected to be built as NIST and NSA have made clear by their desire for pq crypto standards. 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…

It's tricky to get a bead on what it is people think I'm arguing here. My argument is simple and narrow: if it's an attack discovered independently that can break a cryptosystem with realistic parameters over a weekend on a laptop, it's not an NSA backdoor. NSA backdoors are trivially exploitable by NSA, but not trivially exploitable by anyone with the relevant mathematics background.

Re: Breaking rainbow takes a weekend on a laptop

#37

Post by ototot »

olliej wrote: post #32

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

Is this[0] the correct link you're mentioning?

[0] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/KFgw...

Re: Breaking rainbow takes a weekend on a laptop

#38

Post by secretkeyholder »

tptacek wrote: post #36
secretkeyholder wrote: post #31

Earlier quoted context omitted.

If a cryptographically relevant quantum computer is built - then everyone with a CRQC can recover the secret key for the Q parameter. Not a very good NOBUS plan if CRQC are expected to be built as NIST and NSA have made clear by their desire for pq crypto standards. 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…

It's tricky to get a bead on what it is people think I'm arguing here. My argument is simple and narrow: if it's an attack discovered independently that can break a cryptosystem with realistic parameters over a weekend on a laptop, it's not an NSA backdoor. NSA backdoors are trivially exploitable by NSA, but not trivially exploitable by anyone with the relevant mathematics background.

On what basis do you make that claim?

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.

Re: Breaking rainbow takes a weekend on a laptop

#39

Post by secretkeyholder »

tptacek wrote: post #35
secretkeyholder wrote: post #30

Earlier quoted context omitted.

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.

I don't think you're following the actual dispute on this subthread.

I followed it and was trying to point out that your question was imprecise.

Re: Breaking rainbow takes a weekend on a laptop

#40

Post by pvg »

secretkeyholder wrote: post #38
tptacek wrote: post #36

Earlier quoted context omitted.

It's tricky to get a bead on what it is people think I'm arguing here. My argument is simple and narrow: if it's an attack discovered independently that can break a cryptosystem with realistic parameters over a weekend on a laptop, it's not an NSA backdoor. NSA backdoors are trivially exploitable by NSA, but not trivially exploitable by anyone with the relevant mathematics background.

On what basis do you make that claim? 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…

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 can't talk at people like that here, see

https://news.ycombinator.com/newsguidelines.html

and take it down five notches

Post reply on HN