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

- 4 mins

Exercise 3.6

An avalanche effect is also desirable for the key: A one-bit change in a key should result in a dramatically different ciphertext if the plaintext is unchanged.

  1. Assume an encryption with a given key. Now assume the key bit at position 1 (prior to PC − 1) is being flipped. Which S-boxes in which rounds are affected by the bit flip during DES encryption?
  2. Which S-boxes in which DES rounds are affected by this bit flip during DES decryption?

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. The keybit at position 1 is moved to position 8 by .

The two halves of the key which are independently rotated are referred to as and .

Since is all 0s, then will also be all 0s.

(due to the 1 in position 8).

In rounds 1, 2, 9, and 16, the key halves are rotated 1 position left. In all other rounds, they are rotated 2 positions left.

It’s worth noting that, even after the permutation, a keybit in the first half will remain in the first half after permutation. Second-half keybits will also remain in the second half after permutation.

This allows us to completely forget about when calculating which S-boxes are affected.

2. It’s not necessary to explicitly check what the effect of this bitflip is during decryption key-scheduling, since it must be the same in reverse. If it wasn’t the S-boxes would receive different input during decryption than they do during encryption, and the cipher would not function.

I wrote a python script which can calculate which S-boxes are affected:

one_bit = 7 # off by one so that bit 28 doesn't become bit 0 - is corrected via a +1 when used.

def find_one_bit_location_after_PC1(bit_position):
    map = dict(zip([
            14, 17, 11, 24, 1, 5, 3, 28,
            15, 6, 21, 10, 23, 19, 12, 4,
            26, 8, 16, 7, 27, 20, 13, 2
        ], range(1, 29)))
    return map[bit_position] if bit_position in map else None

for i in range(1,17):
    if i in [1, 2, 9, 16]:
        rotate = 1
    else:
        rotate = 2
    one_bit = (one_bit - rotate) % 28
    subkey_bit = find_one_bit_location_after_PC1(one_bit + 1)
    print "Round {}: 1-bit is occupying position {}\n" \
        "\tAfter PC-2 this is subkey bit {}\n\twhich afects S-box {}\n".format(
            str(i).zfill(2),
            one_bit + 1,
            subkey_bit if subkey_bit else "N/A",
            ((subkey_bit - 1) / 6) + 1 if subkey_bit else "N/A"
        )

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