[RC5] Thoughts on cracking DES

Cedric Tefft cedric at earthling.net
Mon Jan 12 22:17:40 EST 1998

Dakidd wrote:
> I'd like somebody to blowtorch this theory (or is it more properly a
> hypothesis at this stage?)

I'd call it funky math, but OK, here goes...

> 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.

I think I see where you made a wrong turn. You're getting confused by
the fact that the parity bits are embedded in the key rather than at the
end (or entirely separate).  Let me see if I can explain this. 
Paragraph 1.1 above invites us to construct a map of a 64-bit DES key. 
Here's one:


Imagine the garbage in the line above represents a string of 64 bits (A
DES key).  Each 'K' is a key bit.  Each 'P' is a parity bit.  I've
grouped them into 8-bit bytes for clarity.  Now let's rearrange this
string of bits by separating the 'key' bits from the 'parity' bits. 
We'll shove all the parity bits down to the far end:


and just to compact things a little bit:

<--------------------- 56 KEY bits --------------------> <Parity>

We're still looking at the same 64-bit DES key we started with.  The
bits are now in a different ORDER, but the number of key bits and the
number of parity bits has not changed.

Now it's easy to see that we have 56 bits of actual KEY data and eight
bits of PARITY data.  The 56 bits of key data give us 2^56 possible
combinations.  That's where our key space comes from.  Here's the part I
think you missed:  We've ALREADY thrown away the parity bits by the time
we calculate the key size.

What you're essentially saying is "why calculate all 2^56 combinations
when some of those combinations , because of bad parity, would yield
invalid DES keys"?  What you're forgetting, however, is that parity
accounts for eight of the ORIGINAL _64_ bits, NOT eight of the 56 key
bits.  Some of the 2^64 combinations DO yield invalid DES keys.  And
when you subtract those invalid combinations from the original 2^64
combinations, you are left with 2^56 valid DES keys.

> 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.

This is absolutely true.  The block you've mentioned is 64 bits long. If
you do the math you'll find that when you subtract all the INVALID DES
keys from the 2^64 combinations you can make with 64 bits, you'll have
2^56 VALID DES keys left.

Hope that explains things.


- Cedric

*      Cedric Tefft: Proto-Human, Reluctant Programmer     *
*            email: cedric at earthling.net                   *
* PGP FingerPrint: E114-CA05-E498-8A88-0762-79BB-A117-C59B *

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