5 ms·

What does it mean to "break 2 primes"? Is there some prime number that's calculated secretly but somehow unknown?

micaeked 11y ago
See the original article: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/ https://freedom-to-tinker.com/blog/haldermanheninger/how-is-...
mikeyouse 11y ago
From micaeked's link; For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn’t just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime. I'm not an expert by any stretch, but this is my understanding; For a client and server to communicate securely, they can exchange crypto keys publicly via Diffie-Hellman. D-H relies on a very large prime number and a second smaller prime, both of which can be broadcast publicly. The two clients add their own secret key to the primes, perform an operation, and send the result to each other. They then each perform one more operation on the received number with their secret key. If you compare the two resulting values, and they match, then you've established trust and can communicate using the resulting key. This is safe since the primes are so large and the computational complexity is so high, it'd be infeasible to break them in the lifetime of the connection. However, to save a bit of time, rather than calculating a new very large prime every time, much software just had "built-in" primes (512-bit and 1024-bit numbers) and relied on the secret keys to provide security. A recent paper proved that with breakthroughs in algorithms and a huge budget, reusing primes wasn't safe. The authors showed that for a known 512-bit prime, with a week of precomputation on a computing cluster, they could break subsequent connections using that prime in about one minute. Extrapolating their results to 1024-bit primes, they estimated to "break one prime per year" would cost on the order of $200M - $300M in hardware, which is well within the budget of the NSA who spend about 5x that amount annually on crypto programs and more than 50x annually for their entire budget. They then examined a bunch of public VPN networks and saw that in their estimation, about 66% use one of two 1024-bit primes. So if the NSA had been running their 1024-bit prime-breaker for two years and had precomputed the groups for the two most popular primes, breaking each subsequently 'secure' connection would take about 30 core-days or a matter of seconds for someone with the budget of the NSA.
- benten10 11y ago
  I suspect (or wish, rather) that this is likely not what happened. I imagine this suit over at NSA, who probably started from a technical background. Couple of guys from a project team tell him they can break significant portions VPN connections, for $400M (because govt). All they need is to break a couple of primes. He thinks for a couple of days. He asks what happens if someone changes the primes. Silence. Someone says processing power will have made cracking further primes much easier in the future. "But the size of primes will have grown too," he says. "Not this time guys, maybe someday." This reminds me of a link I found here a couple of days ago. 1 Euro for 4096 bits of Prime. Mmmmm. http://www.mappamathics.com/ http://www.mappamathics.com/
  - mikeyouse 11y ago
    Then the NSA suit realizes that changing a few primes would require massive bureaucratic organizations to coordinate and rewrite / upgrade software that's "in the wild" without a compelling financial incentive to do so and then he laughs maniacally. But seriously though, is there any doubt that the NSA would spend even 1/30th of their annual budget to intercept traffic that self-selects to be "more sensitive" than random internet noise. How much intel could you gather if you had 2/3 of the privileged conversations of companies, countries, and citizens who were explicitly trying to protect their communications? Even if the advantage only lasted a few years, it'd be an absolute gold mine. Not that it needs to be though, there isn't exactly a Board of Directors ensuring that the NSA investments meet certain returns. Cool link for the primes though, that's a pretty clever idea.
  - abraae 11y ago
    Cool idea! But I (perhaps overly suspiciously) wonder if they would be tempted to mine just a few prime numbers, then sell them over and over. They state "For the standard ordering process, we don’t guarantee that the prime numbers are unique."

See the original article: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/ https://freedom-to-tinker.com/blog/haldermanheninger/how-is-...

mikeyouse 11y ago

From micaeked's link; For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn’t just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime. I'm not an expert by any stretch, but this is my understanding; For a client and server to communicate securely, they can exchange crypto keys publicly via Diffie-Hellman. D-H relies on a very large prime number and a second smaller prime, both of which can be broadcast publicly. The two clients add their own secret key to the primes, perform an operation, and send the result to each other. They then each perform one more operation on the received number with their secret key. If you compare the two resulting values, and they match, then you've established trust and can communicate using the resulting key. This is safe since the primes are so large and the computational complexity is so high, it'd be infeasible to break them in the lifetime of the connection. However, to save a bit of time, rather than calculating a new very large prime every time, much software just had "built-in" primes (512-bit and 1024-bit numbers) and relied on the secret keys to provide security. A recent paper proved that with breakthroughs in algorithms and a huge budget, reusing primes wasn't safe. The authors showed that for a known 512-bit prime, with a week of precomputation on a computing cluster, they could break subsequent connections using that prime in about one minute. Extrapolating their results to 1024-bit primes, they estimated to "break one prime per year" would cost on the order of $200M - $300M in hardware, which is well within the budget of the NSA who spend about 5x that amount annually on crypto programs and more than 50x annually for their entire budget. They then examined a bunch of public VPN networks and saw that in their estimation, about 66% use one of two 1024-bit primes. So if the NSA had been running their 1024-bit prime-breaker for two years and had precomputed the groups for the two most popular primes, breaking each subsequently 'secure' connection would take about 30 core-days or a matter of seconds for someone with the budget of the NSA.

benten10 11y ago
I suspect (or wish, rather) that this is likely not what happened. I imagine this suit over at NSA, who probably started from a technical background. Couple of guys from a project team tell him they can break significant portions VPN connections, for $400M (because govt). All they need is to break a couple of primes. He thinks for a couple of days. He asks what happens if someone changes the primes. Silence. Someone says processing power will have made cracking further primes much easier in the future. "But the size of primes will have grown too," he says. "Not this time guys, maybe someday." This reminds me of a link I found here a couple of days ago. 1 Euro for 4096 bits of Prime. Mmmmm. http://www.mappamathics.com/ http://www.mappamathics.com/
- mikeyouse 11y ago
  Then the NSA suit realizes that changing a few primes would require massive bureaucratic organizations to coordinate and rewrite / upgrade software that's "in the wild" without a compelling financial incentive to do so and then he laughs maniacally. But seriously though, is there any doubt that the NSA would spend even 1/30th of their annual budget to intercept traffic that self-selects to be "more sensitive" than random internet noise. How much intel could you gather if you had 2/3 of the privileged conversations of companies, countries, and citizens who were explicitly trying to protect their communications? Even if the advantage only lasted a few years, it'd be an absolute gold mine. Not that it needs to be though, there isn't exactly a Board of Directors ensuring that the NSA investments meet certain returns. Cool link for the primes though, that's a pretty clever idea.
- abraae 11y ago
  Cool idea! But I (perhaps overly suspiciously) wonder if they would be tempted to mine just a few prime numbers, then sell them over and over. They state "For the standard ordering process, we don’t guarantee that the prime numbers are unique."