[611] in cryptography@c2.net mail archive
Re: The unmentionable algorithm
daemon@ATHENA.MIT.EDU (Steven Bellovin)
Mon Apr 21 13:33:37 1997
To: jamesd@echeque.com
cc: Adam Back <aba@dcs.ex.ac.uk>, coderpunks@toad.com, cryptography@c2.net
Date: Mon, 21 Apr 1997 00:21:54 -0400
From: Steven Bellovin <smb@research.att.com>
I should have stuck with my usual policy...
At 09:40 PM 4/20/97 -0400, Steven Bellovin wrote:
> DES really is easy to describe. The implementation problems arise
> because we generally use languages that are too low-level. This is
> it:
>
> for i = 1 to 16
> l[i] = r[i-1]
> r[i] = l[i-1] XOR f(R[i-1], K[i])
Except of course that f is not at all easy to describe,
and you have not defined R, and you have left out some other
stuff.
That's a typo; the R should have been r. It's an array, as is obvious
from this description. And I did define f; you merely chose not to
quote it. It was just a few permutations.
> What have I left out? Nothing complex.
If your claim was true, you would not have left it out.
I didn't -- I summarized it in the following sentences. IP and IP inverse
are of no cryptographic significance. (In fact, they're an artifact
of the serial/parallel conversion vintage mid-70's.) Key setup is also
a permutation; I left it out mostly because you'd left it out of your
initial RC4 discussion. The published description, in terms of PC1 and
PC2, is actually more complex than needed; it's an implementation-level
description, based on mid-70's hardware.
If I am allowed to use "high level functions" I can define any
algorithm in one line.
You can define RC4 in ordinary arithmetic operations in a few
lines.
If you try to define DES in terms of those ordinary arithmetic
operations, you will run on for about ten times as long.
Permutations are quite a simple primitive -- tractable mathematically,
very easy to implement in hardware, etc. I see no particular reason
to assume that ordinary arithmetic is simpler than ordinary permutations.
You're missing the basic point, of course. RC4 *is* simpler than DES,
but the simplicity has nothing whatsoever to do with the algorithmic
complexity. The complexity in DES comes from the precise values of
the E, PC1/PC2, P, and S permutations -- they're quite carefully
interwoven, and trying to change just one of them will significantly
weaken the algorithm. (But there are very many possible values for
the collection; you merely have to chose them appropriately. See
Coppersmith's paper on the DES design rules for more details.)
Of course, RC4 has its own complexities. To mention just one, what
is the mean cycle time of it? That is, on average how many iterations
must there be before the state variables (including x and y) return
to their initial value? Is this a function of key size? Of key values?
The question turns out to be quite important, since it determines the
rekey interval. For DES in OFB mode, for example, the mean cycle length
is 2^63 + .5 -- *if* you use 64-bit output feedback. For any other values,
the mean cycle time is in the range 2^31 to 2^32. This is quite
unsatisfactory for very many applications. RC4 has a much larger
state space, but how well does it use it, and how likely is a pathological
failure?
Btw -- for this question, it's much easier to analyze DES/OFB, treating
DES as a black box, than it is to analyze RC4.... (For more discussion
about OFB mode, see Davies and Price's ``Security For Computer Networks'',
and the references they cite.)
