What Are the Values for Which H(x,y) Always Equals y?

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

 

[wais]

Hi there,

I understand that you are struggling with solving Part B of the DES question. It seems like you have already put in a lot of effort and have some ideas on how to approach the problem. Let me see if I can offer some suggestions that may help you.

First, it might be helpful to break down the problem into smaller parts. Instead of trying to solve it for all values of x, try to solve it for specific values of x and see if you can find a pattern or a general rule that applies to all values of x. This might make the problem more manageable.

Second, consider using different values for y. Since the goal is to find values of x and y that will always result in H(x,y) = y, try plugging in different values for y and see if you can find a relationship between x and y that satisfies this condition.

Additionally, as you mentioned, the complement rule of DES (Part A) may be helpful in solving Part B. Perhaps you can use this rule in conjunction with the other properties of DES (such as weak keys) to find a solution.

Lastly, don't be afraid to seek help from others. You mentioned that even if someone doesn't understand how DES works, they can still help if they know algebra. Consider reaching out to others for their insights and perspectives on the problem. Sometimes, all it takes is a fresh set of eyes to see a solution.

I hope these suggestions are helpful to you and wish you the best of luck in solving Part B of the DES question. Keep persevering and I'm sure you will find a solution.