Prev: Mutual Databases.
Next: How secure is one's computer?
From: migueletto on 10 Jul 2010 06:38
In this type of attack we:

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.
From: Mok-Kong Shen on 10 Jul 2010 11:06
migueletto wrote:

> 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

From: mosherubin on 11 Jul 2010 04:12
On Jul 10, 1:38 pm, migueletto <miguele...(a)gmail.com> wrote:
> In this type of attack we:
>
> 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.

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
 | 
Pages: 1
Prev: Mutual Databases.
Next: How secure is one's computer?