Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 3 Solutions - Ex3.8

- 9 mins

Exercise 3.8

DES has a somewhat surprising property related to bitwise complements of its inputs and outputs. We investigate the property in this problem. We denote the bitwise complement of a number (that is, all bits are flipped) by . Let ⊕ denote bitwise XOR. We want to show that if

then

This states that if we complement the plaintext and the key, then the ciphertext output will also be the complement of the original ciphertext. Your task is to prove this property.

Try to prove this property using the following steps:

  1. Show that for any bit strings A,B of equal length,

    and

    (These two operations are needed for some of the following steps.)

  2. Show that .
  3. Show that .
  4. Using the two results from above, show that if are the keys generated from , then are the keys generated from , where .
  5. Show that .
  6. Show that .
  7. Using all previous results, show that if generate , then generate .
  8. Show that if , then is true.

Solution

I haven’t yet verified this solution independently. If you spot any mistakes, please leave a comment in the Disqus box at the bottom of the page.

1. Since this is a bitwise operation, there is no way for one bit to affect another in its sequence, we can prove this property by proving that it holds true for one bit. If the property always holds true for 1 bit, then it must hold true for all the other bits in the bitwise operation. The easiest way to do this is with a truth table:

As you can see, these properties hold true for all possible values of and .

2. Since is a simple, determininistinc, bitwise permutataion, where the value of the input bits don’t affect where they’re mapped to, this property is trivially, and by definition, true and does not need to be proved. Whether the bits are flipped before or after they are re-ordered makes no difference to the outcome, since each bit flip is an atomic operation unaffected by the ordering or values of other bits.

3. The subkey rotations are also simple, deterministic permutations. As such, by the same reasoning as above, this property is also trivially true by definition.

4. Above, we showed that, at least up until is applied, if you provide the bitwise complement of a key , it will generate the bitwise complement of the subkeys would have produced. As with and , we can show that is another simple bit permutation. As such, the subkeys which are fed into for are guaranteed to be the bitwise complement of those which would have been fed into for in all cases.

5. Again, is a simple bit-order permutation, so is trivially true.

6. is slightly different, in that it is not a simple bit-order permutation. is a function that maps each bit in a vector to one or two bits in a larger vector. The bits which map to only one location in the expanded vector can be ignored, since computing their compliment behaves the same as a normal permutation. To prove that , we need to consider whether it matters if the bits are flipped before or after being mapped to the two locations in the expanded vector. It’s worth noting here that there are no combinatory operations performed, a single bit in the expanded vector always has one “parent” in the original vector. As such, it’s fairly obvious that flipping one bit prior to mapping, or flipping the two copies after the mapping, makes no difference to the outcome.

7. In order to prove this property we need to do a proof by induction. We first need to show that encrypting with will produce where is the result after one round of encrypting with .

After we have proved this to be true, we need to prove that the same holds with producing from . The first step proves the first “domino” to be true. The next step proves that all the other “dominoes” will fall after it (i.e. the equality holds through all rounds).

Firstly we need to look at the function. We have proved in previous steps that for all rounds, for , the subkey being passed into will be the complement of subkey which would have been generated by . We also know by definition that receives as input.

As such we can construct the following definition of what happens within the function (where is the application of the S-Boxes and is the final permutation):

Using the equality we proved in (6), we can rearrange this to an equivalent definition:

Now, using the equality we proved in (1) (which is that ) we can simplify the definition:

At this point, we’ve proved something quite surprising, which is that the input to the S-boxes is identical when encrypting with as it is when encrypting with .

As such, we don’t need to do any proofs relating to and since they will receive the same input in both cases. Since they receive the same input, they will produce the same output in both cases. As such we have shown that:

The fact that the S-boxes receive the same input in both cases lies at the heart of why holds. The S-Boxes are non-linear, so for any S-box , . As such, if the S-Boxes didn’t receive the same input in both cases, there’d be no way for the equality to hold, since would produce different, unrelated output.

The only other operation to perform in the round is to XOR the output of with . To finish proving that will produce from , we need to prove the following equality:

Using the equality we just proved about we can simplify slightly:

We can now finish the proof by invoking the equality we proved in (1) (which is that ):

This proves the equality by demonstrating that they are equalent statements.

Now that we’ve proved that inverting the key and input will produce bitwise inverted output after one round, we can extend this logic to say that for any round, if the subkey and input to that round are bitwise inverted, then it will produce the complement of what that round would have produced absent the inversion. I wont duplicate all of the work we did above, since all the equalities whold true for input/key index and as they do for index and .

We know via the work we did above that Round 2 will receive the complement of the subkey and of the input it would have received, had the input and key not been bitwise inverted. As such, round 2 will produce the complement of the output that it would have. This means that Round 3 will receive the compliment of the subkey and input that it would have… etc. This property cascades through all the rounds, and describes a (slightly informal) proof by induction.

8. All there is left to do to prove the equality is to show that . Since this is the inverse of and this property holds for all simple permutations, then it is trivially true.

We know that the input to will be the complement of what it would have received had the key and input not been bitwise inverted before encryption, since we know that the final round will produce output with this property.


Thomas Busby

Thomas Busby

I write about computing stuff

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora