Re: DES cracker.

[Adam Back <aba@dcs.ex.ac.uk>]

[cc'd to cypherpunks]

Michael Johnson <mikej2@Exabyte.COM> writes:
> On Thu, 17 Oct 1996, Ted DiSilvestre wrote:
> >... 
> > As someone posted a few weeks ago, rather than find one message to crack we
> > should work on ten or a hundred simultaneously if possible. This seems to
> > be the easiest way (assuming we can find this many "good" messages) to
> > increase cracking efficiency by orders of magnitude.
> 
> Hmmm... I don't see that this increases cracking efficiency. The suprising
> (to me) result is that it doesn't really hurt it any. The increase in
> average expected time to find a particular key is offset by the fact that
> more keys are tried at once. We could crack just as many keys per year, on
> average, but we become less sure of which keys will be cracked first.

You do save something: you only need one key schedule per key that you
try.  You can try the key against multiple ciphertexts.

A negative effect is that you might loose cacheing opportunities as
code and data are increased.

For timings you're likely to get for DES, you suffer from the law of
diminishing returns quickly, and the additional keys/sec from doing
more keys tapers off asymptotically.

The number of keys it would be most efficient to use (say where adding
another key speeds things up by less than 1%, or whatever) hinges
heavily on the actual balance between how fast the key schedule can be
made to go as compared to a CBC block operation (or whatever mode
you're attacking).  Also the protocol you are attacking, and the
position of the known plaintext in this block affects things greatly,
the further along the plaintext, the more blocks you have to cycle
through, and more data you have to move around.

To illustrate the effect, here's some quick cacluations based (loosly)
on the timings being quoted.

With Peter Trei's projected DES block timing from pentium 90 to
pentium 133, and approximate equivalence of ecb and cbc demonstrated
by Eric's code (this set of figures is hand-waving: I'm not at all
sure like is being compared with like, and we are now extrapolating
from extrapolations), combining with Eric's keyschedule timing:

keyschedule 12.2us (Eric Young's) 
DES cbc block = 0.47us (from Peter Trei's extrapolated pentium 133Mhz)

n keys    |  key   |   DES  | elapsed for | elapsed per |
at a time |  sched |   cbc  | n key tests | key test    | keys/sec
-----------------------------------------------------------------------
     1      12.2us     1.4us      13.6us         13.6us    73.5k keys/s
     2      12.2us     2.8us      15.0us          7.5us   133.2k keys/s
     4      12.2us     5.6us      17.8us          4.5us   224.2k keys/s
     8      12.2us    11.3us      23.5us          2.9us   340.7k keys/s
    16      12.2us    22.6us      34.8us          2.2us   460.3k keys/s
    32      12.2us    45.1us      57.3us          1.8us   558.3k keys/s
    64      12.2us    90.2us     102.4us          1.6us   624.8k keys/s
   128      12.2us   180.5us     192.7us          1.5us   664.3k keys/s
   256      12.2us   361.0us     373.2us          1.5us   686.0k keys/s

So 256 keys gives ~9x improvement in keys/sec with these even less
accurate guestimates, and using more keys won't increase that
improvement all that much, asymptotically tailing off around 9.5x for
reasonable numbers (< 64k keys).

Improving the key schedule in the second table doesn't add hardly
anything, because it is basically irrelevant when you get to 256 keys.
(However, a faster key schedule _is_ significant for 1 key at a time).

I think that Peter Trei / Phil Karn are fairly close to the limit, and
if anything the resulting figure will be a fair bit short of what I
have extrapolated because I suspect their peak Mb/s figure will go
down when you start doing practical things with the addition of extra
data shifting, etc.

So it all depends on what corners can be cut in the key schedule, and
how much you gain by coding the keyschedule in hand optimised
assembler, and all the other factors discussed above, in summary:

- keyschedule / CBC block timings ratio
- how far into the message is the known plaintext (how many blocks to cycle)
- cache limits (additional restriction on optimal number of keys) 
- extra code overhead over peak cache Mb/s (moving data, extra code)
- extra code size and complexity (for multiple key code)

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`