[RC5] Another way to win DES-II (joke?)

Shannon Jones scj at pobox.com
Thu Jul 30 14:49:00 EDT 1998


Hello!  I had trouble sleeping last night, so I lugged my copy of "Applied
Cryptography" off the shelf and started to read the section
on DES.

I didn't stay awake long :)  But I did read a method for cracking DES where
you try every key with a given plaintext and then store the
cyphertext.  Then to decrypt a message that has this known plaintext, you
simply look up the key.

This attack could be used against DES-II-3.  All of the messages start with
the preamble: "The unknown message is: "  We take the first 56 bits of this
message, run it through every possible key and store the cyphertext.  When
the contest starts, we find out who has that cyphertext, and they look up
the key that goes with it.  If we did this, we could win every DES-II
contest in... 5 minutes or so.  This assumes we sort the cyphertext.  If we
don't sort, we will have to wait for each user to search his database for
the correct cyphertext.

The problem?  Well, we would have to store at least 56 bits of information.
 That is pretty hard :) I estimated that we have about 2^15 (32,768) active
users.  If we divide the storage up evenly, each computer will need to
store 2^41 bits or 2^38 bytes.  That is ONLY
256 GIG each.  So we need more participants, or we need larger hard
drives...

Now, if we assume that each user would be willing to store 128meg on their
machine (Hey, I would burn a few CDs and most people would give up a Zip
disk, let their old 540mb HD fill up or recycle a few old AOL disks), we
would need 2^26 (67 million) active users.  Now, if we are doubling disk
capacity every 126 days, we will reach this level in about 1386 days, or
about 3.8 years.

And then it hit me:  Why don't we use @Backup to store the data for us? 
The keymaster could sign up for @Backup and just upload this database. 
They promise unlimited storage. . .  I wonder if they would gripe about us
putting 8.4 million gig on their system, for only $19.95 a month?

Well, maybe for DES-III or something!  Anybody have an idea of how to make
this possible?  I doubt it will work unless we all upgrade to
multi-terabyte drives or something.

What is the state-of-the-art in super mass storage?  How much would it cost
the EFF to build a huge storage array, pre-calculate the
DES-II challenge and sort and store the results?  Maybe for the price of a
new DESCracker, they could build a machine that could look up the answer to
the next DES-II challenge in less than a minute.

Ok, so I am dreaming :)
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list