Chosen plain text attack on Chaocipher
migueletto
1) Choose a plaintext
2) Submit the plaintext for encipherment
3) Get back the ciphertext
Our task is to recover the unknown key (that is, the initial settings
on both wheels).
How well does Chaocipher perform under this type of attack ?
Before we begin our attack, let's see what happens to the wheels when
plain text is enciphered with known keys.
First we choose our plaintext: a long sequence of 'A's:
AAAAAAAAAAAAAAAAAA....
Assume left wheel is OUHJTGLXAIEMKWVZQRPBSNYFCD and right wheel is
ANYLCGZHWBUEIMFVQRJXTOSKDP (both chosen at random). This table shows
the sequence of: iteration number, left wheel, right wheel, cipher
letter, plain letter:
1: OUHJTGLXAIEMKWVZQRPBSNYFCD ANYLCGZHWBUEIMFVQRJXTOSKDP O A
2: OHJTGLXAIEMKWUVZQRPBSNYFCD NYCGZHWBUEIMFLVQRJXTOSKDPA D A
3: DHJTGLXAIEMKWOUVZQRPBSNYFC NYGZHWBUEIMFLCVQRJXTOSKDPA C A
4: CHJTGLXAIEMKWDOUVZQRPBSNYF NYZHWBUEIMFLCGVQRJXTOSKDPA F A
5: FHJTGLXAIEMKWCDOUVZQRPBSNY NYHWBUEIMFLCGZVQRJXTOSKDPA Y A
6: YHJTGLXAIEMKWFCDOUVZQRPBSN NYWBUEIMFLCGZHVQRJXTOSKDPA N A
7: NHJTGLXAIEMKWYFCDOUVZQRPBS NYBUEIMFLCGZHWVQRJXTOSKDPA S A
8: SHJTGLXAIEMKWNYFCDOUVZQRPB NYUEIMFLCGZHWBVQRJXTOSKDPA B A
9: BHJTGLXAIEMKWSNYFCDOUVZQRP NYEIMFLCGZHWBUVQRJXTOSKDPA P A
10: PHJTGLXAIEMKWBSNYFCDOUVZQR NYIMFLCGZHWBUEVQRJXTOSKDPA R A
11: RHJTGLXAIEMKWPBSNYFCDOUVZQ NYMFLCGZHWBUEIVQRJXTOSKDPA Q A
12: QHJTGLXAIEMKWRPBSNYFCDOUVZ NYFLCGZHWBUEIMVQRJXTOSKDPA Z A
13: ZHJTGLXAIEMKWQRPBSNYFCDOUV NYLCGZHWBUEIMFVQRJXTOSKDPA V A
14: VHJTGLXAIEMKWZQRPBSNYFCDOU NYCGZHWBUEIMFLVQRJXTOSKDPA U A
15: UHJTGLXAIEMKWVZQRPBSNYFCDO NYGZHWBUEIMFLCVQRJXTOSKDPA O A
16: OHJTGLXAIEMKWUVZQRPBSNYFCD NYZHWBUEIMFLCGVQRJXTOSKDPA D A
17: DHJTGLXAIEMKWOUVZQRPBSNYFC NYHWBUEIMFLCGZVQRJXTOSKDPA C A
18: CHJTGLXAIEMKWDOUVZQRPBSNYF NYWBUEIMFLCGZHVQRJXTOSKDPA F A
19: FHJTGLXAIEMKWCDOUVZQRPBSNY NYBUEIMFLCGZHWVQRJXTOSKDPA Y A
20: YHJTGLXAIEMKWFCDOUVZQRPBSN NYUEIMFLCGZHWBVQRJXTOSKDPA N A
21: NHJTGLXAIEMKWYFCDOUVZQRPBS NYEIMFLCGZHWBUVQRJXTOSKDPA S A
22: SHJTGLXAIEMKWNYFCDOUVZQRPB NYIMFLCGZHWBUEVQRJXTOSKDPA B A
23: BHJTGLXAIEMKWSNYFCDOUVZQRP NYMFLCGZHWBUEIVQRJXTOSKDPA P A
24: PHJTGLXAIEMKWBSNYFCDOUVZQR NYFLCGZHWBUEIMVQRJXTOSKDPA R A
25: RHJTGLXAIEMKWPBSNYFCDOUVZQ NYLCGZHWBUEIMFVQRJXTOSKDPA Q A
26: QHJTGLXAIEMKWRPBSNYFCDOUVZ NYCGZHWBUEIMFLVQRJXTOSKDPA Z A
27: ZHJTGLXAIEMKWQRPBSNYFCDOUV NYGZHWBUEIMFLCVQRJXTOSKDPA V A
28: VHJTGLXAIEMKWZQRPBSNYFCDOU NYZHWBUEIMFLCGVQRJXTOSKDPA U A
29: UHJTGLXAIEMKWVZQRPBSNYFCDO NYHWBUEIMFLCGZVQRJXTOSKDPA O A
30: OHJTGLXAIEMKWUVZQRPBSNYFCD NYWBUEIMFLCGZHVQRJXTOSKDPA D A
...
Note the ciphertext we got: ODCFYNSBPRQZVU ODCFYNSBPRQZVU
ODCFYNSBPRQZVU ...
It is a repetition of the same 14 letters. But there is more.
Because of the permutation rules, the left wheel advances in a
peculiar pattern, with a fixed sequence of 12 letters from positions 2
to 13 and a shifting sequence of 14 letters at the remaining
positions.
From iteration 2 to the end, the fixed pattern
is: .HJTGLXAIEMKW.............
The remaining 14 letters are exactly our repeating ciphertext pattern,
only in reverse order.
Now consider a real attack, where the key is unknown (for simplicity I
will use the same key of the previous example). We submit 14 'A's for
encipherment and get the ODCFYNSBPRQZVU as ciphertext. First we
reverse it to UVZQRPBSNYFCDO. Then we shift one place to the right so
we get O on the first position: OUVZQRPBSNYFCD (because the first
ciphertext we got was 'O' and we want it be the first letter in the
wheel). Then we insert the 12-letter gap at position 3:
OU............VZQRPBSNYFCD (note that on the first iteration the gap
is at position 3, not 2).
We have just found 14 letters of the left wheel in their correct
positions. Since we know that 'A' enciphers to 'O' in the first pass
and we put 'O' in the first position of left wheel, we must put 'A' in
the first position of the right wheel.
The key so far is:
Right wheel : A.........................
Left wheel : OU............VZQRPBSNYFCD
We have recovered 1+14 of 26+26 wheel letters. That is 15/52 = 28% of
the key. Not bad for a chosen plaintext of just 14 letters.
Once we removed the entropy of the plaintext, Chaocipher started
leaking information about the key. A chosen plaintext attack is
usually considered unrealistic, but it can provide useful information
into the inner workings of the cipher. And in this specific case, the
amount of chosen plaintext was very small.
Regards.
Mok-Kong Shen
> Once we removed the entropy of the plaintext, Chaocipher started
> leaking information about the key. A chosen plaintext attack is
> usually considered unrealistic, but it can provide useful information
> into the inner workings of the cipher. And in this specific case, the
> amount of chosen plaintext was very small.
Sorry that I am not yet quite clear of your point. Could you, without
prior knowledge of the algorithm, deduce at least a part of the
algorithm? Or do you mean something else?
Thanks.
M. K. Shen
mosherubin
See http://brainwagon.org/2010/07/06/visual-inspection-of-chaocipher-output-implies-weakness/
for a similar observation. You certainly squeezed a lot of juice out
of a minimal number of chosen plaintext <g>.
Moshe Rubin
mvandew...@gmail.com
> for a similar observation. You certainly squeezed a lot of juice out
> of a minimal number of chosen plaintext <g>.
>
> Moshe Rubin
I've been tinkering with the Chaocipher over on my blog a bit, and
probably will continue a bit longer. I find the cipher to be
deliciously ingenious, although I suspect that (at least in the modern
computer age) it will be cracked with relative ease.
I made exactly the same observation as the original poster: that if
you passed in a file consisting of entirely the same character, you
get output which cycles with a very short period. This clearly means
that information in the plaintext leaks into the cipher text, which is
obviously good for the code breaker. I've since worked up a little
solver that takes the cipher/plaintext pairs and solves for the
original key in the straightforward way. I documented that on my
blog back on July 8th...
http://brainwagon.org/2010/07/08/progress-on-the-chaocipher/
I haven't had a lot of time to work on it since then, but I have
discovered that there are a number of typos in the original Exhibit 1
text, and that Exhibit 2 must use some variant of the original cipher
(or, I could have a bug) because it doesn't recover a key that
works.
I've also begun to work on a version of the solver that works in
ciphertext only mode using a dynamic programming approach. Not sure
if it is going to pan out yet. Stay tuned.