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

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

The cryptography mailing list

Reply via email to