[209] in cryptography@c2.net mail archive
Re: RC4 keysearch
daemon@ATHENA.MIT.EDU (Adam Back)
Mon Feb 10 14:58:17 1997
Date: Mon, 10 Feb 1997 18:20:53 GMT
From: Adam Back <aba@dcs.ex.ac.uk>
To: reinhold@world.std.com
CC: kelsey@email.plnet.net, cryptography@c2.net
In-reply-to: <v03007801af24d54ca766@[10.0.2.15]> (reinhold@world.std.com)
Arnold Reinhold <reinhold@world.std.com> writes:
> John Kelsey suggests:
> >
> >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.
>
> I do not believe this can be done with RC4 to any significant extent. The
> key scheduling step requires all the key bits together.
With SSL, the key which is scheduled is obtained by using the MD5 of
the 11 byte salt and 5 byte key, and then by using the resulting key
as the RC4 key, and running the RC4 keyschedule on this key.
The consecutive RC4 keys tested are MD5 hashes of the consecutive
notional keys, so there is nothing you can get from pre-computing part
of the schedule.
With Andrew Roos' SSL brute forcing code, he managed to get a small
amount of speed up by precomputing part of the MD5 digest. This
translates into an overall increase in 40 bit SSL keys/sec tested of
around 1%.
Adam
--
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
