I've been taught that one-time pads are the only perfect encryption since the only way to recover the message is by knowing the key.

For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message.  This approach will produce all messages that can be expressed with 100 bits.

However, not all bitstrings are random, e.g. 11111111111111 is less random than 01101001001101.  This observation seems to contradict the idea of an unbreakable one time pad.

We know two random bitstrings are independent of each other, as well as independent from non-random bitstrings.  So, knowing a random bitstring will not allow you to shorten the description of a second bitstring and vice versa.  Thus, if we randomly generate a bitstring BS1, then when XORed with the key BS2 it will produce a third bitstring BS3 that is not compressible.  

Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3).  Then, either BS1 and BS2 are not both random or are not independent.  The only case where they are random, but not independent, is if one is a part of the other.

This means that if XORing BS1 with ciphertext BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

So, at least in theory, it seems that one-time pads are breakable, although this approach is not computable since we'd need to compute that a bitstring is truly random.  

This argument contradicts what I've been taught, and I'm wondering if OTPs are only said to be perfect because randomness is not computable.


  For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can be expressed with 100 bits.


That's not the reason why one-time-pads are considered secure. The reason is that even if you try all possible keys that you get all possible plaintext and you have no method of choosing which one is right. The size of the plaintext/ciphertext/keystream doesn't matter.


  However, not all bitstrings are random, e.g. 111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.


111111111111 is equally likely as 01101001001101 or any other value of the same size when chosen randomly.


  Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3). Then, either BS1 and BS2 are not both random or are not independent. The only case where they are random, but not independent, is if one is a part of the other.


Values are compressible if they are part of a set where certain values are more likely than others. This is not the case for $C = P \oplus K$ if $K$ is fully random. This is because $C$ will be fully random as well, independent of $P$ being random or not.


  This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.


This will never be the case as BS5 will not be compressible; each possible value of BS5 will be as likely as the other values of BS5 because of the reasons explained above.
