Relationship between the use of a mask and entropy

Question

This is part of an assignment and I'm not sure what conclusion I'm supposed to draw from the result.

We were supposed to generate two 1024 bytes words, one using an algorithm that randomly generate 0 and 1 (50%/50%) and one using an algorithm with a "secret" probability distribution. I'll call them word 1 and word 2 from now.

We were supposed to calculate the empirical entropy of each word bit per bit first, and then byte per byte.

I got the following results :

word 1 (bit per bit): 1.00

word 1 (byte per byte): 7.79

word 2 (bit per bit): 0.95

word 2 (byte per byte): 0.81

We where then supposed to generate a random 1024 bytes mask and apply it on each word, giving us word 1m and word 2m. The results are this time:

word 1m (bit per bit): 1.00

word 1m (byte per byte): 7.81

word 2m (bit per bit): 1.00

word 2m (byte per byte): 7.81

I'm not sure what those results mean! Of course I noticed the fact that the byte per byte empirical entropy of word 2 is low, which probably means that some specific bytes are appearing more often than other, but I don't know what happen for word 2m

Not sure I made myself very clear, don't hesitate to ask for clarifications. Thanks !

Answer 1

A uniform random source has maximum entropy: 1 bit per bit. It's fully unpredictable.

There's no way to measure the entropy of a source since you can only get a partial, finite view of it. If you see no pattern in the first $n$ bits, that doesn't prove that the source doesn't repeat every $n$ bits. Conversely, an ideal random source can return $n$ identical bits, it's just very unlikely (probability $2^{-n}$). So when you estimate the entropy of a uniform random source by sampling it, you can expect to get an entropy measure of about 1 bit per bit, whereas a non-random source usually has less (but only if your entropy estimation manages to catch the non-randomness).

You're getting 1 bit/bit and 7.79 ≈ 8 bit/byte (clearly not 7.79 byte/byte: it's a number between 0 and 1) as the entropy estimate for source 1 which is supposed to be uniformly random. This is within expected bounds.

You're getting 0.95 bit/bit and 0.81 bit/byte for source 2. This indicates that source 2 has pretty much equal numbers of 0's and 1's, but there's a very strong correlation between successive bits since grouping bytes together gives a low entropy estimate.

When you apply a uniformly random mask, the resulting combination becomes itself random. This is because every bit has a .5 chance of being flipped, so each 0 bit in the source has equal chances of being 0 or 1 in the combination, and each 1 bit in the source also has equal chances of being 0 or 1 in the combination. The entropy estimates that you get for source 1 with the random mask and for source 2 with the random mask are close to 1 bit/bit as expected.

Note that the mask is a xor, not an and. A bitwise and with a uniform random source would merely reduce the entropy by forcing about half the bits to 0.

This observation that an unpredictable mask xored with an arbitrary source results in an unpredictable combination is the basis of stream ciphers.