what has the NSA broken?

[Andy Isaacson]

Tinfoil hat time ...

http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security

With today's disclosures, the question turns to -- what has the NSA
broken?  Unfortunately the journalists bowed to pressure from the
espionage-industrial complex and decided not to publish specific
details of what's broken; and the Snowden documents don't include all
the compartmentalized details anyways.  So all we can do is speculate
based on what is already known and the high level overview provided.

I don't believe that NSA has a complete AES break.  Call me foolish if
you must, but it's just not consistent with what we know so far.  I
believe that a correctly implemented, truly randomly keyed AES-256-CBC
or -CTR cipher is robust against cryptanalysis.  It seems just barely
possible that AES-128 has a complete break, since I suspect NSA can do
2^80 work on 2^60 bytes if it gives them decrypts of all the AES-128
they can sniff.

However, virtually nobody properly keys their ciphers with physical
entropy.  I suspect that correlated key PRNG attacks are almost
certainly a significant part of the NSA/GCHQ crypto break.  Many
deployed systems expose a significant amount of correlated output of
/dev/urandom or the in-process PRNG.  Given a global passive adversary
and serveral TFLOPs of built-to-spec supercomputers [1], this seems like
an obvious place for a hidden advance.

Also, retrieving key material from endpoints is a high return activity.
Nearly nobody uses PFS ciphersuites, many HTTPS privatekeys are used for
multiple years, and a single 1 KiB leak of key material is sufficient to
decrypt all traffic under that key.  (You don't even need the whole key,
just half the bits are plenty to reconstruct RSA keys using attacks in
the open literature.)  Insiders copying privatekey files after hours,
DRAM remanence after "hardware failure" in SSL offload boxes, bugdoors
leaking key bits in subtly biased entropy from crypto accelerator
hardware, on-disk encrypted keys decrypted due to low entropy
passphrases, etc.  Any key stored on a US-based VPS is obviously
compromised.  (Doubly so if your VPS is linode.)  Radio emissions from
colocated boxes are a nearly completely unexplored area of research.
Server-class IPMI baseboard coprocesssors have undisclosed access to
host RAM at runtime, and often unaudited access via provider
management-plane Ethernets.  If I had to get the keys out deniably, I'd
be scanning RAM for high entropy key schedules and leaking key bits in
the timing of heartbeat messages.

It seems fairly likely that NSA is at least a decade ahead of academic
RSA factoring.  I've heard second-hand stories of $10M machines of
custom ASICs built to attack RSA before 2005, and third-hand stories of
machines far weirder than that.  RSA-1024 I'd treat as dead, RSA-2048 is
probably robust enough that if NSA have an attack it would be too
valuable to risk exposing under anything but an existential threat
scenario.

Non-AES legacy/proprietary ciphers are probably toast.  People switching
to RC4, stahp!  A5/2, lulz.  Maybe GOST and twofish and Salsa20 are
secure; I've met djb and all my checks for NSA minders came up negative.

[1] Cray is still in business, building 10,000 CPU with attached FPGA
    and 1µs interconnect megaclusters for "undisclosed government
    customers".  The systems listed as "Government" in the latest top500
    list are just the tip of the iceberg; larger systems are built and
    installed without any public disclosure.

-andy