🚀 go-pugleaf

In article <1992Nov19.150019.19072@news.nd.edu>, scharle@lukasiewicz.cc.nd.edu
(scharle) writes:
| || The recently demonstrated fact that DES is *not* a group indicates that
| || a double encryption *is* stronger than single encryption.
| 
|     Excuse me, for I am really an amateur in this subject, but I
| don't see the chain of reasoning here.  If I am just being particularly
| dense, please keeps the flames low, and I'll shut up.
| 
|     What has been shown is that iteration of DES with different keys 
| results, in general, in encryption which is different from DES.  I 
| believe that that is different from showing that iteration results
| in something _stronger_.  As far as I can see, it is consistent
| with someone discovering that two applications of DES could result
| in a encryption which is in fact easier to break -- for example,
| there could be some interaction between keys, that would result in
| an easy cipher to break, so that there would have to be some care
| in choosing keys.  It is also consistent with it being discovered
| that iterations of DES are _equally_ difficult to break as single 
| uses, perhaps just a different method has to be used.

This situation provides an excellent way to demonstrate a fundamental
approach for reasoning about cryptosystems.

Can double DES encryption be weaker than single DES encryption?  The
answer is, in general, no - and I can prove this knowing nothing at all
about DES.

Suppose it were true that double encryption was weaker, and suppose I'm
a cryptanalyst with access to E(C,k), where E is DES encryption, C is
cleartext, and k is the unknown key.  Rather than attack the "hard"
problem of single DES encryption, I'd simply choose my own k' and do my
own double encryption:  I'd attack the "easier" encryption E(E(C,k),k').
It cannot possibly hurt me that I *know* k'!

Conclusion:  While it may be that for SOME values of k', some kind of
cancellation takes place, if they are at all common, then SINGLE DES
encryption is *already* weak, since looking for such a k' would amount
to an easy attack against it.

General principle:  Anything the cryptanalyst can already do for himself
cannot weaken the cryptosystem significantly - since if it did, he WOULD
do it for himself.

Note that this approach cannot prove that double encryption is HARDER to
break than single encryption - it can only show that it cannot be EASIER.
Whether DES forms a group or not, it is possible that double encryption is
stronger, and it's possible that double encryption is equally strong.
Without further work, we just don't know.  (Actually, "meet in the middle"
attacks show that double encryption, done this way, cannot be MUCH stronger
than single encryption - though it may be SOMEWHAT stronger.)

							-- Jerry