[RC5] Thoughts on cracking DES

Dakidd dakidd at mindspring.com
Mon Jan 12 20:45:43 EST 1998


I'd like somebody to blowtorch this theory (or is it more properly a
hypothesis at this stage?) It seems to make sense to me, but does it makes
sense to anybody else?

Excerpted from a step-by-step file on how to do DES:

Here's how to do it, step by step:

 1  Process the key.

 1.1  Get a 64-bit key from the user. (Every 8th bit (the least
significant bit of each byte) is considered a parity bit. For a key to
have correct parity, each byte should contain an odd number of "1"
bits.)


OK, from this, it would seem to me that there are not 2^56-1 possible key
values, but in fact, there are only (2^56-1)/2 possibilities, due to the
fact that one half of the values are going to generate keys with invalid
parity.

With RSA requiring that the parity bits in the submitted key conform to 
the
FIPS standard for key parity, does it not seem reasonable to only check
keys that can be valid?

IE:
Any key containing a byte with the value of 0x9c (or 0xc9) would be an
invalid key because 0x9f in binary is 10011100 (and 0xc9 is 11001001) -
both a byte with an even number of ones. This would wipe out entire blocks
of keyspace from consideration due to not having the correct parity.
Consider the keyblock starting at 0xc900 0000 0000 0000 and running to
0xc9ff ffff ffff ffff - The entire range could be marked off due to all of
it's possible keys having invalid parity.

Similarly, any block with one or more 0x00, 0x03, 0x05, 0x06, 0x09, 0x0a,
0x0c, or 0x0f bytes could be automatically disqualified, saving HUGE 
chunks
of processing time.

It also seems to follow that even if each key-candidate had to have each 
of
it's bytes parity-checked, such a check would take vastly smaller amounts
of time than to actually attempt a decrypt with it and then throw it away
when it was found not to be the key anyway.

It seems too darn simple a method of eliminating 50% of the keyspace
without having to crunch a single key, but it appears that it makes sense.

Is it just me, or does this seem like something that's been overlooked?
Something this simple MUST have been considered by somebody, I would 
think,
'cause I'm far from any kind of genius. If I can come up with it, how many
others have done the same already? Or has it simply been overlooked by 
some
bizarre fluke?










Don Bruder - Dakidd at mindspring.com     Dakidd at jomax.net
             Dakidd at grfn.org           +------------------------------+
+---------------------------------+    |Do you ever get the feel that |
|I will choose a path that's clear|    |the story's too damn real and |
|I will choose free will -Rush    |    |in the present tense? -J. Tull|
+---------------------------------+    +------------------------------+
Saddle-tramp by day, 'net-freak by night. What a contrast, eh?


--
To unsubcribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list