Question

Alice and Bob are discussing Alice’s healthy eating. They suspect Eve is listening in, so they use double encryption. Message blocks are eight bits. Each block encodes a character using ASCII.

A block is first encrypted by flipping a single bit (changing 1 to 0 or 0 to 1). The key is a value from 0 to 7 and says which bit to flip. So if the key is 5, bit number 5 in each 8-bit block is flipped. Number bits from 0 to 7, starting at the right bit. (The book sometimes numbers bits in the other direction.)

The second key is a value from 0 to 7 and says how much to rotate the block left. So if the key is 2, blocks are rotated left by two bit positions.

Here is a plaintext block for ‘A’ : 0100 0001. Say the key is (4, 3). First flip bit 4: 0101 0001, and then rotate left by three: 1000 1010.

Eve intercepts the message

0000 1010 0010 1010 1000 0010 0111 1010 0010 1010 0100 0010 0000 1010

She suspects the first three blocks encode EAT. She knows the two ciphers that Alice and Bob are using, but does not know the two keys. Exhaustive search would require trying up to 8x8 = 64 key pairs until the first three blocks deciphered to EAT.

So she uses a known plaintext attack with Meet-in-the-Middle

Plaintext:   EAT
bit to flip	A: block as 24 bits	B: Col A in hex
none
0
1
2
3
4
5
6
7

Fill in the table by enciphering the first three blocks (1 byte each) of the known plaintext using the first cipher. The row labeled none is the 24 bits of unenciphered plaintext.

Now, fill in the second table by deciphering the first three blocks of the intercepted ciphertext using the second cipher. You are de-ciphering, so the rotation is right. There should be a match in column D to a cell in column B. Now Eve has the full key.

	C	D
Second key (rotation)	First 3 half-deciphered blocks in binary	Column C in hex
0
1
2
3
4
5
6
7

Use the full key to decipher the message. What is the secret that Alice sent to Bob?

1. Last four blocks of the secret message (from above):

2. Last four ciphertext blocks (i) half-deciphered using the rotation that matched column D:

3. Last four ciphertext blocks (ii) completely deciphered by un-flipping the bit determined by the match with column B:

4. Above (iii) bit patterns as hex

5. ASCII characters represented by the (iv).

6. Full message sent from Alice to Bob:

7. Are you going to take Alice’s advice?

Answer 1

The attached images solve this question through the following steps:

1) Meet-in-the-middle step

2) Table entries

3) Guessing key

4) decrypting the ciphertext

5) Answering all your questions

Refer to the images.....