[Cryptography] Impossible trapdoor systems (was Re: Opening Discussion: Speculation on "BULLRUN")

Perry E. Metzger perry at piermont.com
Sun Sep 8 14:49:53 EDT 2013


On Sat, 07 Sep 2013 20:14:10 -0700 Ray Dillinger <bear at sonic.net>
wrote:
> On 09/06/2013 05:58 PM, Jon Callas wrote:
> 
> > We know as a mathematical theorem that a block cipher with a back
> > door *is* a public-key system. 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've seen this assertion several times in this thread, but I cannot
> help thinking that it depends on what *kind* of backdoor you're
> talking about, because there are some cases in which as a crypto
> amateur I simply cannot see how the construction of an asymmetric
> cipher could be accomplished.
> 
> As an example of a backdoor that doesn't obviously permit an
> asymmetric-cipher construction, consider a broken cipher that
> has 128-bit symmetric keys; but one of these keys (which one
> depends on an IV in some non-obvious way that's known to the
> attacker) can be used to decrypt any message regardless of the
> key used to encrypt it.

That key would then be known as the "private key". The "public key"
is the set of magic values used in the symmetric cipher (say in the
one way functions of the Feistel network if it were a Feistel cipher)
such that such a magic decryption key exists.

> However, it is not a valid encryption key; no matter what you
> encrypt with it you get the same ciphertext.

So? If you have an algorithm that creates such ciphers in such a way
that the magic key is hard to find, then you produce all that you want
and you have a very powerful primitive for constructing public key
systems. You don't have an obvious signature algorithm yet, but I'm
sure we can think of one with a touch of cleverness.

That said, your hypothetical seems much like "imagine that you can
float by the power of your mind alone". The construction of such a
cipher with a single master key that operates just like any other key
seems nearly impossible, and that should be obvious.

A symmetric cipher encryption function is necessarily one-to-one and
onto from the set of N bit blocks to itself. After all, if two blocks
encrypt to the same block, you can't decrypt them, and one block
can't encrypt to two blocks. If every key produces the same function
from 2^N to 2^N, it will be rapidly obvious, so keys have to produce
quite different mappings.

Your magic key must then take any block of N bits and magically
produce the corresponding plaintext when any given ciphertext
might correspond to many, many different plaintexts depending
on the key. That's clearly not something you can do.

Perry
-- 
Perry E. Metzger		perry at piermont.com


More information about the cryptography mailing list