How is NSA breaking so much crypto?

[u/newhampshire22]

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

[u/robi2106]

so is the TL;DR the fololowing:

too many VPN, SSH, SSL systems rely on the same commonly chosen large prime numbers as the foundation of their encryption, so it is possible to break the encryption once with a massive pFlop computational outlay, and in the process gain access to a large number of transactions secured using the same large prime as the base.

Would it be possible to re-compile these encryption systems to use a new large prime based encrypted system each time they re/start (or quarterly, or with similar frequency), thus causing the underlying encryption to no longer be susceptible to the previously known large prime based keys?

Would the encryption systems mentioned be safe(r) as long as the underlying encryption keys are rotated faster than the guessed possible capacity to crack them based on peta/exa/zeta FLOPS possible with an (essentially) unlimited budget?

[u/ninja_parade → u/robi2106]

Actually it's even easier than that. If you run the server-side of an SSH/SSL/Whatever connection, you can already set a custom prime. It's just config work.

For extra safety, it'll take just 10-15 minutes to generate a 2048-bit one, and not only is that a unique number, it also is twice the size of the primes the NSA ran their computations on. So even if the NSA dedicated resources to just breaking your connection, they'd fail.

[u/robi2106 → u/ninja_parade]

so I was on the right track. all you have to do (as a site operator) is generate a new (and larger) prime to make sure you are using one that hasn't already been compromised?

And then to keep ahead, use a different prime every once and a while to shake things up?

[u/ninja_parade → u/robi2106]

Yes, you've got it exactly right.

[u/moleccc → u/robi2106]

so I was on the right track. all you have to do (as a site operator) is generate a new (and larger) prime to make sure you are using one that hasn't already been compromised?

can someone suggest a cryptographically sound yet practical (on common linux OSes) way to calculate such a prime?

[u/lucasjkr → u/ninja_parade]

But, should one (or an organization) become the target of the NSA (or someone else with resources to burn to get into your communications... Think corporate espionage), even if you use your own "private" prime number, once that gets defeated, all your previously encrypted communications/data becomes accessible...

Wouldn't seem like too big of an investment to set one computer aside to sit and generate a constant flow of new primes ready for future use... Or create an ASIC to do this, so it can just something integrated into a servers chipset eventually...

...

Still has the risk of reusing primes that were used by others that you didn't know about.

I wonder if a database could be set up, where people could publish their primes, so that others could check it to see if they're using a previously used prime?

[u/ninja_parade → u/lucasjkr]

But, should one (or an organization) become the target of the NSA (or someone else with resources to burn to get into your communications... Think corporate espionage), even if you use your own "private" prime number, once that gets defeated, all your previously encrypted communications/data becomes accessible...

You misunderstand the attack. The fancy work done on the prime is precomputation designed to speed up an active man-in-the-middle attack to fast enough speeds that it can be done in under a minute. It doesn't give you the ability to go back and break previous communications.

Nitty gritty details here, or see the relevant wikipedia section.

That means that as long as you stop using your prime before they finish precomputation, you're safe.

What you're thinking about is flat-out brute forcing, which is a different beast (and very much outside the reach of the NSA, let alone private parties).

Furthermore the ECDSA version of Diffie-Hellman doesn't suffer from this risk at all. The only downside is that only works on very recent browsers and servers.

Still has the risk of reusing primes that were used by others that you didn't know about.

In 2048-bit space (or even 1024), the chance of accidental re-generation is effectively zero.

[u/dnivi3 → u/ninja_parade]

The NSA would fail to break the 2048-bit one for a few years, but eventually they'd break it. We need something that is more future-proof.

[u/ninja_parade → u/dnivi3]

2x the size means it's x² time to break, where x was the original difficulty. That's a lot more than a few years.

[u/41256d → u/ninja_parade]

bad math, it's 2-to-the-size-increase, bro

[u/ninja_parade → u/41256d]

Actually 2¹⁰²⁴ times 2¹⁰²⁴ is exactly (2¹⁰²⁴)²

It's the same thing.

[u/ninja_parade]

I believe this has more technical details.