Solving Part B of DES Question

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

 

[anathema]

Hello, thank you for sharing your problem with us. I am a scientist with a background in cryptography, and I would be happy to offer some insights and suggestions.

First of all, congratulations on successfully proving the complement rule of DES in part A of the problem. That is a great accomplishment and shows your understanding of the encryption system.

Now, let's focus on part B of the problem. The given hash function, H(x,y) = DES_x(y) XOR y, is an interesting one. From a mathematical perspective, we can see that for a specific value of x, say x*, H(x*,y) will always equal y. This is because the output of DES_x* will be the same as y, and XORing it with y will give us y again.

However, as you correctly pointed out, we need this to work for all values of x. This means that we need to find a value of x that will make DES_x(y) equal to 0 for all values of y. This is where the complement rule of DES that you proved in part A might come in handy.

One approach you could take is to consider the values of x that satisfy the complement rule. These values will have the property that DES_x(y) = 0 for all values of y. This means that if we use these values of x in our hash function, H(x,y) will always equal y.

You also mentioned the concept of weak keys in DES. While weak keys can be useful in some cases, I don't think they will be of much help in this particular problem. Weak keys are weak because they cause certain patterns to appear in the encrypted data, but in this problem, we need the encrypted data to be unpredictable and not follow any pattern.

In conclusion, my suggestion would be to explore the values of x that satisfy the complement rule and see if they can be used in the hash function to achieve the desired property. I hope this helps, and I wish you the best of luck in solving part B of the problem.

 

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