[Cryptography] Opening Discussion: Speculation on "BULLRUN"

[Ray Dillinger]

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.  However, it is not a valid encryption
key; no matter what you encrypt with it you get the same
ciphertext.

There's a second key (also known to the attacker, given the IV)
which is also an invalid key; it has the property that no
matter what you encrypt or decrypt, you get the same result
(a sort of hash on the IV).

How would someone construct an asymmetric cipher from this?
Or is there some mathematical reason why such a beast as the
hypothetical broken cipher I describe, could not exist?

Bear