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:

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

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.