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 
  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; a
 nd 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

The cryptography mailing list

Reply via email to