Hacker News Reader

Comment by FiloSottile | Hacker News Reader

Given how expensive this computation would have been in 1997, it makes perfect sense they'd taken months, but even if we assume they tried all timestamps of 1997 and selected arbitrarily among the first 16 viable candidate of any timestamp, that's just ~30 bits of freedom.

Finding out there is a class of weak 256-bit elliptic curves so large that they can be hit randomly with 2^30 tries would be a cryptanalytic breakthrough analogous to discovering all elliptic curve cryptography is broken.

Read section 3.1 of the Koblitz and Menezes paper. It was already implausible with 160 bits of freedom. https://eprint.iacr.org/2015/1018

If you want to believe the NSA knows ECC is broken and chose to risk moving the US government to it and somehow no one figured out the same break in 30 years, you're free to do so. But pretending the seed choice plays any role in that theory is over.

View on HN

This is unrelated to the above comment, but I figured I'd ask while we're here. You state at the end of your blog post on this topic that you'd now probably recommend the NIST curves over Curve25519. Why is that?

I'm guessing affinity towards prime curves vs cofactor.

As a complete layman, I do wonder why n grows with each subsequent curve, rather than with number of bits. Does this not suggest they were 'searching harder'?

Almost all of the smaller values of n are not valid curve values, so they were searching "harder" but just for valid seeds. If you look at the generator output in [1], you'll see that:

1. Only a very small number of valid seeds were discarded when compared to the number of n values. It seems we don't yet know why about half of the valid seeds were discarded but the explanation of a buggy curve validity checker doesn't seem implausible to me.

2. Directly to your point, most of the prime192 and prime239 curves required larger n values to find a valid seed and they are both smaller and used an earlier timestamp.

[1]: https://words.filippo.io/seeds-solved/

>they can be hit randomly with 2^30 tries

More precisely: not very random tries.

unless your guess is that the hypothetical ECC weakness is somehow correlated with the LCG structure, the draws from the LCG are as good as random.

It is possible such a correlation could occur. but it would be much weirder than this being the result of a random search, which would already be very weird.

I find it slightly less weird because I see potential for indirect attacks on the not-quite-so-ECC parts of actual implementations. Wherever a network client can ask many times for each of the different, but somehow not entirely uncorrelated curves, it might be able to expose previously not deemed critical side channels. Following in the general direction of the discoveries that so far resulted in IV and padding determinism/randomness being considered as important as the "actual crypto" itself. In that case the structures that would need to somehow interact would not be ECC and LCG, but merely LCG and key derivation..

Yeah... It would only be the second time they tried to do exactly that, with elliptic curve related crypto nonetheless

If your comparison here is to Dual EC, the two constructions are utterly unalike; you might as well compare it to the DES S-boxes.

Sure, the construction is different, but for all I know, there is a weakness in some subset of curves, and by not using open "nothing up my sleeve" practices for selecting their curves, they invited speculation. My point is that this is an untrustworthy actor who has shown itself to be untrustworthy on many occasions, and that you could make a similar migration argument about that, since it was pushed through FIPS. The fact that it was also EC based was not very relevant, I just thought that was funny.

I'm having trouble understanding what you're arguing here. We now know they essentially did use a nothing-up-my-sleeves seed; they just didn't care enough (it was a very different time) to reveal that.

"..chose to risk moving the US government to it.."

Oof, about that...

go on...

3DES...

What about it?

It was widely used, even in government and military. Who knows if they actually used the same as everyone else in actuality. I guess none of this is proven beyond doubt, given the nature of all this?!

    Reporting on declassified history says the NSA pushed for a shorter DES key; the compromise was 56 bits

    NSA and a suspected cryptographic backdoor: the Dual_EC_DRBG random-number generator was the subject of reporting about an NSA backdoor and an alleged payment to RSA. RSA denied knowingly weakening its products.

    TLS 1.0’s CBC chaining made IVs predictable and enabled the BEAST attack. That’s a documented protocol weakness, allegedly put in there by US state actors on purpose.

YMMV but none of this would surprise any reasonable person given Snowden's revelations.

> TLS 1.0’s CBC chaining made IVs predictable and enabled the BEAST attack. That’s a documented protocol weakness, allegedly put in there by US state actors on purpose.

This is errant nonsense. At the time SSL/TLS were designed, using CBC with block ciphers was generally considered best practice - it was not at all an unusual choice.

Arrant nonsense, surely?

Don't know what's so sure about it, either is perfectly valid.

Using CBC is fine. TLS and (prior to that) IPSEC set the CBC IV of messages to the last ciphertext block of the previous message --- pretending as if they were encrypting one long stream, rather than discrete messages. That's never been OK, and cryptographers warned about it at the time.

This CBC chaining thing is my all-time absolute favorite cryptography conspiracy theory, because on the IETF list where it happened (it happened for IPSEC, not for TLS, for what it's worth) Phil Rogaway pled with long-time standards body people --- even took up a petition of cryptographers, including Rivest --- and was openly and viciously mocked for the attempt.

The US government had no need to corrupt IPSEC standardization. The IETF did the work for them without prompting.

Hello, the US government paid the IPSEC devs to include weak and backdoored algos back then. All revealed during the Snowden era

Nobody thinks the people who shouted down Phil Rogaway, who include relatively famous standards nerds, were NSA plants. It's uncharitable for me to keep calling them out by name, but IYKYK.

You have far more to fear from standards bodies just acting like standards bodies (limited recent exceptions notwithstanding) than from government interference with standards. Like I said, all NSA usually needs to do is sit back and wait for standards groups to come up with Heartbleed on their own.

Please please don't bring AI generated text as arguments such discussions. Especially not without saying that that's what you are quoting.

Quoting something implies that it has certain authority (like a crypto expert) and the correctness track record of AI generated text is obviously shaky.

There's only so many formatting choices available on HN. Making a nice looking "bullet point list" of things, the best I've found is so far is to

    use
 
    monospace

    support

:shrug: That does not mean they're quotes or else there'd be a [1] with a link or names. Let me know if you have a better way; make sure it looks nice!

Pushing for shorter keys can be reasonable, otherwise we would all use 16 MB keys

There is some evidence that they have done it becore.

Specifically, that they had a backdoor for Dual EC DRBG[1], and pushed for a shorter key lenghth for DES, to intentionally weaken it.

It is, obviously, controversial. But I think there is certainly enough there that I wouldn't be confident that the NSA wouldn't recommend something they knew to be weak in some way, even to other government organizations.

[1]: https://en.wikipedia.org/wiki/Dual_EC_DRBG

  >even if we assume they tried all timestamps of 1997

Why limit to that? Especially since the official history had it as "hashed passphrase" (which would, of course, provide ample entropy).

A confusing official story doesn't disprove anything. If anything, that would be standard operating procedure for a signals intelligence plant.

  >Finding out there is a class of weak 256-bit elliptic curves so large that they can be hit randomly with 2^30 tries would be a cryptanalytic breakthrough

NSA is the largest employer of mathematicians in the world.

A breakthrough would indeed be a terrible thing to waste. If I had one, I'd make a good and boring official cover story, and stick to it! Regular old spy-craft stuff, in other words. ;)

There are plenty of weak curves. See djb's safecurves project. Maybe the NSA found an unknown type of weakness.

There are now multiple cryptographers on this thread (not counting me; I'm not a cryptographer) explaining why this is now utterly implausible.

Unfortunately one of these cryptographers' responses are in a thread that was collapsed for wrongthink.

The word "wrongthink", always a hallmark of the arguments most worth paying attention to!

A self-promoting non-cryptographer who only relies on his message board fan club is not worth paying attention to!

Oof. Devastating.

Where do you get the 2^30 from? drand48 could be f_0, but they could have tried f_1, f_2, ... as well and chosen the f_n that yielded the desired but plausible values.

All we know is that drand48 gave values that the NSA was happy with.

Reply on news.ycombinator.com