3

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?

Improve this question
2
  • If the answer is no, can you think of a way to make the result of the XOR appear random?
    – jburcham
    Oct 5, 2018 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, 2018 at 3:41

3 Answers 3

Reset to default
11

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.

Improve this answer
6
  • 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 21:25
1

Yes.

To complement Patrick's very good answer, consider the following setting:

Bob is given two bit streams, A and B.

One is just true random bits; another is composed by XOR-ing true random bit stream with a bit stream given by Alice.

Question: Is there any way of modulating the bit stream she produces, that might give Bob better than 50% chance of guessing which stream is just random bits and which is XOR-ed with Alice's stream?

Answer: No. No matter what agreements Alice and Bob make beforehand, there is no way for Alice to make the XOR-ed stream deviate in any statistical way from complete random stream.

Improve this answer
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.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .