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}$


It entirely depends on the scheme used. It is possible to define a scheme that is provable secure for small messages (a one-time-pad on 128 bit messages, ignoring the 128 bit encryption) to one that can be broken almost instantly (many-time pad followed by CBC mode encryption vulnerable to padding oracle attacks).

If you want to have 256 bit security then you should simply use a 256 bit key with a known secure block cipher (128 bit security against Grovers' algorithm over the full block cipher). There is little need to go over 256 bit security. Simply applying a "XOR encryption" may give you a false sense of security.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.