The Problem. Alice has a plaintext p, a random bitstring b, and a key k.  She wishes to send the message p to Bob.  In order to do this, she uses the bitstring to encode the plaintext into ciphertext c.  She also wishes to send Bob the bitstring, but wishes to encode it first.  She uses the key to encode the bitstring into a second bitstring b'.  Alice sends Bob c and b'.  Trudy captures these as a passive wiretapper.  What should Trudy do to decode the message?

The Solution. Here is a more complete description of the strings involved.  The message p and the and the bitstring b both have length N, which we assume is large.  We can write these out as bitstrings
        b = (b₁,...,b_N)
        p = (p₁,...,p_N)
The key k has length L, which we assume is small.  However, by repeating the key enough times, we can fill it out to length N so that
        k = (k₁,...,k_N)
where
        k_i = k_{i mod L}
The encoding is done by using exclusive or on each of the bits. We denote this by + so that
        c = p + b = (p₁+b₁,...,p_N+b_N)
        b' = b + k = (b₁+k₁,...,b_N+k_N)

Here is the one minute answer to this:  Both encryptions are using XOR.  XORing with a given string is 1-1 and therefore invertible.  The way of inverting  this is to XOR with the same string again.

Here are the details.  Exclusive or is the same thing as addition mod 2. This is associative and commutative and has the property that anything added to itself is 0. If Trudy adds b' and c together, she gets
        b + c = ( b + k ) + ( p + b )
                 = p + k + b + b
                 = p + k
But this is just the plaintext p encoded using the key k. Since k is short, this is just a polyalphabetic cipher and we can break this using techniques we've seen in class.

You cannot hope to use a statistical attack to decode b from b'. The reason for this is that there b has no statistical regularities, so you cannot use digrams and trigrams in hopes of discovering the key length. If the key length is short, you might try ennumerating all possible keys. If you do this, you will not know when you have succeeded in finding b from b'. You will only know this when your proposed key produces a proposed b which actually succeeds in decoding c. However, since there are 2^L keys of length L, this brute force attack will not work if L is moderately large.