2

XOR has the following truth table:

0, 0 : 0
0, 1 : 1
1, 0 : 1
1, 1 : 0

So per bit in an XOR operation, there is a 50% chance of that result being 1 and 50% chance of it being 0. If you XOR a random number (all possibilities were equally likely when created, say from a CSPRNG) and a non-random number, does that result appear random?

  • If the answer is no, can you think of a way to make the result of the XOR appear random? – jburcham Oct 5 '18 at 18:43
  • 1
    The encryption between your browser and this website does just that. It uses AES to generate a random stream of data, then XORs that data with the web page before sending the page to your computer. The result is that the data being sent from the site to your computer looks completely random. – forest Oct 6 '18 at 3:41
9

A random value does not loose any of its randomness if it is combined without information loss with a non-random value. XOR against some fixed (i.e. non-random) value does not cause such information loss, i.e. the original random value can be recreated from the result by simply XORing again with the same fixed value. Contrary to that AND or OR would cause information loss, i.e. they can not be reversed.

But the randomness does not increase either. Thus, if you XOR a 8 bit random value to a 32 bit non-random value it will result in 8 bit of randomness, not 32 bit.

  • So for example: lets say we have A = [0,1,1,0] and B = [1,1,1,0], where A was randomly produced from a RNG and B is not random at all. Then C = XOR(A,B). Would C be considered a random value? – jburcham Oct 5 '18 at 18:48
  • @jburcham: Yes, C will be random and as much random as A was. That's what I've tried to say with my answer. – Steffen Ullrich Oct 5 '18 at 18:50
  • 2
    One caveat would be that you shouldn't use something like XOR to generate additional random data. Both A and C are random, but concatinating A and C together is not random since you used a known process to derive the second half of AC from A. I know that wasn't said in the question or answer, but I felt it was useful to add in case anyone tried to use XOR to lengthen a random sequence. – Daisetsu Oct 5 '18 at 20:27
  • 2
    To demonstrate what Daisetsu is saying, if values A and B are random, then Concat(A,B) is more random than A or B by themselves. However, if C is non-random, and D = XOR(A,C), then Concat(A,D) is only as random as A by itself. – Ghedipunk Oct 5 '18 at 21:21
  • @Ghedipunk: Of course you can only get as much (and maybe less) randomness from a deterministic computation as you put into it. In your second example only A is random and thus you cannot get more randomness than A has provided out of it. – Steffen Ullrich Oct 5 '18 at 21:25
0

Some easy math can provide you an answer.

Let us say you have a sequence of N bits. p(n) can be the probability that bit number n among the N has value 1. Then obviously 1-p(n) is a probability that it is a 0.

Now let us do a XOR of the previous sequence of N bits with a sequence of same length that is random. For this second sequence, p'(n) = 0.5 as there is equal probability to have a 0 or a 1.

To compute the p''(n) probably for the result to be a bit at value one, we need to search for cases where the result is 1.

There are two cases:

  • bit from first sequence is 1 (probability p(n)) and bit from second sequence is 0 (probability 1-p'(n))
  • OR bit from first sequence is 0 (probability 1-p(n)) and bit from second sequence is 1 (probability p'(n))

So the probability p''(n) that the resulting bit at position n has value 1 is p(n) × (1-p'(n)) + (1-p(n)) × p'(n)

But since p'(n) = 0.5 = 1-p'(n) (we said it is random), the above formula simplifies itself easily:

  • p''(n) = p(n) × (1 - p'(n)) + (1 - p(n)) × p'(n)
  • p''(n) = p(n) × 0.5 + (1 - p(n)) × 0.5
  • p''(n) = p(n) × 0.5 + 0.5 - 0.5 × p(n)
  • p''(n) = 0.5

The resulting string is random, as soon as one of the two being XORed was random.

This is the core property of the XOR operation, coming from its logic table, that explains why perfect encryption is achieved with XORing something with a random string as the result is random and hence could be decrypted equally to any value in the complete space of values. And of course it is impractical to use because it needs a random sequence of the same length than what needs to be encrypted, never to be reused, and to be shared between the sender and the recipient.

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.