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

>> >> 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 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. Well, if that "someone" were the NSA, they might well be very happy to be remembered as the guy who made it possible break in to much of the world's communication! However, I find this argument unconvincing. It has the feel of a standard reduction, but isn't, because the reduction is to a known problem that's widely thought to be difficult - it's to a vaguely defined, broad class of problems, "designing a much faster public key system". Just because the construction gives you something like a public key system, doesn't mean if gives you anything practical for use that way. For example, suppose the master key works - but only for 1/2^k possible cleartext blocks, or even 1/2^k possible keys. This makes it useless as a public-key system even for very small k, but quite useful to an attacker even for larger k. Or suppose the master key works on all messages and keys, but is inefficient, requiring large amounts of time or memory, or the pre-computation of large lookup tables. Here's a thought experiment: Suppose differential cryptanalysis were known only to you, and you were in a position to influence the choice of S-boxes for a cryptosystem. Your "master key" would be the knowledge that DC would work very effectively against the system - but it would still require a lot of time and memory to do so. You'd even have a leg up on everyone else because you'd know the differentials to use up front - though that's a trivial advantage, since once you know to look for them, finding them is easy enough. In fact, as far as I know, no one has had any reason to pose questions like: Could you choose S-boxes that allow some kind of pre-computation step to make application of DC to messages much faster? DC requires gathering up a large number of plaintext/cyphertext pairs; eventually, you f ind examples of you can use. But could there be some way of producing pairs so that success is more likely to come earlier? Could it be that there's some pre-secret that allows computation both of those tables and and of the S-boxes, such that given only the S-boxes, finding the pre-secret and the tables isn't practical? Once DC was known and it was found the NSA had actually strengthened DES's S-boxes to protect against it, no one really looked into such issues - basically, who cared? If you really want to think in tin-hat terms, consider linear cryptanalysis. While DES was strong against DC, it was quite weak against LC. People interpreted this as meaning that NSA didn't know about LC. But ... maybe out in Area 51, or wherever Langley does work with alien technologies, they knew about LC *all along*, and *deliberately* made DES weak against it! (Why LC and not DC? Because as we subsequently learned from Don Coppersmith, DC was already known in the non-NSA community, and the NSA knew that it was known.) Please keep in mind that I'm not proposing that NSA actually did anything like this for any widely-used cryptosystem. I don't even see how they could have with respect to, say, AES, since they had no hand in the design of the algorithm or the choice of constants. The only thing I'm arguing here is that the "theorems" that say such a thing could never happen prove nothing of the sort. -- Jerry ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography

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

-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Sep 5, 2013, at 9:33 PM, "Perry E. Metzger" 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

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

On Thu, 5 Sep 2013 23:24:54 -0400 Jerry Leichter wrote: > They want to buy COTS because it's much cheap, and COTS is based on > standards. So they have two contradictory constraints: They want > the stuff they buy secure, but they want to be able to break in to > exactly the same stuff when anyone else buys it. The time-honored > way to do that is to embed some secret in the design of the > system. NSA, knowing the secret, can break in; no one else can. > There have been claims in this direction since NSA changed the > S-boxes in DES. For DES, we now know that was to protect against > differential cryptanalysis. No one's ever shown a really > convincing case of such an embedded secret hack being done ... but > now if you claim it can't happen, 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 Perry -- Perry E. Metzgerpe...@piermont.com ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography