[Cryptography] Opening Discussion: Speculation on "BULLRUN"

[Jerry Leichter]

On Sep 7, 2013, at 12:31 AM, Jon Callas wrote:
>> I'm sorry, but this is just nonsense.  You're starting with informal, rough definitions and claiming a mathematical theorem.
> 
> Actually, I'm doing the opposite. I'm starting with a theorem and arguing informally from there....
Actually, if you look at the papers cited, *they* are themselves informal.  The fundamental thing they are lacking is a definition of what would constitute a "master key".  Let's see if we can formalize this a bit:

We're given a block cipher E(K,P) and a corresponding decryption algorithm D(K,C).  The system has a master key M such that D(E(K,P),M) == P.  This is what a "master key" does in a traditional lock-and-key system, so unless we see some other definition, it's what we have to start with.  Is there such a system?  Sure, trivially.  Given any block cipher E'/D', I simply define E(K,P) = E'(M,K) || E'(K,P).  (I can optimize the extra length by leaking one randomly chosen bit of E'(M,K) per block.  It won't take long for the whole key to be transmitted.)  OK, where's the public key system?

So maybe there isn't *one* master key, but let's go to the extreme and say there is one unique master per user key, based on some secret information S.  That is:  Given K, there is a function F(S,K) which produces a *different* key K', with the property that D(K,C) == D(K',C).  Or maybe, as in public key systems, you start with S and some random bits and produce a matched pair K and K'  But how is this a "master key" system?  If I wasn't "present at the birth" of the K that produced the cyphertext I have in hand ... to get K' now, I need K (first form) or S and the random bits (second form), which also gives me K directly.  So what have I gained?

I can construct a system of the first form trivially:  Just use an n-bit key but ignore the first bit completely.  There are now two keys, one with a leading 0, one with a leading 1.  Constructing a system of the second form shouldn't be hard, though I haven't done it.  In either case, it's uninteresting - my "master key" is as hard to get at as the original key.

I'm not sure exactly where to go next.  Let's try to modify some constraints.  Eliminate directly hiding the key in the output by requiring that E(K,.) be a bijection.  There can't possibly be a single master key M, since if there were, what could D(M,E(M,0...0)) be?  It must be E(K,0...0) for any possible K, so E(K,0...0) must be constant - and in fact E must be constant.  Not very interesting.  In fact, a counting argument shows that there must be as many M's as there are K's.  It looks as we're back to the two-fold mapping on keys situation.  But as before ... how could this work?

In fact, it *could* work.  Suppose I use a modified form of E() which ignores all but the first 40 bits of K - but I don't know that E is doing this.  I can use any (say, 128-bit) key I like, and to someone not in on the secret, a brute force attack is impossible.  But someone who knows the secret simply sets all but the first 40 bits to 0 and has an easy attack.

*Modified forms (which hid what was happening to some degree) of such things were actually done in the days of export controls!*  IBM patented and sold such a thing under the name CDMF (http://domino.research.ibm.com/tchjr/journalindex.nsf/600cc5649e2871db852568150060213c/a453914c765e690085256bfa0067f9f4!OpenDocument).  I worked on adding cryptography to a product back in those days, and we had to come up with a way to be able to export our stuff.  I talked to IBM about licensing CDMF, but they wanted an absurd amount of money.  (What you were actually paying for wasn't the algorithm so much as that NSA had already approved products using it for export.)  We didn't want to pay, and I designed my own algorithm to do the same thing.  It was a silly problem to have to solve, but I was rather proud of the solution - I could probably find my spec if anyone cares.  It was also never implemented, first because this was right around the time the crypto export controls got loosened; and second because we ended up deciding we didn't need crypto anyway.  We came back and did it very differently much later.  My two fun memories from the experience:  (a) Receiving a FAX from NSA - I still have it somewhere; (b) being told at one point that we might need someone with crypto clearance to work on this stuff with NSA, and one of my co-workers chiming in with "Well, I used to have it.  Unfortunately it was from the KGB."

Anyway ... yes, I can implement such a thing - but there's still no public key system here.

So ... would *you* like to take a stab at pinning down a definition relative to which the theorem you rely on makes sense?

                                                        -- Jerry