1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ If you want I can give some insight about this deleted question in comments - there would be lots of reasons not to use this (deleted questions + comments are visible to trusted users and mods for some time). $\endgroup$
    – Maarten Bodewes
    Commented May 19 at 16:01
  • $\begingroup$ @MaartenBodewes wow, thanks for the reaction! Sorry for late reaction as I wasn't expecting comments so I wasn't checking this site. I actually deleted, because I realized this must be a special case of XOR encryption and that the downsides must be similar with the downsides of XOR. But yeah, I'm open to new insight! $\endgroup$
    – H-a-y-K
    Commented May 22 at 17:17

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Oh, in my proposal, the encryption is in 2 stages. What I'm wondering is, why not encrypt the already encrypted text with some other encryption algorithm with an additional layer of xor encryption (as it's easy computationally). My assumption was that probably there's some easy algebraic attack against xor encryption and the obstacle is easy to overcome, or, it's just not worth it for some reason. $\endgroup$
    – H-a-y-K
    Commented May 23 at 4:32
  • 1
    $\begingroup$ So? If your scheme is not secure then what are you adding? Some kind of confuscation? The idea that you can determine patterns is enough to render it inconsequential. If you want to combine schemes then just do a stream cipher instead of flipping specific bits. $\endgroup$
    – Maarten Bodewes
    Commented May 23 at 13:42
  • $\begingroup$ Okay, I see the flaw in my reasoning. Thanks $\endgroup$
    – H-a-y-K
    Commented May 25 at 6:46
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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