[146636] in cryptography@c2.net mail archive
Re: [Cryptography] Can you backdoor a symmetric cipher (was Re:
daemon@ATHENA.MIT.EDU (Jon Callas)
Fri Sep 6 00:42:59 2013
X-Original-To: cryptography@metzdowd.com
From: Jon Callas <jon@callas.org>
In-Reply-To: <20130906003300.09060827@jabberwock.cb.piermont.com>
Date: Thu, 5 Sep 2013 21:42:29 -0700
To: "Perry E. Metzger" <perry@piermont.com>
Cc: Jerry Leichter <leichter@lrw.com>, cryptography@metzdowd.com,
Jon Callas <jon@callas.org>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Sep 5, 2013, at 9:33 PM, "Perry E. Metzger" <perry@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-----
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
