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

Text File | 1992-10-15 | 4.9 KB | 112 lines

Newsgroups: sci.crypt
Path: sparky!uunet!utcsri!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]> <[e-mail]>
Date: Thu, 15 Oct 1992 21:13:00 GMT
Lines: 99

In article <[e-mail]> [e-mail] writes:
>In article <[e-mail]> Mark Henderson
>writes:
>
>>In article <[e-mail]> [e-mail]
>> (Ari Huttunen) writes:
>>>In article <[e-mail]> [e-mail] (Dave Ferret) writes:
>>>
>>>Any encryption scheme that has a fixed block length *must* do this. Think
>>>of a series of encryptions:
>>>    x_1 -> x_2 -> x_3 -> ... -> x_k -> ... -> x_n -> ...
>>>If 'n' is greater than the possible number of messages that can be encoded
>>>in the fixed length block, there must be some blocks in the chain that
>>>are the same (pigeonhole principle). Let x_k and x_n be the same blocks.
>>>Then by encrypting x_k (n-k)-times yields x_k.
>>>
>>>(n-k) might be quite large, though. ;-)>
>>
>>However there is nothing in your argument to say that (k,n) are not
>>dependent on the original block being encrypted.>
>>
>>for "circular", we want something more like:>
>>
>>there exists n such that
>>
>> n
>>E (x) = x   for all blocks x  >>
>>
>>where E is the encryption function in question.
>
>Few encryption systems have this property in general.  As I recall, the
>system known as Bifid (see H. F. Gaines' Cryptanalysis for a brief
>summary) has this property.  For a given keysquare and period, n is not
>known, but is fixed for that particular set.

All encryption systems must have this property.  While it is true that
there will often be many different orders of blocks
                               i
    order(x) = smallest i  such that  E (x) = x

we can always take n = lcm( order(x) : over all blocks x ) to get

          n
         E (x) = x for all x

We would hope that n is large for any system in use.  This is true for
DES, as you will see below.

In article <[e-mail]> [e-mail] (Bill Unruh) writes:
>[e-mail] (Keith W. Campbell) writes:
>
>>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.
>
>So a chosen plaintext attack of "only" 2^32 should crack DES, rather
>than the 2^47 or something of the differential analysis attack? Sounds
>like a significant advance in the breaking of DES since the former has
>been widely reported as breaking DES:)?

Sorry, but this does NOT lead to a practical attack on a system which
uses DES. If you can entice the victim into n1 ~ 2^32 encryptions, you
can get the plaintext. (Note that this only applies to systems which use
DES in ECB mode). You still don't have the key nor an efficient method
for encrypting or decrypting blocks not included in this cycle.

You may continue to collect more plaintext-ciphertext pairs by following
other cycles yielding cycle lengths n2, n3, ..., n_k. This process should
give a complete description of the mapping after traversing k ~ 2^32 cycles.
(There 2^64 points with about 2^32 in each cycle).  Your obliging victim
has done 2^64 encryptions for you; it would have been more efficient to
check each of the 2^56 keys yourself.

Michael Wiener and I submitted a paper to Crypto '92 entitled "DES is not
a Group". The principal argument is as follows.

Consider the closure of DES encryptions under composition.  Our claim is
that this group must include permutations which are not equivalent to DES
encryption with any key.  Each of the n_i collected above must divide
the order of the group.  Compute n = lcm( n_i, i=1..k ).  If n > 2^56 then
the group must be larger than the set of DES encryptions.

The paper includes the lengths of several hundred cycles of DES.
The lcm of those lengths exceeds 10^2499.  It is clearly not practical
to use E^n(x) to recover x for such large n.
--
Keith W. Campbell                                Bell-Northern Research
                      P.O. Box 3511, Station C, Ottawa, Canada, K1Y 4H7
e-mail:    [e-mail]                          voice:  [phone]