[Discuss] NSA capabilities

[tmetro+blu at gmail.com (Tom Metro)]

[please update the subject; it has nothing to do with KeePassX]

Richard Pieri wrote:
> I assert that the NSA have compromised the public CAs just as they have
> compromised the service providers.

Plausible.


> Certificate + handshake = session key => decrypted session in real time.
> Any user, any session, any time, any reason. No cryptanalysis needed. No
> brute force needed.

I haven't looked at reference material to refresh my understanding on
this, so it may be wrong, but my recollection is that a CA compromise
would only facilitate man-in-the-middle attacks.

The CA is there to sign the customer's public key. I don't think this
necessitates that the CA generate the key-pair or have possession of the
private key. A quick Google confirms this:

http://www.sslshopper.com/what-is-a-csr-certificate-signing-request.html

  A CSR or Certificate Signing request is a block of encrypted text that
  is generated on the server that the certificate will be used on. ... A
  private key is usually created at the same time that you create the
  CSR. ... A certificate authority will use a CSR to create your SSL
  certificate, but it does not need your private key. You need to keep
  your private key secret.

So an NSA agent possessing the CA root could generate a new key pair,
sign it with the CA key, and impersonate any server using that
authority. This could then be used as part of a man-in-the-middle
attack, where you think you are connecting to https://gmail.com/, but
actually you're conversing with an NSA proxy.

Given that most users are unaware of CA changes at sites they visit, the
NSA really only needs one CA root from a common CA and they could
generate impersonation certs at will. (Some "unified threat management"
appliances (a.k.a. corporate proxy servers) do this.)

But these impersonation certs don't help them recover the session key
for a captured SSL session. The NSA could still issue a security letter
to the server owner, and get the private key that way, but that
constrains them much more that what you alluded to.

(Undoubtedly there are CAs who, as a matter of convenience, generate the
key pair, and could be compelled by the NSA to retain the private key. I
believe when I generated a cert for S/MIME at StartSSL they generated
the key pair. Some CAs use browser side tech - ActiveX or JS - to
generate the key. Clearly your best bet is to use known and trusted open
source tool to generate the key pair on your own machine, and only
submit a CSR to the CA.)


> The more that is encrypted, the more known text the NSA has available
> for side-channel attacks. The more that is encrypted, the more
> chances of a hash collision occurring or a pseudo-random key being
> reused. Scaling up works in the NSA's favor...

This strikes me as a wild assertion and I don't follow the logic.
References?

Superficially, it sounds like it could be right, as we've all heard of
attack vectors that make use of known plain text. But the NSA doesn't
*know* what is in a given document.

I could see this applying in subsets if cases. For example, say two
businesses start encrypting their email exchanges. The NSA knows from
past history of captured communications between two parties that their
plaintext includes a bunch of fixed form fields. The unencrypted
metadata clues in the NSA as to who is communicating, and they can then
use the historical known plaintext to mount an attack.

This is only going to help break a session key. I'm not sure this
approach is of any help in breaking asymmetric keys.

If amassing plaintext and corresponding encrypted text was really all
that useful, the NSA could generate warehouses full of it themselves.
The algorithms in use are almost always well known. The only thing
real-life examples buy them is if someone was generating gobs of
encrypted data for a known plaintext using the same session key.


> ...more chances...a pseudo-random key being reused

Yeah, but why is that useful? If a repeat[1] occurs every 2^64, and you
send a high volume of messages, that means the NSA will be able to
decrypt 2 messages out of 18,446,744,073,709,551,615 messages. That's
assuming they've brute forced one to begin with.

1. http://en.wikipedia.org/wiki/Pseudorandom_number_generator#Periodicity


> ...of a hash collision occurring...

That depends on the algorithm, of course. SHA-1 is popular and used in
S/MIME. It has an estimated theoretical collision[2,3] probability of
about 2^60 or 1.15e+18. Is that going to be impacted by a few billion
people sending a few trillion encrypted documents per year? At that rate
you'd see a collision once every ~1 million years (1.15e18/1e12).

If you don't feel comfortable with this, use SHA-2.

2. http://en.wikipedia.org/wiki/SHA-1#Attacks
3.
http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions#Cryptanalysis


I think Kent Borg is following solid reasoning when he says that
encrypting everything will increase costs for the NSA to the point that
the chance that your data gets looked at by some automated process will
be reduced by several orders of magnitude, unless metadata leads them to
focus on you. Encryption is cheap, but still requires enough effort that
hardly anyone will use it, so this is sort of a moot point. (Though we
could alter that behavior by making encryption be the default in
products we develop or deploy.)

On the upside, it is said that the NSA will be more inclined to retain
data that is encrypted, as it raises suspicion, so you've got a free
backup service. :-)

 -Tom

-- 
Tom Metro
Venture Logic, Newton, MA, USA
"Enterprise solutions through open source."
Professional Profile: http://tmetro.venturelogic.com/