[2039] in cryptography@c2.net mail archive
Speeding up a DES cracker yet again
daemon@ATHENA.MIT.EDU (Frank (Giff) Gifford)
Tue Jan 13 15:13:26 1998
Date: Mon, 12 Jan 1998 11:04:09 -0500 (EST)
From: "Frank (Giff) Gifford" <giff@va.pubnix.com>
To: cryptography@c2.net
It's well known that DES has the 'complementation property'. That is,
for a plaintext, key and resulting cipher answer: C = DES(P, K), the
complement of P and K when encrypted will be the complement of C:
~~C = DES(~P, ~K).
Actually - there is another complementation property which I haven't seen
discussed anywhere. Although the existing key crackers (i.e. Bryddes from
Svend) uses the regular complementation property, it should be easy to add
in the other property to reduce the searching by a factor of two.
The property comes about because of the key schedule's PC-1 and PC-2
blocks. PC-1 is considered to be composed of two halves, C0 and D0. For
each round where a left circular shift is done, it operates only on the C0
and D0 blocks independently. That means the bits in C0 remain in C0, the
bits in D0 remain in D0.
Now, the PC-2 block which selects bits from PC-1 has an interesting
property. The first 24 entries will only select bits from the C0 block.
The last 24 entries will only select bits from the D0 block. Mapping this
onto each round of DES, it becomes clear that the bits listed in the C0
block only map to the first four S-boxes, never the last four. And the
bits listed in the D0 block only map the the last four S-boxes, never the
first four.
So, the complementation property we are used to is actually composed of
two complentations.
For the DES encryption (Note! This is the encryption ignoring the IP/IP-1
transforms!): C = DES(P, K),
1) Invert the top half of P and all Key bits from C0 block, the top half
of the output will be complemented, the lower half is unchanged.
2) Invert the bottom half of P and all Key bits from D0 block, the bottom
half of the output will be complemented, the upper half is unchanged.
3) Invert both halves of P and all Key bits, the output will be
complemented.
So, for the price of one test encryption, one should be able to test four
keys simultaneously. For a given target output, XOR the target output
against what was received. Then compare the upper and lower halves
separately. If each half is either 000...0 or 111...1, then you
complement the appropriate key bits and that's it.
Comments? Anybody want to try modifying their source a little to test
that out?
-Giff
