# Attacking DES

1. Oct 9, 2004

### Chu

Hello all, I have a problem with a question reguarding attacking DES. If you don't know how DES (the encryption system) works but know algebra you can still help ;)

Essentially -- Part A of the problem (the 'hard' part based on point values) was to prove the complement rule of DES, mainly that given x' is the compliment of x (x' XOR x = 1..), then DES_x'(y') = c', i.e. if you encrypt the compliment of the message with the compliment of the key, the output is the complment of the original cyphertext. No problems here, the proof was pretty easy but tedious.

Here is part B of the problem, and it is giving me a ton of trouble. I mention part A because I have a gut fealing it is the property used to break this function.

Consider the following has function:

H(x,y) = DES_x(y) XOR y

For what values are we gaurenteed that FORALL (x), H(x,y) = y?

I have done a ton of work that has led nowhere. Obviously, DES_x(y) = 0 for this to work.

I have a fealing, which I am working on now, it might also involve weak keys. Basically, these exist keys with the following properties:

Weak : E_k(x) = e_k(e_k(x))

Semi-weak, exist k_1, k_2 s.t. e_k1(x) = d_k2(x)

Since we need this to work for all x this obviously wouldn't be much help in choosing a value for x, but it might somehow coerce y in a way that we don't end up with the unsolvable expression e_x(e_x(y)) and have to figure out what to XOR this with.