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 se
 t, 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

The cryptography mailing list

Reply via email to