[Cryptography] NSA and cryptanalysis

[Eugen Leitl]

----- Forwarded message from Jerry Leichter <leichter at lrw.com> -----

Date: Sun, 1 Sep 2013 07:11:06 -0400
From: Jerry Leichter <leichter at lrw.com>
To: Peter Gutmann <pgut001 at cs.auckland.ac.nz>
Cc: crypto.jmk at gmail.com, die at dieconsulting.com, "cryptography at metzdowd.com List" <cryptography at metzdowd.com>
Subject: Re: [Cryptography] NSA and cryptanalysis
X-Mailer: Apple Mail (2.1283)

On Sep 1, 2013, at 2:36 AM, Peter Gutmann wrote:

> John Kelsey <crypto.jmk at gmail.com> writes:
> 
>> If I had to bet, I'd bet on bad rngs as the most likely source of a
>> breakthrough in decrypting lots of encrypted traffic from different sources.
> 
> If I had to bet, I'd bet on anything but the crypto.  Why attack when you can
> bypass [1].
Well, sure.  But ... I find it hard to be quite so confident.

In practical terms, the vast majority of encrypted data in the world, whether in motion or at rest, is protected by one of two algorithms:  RSA and AES.  In some cases, RSA is used to encrypt AES keys, so an RSA break amounts to a bypass of AES.  If you want to consider signatures and authentication, you come back to RSA again, and add SHA-1.

This is not to say there aren't other techniques out there, or that new ones aren't being developed.  But to NSA it's clearly a game of numbers - and any kind of wedge into either of just two algorithms would expose huge amounts of traffic to interception.

Meanwhile, on the authentication side, Stuxnet provided evidence that the secret community *does* have capabilities (to conduct a collision attacks) beyond those known to the public - capabilities sufficient to produce fake Windows updates.  And recent evidence elsewhere (e.g., using a bug in the version of Firefox in the Tor Browser Bundle) has shown an interest and ability to actively attack systems.  (Of course, being able to decrypt information without an active attack is always the ideal, as it leaves no traces.)

I keep seeing statements that "modern cryptographic algorithms are secure, don't worry" - but if you step back a bit, it's really hard to justify such statements.  We *know*, in a sense, that RSA is *not* secure:  Advances in factoring have come faster than expected, so recommended key sizes have also been increasing faster than expected.  Most of the world's sites will always be well behind the recommended sizes.  Yes, we have alternatives like ECC, but they don't help the large number of sites that don't use them.

Meanwhile, just what evidence do we really have that AES is secure?  It's survived all known attacks.  Good to know - but consider that until the publication of differential cryptanalysis, the public state of knowledge contained essentially *no* generic attacks newer than the WW II era attacks on Enigma.  DC, and to a lesser degree linear cryptanalysis not long after, rendered every existing block cipher (other than DES, which was designed with secret knowledge of DC) obsolete in one stroke.  There's been incremental progress since, but no breakthrough of a similar magnitude - in public.  Is there really anything we know about AES that precludes the possibility of such a breakthrough?

There's a fundamental question one should ask in designing a system:  Do you want to protect against targeted attacks, or do you want to protect against broad "fishing" attacks?

If the former, the general view is that if an organization with the resources of the NSA wants to get in, they will - generally by various kinds of bypass mechanisms.

Of the latter, the cryptographic monoculture *that the best practices insist on* - use standard protocols, algorithms and codes; don't try to invent or even implement your own crypto; design according to Kirchoff's principle that only the key is secret - are exactly the *wrong* advice:  You're allowing the attacker to amortize his attacks on you with attacks on everyone else.

If I were really concerned about my conversations with a small group of others being intercepted as part of dragnet operations, I'd design my own small variations on existing protocols.  Mix pre-shared secrets into a DH exchange to pick keys.  Use simple steganography to hide a signal in anything being signed - if something shows up signed without that signal, I'll know (a) it's not valid; (b) someone has broken in.  Modify AES in some way - e.g., insert an XOR with a separate key between two rounds.  A directed attack would eventually break all this, but generic attacks would fail.  (You could argue that the failure of generic attacks would cause my connections to stand out and thus draw attention.  This is, perhaps, true - it depends on the success rate of the generic attacks, and on how many others are playing the same games I am.  There's no free lunch.)

It's interesting that what what little evidence we have about NSA procedures - from the design of Clipper to Suite B - hints that they deploy multiple cryptosystems tuned to particular needs.  They don't seem to believe in a monoculture - at least for themselves.
                                                        -- Jerry

_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5