[204] in cryptography@c2.net mail archive
RC4 keysearch
daemon@ATHENA.MIT.EDU (John Kelsey)
Sun Feb 9 11:45:41 1997
To: "Perry's Crypto List" <cryptography@c2.net>
Reply-To: kelsey@email.plnet.net
From: John Kelsey <kelsey@email.plnet.net>
Date: Sat, 08 Feb 97 19:27:12 CST
-----BEGIN PGP SIGNED MESSAGE-----
[ To: cryptography@c2.net ## Date: 02/07/97 12:19 pm ##
Subject: RC4 keysearch. ]
>From: Arnold G. Reinhold
>Subject: Re: 40-bit rc2/4
>Cc: cryptography@c2.net
>Date: Thu, 06 Feb 97 12:2
>A while ago, I did a back-of-the envelope design of a hardware
>N/128-bit RC4 cracker using the same ASIC cells that Michael
>Wiener employed in his paper, "Efficient DES Key Search."
>N/128-bit RC4 means RC4 with a 128 bit random key, all but N
>bits of which are revealed. 40/128-bit RC4 is used in SSL, for
>example.
Has anyone looked at how much cost is added by doing something
like real_key = md5_hash(salt,short_key)? Can you still get the
fast export approval if you do this rather than just prepending
or appending the salt to the key? It's obvious that doing this
adds quite a bit of difficulty to the keysearching problem. (My
understanding was that this was allowed, but I'd like to be
sure.)
There are a few obvious speedups available for RC4 keysearch.
For example, if you have an implementation that does
real_key = salt || short_key with an 11-byte salt and a 5-byte
key, then an attacker can tackle the first 11 bytes of key
scheduling once, and have all processors start from there. If
each searching machine can afford the memory, they can also
search the short_key value in sorted order, and cache the
intermediate permutation arrays from each byte's search. Thus,
I save the results from scheduling 00 00 00 00 --, and start from
that permutation array for 00 00 00 00 00 through 00 00 00 00 ff.
I have also saved the permutation array for 00 00 00, and I can
use that one to get from 00 00 00 00 -- to 00 00 00 ff --. And
so on, up the chain. (Scheduling the prepended salt first gives
the biggest and most useful gain. The gain of the rest of these
is dependent on the amount of work required to copy the
intermediate permutation array state out. If that's 256
operations, then it probably pays to cache this state for all
but the next-to-last byte in the key.) Getting other
interesting speedups out of this seem to depend on analyzing
RC4's key scheduling routine.
>Therefore, I estimate that RC4 has about an 8 bit key length
>advantage over DES in resistance to brute force attack using
>special purpose hardware. That is, a 56 bit DES key is about as
>resistant as a 48/128 bit RC4 key to exhaustive hardware key
>search.
Was IBM allowed to export CDMF? (This is 40-bit DES that
uses a couple of encryptions to avoid giving away information
about specific bit values of the key.) My impression was that
they weren't allowed to export even that. (DES-40 without this
would be about the same as RC4-32 by your calculations above.)
Even adding in a couple of encryptions for CDMF, I'd still
expect relatively little security. Maybe NSA's custom DES
brute-force machines don't include a way to load the key
register from the output of an encryption value.
>Arnold Reinhold
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMv0nakHx57Ag8goBAQEJowP/Yb6kQa41ZBCVMONnmHWHpYPYWlNGGmDx
Y2FU6AVlXw2pi9S28bTKoiNiBXBaUcIwZtksKqmld757dp5nVXUIqIP/LvFyT7uC
Ieqd3wDXWEKPaUuo0c09ymFOcQV/3ONuVKf1L/YmaHES6eAr86xZF1NlSfiC0n1f
eosdUKjc3hg=
=Xdsm
-----END PGP SIGNATURE-----
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
