[Cryptography] Can you backdoor a symmetric cipher (was Re: Opening Discussion: Speculation on "BULLRUN")

[Jon Callas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sep 5, 2013, at 9:33 PM, "Perry E. Metzger" <perry at piermont.com> wrote:

> 
> It is probably very difficult, possibly impossible in practice, to
> backdoor a symmetric cipher. For evidence, I direct you to this old
> paper by Blaze, Feigenbaum and Leighton:
> 
> http://www.crypto.com/papers/mkcs.pdf
> 

There is also a theorem somewhere (I am forgetting where) that says that if you have a block cipher with a back door, then it is also a public key cipher. The proof is easy to imagine -- whatever trap door lets you unravel the cipher is the secret key, and the block cipher proper is a PRF that covers the secret key. I remember the light bulb going on over my head when I saw it presented.

So if you have a backdoored symmetric cipher, you also have a public key algorithm that runs five orders of magnitude faster than any existing public key algorithm.

This suggests that such a thing does not exist. We have a devil of a time making public key systems that actually work. Look at all we've talked about with brittleness of the existing ones, and how none of the alternatives (Lattice, McElice, etc.) are really any better and most of those are really only useful in a post-quantum world. It doesn't prove it, but it suggests it.

The real question there is whether someone who had such a thing would want to be remembered by history as the inventor of the most significant PK system the world has ever seen, or a backdoored cipher.

	Jon



-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii

wj8DBQFSKV02sTedWZOD3gYRAnK5AJ9aB8I0csP1ryW6aaXEqMPOyL31PwCfZuUs
swH73+Zqwqy4ZFeD7QjWoyM=
=BnW3
-----END PGP SIGNATURE-----