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

Jerry Leichter leichter at lrw.com
Fri Sep 6 07:08:38 EDT 2013

>> 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 find 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

More information about the cryptography mailing list