0
$\begingroup$

If a symmetric encryption key $K$ has been generated by some recommended (NIST for example) RBG then we should have a key with high entropy.

But if we xor other bit-strings (e.g. IVs, other keys, etc.) to $K$, how does this affect the level of the entropy of the resulting bit-string?

Specifically, how is the level of entropy affected if we apply:

  1. $K \oplus K^*$, where $K^*$ has the same/similar level of entropy as $K$.
  2. $K \oplus IV$, where $IV$ has a much lower entropy than $K$.
  3. $K \oplus C$, where $C$ is some ciphertext output that is (repeatedly) fed back into the cipher to begin a new round.

In short, I am interested in the effects of entropy levels when a 'strong entropy' bit string is xored with a 'weak entropy' bit string or another 'strong entropy' bit string.

Related to Q3, I wonder how many times an output can be xored with the same key before entropy is lowered (assuming that happens at all). We assume the output $C$ is different each time.

It seems this cannot happen because the output $C$ of a cipher should necessarily be unpredictable, but that is on the assumption that xoring two high entropy bit strings will always retain a high entropy.

  1. Is there a simple mathematical way to show entropy is retained or lost when two bit strings are xored?
$\endgroup$
2
$\begingroup$

If I take a strong key K of length $n$ taken from a good source of randomness, it will have $n$ bits of entropy and will be independent of anything else (not derived from it).

If we later Xor it with a weak password K* for instance or something else we still have the same $n$ bits of entropy.

Each bit is still uniformly random and independent of each other. Even if K* bits were biased and correlated.

It is easy to see with an example. If we Xor a random key with all zeros, we get the same; if some bits are 1, it's just a negation, and negating a uniformly random bit is still uniformly random. Also, correlated bits won't make a difference. If I negate every other bit, or follow some other pattern, it makes no difference.

However if you XOR with something dependent on the key, all bets are off, and you could end up with 0 entropy, for instance, by Xoring with itself.

$\endgroup$
  • $\begingroup$ But is there a clear and simple way to show this mathematically? I refer to Q4. $\endgroup$ – Red Book 1 Oct 24 '18 at 10:25
  • $\begingroup$ Is not the ciphertext a random string of bits that depends on the key? $\endgroup$ – Red Book 1 Oct 25 '18 at 14:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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