Re: Other Efforts

Ryan D Pierce (rdpierce@midway.uchicago.edu)
Wed, 11 Jun 1997 14:42:29 -0500


[my response showing how random and sequential methods are statistically
equivalent deleted, as someone beat me to it]

If you were the NSA with a DES farm and you had no reason to believe
that any keys would be more likely than others, it wouldn't make
a difference if you checked sequentially or randomly. Both have the
same odds of recovering the message in the same time in a brute force
attack.

(Side note; if you can reduce the keyspace, you have an incredible
advantage. I.e. if you know it is an 8 character string of upper case
letters, you have 26^8 keys, not 2^56 keys to search. That amounts
to 1/345000 the keyspace you'd have to search. Of course RSA stated that
they generated the key randomly, hence we can't reduce the keyspace
this way.)

Of course sequential searches in a competitive environment can be bad;
they give the opponent info about exactly what keyspace you've already
searched and what keyspace you will search next. If we have 100 keys, I
have equal processing power as deschall, and I check out a deschall key and
get 12, I then can start cracking at, say, 15 while the next key deschall
searches is 13. I can then cover 15-100 sequentially before deschall does,
and if the key lies there, I am guaranteed to find it before deschall.

Ryan