5 ms·

This recent publication illustrates a problem that we have trying to keep our communications secure. If we all use a single "strong" prime number with our cryp

by olympus 11y ago

This recent publication illustrates a problem that we have trying to keep our communications secure. If we all use a single "strong" prime number with our crypto then the NSA has a huge incentive to pre-compute results from that single strong number. Now that we know that the NSA is doing this, we won't all use a proven strong number, and we will all start to do key exchanges with another method, and it will become the common thread that the NSA can attack. So the NSA will pretty much always attack whatever common procedure we all use and find the weak point. If we all used different methods for key exchanges and encryption then we will all be fractured and the NSA can easily pick off their targets individually. What's the answer to this problem? Is there crypto that we can all use that the NSA won't be able to crack even if they have a strong incentive to do so? And why aren't we all using if such a solution exists?

tptacek 11y ago
Not really. This precomputation attack only works because attacks on 1024 bit discrete logs were already plausible. We don't choose cryptographic parameters to make the NSA's job harder; we choose them to make the job implausible. So it's exactly the wrong message to take from this paper that we should mix up parameters more; rather, the message is: don't use weak moduli.
- olympus 11y ago
  > don't use weak moduli. By this do you mean don't use 1024 bit keys? Would using 2048 bit (or larger) mean that the NSA wouldn't be able to buy a computer that could do the computation within a year? Why don't we all use 2048 bit keys then? Is the communication and processing overhead so high that we'd rather be vulnerable? Edit to add: I'm not an expert, but I'm competent enough to force a certain level of crypto on my computer and to know not to trust the communication when a website forces a fallback to a lower level. But sometimes I wish there was a level of explanation (of why we want to do certain things) that was above what you would give to "Joe off the street" and below the explanation that you would give to a graduate student in cryptography.
  - tptacek 11y ago
    NSA almost definitely can't buy a computer that can break 2048 bit conventional multiplicative group discrete logs, and if by same insane space-alien-technology chance they can, the implication is that conventional multiplicative group discrete logs are probably entirely unsuitable for secure cryptography: no amount of jazz-hands with parameters will save you. Reminder: 2048 bit discrete logs aren't just twice as hard as 1024 bit discrete logs! Yes: 2048 bit RSA and DH are significantly slower than 1024 bit, and that's a big part of why they're still in use.
  - snuxoll 11y ago
    > By this do you mean don't use 1024 bit keys? Would using 2048 bit (or larger) mean that the NSA wouldn't be able to buy a computer that could do the computation within a year? Keep in mind, going from 1024 to 2048 bit DH parameters doesn't double the search space, it raises it from 2^1024 to 2^2048. At some point the search space gets so large that you'd need more energy than required to boil all of Earth's oceans to find the key, which makes such a brute-force attack implausible.
    - cinquemb 11y ago
      I haven't had much crypto-in-practice background (outside of thought experiments), but I have some math background so I'm quite curious. Shouldn't people also be worried about non brute force attacks based on finding mathematical solutions? I mean, "The Uneasy Relationship Between Mathematics and Cryptography"[0]? [0] http://www.ams.org/notices/200708/tx070800972p.pdf http://www.ams.org/notices/200708/tx070800972p.pdf
      - tptacek 11y ago
        The attacks we're talking about are non-brute-force mathematical attacks (specifically, in this case, the index calculus). A pure brute-force attack on a 2^1024 search space would be comically implausible.
    - netheril96 11y ago
      Actually that is wrong. The search space of 1024 bit Diffie Hellman is about 2^80, of 3248 bit about 2^128. I failed to find a number for 2048 bit DHE.
PlzSnow 11y ago
"If we all use a single "strong" prime number with our crypto then the NSA has a huge incentive to pre-compute results from that single strong number. Now that we know that the NSA is doing this" We don't know the NSA is doing this. There's no evidence whatsoever beyond conspiracy theory stuff.
- mentat 11y ago
  Except, you know, actual leaked documents and it being the most reasonable expectation for their claimed capabilities.
  - PlzSnow 11y ago
    IOW no evidence whatsoever.
    - AnimalMuppet 11y ago
      Sure, if you dismiss all the evidence there is, then there's no evidence. If that reassures you, great. Just don't be surprised that the rest of us are not reassured...
- rogeryu 11y ago
  > We don't know the NSA is doing this. There's no evidence whatsoever beyond conspiracy theory stuff. We don't know the NSA is not doing this. There is ample evidence that they do a lot more than we conspired about.
  - PlzSnow 11y ago
    "We don't know the NSA is not doing this." Please look at what you wrote! Am I dreaming? This is the level of argument that is being used?
    - mappu 11y ago
      I'm assuming you believe in the passive intercept so this will focus on the 1024-bit prime. It is crackable with the NSA's leaked budget and it fits their mission. If you had the NSA's leaked budget, you could crack this. I could crack this. The budget is not astronomical and it could be cracked by dozens of governments your country doesn't get along with. That's why it's important to defend against it because even if you trust the NSA, the attack is equally available to Russia / China / North Korea / your country's boogeyman-of-the-day. The whole global internet is under threat along with billions of dollars of eCommerce GDP.

by olympus 11y ago

tptacek 11y ago

Not really. This precomputation attack only works because attacks on 1024 bit discrete logs were already plausible. We don't choose cryptographic parameters to make the NSA's job harder; we choose them to make the job implausible. So it's exactly the wrong message to take from this paper that we should mix up parameters more; rather, the message is: don't use weak moduli.

olympus 11y ago
> don't use weak moduli. By this do you mean don't use 1024 bit keys? Would using 2048 bit (or larger) mean that the NSA wouldn't be able to buy a computer that could do the computation within a year? Why don't we all use 2048 bit keys then? Is the communication and processing overhead so high that we'd rather be vulnerable? Edit to add: I'm not an expert, but I'm competent enough to force a certain level of crypto on my computer and to know not to trust the communication when a website forces a fallback to a lower level. But sometimes I wish there was a level of explanation (of why we want to do certain things) that was above what you would give to "Joe off the street" and below the explanation that you would give to a graduate student in cryptography.
- tptacek 11y ago
  NSA almost definitely can't buy a computer that can break 2048 bit conventional multiplicative group discrete logs, and if by same insane space-alien-technology chance they can, the implication is that conventional multiplicative group discrete logs are probably entirely unsuitable for secure cryptography: no amount of jazz-hands with parameters will save you. Reminder: 2048 bit discrete logs aren't just twice as hard as 1024 bit discrete logs! Yes: 2048 bit RSA and DH are significantly slower than 1024 bit, and that's a big part of why they're still in use.
- snuxoll 11y ago
  > By this do you mean don't use 1024 bit keys? Would using 2048 bit (or larger) mean that the NSA wouldn't be able to buy a computer that could do the computation within a year? Keep in mind, going from 1024 to 2048 bit DH parameters doesn't double the search space, it raises it from 2^1024 to 2^2048. At some point the search space gets so large that you'd need more energy than required to boil all of Earth's oceans to find the key, which makes such a brute-force attack implausible.
  - cinquemb 11y ago
    I haven't had much crypto-in-practice background (outside of thought experiments), but I have some math background so I'm quite curious. Shouldn't people also be worried about non brute force attacks based on finding mathematical solutions? I mean, "The Uneasy Relationship Between Mathematics and Cryptography"[0]? [0] http://www.ams.org/notices/200708/tx070800972p.pdf http://www.ams.org/notices/200708/tx070800972p.pdf
    - tptacek 11y ago
      The attacks we're talking about are non-brute-force mathematical attacks (specifically, in this case, the index calculus). A pure brute-force attack on a 2^1024 search space would be comically implausible.
  - netheril96 11y ago
    Actually that is wrong. The search space of 1024 bit Diffie Hellman is about 2^80, of 3248 bit about 2^128. I failed to find a number for 2048 bit DHE.

PlzSnow 11y ago

"If we all use a single "strong" prime number with our crypto then the NSA has a huge incentive to pre-compute results from that single strong number. Now that we know that the NSA is doing this" We don't know the NSA is doing this. There's no evidence whatsoever beyond conspiracy theory stuff.

mentat 11y ago
Except, you know, actual leaked documents and it being the most reasonable expectation for their claimed capabilities.
- PlzSnow 11y ago
  IOW no evidence whatsoever.
  - AnimalMuppet 11y ago
    Sure, if you dismiss all the evidence there is, then there's no evidence. If that reassures you, great. Just don't be surprised that the rest of us are not reassured...
rogeryu 11y ago
> We don't know the NSA is doing this. There's no evidence whatsoever beyond conspiracy theory stuff. We don't know the NSA is not doing this. There is ample evidence that they do a lot more than we conspired about.
- PlzSnow 11y ago
  "We don't know the NSA is not doing this." Please look at what you wrote! Am I dreaming? This is the level of argument that is being used?
  - mappu 11y ago
    I'm assuming you believe in the passive intercept so this will focus on the 1024-bit prime. It is crackable with the NSA's leaked budget and it fits their mission. If you had the NSA's leaked budget, you could crack this. I could crack this. The budget is not astronomical and it could be cracked by dozens of governments your country doesn't get along with. That's why it's important to defend against it because even if you trust the NSA, the attack is equally available to Russia / China / North Korea / your country's boogeyman-of-the-day. The whole global internet is under threat along with billions of dollars of eCommerce GDP.