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 12letter 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: MokKong 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 12letter 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/visualinspectionofchaocipheroutputimpliesweakness/ 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? 