UMM CSci 4509 Spring 2005 -- Problem set 3

CSci 4509 Cryptographic Protocols -- Problem set 3.

Problem 1: ciphertext stealing

Reading: Ch. 9 in Schneier.

You are given the following simple 8-bit SPN with just one round and an 4-by-4 S-box (used twice: once for bits 1 through 4, and once for bits 5 to 8). The SPN operates the following way:

an 8-bit plaintext block is XOR-ed with the key K0, bits 1 through 4 and bits 5 to 8 are passed through the S-box defined as follows:

0 1 2 3 4 5 6 7 8 9 A B C D E F

6 B 9 1 7 A 3 4 F 0 E D 8 2 5 C
the 8-bit output of the two S-boxes is permuted using the following permutation:

1 2 3 4 5 6 7 8

8 1 7 2 6 3 5 4
the result is XOR-ed with the key K1. This is the output of the cipher.

The key schedule is as follows: given a 12-bit key, the SPN uses the first 8 bits as K0 and the last 8 bits as K1 (thus the middle 4 bits are used in both keys). This is similar to the key schedule for the SPN in the Stinson book (see p. 76).

The key for this example is

1 0 0 1   1 1 0 0   1 1 0 1

Part 1

The cipher is used in ECB mode. Encrypt the following plaintext using ciphertext stealing:

1 1 0 0 0 1 0 1   0 1 1 0 1 0 1 1   1 0 1

Show the decryption of the text, make sure that you get the original plaintext back.

Part 2

The same cipher is used in CBC mode with IV = 01010101. Encrypt the same plaintext using ciphertext stealing.

Show the decryption of the text, make sure that you get the original plaintext back.

Problem 2. Insertion attack

Reading: Ch. 9 in Schneier.

Ann, Brian, and Chris are using a Vigenere cipher with a long randomly generated key. Ann encrypts a message and sends it to Brian. The encryption looks like this:

WMLSWTDIRYYZICEXIMRLOQYJTFPICKHZGNPTXGSAZSRPFIPTSJXTAWV

Brian decrypts the message, reads it, and decides to send it to Chris. To do this, he re-encrypts the plaintext using the same key. Unfortunately Brian's encryption device has a mechanical problem: every once in a while it inserts the letter X in the plaintext. Brian's encryption came out like this:

WMLSWTDIRYYZICEXXPDXRWQHGWVSWNEINODIIRFVEBGEQUSJNVAGVSXR

Your task is to determine everything you can about the plaintext and the key. How difficult would it be to determine the remaining part of the plaintext and of the key without any assumptions about either?

Completely optional, no extra credit. Can you guess the rest of the plaintext? How confident are you of your guess?

Problem 3

Stinson, Exercise 4.5(a). Hint: show that the equation has another solution that's easy to compute knowing x. Note that the equation that you are trying to solve is modulo 2^2m, i.e. you are given x, and you are trying to find y (different from x) s.t.
x^2 + a * x + b = y^2 + a * y + b mod 2^2m

Problem 4

Stinson, Exercise 4.6.

Problem 5

You are given the following compresion function which, given 6 bits, outputs 3 bits:
compress(x1,x2,x3,x4,x5,x6) = x1 XOR x6, x2 XOR x5, x3 XOR x4. For instance, compress(101110) = 1 XOR 0, 0 XOR 1, 1 XOR 1 = 110

Part 1.Use the Merkle-Damgard construction, compute MAC for the message 101 110 110.
Part 2. Is the compression function second preimage resistant? If yes, please explain why; if no, demonstrate how you would solve the second preimage problem.
Part 3. Is the compression function collision resistant? If yes, please explain why; if no, demonstrate how you would solve the collision problem.

Problem 6

Stinson, Exercise 4.12.

Problem 7

Stinson, Exercise 4.15. Is this a strongly universal hash family? Please explain your answer.

CSci 4509 homepage