[Cryptography] Opening Discussion: Speculation on "BULLRUN"

[Jerry Leichter]

Following up on my own posting:
> [The NSA] want to buy COTS because it's much cheap, and COTS is based on standards.  So they have two contradictory constraints:  They want the stuff they buy secure, but they want to be able to break in to exactly the same stuff when anyone else buys it.  [Y]ou have to explain how the goal in NSA's budget [of influencing the commercial crypto community to move in directions NSA can attack] could be carried out in a way consistent with the two constraints.
So here's a thought experiment for a particular approach:  Imagine that it's the case that half of all possible AES keys are actually "pseudo-weak", in the sense that if you use one of them, some NSA cryptanalytic technique can recover the rest of your key with "acceptable (to NSA)" effort.  Their attack fails for the other half of all possible keys.  Further, imagine that NSA has a recognizer for pseudo-weak keys.  Then their next step is simple:  Get the crypto industry to use AES with good, randomizing key generation techniques.  Make sure that there is more than one approved key generation technique, ideally even a way for new techniques to be added in later versions of the standard, so that approved implementations have to allow for a choice, leading them to separate key generation from key usage.  For the stuff *they* use, add another choice, which starts with one of the others and simply rejects pseudo-weak keys (or modifies them in some way to produce strong keys.)  Then:

- Half of all messages the world sends are open to attack by NSA until the COTS producers learn of the attack and modify their fielded systems;
- All messages NSA is responsible for are secure, even if the attack becomes known to other cryptanalytic services.

I would think NSA would be very happy with such a state of affairs.  (If they could arrange it that 255/256 keys are pseudo-weak - well, so much the better.)

Is such an attack against AES *plausible*?  I'd have to say no.  But if you were on the stand as an expert witness and were asked under cross-examination "Is this *possible*?", I contend the only answer you could give is "I suppose so" (with tone and body language trying to signal to the jury that you're being forced to give an answer that's true but you don't in your gut believe it).

Could an encryption algorithm be explicitly designed to have properties like this?  I don't know of any, but it seems possible.  I've long suspected that NSA might want this kind of property for some of its own systems:  In some cases, it completely controls key generation and distribution, so can make sure the system as fielded only uses "good" keys.  If the algorithm leaks without the key generation tricks leaking, it's not just useless to whoever grabs onto it - it's positively hazardous.  The gun that always blows up when the bad guy tries to shoot it....
                                                        -- Jerry