# Extra: Authenticated Encryption CBC-XOR

### Problem

Show two types of forgery attacks for authenticated encryption scheme CBC-XOR.

```
Given a pseudorandom permutation F
Gen: k <- {0, 1}^n
Enc: On input a message m = B_0 || B_1 || ... || B_l and a key k, 
     uniformly generate an IV <- {0, 1}^m
    1. Compute B_{l+1} = B_0 ^ B_1 ^ ... ^ B_l
    2. Do CBC encryption on m || B_{l+1} using k and IV
        - Output ciphertext c := IV || c_0 || c_1 || ... || c_l || c_{l+1}
Dec: On input a ciphertext c = IV || c_0 || c_1 || ... || c_l || c_{l+1} and a key k
    1. Do CBC decryption on c_0 || c_1 || ... || c_l || c_{l+1} using k and IV
    2. Check if B_{l+1} = B_0 ^ B_1 ^ ... ^ B_l
        - If true, output plaintext B_0 ^ B_1 ^ ... ^ B_l
        - If false, output error
```

### Solution

#### Method 1 - Truncation

Query $$m = B\_0 || B\_1 || (B\_0 \oplus B\_1)$$ and obtain the ciphertext $$c = IV || c\_0 || c\_1 || c\_2 || c\_3$$.

Thus $$c^\* = IV || c\_0 || c\_1 || c\_2$$ should be a valid ciphertext for $$m^\* = B\_0 || B\_1$$

#### Method 2 - Swap

Query $$m = B\_0 || B\_1 || B\_2$$ and obtain the ciphertext $$c = IV || c\_0 || c\_1 || c\_2 || c\_3$$

Thus

* $$F\_k(IV \oplus B\_0) = c\_0$$
* $$F\_k(c\_0 \oplus B\_1) = c\_1$$
* $$F\_k(c\_1 \oplus B\_2) = c\_2$$
* $$F\_k(c\_2 \oplus B\_0 \oplus B\_1 \oplus B\_2) = c\_3$$

Hence $$c^\* = IV || c\_1 || c\_0 || c\_2 || c\_3$$ should be a valid tag for $$m^\* = B^*\_1 || B^*\_0 || B^\*\_2$$, where

* $$B^\*\_0 = c\_0 \oplus B\_1 \oplus IV$$
* $$B^\*\_1 = IV \oplus B\_0 \oplus c\_1$$
* $$B^\*\_2 = c\_1 \oplus B\_2 \oplus c\_0$$
* $$B^*\_0 \oplus B^*\_1 \oplus B^\*\_2 =  c\_0 \oplus B\_1 \oplus IV \oplus IV \oplus B\_0 \oplus c\_1 \oplus c\_1 \oplus B\_2 \oplus c\_0 = B\_0 \oplus B\_1 \oplus B\_2$$