How is n-bit security calculated with nested encryption? What will the total $n$-bit security be if I encrypt a message with a 128-bit XOR cipher and then take that ciphertext and encrypt it with a 128-bit key. 


Is the total security level now 256? 


One definition on n-bit security said;


  n-bit security means that the attacker would have to perform $2^n$
  operations to break it



But say you are brute forcing then is this $n$ the total amount of combinations or just the expected number of combinations?
This solution considers the cipher as AES with 128-bit key and the X-OR is the one-time pad.

A careful investigation will show that 128-bit XOR is not going to help.

$$c = F_{k_1,k_2}(p) = E_{k_1}(p\oplus k_2)$$

The Ciphertext-Only attack;

If you give only one ciphertext then there is no solution. Since the decryption of the given ciphertext with every possible key is a valid plaintext and we cannot distinguish. If we assume that it is in English or another language we can only reduce the key space.

The Known-Plaintext Attack


Now, assume that we have a plaintext-ciphertext pair with $k_1,k_2$. Now we can brute-force but this will be $2^{256}$. $$p = F^{-1}_{k_1,k_2}(c) = D_{k_1}(c) \oplus k_2$$ Since once we 
decrypted we cannot determine the $k_2$, we have to search for it.
Now assume that we have more than one plaintext-ciphertext pairs encrypted with the same keys $k_1,k_2$.

Execute the key search only $k_1$ for both cyphertext simultaneously.
$$p_1 = F^{-1}_{k_1,k_2}(c_1) = D_{k_1}(c_1) \oplus k_2$$ $$p_2 = F^{-1}_{k_1,k_2}(c_2) = D_{k_1}(c_2) \oplus k_2$$

For every iteration check the if;
$$ p_1 \oplus  D_{k_1}(c_1) =  p_2 \oplus  D_{k_1}(c_2) $$
then we find the $k_1$ and $k_2$ where the $k_2$ is the $p_1 \oplus  D_{k_1}(c_1)$ 

The total complexity will be $\mathcal{O}(2 \cdot 2^{128}) = \mathcal{O}( 2^{129})$


The key-space is $2^{256}$ but the provided security is $2^{129}$