Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
FiloSottile17 hours ago | parent | context | favorite | on: Claude reveals ECDSA curve origins 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. help 
feanaro12 hours ago | next[–] 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? reply commandersaki9 hours ago | parent | next[–] I'm guessing affinity towards prime curves vs cofactor. reply skew-aberration16 hours ago | prev | next[–] 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'? reply cyphar15 hours ago | parent | next[–] 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/ reply edelbitter17 hours ago | prev | next[–] >they can be hit randomly with 2^30 tries More precisely: not very random tries. reply mswphd16 hours ago | parent | next[–] 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. reply edelbitter15 hours ago | root | parent | next[–] 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.. reply palisade16 hours ago | prev | next[–] "..chose to risk moving the US government to it.." Oof, about that... reply wilkystyle15 hours ago | parent | next[–] go on... reply thayne12 hours ago | root | parent | next[–] 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 reply tharkun__15 hours ago | root | parent | prev | next[–] 3DES... reply djohnmustard14 hours ago | root | parent | next[–] What about it? reply tharkun__13 hours ago | root | parent | next[–] 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. reply teiferer8 hours ago | root | parent | next[–] 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. reply tptacek11 hours ago | root | parent | prev | next[–] 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. reply rurban6 hours ago | root | parent | next[–] Hello, the US government paid the IPSEC devs to include weak and backdoored algos back then. All revealed during the Snowden era reply afiori7 hours ago | root | parent | prev | next[–] Pushing for shorter keys can be reasonable, otherwise we would all use 16 MB keys reply duskwuff12 hours ago | root | parent | prev | next[–] > 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. reply tptacek11 hours ago | root | parent | next[–] 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. reply robrain12 hours ago | root | parent | prev | next[–] Arrant nonsense, surely? reply mitxela4 hours ago | prev | next[–] There are plenty of weak curves. See djb's safecurves project. Maybe the NSA found an unknown type of weakness. reply smolder10 hours ago | prev[–] Hello, NSA representative. reply
Consider applying for YC's Winter 2027 batch! Applications are open till November 2. Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact Search: