12 ms·

How is NSA breaking so much crypto? (2015)

347 points by notRobot 6y ago

hyper_reality 6y ago
To summarise: the authors speculate that the NSA invested in a lot of resources into breaking Diffie-Hellman key exchange for certain 1024-bit primes. Just a few hardcoded 1024-bit primes were used in the majority of VPN handshakes and a significant minority of HTTPS and SSH handshakes worldwide in 2015. This would give the NSA the ability to recover the shared symmetric key used in these encrypted communications, and therefore decrypt them. Since then several protocols have shifted towards preferring Elliptic Curve Diffie-Hellman key exchange which doesn't suffer from the same attack, or at least using larger primes for plain DHKE (1536-bit and above). However I don't know the extent of this - a lot of VPNs at least are still using the old, weak DH keys.
- nimbius 6y ago
  Bingo. Garbage primes that were either pushed by NIST to vendors or bribed to be included as default. The absolute arrogance of the authors in the Snowden papers in detailing the leak was probably the most powerful driver of things like dh parameters that roll every few days, and ed25519 that flat out rejected the nsa premise that primes were at all trustworthy Fast forward to today, and devs/cryptographers absolutely threw the nsa and cia out on their asses for their SPECK kernel argument hinging on the seemingly ironclad credibility of "it's classified." Corporate players will still sneak backdoors;it's what they do. But the real blow to the intelligence community is the loss of default trust and the active denial by the open source community.
  - api 6y ago
    My understanding is that it wasn't that the primes were bad but that they were hard coded, never changed, and the bit size was small enough to make attacks based on that practical. I'm on the fence about speck. It's so simple that there isn't much room in there for a back door, meaning that if there is one it implies that the NSA knows something we don't about ARX ciphers. If the NSA knows something we dont about ARX, then could they also know something about ChaCha?
    - Taek 6y ago
      All you need to know is one unique property to slip in a backdoor that nobody else may suspect for a long time. The NSA has given us good reason to question everything they release.
      - jas- 6y ago
        Have you considered the adversary and their tactics?
    - cryptonector 6y ago
      Rotating DH groups periodically is difficult. SSHv2, for example, has support for this. It takes a lot of computation to generate new groups, but then how do the client and server agree on a group? Well, the server tells the client, and the client has to like it -- i.e., the client has to trust the server's group. This isn't better than just having a bigger nothing-up-my-sleeves group to begin with. That, ultimately, has been the solution the community landed at: nothing-up-my-sleeve curves for ECDH and EdDSA. The nothing-up-my-sleeve part is all about setting / agreeing to obvious and hard guidelines for generating and selecting curves before doing the selection, then you can see that a curve was generated and selected without any hidden agendas. We have several of these now that are generally thought to be secure, though, of course, it's hard to say for sure. It's a pretty good outcome.
      - ustolemyname 6y ago
        If the client doesn't trust the server, the crypto protocol is a little irrelevant. I otherwise agree that we (ostensibly) are in a better place now with pre-defined curves.
        dcow 6y ago
        > If the client doesn't trust the server, the crypto protocol is a little irrelevant. What? No. The protocol is the only thing that is relevant. Peers don't generally trust each other a priori at all. They trust the protocol. If they can authenticate each other within the bounds of the protocol then they trust each other. If one party no has reason to distrust a certain protocol, then it should not be used as a basis for establishing trust. If the two peers can't agree on a protocol: stalemate. If I compromise your server and only serve weak protocols a responsible client won't authenticate me whereas a vulnerable client would take my word that my protocol is secure.
  - StanislavPetrov 6y ago
    >But the real blow to the intelligence community is the loss of default trust and the active denial by the open source community. Their loss is our gain.
- nuker 6y ago
  > Since then several protocols have shifted towards preferring Elliptic Curve Diffie-Hellman key exchange which doesn't suffer from the same attack .. There was a strange twist in this story: "Then, in August of this year, NSA freaked out.". And this guy is a professional. https://blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/ https://blog.cryptographyengineering.com/2015/10/22/a-riddle...
- ChristianBundy 6y ago
  Interesting. Is it possible to tell which Diffie-Hellman primes are used on an HTTPS connection? Back in 2016 I noticed that OpenSSL was using the wrong primes (https://github.com/openssl/openssl/commit/fb015ca6f05e09b11a3932f89d25bae697c8af1e https://github.com/openssl/openssl/commit/fb015ca6f05e09b11a...) and since then I've been very curious to know how prevalent the previous DH primes are.
ColinWright 6y ago
Huge discussions from earlier submissions: https://news.ycombinator.com/item?id=10390822 https://news.ycombinator.com/item?id=10390822 https://news.ycombinator.com/item?id=13198567 https://news.ycombinator.com/item?id=13198567 There's probably a lot of information in those discussions, but you can't comment there, so if you have anything to add, this is the place.
javajosh 6y ago
Wouldn't it be easiest to just backdoor all clients, everywhere? And ideally you'd even do some basic threat analysis at the device to save you some compute resources.
- cheez 6y ago
  That's what they did
  - rurban 6y ago
    On the hardware level in the most popular chips (Intel, AMD, Arm, Qualcomm baseband), and in various closed source OS. Of the good HW I don't see it in Power or Risc V yet.
- rvnx 6y ago
  You mean "Popular software XX" auto-updating ? It's likely already operational ;) Silent updates are extremely dangerous. This is why you can see some Israelis, for example, refusing over-the-air updates on their phone while traveling.
  - 6AA4FD 6y ago
    You mean random Israeli citizens refuse OTA updates while abroad anywhere? Can you elaborate, I feel like I'm missing something important.
    - lostcolony 6y ago
      Can't speak to the post, but, 'random Israeli citizens' likely are also "ex-military Israeli citizens" given the mandatory 2 year term for most of those who grow up there. So any OTA update concerns the military has are likely common social practice as well.
      - 6AA4FD 6y ago
        I had forgotten about that. Thank you for the insight.
rvnx 6y ago
The way magic numbers and curves are elected is not a naive process. The obvious backdoor in Dual EC-DRBG is a good example, and you have companies helping the NSA in very extensive ways (e.g. Crypto AG). It's just logic, the goal of the NSA is to protect interests of the US, if it involves pushing rigged / weak algorithms for the greater "good" (at least from a US perspective), they'll do it. It's legal, and logical.
- softwarejosh 6y ago
  Yeah logical if youre fine with degrading the US dtandards. Therell be nobody to spy on if nobody buys our dogshit products.
  - rvnx 6y ago
    Well they are quite addictive and good products. Without SSH or TLS life would be more sad.
    - espadrine 6y ago
      SSH is Finnish, originally; not American.
      - rvnx 6y ago
        Wow cool, I always believed (wrongly) it was US
- Narkov 6y ago
  > It's just logic, the goal of the NSA is to protect interests of the US, >It's legal, and logical. In the short term it may have been a good idea but Blind Freddy could have seen the damage it would/did cause when people discovered it. As others have said, the NSA/CIA is on default-distrust now with crypto devs. That's not protecting the US interests.
6AA4FD 6y ago
A novel (to me) thought: if we count on the government not to break our crypto (edit: originally said break the law, I don't want to comment on the legality of nsa actions here, it strikes me as off topic), we are already screwed. A million other crypto discussions have surfaced: if someone wants your keys, the can break your knees (rhymes too). If VA stops paying benefits, unless the organization that funds and controls them steps in, a lot of people are very screwed. While it's admirable to ensure crypto at every level (especially to address threats from other states or private individuals), ultimately as long as all three branches let the NSA eat our proverbial lunches and sneak under my mattress (gag orders, huge budget, sealing court records, etc), secure crypto is going to be a sisyphean at best. Obviously there are good reasons to push the stone upwards, but the fitting solution to problems like infiltration and gag orders seems like it will be a political one not a technical one.
- _bxg1 6y ago
  I think it's still worthwhile to make it as expensive for them as possible. Sure, they have supercomputers that can break any crypto a normal citizen is using. But can they break every piece of encrypted data that everyone is using? Maybe not. And if so, they're going to spend a lot of money on hardware and electricity to do so (especially as Moore's Law putters out). Now, that doesn't apply to cases when they can get their hands on a centralized key through back-room court orders. But we do also have the ability to avoid using at least some of those products in the first place.
  - 6AA4FD 6y ago
    Consider that we have openssl and libressl (a fork) for open source ssl libraries (if I'm missing any please correct me). With gag orders and infiltration, is it unrealistic to assume that the NSA at least could backdoor both of them? Also consider things like adding bogus/weak crypto to NIST, intel ME and other hardware backdoors. Yes, with enough collective effort there are ways around all of it (option a), but ultimately with that much collective time and money it might be more effective to vote, advocate, and advertise (option b). Furthermore, if you go option a, anyone who poses a threat to whoever holds the reins can still be successfully abducted. (edit: and free speech/safety in political dissent is one of the major prizes everyone has their eyes on here)
sneak 6y ago
https://github.com/caprover/caprover/issues/533 https://github.com/caprover/caprover/issues/533
mlcrypto 6y ago
Satoshi knew to use elliptic curves in 2009 for Bitcoin. Coincidence? Also perfect opsec and near perfect implementation...
- bouncycastle 6y ago
  Elliptic curves produce smaller keys which meant that addresses could take up less space and be more portable, so perhaps that was part of the motivation.
- throw9490 6y ago
  Every crypto geek knew to use ECC in 2009. Hell, the Windows Genuine Advantage system, which goes back to Windows 98SE, uses ECC for its keys. [1] https://internetcafe.ph/forum/4-lounge/17183-all-u-need-to-know-about-windows-product-key https://internetcafe.ph/forum/4-lounge/17183-all-u-need-to-k...
- ratiolat 6y ago
  ECC is referenced in Uplink, released 2001. https://en.wikipedia.org/wiki/Uplink_(video_game) https://en.wikipedia.org/wiki/Uplink_(video_game) Coincidence?
est31 6y ago
I think in the long term, we'll move away from relying on one algorithm only, like AES or DHKE, but combine them. So for key exchange we will use DH plus ECDH plus whatever comes out of the post quantum NIST competition, and use all three as inputs for both parties to a KDF to produce the derived key. Attacks against any one of the algorithms won't turn into feasible attacks onto all of them.
- arberavdullahu 6y ago
  Combining two algorithms is very hard and when it does it can become insecure(new attacks can be found). Even if you can combine and its secure then it becomes infeasible to use it often as the length of keys, IV, etc. increases
  - est31 6y ago
    I didn't mean deep combination that changes how an algorithm works internally. Of course that would be a stupid idea. The algorithms would still work the same, would use separate random numbers, etc. You'd just combine them at the integration level, treating each algorithm like a black box. Think of two servers first doing DH and then doing ECDH. You'd get two shared keys. This is inefficient because it has more roundtrips than doing the algorithm's steps in parallel, but helps with understanding. These two secrets can then serve as inputs to your KDF which derives multiple secrets for each of the data ciphers you use. E.g. first AES with the first secret then encrypt that with ChaCha20 with the second secret. As long as your KDF is preimage resistant, you can't get from one algo to another. And yes, length of keys and computation do increase. But I argue that this will be a cost worth paying at least in some scenarios. Especially in a time we make our CPUs slower by double digit percentages for all computation in the name of security.
londons_explore 6y ago
Crypto should aim to be secure for at least 100 years given current compute performance growth. That's one human lifetime. At no point was that true for 1024 bit DH keys. So why did anyone ever implement it?
- bostik 6y ago
  At a guess, it was likely a tradeoff between security and computational cost. I used to do freelancing for an ICT magazine and in early-to-mid 00s ran some numbers, as part of an article I did on limitations of applied cryptography. You can't do 1024-bit math on 32-bit or even 64-bit integers. Not without bignum libraries, which in turn make use of applied number theory. Under the hood the multiplication of two large numbers is an O(n^2) operation. Performing an RSA or DH calculation with decent desktop computer in ~2003 took about 20ms with a 1024-bit number, and 80ms with a 2048-bit number. IIRC the first was expected to be theoretically breakable in a decade or so, assuming Moore's Law held true. The second was thought to be computationally infeasible for at least 100 years. These days the professionally paranoid use 4096-bit keys. (Or more recently, the nice 25519 curve which is more compact.) So raising the security margin from "reasonable" to "paranoid", back in the day, would have required 4x the hardware investment to serve the same amount of traffic, and it would have imposed severe latency issues for everyone. We also have to consider the fact that most commercial secrets have a shelf life of years to a couple of decades. So before "E2E for everyone" became a thing, there simply wasn't widespread interest for crypto that could protect personal secrets for a lifetime. With regards to using cryptography for personal privacy, cypherpunks were well ahead of their time. It's only become a mainstream issue in the last 5 years or so.
  - MaximumYComb 6y ago
    Isn't multiplication of two integers with length n O(nlog(n)) with the Harvey-Hoevan algorithm? Is the limitation our 64-bit computers?
    - wbhart 6y ago
      Harvey-van der Hoeven. And yes it is. But this is an asymptotic cost meaning you have to have absolutely enormous integers before the cost will be lower than the old algorithm. In fact, the crossover is so large it is quite possibly out of the range of anything we'll practically ever compute. In particular, crypto typically works with integers zillions of times smaller, so you certainly don't want the Harvey-van der Hoeven algorithm for that.
xparco 6y ago
By being the author of the crypto that you idiots think is grassroots
phkamp 6y ago
Underestimating what an organization like NSA has the resources and imagination to do, is a chronic ailment. https://archive.fosdem.org/2014/schedule/event/nsa_operation_orchestra/ https://archive.fosdem.org/2014/schedule/event/nsa_operation...
sargun 6y ago
The real question I have is where is this money going? I've looked at positions at NSA, and I know at lease one person that works there. They aren't making heaps of money. How are they recruiting so many qualified individuals?
- cipher_314159 6y ago
  From what I understand: tech, mission, and tickets. Say what you want, the NSA probably has some of the most interesting tech problems you'll encounter. Part of that is due to the unique job that they do-- by definition, they're doing things that nobody else in the US is allowed to do, so they need people to solve problems that don't exist elsewhere. Part of that is due to having a huge amassed knowledge particular to their area of work, which allows them to work on things that other people/organizations simply don't even know about. Also: the NSA has supercomputers that make your eyes bleed. A buddy of mine who worked there says that even their power bills are classified. Back in the day, they developed a lot of highly specialized, one-of-a-kind hardware. Cray processors had a popcount instruction that was supposedly put in place at the NSA's behest. They can afford to get specialized treatment and demand specialized features from folks who build their computers. If speculation regarding their signal collection capabilities is true, then they also have to have serious signal processing and communications tech, too. The NSA has interesting challenges and cool tech to work with. That can attract a LOT of people. Another issue is mission. Look, you may not agree with the NSA's techniques and methods. But at least the original goal of the NSA-- breaking codes used by foreign adversaries to gain an intelligence and military advantage-- is pretty standard military fare, and not inherently evil. SIGINT played a major role in shortening WWII, and who knows may have happened since then (since it's all classified). The folks I know who work there are proud of their work, and believe they're doing the right thing. I'll note that these are GOOD people whom I respect, which leads me to believe that the NSA isn't just moustache-twirling and evil cackling. Some people work there because they believe they are genuinely serving their country. Finally: tickets. Several of the folks I know have gone to the NSA, worked there a few years, then jumped ship to take industry jobs with clearances. Government contractors pay a premium for cleared workers, and if you show up with a TOP SECRET clearance in hand, your job interview chances just got better. It's a good way to set yourself up for decent job security and comfortable pay.
OnlyRepliesToBS 6y ago
porkchop sandwiches
gigama 6y ago
Meanwhile Barr (and predecessors) complain about sigintel "going dark" due to encryption... always sounded like a red herring to me. When you manage to break an encryption method you protect your zero-day investment by encouraging everyone to continue to think you can't. #SetecAstronomy

347 points by notRobot 6y ago

To summarise: the authors speculate that the NSA invested in a lot of resources into breaking Diffie-Hellman key exchange for certain 1024-bit primes. Just a few hardcoded 1024-bit primes were used in the majority of VPN handshakes and a significant minority of HTTPS and SSH handshakes worldwide in 2015. This would give the NSA the ability to recover the shared symmetric key used in these encrypted communications, and therefore decrypt them. Since then several protocols have shifted towards preferring Elliptic Curve Diffie-Hellman key exchange which doesn't suffer from the same attack, or at least using larger primes for plain DHKE (1536-bit and above). However I don't know the extent of this - a lot of VPNs at least are still using the old, weak DH keys.

nimbius 6y ago
Bingo. Garbage primes that were either pushed by NIST to vendors or bribed to be included as default. The absolute arrogance of the authors in the Snowden papers in detailing the leak was probably the most powerful driver of things like dh parameters that roll every few days, and ed25519 that flat out rejected the nsa premise that primes were at all trustworthy Fast forward to today, and devs/cryptographers absolutely threw the nsa and cia out on their asses for their SPECK kernel argument hinging on the seemingly ironclad credibility of "it's classified." Corporate players will still sneak backdoors;it's what they do. But the real blow to the intelligence community is the loss of default trust and the active denial by the open source community.
- api 6y ago
  My understanding is that it wasn't that the primes were bad but that they were hard coded, never changed, and the bit size was small enough to make attacks based on that practical. I'm on the fence about speck. It's so simple that there isn't much room in there for a back door, meaning that if there is one it implies that the NSA knows something we don't about ARX ciphers. If the NSA knows something we dont about ARX, then could they also know something about ChaCha?
  - Taek 6y ago
    All you need to know is one unique property to slip in a backdoor that nobody else may suspect for a long time. The NSA has given us good reason to question everything they release.
    - jas- 6y ago
      Have you considered the adversary and their tactics?
  - cryptonector 6y ago
    Rotating DH groups periodically is difficult. SSHv2, for example, has support for this. It takes a lot of computation to generate new groups, but then how do the client and server agree on a group? Well, the server tells the client, and the client has to like it -- i.e., the client has to trust the server's group. This isn't better than just having a bigger nothing-up-my-sleeves group to begin with. That, ultimately, has been the solution the community landed at: nothing-up-my-sleeve curves for ECDH and EdDSA. The nothing-up-my-sleeve part is all about setting / agreeing to obvious and hard guidelines for generating and selecting curves before doing the selection, then you can see that a curve was generated and selected without any hidden agendas. We have several of these now that are generally thought to be secure, though, of course, it's hard to say for sure. It's a pretty good outcome.
    - ustolemyname 6y ago
      If the client doesn't trust the server, the crypto protocol is a little irrelevant. I otherwise agree that we (ostensibly) are in a better place now with pre-defined curves.
      - dcow 6y ago
        > If the client doesn't trust the server, the crypto protocol is a little irrelevant. What? No. The protocol is the only thing that is relevant. Peers don't generally trust each other a priori at all. They trust the protocol. If they can authenticate each other within the bounds of the protocol then they trust each other. If one party no has reason to distrust a certain protocol, then it should not be used as a basis for establishing trust. If the two peers can't agree on a protocol: stalemate. If I compromise your server and only serve weak protocols a responsible client won't authenticate me whereas a vulnerable client would take my word that my protocol is secure.
- StanislavPetrov 6y ago
  >But the real blow to the intelligence community is the loss of default trust and the active denial by the open source community. Their loss is our gain.
nuker 6y ago
> Since then several protocols have shifted towards preferring Elliptic Curve Diffie-Hellman key exchange which doesn't suffer from the same attack .. There was a strange twist in this story: "Then, in August of this year, NSA freaked out.". And this guy is a professional. https://blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/ https://blog.cryptographyengineering.com/2015/10/22/a-riddle...
ChristianBundy 6y ago
Interesting. Is it possible to tell which Diffie-Hellman primes are used on an HTTPS connection? Back in 2016 I noticed that OpenSSL was using the wrong primes (https://github.com/openssl/openssl/commit/fb015ca6f05e09b11a3932f89d25bae697c8af1e https://github.com/openssl/openssl/commit/fb015ca6f05e09b11a...) and since then I've been very curious to know how prevalent the previous DH primes are.

ColinWright 6y ago

Huge discussions from earlier submissions: https://news.ycombinator.com/item?id=10390822 https://news.ycombinator.com/item?id=10390822 https://news.ycombinator.com/item?id=13198567 https://news.ycombinator.com/item?id=13198567 There's probably a lot of information in those discussions, but you can't comment there, so if you have anything to add, this is the place.

javajosh 6y ago

Wouldn't it be easiest to just backdoor all clients, everywhere? And ideally you'd even do some basic threat analysis at the device to save you some compute resources.

cheez 6y ago
That's what they did
- rurban 6y ago
  On the hardware level in the most popular chips (Intel, AMD, Arm, Qualcomm baseband), and in various closed source OS. Of the good HW I don't see it in Power or Risc V yet.
rvnx 6y ago
You mean "Popular software XX" auto-updating ? It's likely already operational ;) Silent updates are extremely dangerous. This is why you can see some Israelis, for example, refusing over-the-air updates on their phone while traveling.
- 6AA4FD 6y ago
  You mean random Israeli citizens refuse OTA updates while abroad anywhere? Can you elaborate, I feel like I'm missing something important.
  - lostcolony 6y ago
    Can't speak to the post, but, 'random Israeli citizens' likely are also "ex-military Israeli citizens" given the mandatory 2 year term for most of those who grow up there. So any OTA update concerns the military has are likely common social practice as well.
    - 6AA4FD 6y ago
      I had forgotten about that. Thank you for the insight.

rvnx 6y ago

The way magic numbers and curves are elected is not a naive process. The obvious backdoor in Dual EC-DRBG is a good example, and you have companies helping the NSA in very extensive ways (e.g. Crypto AG). It's just logic, the goal of the NSA is to protect interests of the US, if it involves pushing rigged / weak algorithms for the greater "good" (at least from a US perspective), they'll do it. It's legal, and logical.

softwarejosh 6y ago
Yeah logical if youre fine with degrading the US dtandards. Therell be nobody to spy on if nobody buys our dogshit products.
- rvnx 6y ago
  Well they are quite addictive and good products. Without SSH or TLS life would be more sad.
  - espadrine 6y ago
    SSH is Finnish, originally; not American.
    - rvnx 6y ago
      Wow cool, I always believed (wrongly) it was US
Narkov 6y ago
> It's just logic, the goal of the NSA is to protect interests of the US, >It's legal, and logical. In the short term it may have been a good idea but Blind Freddy could have seen the damage it would/did cause when people discovered it. As others have said, the NSA/CIA is on default-distrust now with crypto devs. That's not protecting the US interests.

6AA4FD 6y ago

A novel (to me) thought: if we count on the government not to break our crypto (edit: originally said break the law, I don't want to comment on the legality of nsa actions here, it strikes me as off topic), we are already screwed. A million other crypto discussions have surfaced: if someone wants your keys, the can break your knees (rhymes too). If VA stops paying benefits, unless the organization that funds and controls them steps in, a lot of people are very screwed. While it's admirable to ensure crypto at every level (especially to address threats from other states or private individuals), ultimately as long as all three branches let the NSA eat our proverbial lunches and sneak under my mattress (gag orders, huge budget, sealing court records, etc), secure crypto is going to be a sisyphean at best. Obviously there are good reasons to push the stone upwards, but the fitting solution to problems like infiltration and gag orders seems like it will be a political one not a technical one.

_bxg1 6y ago
I think it's still worthwhile to make it as expensive for them as possible. Sure, they have supercomputers that can break any crypto a normal citizen is using. But can they break every piece of encrypted data that everyone is using? Maybe not. And if so, they're going to spend a lot of money on hardware and electricity to do so (especially as Moore's Law putters out). Now, that doesn't apply to cases when they can get their hands on a centralized key through back-room court orders. But we do also have the ability to avoid using at least some of those products in the first place.
- 6AA4FD 6y ago
  Consider that we have openssl and libressl (a fork) for open source ssl libraries (if I'm missing any please correct me). With gag orders and infiltration, is it unrealistic to assume that the NSA at least could backdoor both of them? Also consider things like adding bogus/weak crypto to NIST, intel ME and other hardware backdoors. Yes, with enough collective effort there are ways around all of it (option a), but ultimately with that much collective time and money it might be more effective to vote, advocate, and advertise (option b). Furthermore, if you go option a, anyone who poses a threat to whoever holds the reins can still be successfully abducted. (edit: and free speech/safety in political dissent is one of the major prizes everyone has their eyes on here)

sneak 6y ago

https://github.com/caprover/caprover/issues/533 https://github.com/caprover/caprover/issues/533

mlcrypto 6y ago

Satoshi knew to use elliptic curves in 2009 for Bitcoin. Coincidence? Also perfect opsec and near perfect implementation...

bouncycastle 6y ago
Elliptic curves produce smaller keys which meant that addresses could take up less space and be more portable, so perhaps that was part of the motivation.
throw9490 6y ago
Every crypto geek knew to use ECC in 2009. Hell, the Windows Genuine Advantage system, which goes back to Windows 98SE, uses ECC for its keys. [1] https://internetcafe.ph/forum/4-lounge/17183-all-u-need-to-know-about-windows-product-key https://internetcafe.ph/forum/4-lounge/17183-all-u-need-to-k...
ratiolat 6y ago
ECC is referenced in Uplink, released 2001. https://en.wikipedia.org/wiki/Uplink_(video_game) https://en.wikipedia.org/wiki/Uplink_(video_game) Coincidence?

est31 6y ago

I think in the long term, we'll move away from relying on one algorithm only, like AES or DHKE, but combine them. So for key exchange we will use DH plus ECDH plus whatever comes out of the post quantum NIST competition, and use all three as inputs for both parties to a KDF to produce the derived key. Attacks against any one of the algorithms won't turn into feasible attacks onto all of them.

arberavdullahu 6y ago
Combining two algorithms is very hard and when it does it can become insecure(new attacks can be found). Even if you can combine and its secure then it becomes infeasible to use it often as the length of keys, IV, etc. increases
- est31 6y ago
  I didn't mean deep combination that changes how an algorithm works internally. Of course that would be a stupid idea. The algorithms would still work the same, would use separate random numbers, etc. You'd just combine them at the integration level, treating each algorithm like a black box. Think of two servers first doing DH and then doing ECDH. You'd get two shared keys. This is inefficient because it has more roundtrips than doing the algorithm's steps in parallel, but helps with understanding. These two secrets can then serve as inputs to your KDF which derives multiple secrets for each of the data ciphers you use. E.g. first AES with the first secret then encrypt that with ChaCha20 with the second secret. As long as your KDF is preimage resistant, you can't get from one algo to another. And yes, length of keys and computation do increase. But I argue that this will be a cost worth paying at least in some scenarios. Especially in a time we make our CPUs slower by double digit percentages for all computation in the name of security.

londons_explore 6y ago

Crypto should aim to be secure for at least 100 years given current compute performance growth. That's one human lifetime. At no point was that true for 1024 bit DH keys. So why did anyone ever implement it?

bostik 6y ago
At a guess, it was likely a tradeoff between security and computational cost. I used to do freelancing for an ICT magazine and in early-to-mid 00s ran some numbers, as part of an article I did on limitations of applied cryptography. You can't do 1024-bit math on 32-bit or even 64-bit integers. Not without bignum libraries, which in turn make use of applied number theory. Under the hood the multiplication of two large numbers is an O(n^2) operation. Performing an RSA or DH calculation with decent desktop computer in ~2003 took about 20ms with a 1024-bit number, and 80ms with a 2048-bit number. IIRC the first was expected to be theoretically breakable in a decade or so, assuming Moore's Law held true. The second was thought to be computationally infeasible for at least 100 years. These days the professionally paranoid use 4096-bit keys. (Or more recently, the nice 25519 curve which is more compact.) So raising the security margin from "reasonable" to "paranoid", back in the day, would have required 4x the hardware investment to serve the same amount of traffic, and it would have imposed severe latency issues for everyone. We also have to consider the fact that most commercial secrets have a shelf life of years to a couple of decades. So before "E2E for everyone" became a thing, there simply wasn't widespread interest for crypto that could protect personal secrets for a lifetime. With regards to using cryptography for personal privacy, cypherpunks were well ahead of their time. It's only become a mainstream issue in the last 5 years or so.
- MaximumYComb 6y ago
  Isn't multiplication of two integers with length n O(nlog(n)) with the Harvey-Hoevan algorithm? Is the limitation our 64-bit computers?
  - wbhart 6y ago
    Harvey-van der Hoeven. And yes it is. But this is an asymptotic cost meaning you have to have absolutely enormous integers before the cost will be lower than the old algorithm. In fact, the crossover is so large it is quite possibly out of the range of anything we'll practically ever compute. In particular, crypto typically works with integers zillions of times smaller, so you certainly don't want the Harvey-van der Hoeven algorithm for that.

xparco 6y ago

By being the author of the crypto that you idiots think is grassroots

phkamp 6y ago

Underestimating what an organization like NSA has the resources and imagination to do, is a chronic ailment. https://archive.fosdem.org/2014/schedule/event/nsa_operation_orchestra/ https://archive.fosdem.org/2014/schedule/event/nsa_operation...

sargun 6y ago

The real question I have is where is this money going? I've looked at positions at NSA, and I know at lease one person that works there. They aren't making heaps of money. How are they recruiting so many qualified individuals?

cipher_314159 6y ago
From what I understand: tech, mission, and tickets. Say what you want, the NSA probably has some of the most interesting tech problems you'll encounter. Part of that is due to the unique job that they do-- by definition, they're doing things that nobody else in the US is allowed to do, so they need people to solve problems that don't exist elsewhere. Part of that is due to having a huge amassed knowledge particular to their area of work, which allows them to work on things that other people/organizations simply don't even know about. Also: the NSA has supercomputers that make your eyes bleed. A buddy of mine who worked there says that even their power bills are classified. Back in the day, they developed a lot of highly specialized, one-of-a-kind hardware. Cray processors had a popcount instruction that was supposedly put in place at the NSA's behest. They can afford to get specialized treatment and demand specialized features from folks who build their computers. If speculation regarding their signal collection capabilities is true, then they also have to have serious signal processing and communications tech, too. The NSA has interesting challenges and cool tech to work with. That can attract a LOT of people. Another issue is mission. Look, you may not agree with the NSA's techniques and methods. But at least the original goal of the NSA-- breaking codes used by foreign adversaries to gain an intelligence and military advantage-- is pretty standard military fare, and not inherently evil. SIGINT played a major role in shortening WWII, and who knows may have happened since then (since it's all classified). The folks I know who work there are proud of their work, and believe they're doing the right thing. I'll note that these are GOOD people whom I respect, which leads me to believe that the NSA isn't just moustache-twirling and evil cackling. Some people work there because they believe they are genuinely serving their country. Finally: tickets. Several of the folks I know have gone to the NSA, worked there a few years, then jumped ship to take industry jobs with clearances. Government contractors pay a premium for cleared workers, and if you show up with a TOP SECRET clearance in hand, your job interview chances just got better. It's a good way to set yourself up for decent job security and comfortable pay.

OnlyRepliesToBS 6y ago

porkchop sandwiches

gigama 6y ago

Meanwhile Barr (and predecessors) complain about sigintel "going dark" due to encryption... always sounded like a red herring to me. When you manage to break an encryption method you protect your zero-day investment by encouraging everyone to continue to think you can't. #SetecAstronomy