Little problem with Vernam Cipher

Question

We have got a task with the following content:

Given is a language with 3 letters: A, B, C.

The binary expression is:

A = 000, B = 1111 and C = 0011 

Two words were encrypted in this language with the same key:

W1 = 0101001110111010101100100 
W2 = 1011001010000000000101011 

Determine the possible message pair.

How am I able to do this?

Answer 1

I think guessing key bits and checking if the plaintext is valid in both words is the way to go (much like a binary puzzle).

For instance, it is clear that at least one of the words starts with an A because if you take the first 4 bits they are all different except for the last one. That rules out BB, BC, CB or CC as combinations of the first letter, because they don't differ by 3 bits where the final bit is 1. Similarly you should be able to rule out two other combinations, leaving only one combination - unfortunately you don't know yet if it is AX or XA. Similarly, you expect an AA and B combination at the final bits as the bits must be each other complements.

I would implement this using left to right guessing of key bits with backtracking in case the pattern becomes impossible for either W1 or W2. You may even start at each end, but I don't think that is needed. You should be able to do this by hand, but programming it may be fun as well.

In the end I see 13 bits set to 0 and 13 bits set to 1, and I had to backtrack 18 times to find a solution (assuming bits set to 0 before possibly back tracking, simply working from left to right), which is entirely doable for a mere human. Of course giving the key, the pattern of W1 or W2 gives away the entire result, so I won't do that.

The complement of the found key is also a solution in this particular case.

---

High level design:

• create a tree for the key;
• create code to perform a breath first search of the key bits;
• create a method to check if a given (partial key) could be valid;
  • create a method that creates a tree of patterns;
  • check for W1 and W2 - up to the key size - if the key produces a tree up to a leaf node;
  • to do this you can search the tree using depth first search;
• create checks to see:
  • if the key is complete;
  • if there can be a partial match at the end;

Beware to check the end conditions correctly, or you may have to do some manual restructuring at the end.

This is not an easy task to program. Basically you need to create a tree for both the key as well as the resulting plaintext to perform the pattern matching.

Answer 2

After, Maarten comment, here an intro to solve by two-time pad;

we have;

A = 000
B = 1111
C = 0011

0101001110111010101100100 
1011001010000000000101011
-------------------------
1110000100111010101001111  x-ored ciphertext gives us x-ored plaintext
1111                       only this possible.
000
-------------------------
1110000100111010101001111  
1111                       
0001111                    only this possible.
-------------------------
1110000100111010101001111  
11111111                       
0001111                    only this possible.
-------------------------
1110000100111010101001111  
11111111                       
0001111                    Now here we have a branching 000 and 0011 
                           but one causes an immediate contradiction.

The rest is left to the OP.