Kryha Cryptanalysis - Known Plain Text Attack

• Wheel unknown
• Superposition Method
• Friedmand's Method
• Start sector
• Cryptograms in-depth
• Known Plain Text Attack. This page.
• Isomorphisms
• Hill Climbing

Introduction

The Kryha machine is vulnerable to a known plaintext attack.

This page describes two cases:

• The wheel and interior Alphabet are unknown.
• Nothing is known (neither the wheel nor the alphabets).

Two other pages provide additional information:

• The Isomorphism page describes this phenomenon and gives an example of using isomorphism to find the key (sectors and alphabets) when the plaintext is known.
• The In-depth page gives an example of how the key of a Kryha (wheels and alphabets) is reconstructed when several in-depth cryptograms are given.

Wheel and interior Alphabet unknown

Introduction

The principle is to assign each letter of the ciphertext to one of the 26 alphabets generated by the Kryha. To do this, we use the Sacco's method. How do we determine the shifts between columns? We will use pairs of identical plaintext/ciphertext letters. If these pairs are identical, they necessarily belong to the same alphabet. Then we sort the alphabets to reconstruct the internal alphabet (the one which is mobile). Finally, we deduce the shifts to move from one pair to the next (wheel reconstruction).

Create the example materials

A cryptogram is created from plaintext.

$ cat MSGS/clair_connu.sh
#!/bin/sh
python3 kryha_tui.py -o  \
    -i KPFQVGMASCHYNIORDELUBZWJXT

$ cat MSGS/tobe.txt
To be, or not to be, that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And, by opposing, end them. To die, to sleep,
No more, and by a sleep to say we end

$ cat MSGS/tobe.txt | tr -dc '[A-Za-z]' | tr '[a-z]' '[A-Z]' \
	| python3 groupe.py
TOBEO RNOTT OBETH ATIST HEQUE STION WHETH ERTIS NOBLE RINTH
EMIND TOSUF FERTH ESLIN GSAND ARROW SOFOU TRAGE OUSFO RTUNE
ORTOT AKEAR MSAGA INSTA SEAOF TROUB LESAN DBYOP POSIN GENDT
HEMTO DIETO SLEEP NOMOR EANDB YASLE EPTOS AYWEE ND

$ sh MSGS/clair_connu.sh < MSGS/tobe.txt |python3 groupe.py  \
	>| MSGS/clair_connu.cry
UAOHR NPWUI XMQIB AZPVT MXVPG YMYNG CIVOU CDYZT ISIEK SUULK
LEMGO TOYAH VUPJM WVLMV EWTMR MRCWT RMDUB HPVQW KTEWT LRHXS
NHQED DZCXC WWBZC NHCGQ OBCLQ HFEEO UMRDJ SJIJE NGFNC WHOXC
DAHSW GQBQE RKIQC PJOHS NPSEH PWSUM WFKDI RSJXL BG

In the Sacco method, to assign each letter of the cryptogram to an alphabet, a table is created with as many columns as there are sectors of the wheel and 26 rows. The figure above shows only a portion of the table. Cells with the same pattern belong to the same alphabet. We observe that if two cells in different columns belong to the same alphabet, the cells below them (in the same columns) also belong to the same alphabet (but a different one).

1 - Finding the key Length

Suppose two letters belong to the same alphabet. They are X positions apart. If two other letters belong to a different alphabet but are also X positions apart, one of the most likely explanations is that they belong to the same columns as the previous pair. The distance between the first letters of each pair is then a multiple of the number of sectors. We can thus determine the number of secteurs, and then length of the key, which corresponds to the number of sectors multiplied by 26!

Find pairs of identical plain letter/ciphered letter

I created a computer program that searches for plain letter/ciphered letter pairs and for each repetition displays the position of each occurrence and the distance between them.

For example, the plaintext letter A is encrypted as C at positions 114 and 122. The distance between these repetitions is 8.

$ python3 plain_known.py MSGS/clair_connu.cry MSGS/tobe.txt 1
...
AC [114, 122]:  8,
AD [105, 133]:  28,
BO [2, 129]:    127,
DG [155, 191]:  36,
EB [121, 157]:  36,
EC [35, 107]:   72,
EH [3, 146]:    143,
EL [50, 189]:   139,
EM [131, 179]:  48,
EQ [12, 163]:   151,
EW [65, 89, 180]:       24,91,
EX [21, 188]:   167,
HM [20, 64]:    44,
IM [52, 68]:    16,
IN [115, 143]:  28,
LU [130, 178]:  48,
NG [29, 53]:    24,
NP [6, 165]:    159,
OE [103, 127, 159]:     24,32,
OJ [138, 166]:  28,
ON [28, 100]:   72,
OW [7, 78, 154]:        71,76,
RC [77, 109]:   32,
RP [62, 86]:    24,
RS [45, 169]:   124,
SR [80, 132, 160]:      52,28,
SV [18, 66]:    48,
SW [71, 111]:   40,
SY [25, 57]:    32,
TH [85, 125]:   40,
TI [9, 13]:     4,
TQ [102, 158]:  56,
TT [19, 55]:    36,
TU [0, 8]:      8,

Find the key length

Several pairs are 36 positions apart:

• TT [19, 55] : 36
• EB [121, 157] : 36
• DG [155, 191] : 36

• (121-19) = 102 = 2 x 3 x 17
• (155-121) = 34 = 2 x 17

2 - Match an alphabet to the letters of the cryptogram

Each letter of the cryptogram belongs to one of the 26 alphabets generated by a Kryha machine.

Based on Sacco's method, if two letters belong to the same alphabet, we can deduce the other 25 pairs of letters, each belonging (taken separately) to the same alphabet. By following these steps, we can determine which of the cryptogram's letters belongs to each of the 26 alphabets.

If a pair of plaintext/ciphertext letters is repeated, it means that these pairs used the same alphabet.

For example: the pair AC is present at positions 114 and 122. The Sacco coordinates of these positions are as follows:

• 114 = 6 x 17 + 12 (row: 6, column: 12)
• 122 = 7 x 17 + 3 (row: 7, column: 3)

• (1,12) and (2,3) – positions 29 and 37
• (2,12) and (3,3) – positions 46 and 54
• (3,12) and (4,3) – positions 63 and 71
• etc.

By analyzing all the repeating pairs, we obtain the following sequence of alphabets (in groups of 17 values):

	00,01,13,14,11,23,24,10,00,12,06,03,15,12,13,25,22,
	01,02,14,15,12,24,25,11,01,13,07,04,16,13,14,00,23,
	02,03,15,16,13,25,00,12,02,14,08,05,17,14,15,01,24,
	03,04,16,17,14,00,01,13,03,15,09,06,18,15,....

The following program displays the alphabet number on the x-axis and the plaintext letter on the y-axis. The table contains the encrypted letters. For example, for alphabet number 2, the plaintext letter B is encrypted with the letter I.

$ python3 attack_clair.py
                      1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A:        X     Q W R   P B   M T     V   D C       A
B:    I M         J         O               H
C:
D:    R S                           O         G X E
E:V     C       A K U N G X   H Q W   S   B I M   L
F:      H Q W                   V   D
G:                  Z               E   Q W
H:  K U                     B I M           D
I:  P     M     Y           Z       U N         Q
J:
K:                                  Z
L:                  K U       E                     L
M:      E H   W                               O
N:I M       V J   C     O     U   G X   H       S P B
O:O A K U N G X E H   W R S       M T L     J D
P:                        C F           N     E
Q:                                                V
R:  H     R S P         L       D C F           N
S:  Y V     C F   O             E     W R S     I   T
T:U   G     H Q   R S     I M T L Y   J D C   Z O   K
U:B     T                   A           E H         P
V:
W:              T       J   C
X:
Y:            S P   I
Z:

Note: In the previous step, we determined the number of sectors (we found 17). But the result wasn't certain. Indeed, other analyses gave a factor of 19. However, now the value of 17 is confirmed. In fact, in each alphabet, each letter appears only once. If the key length had been incorrect, we would have had the same letter multiple times. In fact, that's what happened to me, because initially, I mistakenly used a key length of 16 and, to my great surprise, I had several occurrences of the same letter in different alphabets.

3 - Find the inner alphabet

We rearrange the columns (the alphabets) so that between each column, the ciphered alphabet shifts by one position.

Here is the list of columns that corresponds to the expected result:

  14-03-18-07-12-11-00-15-04-19-08-23-12-01-16-
  05-20-09-04-13-02-17-06-21-10-25

  14 318 71211 015 419 82312 116 520 9 413 217 6211025
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A: M   V Q   P   T X   W   B       D R           C   A
B:   M     Q                             O I     H
C:
D:   S     G             X             E   R O
E: H C S A M G   Q     K   X W   B U L           I N
F:   H           V Q             W           D       
G:                   Q             W Z       E        
H: I   Y         M           K           B U     D
I:       Y         M     Q   P           Z   U
J:
K:                                           Z
L: E                                 K             U L
M:   E     O       H                           W              
N: U         O I     H C S   M G V     P     X J     B
O:   U L E D R O   N   H   S A M G         K T X   W
P:         E         N     C             F         J
Q:                                     V               
R:           L   D R     N   H C S           F P  
S:     W         E   R O I   Y   C S       V   F     T
T: T   J   Z   U L   D R O I   Y H C S   M G   Q     K
U:                   E             H     A           P
V:
W:       T   J                           C
X:  
Y:       P                                     S
Z:

By completing the diagonals, we deduce the first column which corresponds to the ciphered alphabet (the internal movable alphabet):

	MASCHYNIORDELUBZWJXXTKPFQVG

4 - wheel reconstruction

Now, it's easy to reconstruct the sectors of the wheel:

The first plain letter/ciphered letter pair is T/U. This is the starting position. The U is found in column 6 (letter number 0). The second pair, O/A, has the ciphered letter in column 13, which is 7 positions later. Next, for the pair B/O, the ciphered letter is in column 19, 6 positions further. Then, for the pair E/H, the ciphered letter is in column 0, 7 positions further. Finally, for the pair O/R, the ciphered letter is in position 5, 5 positions further. For now, we have the following shifts:

	7, 6, 7, 5

	7, 6, 7, 5, 6, 7, 6, 8, 6, 10, 5, 6, 5, 7, 6, 5, 9

$ echo UAOHR NPWUI XMQIB AZPVT | \
python3 kryha_tui.py -o \
	-s 7,6,7,5,6,7,6,8,6,10,5,6,5,7,6,5,9 \
	-i MASCHYNIORDELUBZWJXTKPFQVG -d -a 6
TOBEORNOTTOBETHATIST

Note: we have an initial shift of 6 positions because the first plain letter/ciphered letter pair is in column 6.

The whole key is unknown

Introduction

The method is broadly identical to the previous one, but because the outer alphabet is not direct (ABC...Z), the inner alphabet cannot be directly deduced. It is first necessary to find the difference between two inner alphabets (or two outer alphabets).

Create the example materials

A cryptogram is created from plaintext.

$ cat /tmp/known_plain.sh
python3 kryha_tui.py -o  \
        -i KPFQVGMASCHYNIORDELUBZWJXT \
        -e ZCJBWYKNAGQSPFTROXVMDULEHI 
$ cat MSGS/tobe.txt | tr -dc '[A-Za-z]' | tr '[a-z]' '[A-Z]' \
	| python3 groupe.py
TOBEO RNOTT OBETH ATIST HEQUE STION WHETH ERTIS NOBLE RINTH
EMIND TOSUF FERTH ESLIN GSAND ARROW SOFOU TRAGE OUSFO RTUNE
ORTOT AKEAR MSAGA INSTA SEAOF TROUB LESAN DBYOP POSIN GENDT
HEMTO DIETO SLEEP NOMOR EANDB YASLE EPTOS AYWEE ND

$ sh /tmp/known_plain.sh < MSGS/tobe.txt | \
	python3 groupe.py >| MSGS/known_plain.cry
$ cat MSGS/known_plain.cry
OCDQE HZXOS KSWSY RDLJB JEXFX VPFOT EVJCH FOMNL AHRFU MHIIE
YXJTG BDVSL NNTLJ RJQJX BRAKM OIAXA SSXZZ GTNMR FKHVP DHYLP
OSXUY XEFMA QRFXE QVFKY AIEBY GKULD VTSXE TTBTO CAZQQ TQSRV
AKEQX WBIXU SYMWM ZTZNM GCFSN SVPVT RTZLM JRGEY OW

1 - The first steps

We proceed as before:

Search for pairs of identical plaintext/ciphertext letters

$ python3 plain_known.py MSGS/known_plain.cry MSGS/tobe.txt 1
...
AE [114, 122]:  8,
AX [105, 133]:  28,
BD [2, 129]:    127,
DW [155, 191]:  36,
EE [21, 188]:   167,
EF [35, 107]:   72,
EI [121, 157]:  36,
EQ [3, 146]:    143,
ER [65, 89, 180]:       24,91,
ET [131, 179]:  48,
EW [12, 163]:   151,
EY [50, 189]:   139,
HJ [20, 64]:    44,
IJ [52, 68]:    16,
IQ [115, 143]:  28,
LV [130, 178]:  48,
NT [29, 53]:    24,
NZ [6, 165]:    159,
OO [28, 100]:   72,
OT [138, 166]:  28,
OU [103, 127, 159]:     24,32,
OX [7, 78, 154]:        71,76,
RA [77, 109]:   32,
RM [45, 169]:   124,
RT [62, 86]:    24,
SJ [18, 66]:    48,
SR [71, 111]:   40,
SS [80, 132, 160]:      52,28,
SV [25, 57]:    32,
TB [19, 55]:    36,
TG [85, 125]:   40,
TO [0, 8]:      8,
TS [9, 13]:     4,
TX [102, 158]:  56,
...

Finding the key Length (in fact, the number of sectors)

Match an alphabet to the letters of the cryptogram

	00,01,13,14,11,23,24,10,00,12,06,03,15,12,13,25,22,
	01,02,14,15,12,24,25,11,01,13,07,04,16,13,14,00,23,
	02,03,15,16,13,25,00,12,02,14,08,05,17,14,15,01,24,
	03,04,16,17,14,00,01,13,03,15,09,06,18,15,....

2 - The alphabets, but before decimation

Introduction

The ciphered letters are on the y-axis. The alphabets are on the x-axis. The lines contain the same sequence of letters, but shifted.

  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A:N         O   W S             A R         H
B:                  Y         T     G O         I
C:  O                   A               P       T
D:O                     R   B                 T
E:  H     M   N         O E W       K       A
F:    O E   S   I         A   L                 N   U
G:          T         E W           D
H:    H           T       O     S   I           R
I:        R                   N T         E
J:E   S   I         A           H
K:  N T U     O E                   R
L:  I   F                           N T U     O     S
M:    D   A R             P       T     G   E   S
N:                O E       I   F     A     B
O:T       O                   A R             P     N
P:                          T       O E   S
Q:            M   N T         E       I             L
R:    B       Y                   E   S         D   A
S:  R   B       Y       N T U     O     S         D
T:      D     R   B         P     N       G O E
U:              O E
V:  S       F     A   L       H         N T
W:                              E             D
X:      M   N T     G O E           F     A       Q
Y:        F     A   L       H           T U       E
Z:U     O     S                               M   N T

  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A:N         O   W S             A R         H
O:T       O                   A R             P     N
Z:U     O     S                               M   N T
F:    O E   S   I         A   L                 N   U
C:G O                   A               P       T
D:O                     R   B                 T
J:E   S   I         A           H
V:W S       F     A   L       H         N T
Y:S       F     A   L       H           T U       E
L:  I   F                           N T U     O     S
T:I     D     R   B         P     N       G O E
M:K   D   A R             P       T     G   E   S
I:F       R                   N T         E
B:D                 Y         T     G O         I
P:                          T       O E   S
S:A R   B       Y       N T U     O     S         D
R:R   B       Y                   E   S         D   A
W:L                             E             D
Q:B           M   N T         E       I             L
H:Q   H           T       O     S   I           R
E:  H     M   N         O E W       K       A
X:H     M   N T     G O E           F     A       Q
G:Y         T         E W           D
N:P               O E       I   F     A     B
U:M             O E
K:  N T U     O E                   R

	NTU.GOEWS.IKFD.ARLVQ.HYPM.

	AOZFCDJVYLTMIBPSRWQHEXGNUK

3 - The value of decimation

In the chapter on Friedman's method, we established the different cipher alphabets based on shifts (If a sector spans three notches, we have a shift of seven (3+4)). Consequently, each cipher letter in each alphabet is shifted by an integer multiple relative to the same letter in another alphabet.

When using Sacco's method, the cipher alphabets in the first column are all present, but the letters that compose them are shifted relative to each other by a multiple of L. L is the sum of the sector shifts (see Konheim's method).

Therefore, the alphabets we determined previously are not correct. We must perform a decimation operation on them, taking L as the factor.

In short, we need to determine L before calculating the actual alphabets.

We will use Konheim's formula:

	s * L = L[c1] – L[c2]

• L corresponds to the sum of the shifts of each sector. In the case of the standard wheel, L = 111.
• s corresponds to the number of periods, i.e., the difference in position between the two letters divided by the number of sectors.
• c1 corresponds to the index of the first letter modulo the number of sectors.
• c2, likewise, but for the second letter.
• L[x] = is the sum of the shifts of the sectors up to position x. = l[0] + l[1] + … + l[x]
• l[i] corresponds to the shift caused by the i-th sector.

Here is the application of this formula to our problem:

	L[0]-L[1]=25L  => -l[1] = 25L  => l[1] = -25L
	L[1]-L[2]=-12L => l[2] = 12L
	L[7]-L[8]=10L  => -l[8] = 10L  => l[8] = -10L
	L[3]-L[4]=3L   => -l[4] = 3L   => l[4] = -3L

What is the most likely value of L? To find this value, we will calculate the previous formulas for all possible values of L:

$ cat  /tmp/calcule.py
for L in range(26):
    x = (-(25 * L)%26)%26
    y = (12 * L)%26
    z = (-(10 * L)%26)%26
    w = (-(3  * L)%26)%26
    print("%2d: %2d %2d %2d %2d" % (L,x,y,z,w))

$ python3 /tmp/calcule.py
 0:  0  0  0  0
 1:  1 12 16 23
 2:  2 24  6 20
 3:  3 10 22 17
 4:  4 22 12 14
 5:  5  8  2 11
 6:  6 20 18  8
 7:  7  6  8  5
 8:  8 18 24  2
 9:  9  4 14 25
10: 10 16  4 22
11: 11  2 20 19
12: 12 14 10 16
13: 13  0  0 13
14: 14 12 16 10
15: 15 24  6  7
16: 16 10 22  4
17: 17 22 12  1
18: 18  8  2 24
19: 19 20 18 21
20: 20  6  8 18
21: 21 18 24 15
22: 22  4 14 12
23: 23 16  4  9
24: 24  2 20  6
25: 25 14 10  3
$

4 - The inner and outer alphabets

The inner alphabet is reconstructed by decimating (every 7 letters) of the indexes of the rows in the previous table:

	AOZFCDJVYLTMIBPSRWQHEXGNUK

	A......O......Z......F....
	A.C....O.D....Z.J....F.V..
	A.C.Y..O.D.L..Z.J.T..F.V.M
	A.C.Y.IO.D.L.BZ.J.T.PF.V.M
	ASC.Y.IORD.L.BZWJ.T.PFQV.M
	ASCHYNIORDELUBZWJXTKPFQVGM

	NTU.GOEWS.IKFD.ARLBQ.HYPM.

	N......T......U
	N.G....T......U........... 
	N.G.S..T.O....U.E.I....W..
	N.G.S..T.O....U.E.I....W.K
	NAG.SPFTRO..MDULE.I....W.K
	NAGQSPFTRO..MDULEHI...BWYK

5 - wheel reconstruction

Now, it's easy to reconstruct the sectors of the wheel:

	Cryptogram:	O C D Q E ...
	Plain text:	T O B E O ...

 	1 - O / T  -  0
           ASCHYNIORDELUBZWJXTKPFQVGM
           NAGQSPFTRO..MDULEHI...BWYKNAGQSPFTRO..MDULEHI...BWYK

	2 - C / O  - +7
                  ASCHYNIORDELUBZWJXTKPFQVGM   
           NAGQSPFTRO..MDULEHI...BWYKNAGQSPFTRO..MDULEHI...BWYK

	3 - D / B  - +6
                        ASCHYNIORDELUBZWJXTKPFQVGM   
           NAGQSPFTRO..MDULEHI...BWYKNAGQSPFTRO..MDULEHI...BWYK

	4 - Q / E  - +7
                               ASCHYNIORDELUBZWJXTKOFQVGM   
           NAGQSPFTRO..MDULEHI...BWYKNAGQSPFTRO..MDULEHI...BWYK

	5 - E / O  - +5
                                    ASCHYNIORDELUBZWJXTKOFQVGM
           NAGQSPFTRO..MDULEHI...BWYKNAGQSPFTRO..MDULEHI...BWYK

	7,6,7,5,6,7,6,8,6,10,5,6,5,7,6,5,9

References

Books & articles

• Marks, P. 2011. Operational Use and Cryptanalysis of the Kryha Cipher Machine. Cryptologia 35(2): 114-155.
  Note: This article describes the different cryptanalysis methods used against Kryha. The known-plain attack is discussed in detail.
• Machine Cryptography and Modern Cryptanalysis, By Cipher A. Deavours & Louis Kruh, (1985), Artech House Publishers.