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
