[Cryptography] Fwd: freedom-to-tinker.com: How is NSA breaking so much crypto?

Peter Fairbrother peter at m-o-o-t.org
Fri Oct 16 18:26:43 EDT 2015

On 16/10/15 15:39, Peter Gutmann wrote:
> Dan McDonald <danmcd at kebe.com> writes:
>> I also wonder how long it'll be until it works with 1536-bit modulii or
>> larger.
> Anything above 1024 bits is safe for some time yet.

Unless NSA has built asics ..

I gotta repost this, first posted here 09 June. Not so much a 
told-you-so (though it is :) but.. the paper seems to have been 
rewritten, but it's the same paper. The last part of the post is 
particularly apposite:

Not all that new,  but I haven't seen any comment here.

Logjam attack, and the state-level attacks mentioned in the logjam 
paper. https://weakdh.org/

Logjam, like FREAK, degrades crypto suites, in this case TLS DH to 
512-bit "export grade" crypto. It's a bit more sophisticated than FREAK, 
but not much.

7th principle: Holes for "good guys" are holes for bad guys too.

8th principle: In code, nothing ever really goes away.

(big nod to Jerry Leichter)

More controversial, and quite possibly more damaging, is this:

"Threats from state-level adversaries.

Millions of HTTPS, SSH, and VPN servers all use the same prime numbers 
for Diffie-Hellman key exchange. Practitioners believed this was safe as 
long as new key exchange messages were generated for every connection.

However, the first step in the number field sieve — the most efficient 
algorithm for breaking a Diffie-Hellman connection — is dependent only 
on this prime. After this first step, an attacker can quickly break 
individual connections.


A close reading of published NSA leaks shows that the agency's attacks 
on VPNs are consistent with having achieved a break [of the single, most 
common 1024-bit prime]."

I wonder whether the "state level threat" of breaking common 1024-bit DH 
primes is the "major breakthrough" which NSA told Congress about a few 
years ago, for which they got all that lovely extra money.

If so, the people who in 2013 were supporting the idea of replacing 
2048-bit RSA with ubiquitous 1024-bit DH in order to provide FS look a 
bit silly ..

[ the major browsers supported 1024-bit DH but 2048-bit RSA, perhaps due 
to people mistakenly thinking that DH keys needed to be half the size of 
RSA keys - it might be interesting to see where that rumour came from.

To quote Peter Gutmann, posting here:

"It's a debate between two groups, the security practitioners, "we'd 
like a PFS solution as soon as we can, and given currently-deployed 
infrastructure DH-1024 seems to be the best bet", and the theoreticians, 
"only a theoretically perfect solution is acceptable, even if it takes 
us forever to get it"." ]

.. as the only people who could even partially break 2048-bit RSA were 
the major agencies (gimme the private keys sunshine, or go to jail), the 
same ones who could almost universally break 1024-bit DH, but without 
the hassle of warrants or anyone else knowing about it ..

By the way, this was just after Snowden, when Google and the like were 
moving to 2048-bit RSA, and other people were running around like 
headless chickens saying "we must do something".

NSA must have been laughing all the way to the bank.

-- Peter Fairbrother

More information about the cryptography mailing list