Why not flip random bits of the encrypted message for additional security? (hybrid system)

Question

Suppose a binary word of $n$ bits is the result of encryption (doesn't matter with what algorithm) that now has to be sent from person A to person B. Suppose additionally, A and B have a symmetric key that's a subset $s \subseteq \{1,\dots,n\}$. Before sending the message, person A flips all the bits whose indexes are in $s$. E.g. if $s = \{1,2,3\}$ the bits number 1,2,3 would be flipped. Given that $s$ is a symmetric key, person B can recover the initial encrypted message by flipping the bits back.

My question is: is this type of (or similar) approach used anywhere? Why wouldn't it be used everywhere?

Answer 1

Your proposal boils down to introducing a second key, and using it to perform a simple xor encryption. If you have so little confidence in the first algorithm that you would not use it as-is, you should replace it with a well-designed one that you do have confidence in.

On top of that, if you are willing to double the amount of key material you are managing, a second encryption layer makes very inefficient use of it. In general, breaking 2 layers of k-bit encryption takes $2^k + 2^k = 2^{k+1}$ work, whereas a well-designed cipher that takes as much key material should provide $2^{2k}$ security. In your case, note that if you know the first half of the key and you have a single plaintext/ciphertext pair, you can immediately derive the second half of the key.

If I understand your calculation, you are trying to get the order of the power set for $\{1,...,n\}$, which should be $2^n$.

Answer 2

Before sending the message, person A flips all the bits whose indexes are in $s$. E.g. if $s={1,2,3}$ the bits number $1,2,3$ would be flipped.

This is not secure. You might say that only half of the bits are normally flipped when encrypting (which makes sense, as 0 and 1 would be equally possible in the ciphertext). However, this is different from flipping bits that are on specific indices, leaving the other bits untouched. It would mean that the scheme directly leaks plaintext. This is true even if the location of the other bits are not known, as the plaintext bits that have been left alone are likely part of a pattern which can be recognized.

For instance, it could be that 7 subsequent bits are not flipped, storing the the letter M. And adversary might then know that M is the the most likely value there and can therefore know with high certainty that these bits were not flipped. Leaking any part of the message means that the cipher is not secure. No computation necessary.

Answer 3

A variation of your idea called Key-Whitening was used by Ron Rivest (the R in RSA) to strengthen the DES by XORing an extra 64-bit key to the input and yet another extra 64-bit key to the output of DES. The result is called DES-X, and according to wikipedia currently the best known attack requires $2^{32.5}$ known plaintexts-ciphertext pairs and $2^{87.5}$ time.