[Cryptography] NSA and cryptanalysis

[John Kelsey]

What I think we are worried about here are very widespread automated attacks, and they're passive (data is collected and then attacks are run offline).  All that constrains what attacks make sense in this context.  You need attacks that you can run in a reasonable time, with minimal requirements on the amount of plaintext or the specific values of plaintext.  The perfect example of an attack that works well here is a keysearch on DES; another example is the attack on WEP.

All the attacks we know of on reduced-round AES and AES-like ciphers require a lot of chosen plaintexts, or related key queries, or both.  There is no way to completely rule out some amazing new break of AES that makes the cipher fall open and drop your plaintext in the attacker's lap, but I don't see anything at all in the literature that supports that fear, and there are a *lot* of smart people trying to find new ways to attack or use AES-like designs.  So I put this at the bottom of my list of likely problems.

Some attacks on public key systems also require huge numbers of encryptions or specially formed ciphertexts that get sent to the target for decryption--we can ignore those for this discussion.  So we're looking at trying to factor an RSA modulus or to examine a lot of RSA encryptions to a particular public key (and maybe some signatures from that key) and try to get somewhere from that.  I don't know enough about the state of the art in factoring or attacking RSA to have a strong intuition about how likely this is.  I'm pretty skeptical, though--the people. know who are experts in this stuff don't seem especially worried.  However, a huge breakthrough in factoring would make for workable passive attacks of this kind, though it would have to be cheap enough to use to break each user's public key separately.  

Finally, we have the randomness sources used to generate RSA and AES keys.  This, like symmetric cryptanalysis, is an area I know really well.  And my intuition (backed by plenty of examples) is that this is probably the place that is most likely to yield a practical offline attack of this kind.  When someone screws up the implementation of RSA or AES, they may at least notice some interoperability problems.  They will never notice this when they screw up their implementation so that RNG only gets 32 bits of entropy before generating the user's RSA keypair.  And if I know that your RSA key is likely to have one of these 2^{32} factors, I can make a passive attack work really well.  

Comments?

--John