[Cryptography] Opening Discussion: Speculation on "BULLRUN"

[Jerry Leichter]

On Sep 6, 2013, at 8:58 PM, Jon Callas wrote:
>>  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....
> 
> We know as a mathematical theorem that a block cipher with a back door *is* a public-key system.
I'm sorry, but this is just nonsense.  You're starting with informal, rough definitions and claiming a mathematical theorem.

> It is a very, very, very valuable thing, and suggests other mathematical secrets about hitherto unknown ways to make fast, secure public key systems. 
I said all this before.  A back door doesn't have to be fast.  It doesn't have to be implementable using amounts of memory that are practical for a fielded system.  It may require all kinds of expensive pre-computation to be useful at all.  It just has to allow practical attacks.  A back door that reduced the effective key size of AES to 40 bits would amount to an effective break of AES, but would be "a public key system" only in some very technical and uninteresting sense.

And none of this is relevant to whether one could have a system with many weak keys.  Some kind of structure in the round computation structure would be an obvious place to look.

In fact, now that I think of it, here's a rough example of such a system:  Take any secure round-based block cipher and decide that you're not going to use a round computation at all - you'll let the user specify the full expanded per-round key.  (People proposed doing this with DES as a way of getting beyond the 56-bit key size.  It didn't work - DES is inherently good for no more than 56 bits, more or less.  In general doing this with any decent block cipher won't make it any stronger.  But that's not the point of the example.)  There are now many weak keys - all kinds of repetitive structures allow for slide attacks, for example.  Every bad way of designing a round computation corresponds to a set of weak full keys.  On the other hand, for a certain subset of the keys - those that could have been produced by the original (good) round computation - it's *exactly* the original cipher, with *exactly* the original security guarantees.  If I carefully use only keys from that set, I've lost nothing (other than wasted space for a key longer than it needs to be).

So now I have a block cipher that has two sets of keys.  One set makes it as secure as the original cipher; one set makes it easy to break - my back door.  Have I just invented a new public key system?
                                                        -- Jerry