NetNews Usenet Archive 1992 #23/NN_1992_23.iso/spool/sci/crypt/3793

Text File | 1992-10-15 | 3.7 KB | 80 lines

Newsgroups: sci.crypt
Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!cs.utexas.edu!torn!cunews!nrcnet0!bnrgate!bcars267!keith
From: [e-mail] (Keith W. Campbell)
Subject: Re: DES Encryption/ Encrypting more than once.
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: bcars15
Organization: Bell-Northern Research, Ontario, Canada
References: <[e-mail]> <[e-mail]>
Date: Thu, 15 Oct 1992 12:58:30 GMT
Lines: 67

In article <[e-mail]> [e-mail]
writes:
>In article <[e-mail]> [e-mail] (Dave Ferret) writes:
>   Just a sidenote to 'Hackers' words...
>
>   There are also encryption algorithms that when used to encrypt the
>   plaintext over and over and over, will yield the un-encrypted text. (Ie:
>   Its a circular encryption -- Sorry, I don't know the correct term here)

Any permutation of a finite set has this property.  Repeatedly applying the
transformation will eventually lead to a point already visited (because the
set is finite). That repeated point must be the original point (because we
are talking about a permutation).

Any usable encryption which transforms plaintext into ciphertext of the same
length must be a permutation if recovery of the plaintext is to be possible.

This means that DES, IDEA, FEAL, Khufu and most other ciphers you can think
of have this property.

It is only a problem if the cycle length is very short.  A cycle length of
one means that the plaintext and ciphertext are the same.  If the cycle
length is two, an attacker who can arrange to have a chosen text encrypted
may discover the plaintext by having the ciphertext re-encrypted.

For DES these short cycles are very rare and such keys are easy to avoid.
DES and other good ciphers which may be considered to be random mappings
have average cycle lengths of sqrt(pi*n/8) steps where n is the number of
possible plaintexts.

For DES, n=2^64 so the average cycle length is about 0.627*2^32.
So in practice, the cycles of an
encryption algorithm are not problematic.

>Cyclic, as in subgroup. The question is often phrased, "Is DES a
>group?" (under composition of encryption). Last I read (Crypto '90?),
>it was strongly suspected but not conclusively proven to contain no
>cycles* (recall that a finite group must contain at least one cycle).
>A common suggestion for using DES as a superencipherment for itself is
>E_k1(D_k2(E_k1(P))), where E_k1 = encrypt with key k1, etc.  If
>encrypting twice with the same key were a lot stronger than encrypting
>once, then no doubt the algorithm would just do that (bearing
>performance limits in mind, of course).

This is a different question:  Given two keys k1,k2 is it always possible
to find a third key k3 such that E(k2,E(k1,x)) = E(k2,x) for all x?
The reference you cite (which I co-authored) proves that the answer is no.

>-- Craig Presson
>* - here's a reference I haven't read yet, that should be definitive:
>@inproceedings{campbell,
>  author = "Campbell, K.W. and Wiener, M.J.",
>  year = 1993,
>  title = "Proof that {DES} is not a group",
>  booktitle = "Advances in Cryptology --- Crypto '92",
>  publisher = "Springer-Verlag",
>  address = "New York",
>  note = "To appear"}
>Note to me: call & see if this is out yet.

Actually, the title is "{DES} is not a group" I understand that we
shouldn't expect it to be published until at least March 1993.
Hopefully, Springer-Verlag will prove me wrong.
--
Keith W. Campbell                                Bell-Northern Research
                      P.O. Box 3511, Station C, Ottawa, Canada, K1Y 4H7
e-mail:    [e-mail]                          voice:  [phone]