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
[email protected]
http://www.metzdowd.com/mailman/listinfo/cryptography
