|
Home Page Kryha Home Page Kryha Cryptanalysis Home Page
|
IntroductionIf we have several cryptograms encrypted with the same key, we say that these messages are "in-depth." Regardless of the encryption method, it is possible to recover the plaintext of the messages. Therefore, in the end, we will have several plaintext/ciphertext pairs. We can then attack the encryption system and reconstruct it (if it is unknown and not too complex) or, if it is known, reconstruct the key. Note: The superposition page describes (among other things) the use of IC (Index of Coincidence) to prove that messages are in-depth.
The exploits of Parker Hitt against the KryhaIn 1929 and 1930, the American Parker Hitt analyzed two series of in-depth messages. Each of these series had been encrypted using a kryha, but with different wheels. For both series, Parker Hitt succeeded in deciphering the messages and reconstructing the secret elements of the machine: the alphabets and the wheel.
Method Used by Parker HittIn handwritten memos, Parker Hitt described his method:
Commentary on Parker Hitt's methodIn short, Parker Hitt's method consists of first finding the fixed outer alphabet (which corresponds to the plaintext alphabet). This is done by analyzing each column, which corresponds to an alphabet. To move from one column to another (and therefore from one alphabet to another), the alphabets must be shifted (this corresponds to the shifts created by the sectors of the wheel). For the alphabets to be superimposed, they must be in order. Thus, the outer alphabet and the shifts are determined simultaneously. Finally, the inner alphabet is determined by following the shifts of one or more plaintext letters, such as E or T (the most frequent letters). In the end, it is verified whether the messages can be deciphered with the reconstructed key. This method is not easy to automate. It is reserved for professional cryptologists accustomed to using pen and paper and who know how to use their intuition. A personnal exampleI constructed an example similar to the in-depth message series broken by Parker Hitt. Then, I tried to reconstruct the key. Creating in-depth messages$ echo TOBEORNOTTOBETHATISTHE | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI OCEGEHBJYMFHJSIOILJZTE $ echo QUESTIONWHETHERTISNOBL | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI HOYURBQOPDCZXEVBXVUJVD $ echo ERINTHEMINDTOSUFFERTHE | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI JSIRRUHKWTMZDGHUNDPZTE $ echo SLINGSANDARROWSOFOUTRA | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI YRIRHMZOEKPWDXKWNCAZDF $ echo GEOUSFORTUNEORTOTAKEAR | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI CDVQNSQWYIUVDCQWIPLVCC $ echo MSAGAINSTASEAOFTROUBLE | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI UVWECBBLYKJVSHFBOCAHJE $ echo SANDBYOPPOSINGENDTHEMT | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI YPZFVKQUCSJMAQNIUAHVBS $ echo ODIETOSLEEPNOMOREANDBY | python3 kryha_tui.py -o -f 3 \ -i KPFQVGMASCHYNIORDELUBZWJXT -e ZCJBWYKNAGQSPFTROXVMDULEHI DIIGRYXQBRXODIGZWPUPVT The messages lined up
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
[7,6,7,5,6,7,6,8,6,10,5,6,5,7,6,5,9]
0123456789012345678901
Crypto OCEGEHBJYMFHJSIOILJZTE
Clair TOBEORNOTTOBETHATISTHE
Crypto HOYURBQOPDCZXEVBXVUJVD
Clair QUESTIONWHETHERTISNOBL
Crypto JSIRRUHKWTMZDGHUNDPZTE
Clair ERINTHEMINDTOSUFFERTHE
Crypto YRIRHMZOEKPWDXKWNCAZDF
Clair SLINGSANDARROWSOFOUTRA
Crypto CDVQNSQWYIUVDCQWIPLVCC
Clair GEOUSFORTUNEORTOTAKEAR
Crypto UVWECBBLYKJVSHFBOCAHJE
Clair MSAGAINSTASEAOFTROUBLE
Crypto YPZFVKQUCSJMAQNIUAHVBS
Clair SANDBYOPPOSINGENDTHEMT
Crypto DIIGRYXQBRXODIGZWPUPVT
Clair ODIETOSLEEPNOMOREANDBY
0123456789012345678901
1 - Create the Alphabet TableThe first step is to distribute the letters of the plaintext into the different alphabets used. The vertical axis represents the letters of the ciphertext. Each column corresponds to the different alphabets in the order of the encryption. For example, if we take the first line (TOBEORNOT...=> OCEGEHBJY...), the plaintext letter R (the 6th letter) is located in column number 5 (the first column has the index 0). It is on row H, because H is the encryption of R.
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 A: N T U B: I N E T M C:G O A P E R O A R D:O E H O E R L E: B G O D E E F: D O F A G: E S O H:Q G R E B O U H B I: D I U M H N T J:E O S E S O L K: Y M A S L: S I K M: S T D I N: S E F O:T U N N A R P: A W R A R D Q: U O L G T R: L N T E S: R F O A T T T: N H Y U:M S H P N F D N V: S O B E R S E B W: A R I R O E X: S P H W I Y:S E O T Z: N A T R T 2 - Complete the columns that have the same alphabetWe can see that the letter O is represented by the letter J in columns 7 and 19. We can therefore deduce that columns 7 and 19 correspond to the same alphabet. All the letters present in column 7 can be reproduced in column 19, and vice versa. The following columns correspond to identical alphabets: 0 and 12, 1 and 17, 4 and 20, 7,11 and 19, 10 and 18, 13 and 21. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 A:N T U N T U B: M I N E T M C:G O A P E G R O E A R D:O E R H O L E R L E: B G O D E O E F: D O A F O A G: E S O S H:Q G R E B H B Q O U H B G O I: D I U M H N T D M J:E L O S O E S O L K: Y M A M S M L: S K S I K S M: S I T D I D I N: S E F S O:T U N N T A R U N P: A D W R D A R D Q: U O L L G T L G R: L N T E L T S:A R F O A T R T T: H N Y H Y U:M S H P N P M F D N P V: S O B E E R S E B W: A R I R O E R X:H S P H W I P W Y:S E O T S Z: N A T T R T 3 - Order the alphabetsBecause the internal alphabet of the Kryha is disordered, the letters of the plaintext appear in each alphabet in a different order. If we want to reconstruct the machine's alphabets, we must rearrange the rows of the table so that the plaintext letters appear in the same order, regardless of the column (alphabet).
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 G: E S O S I: D I U M H N T D M Z: N A T T R T Q: U O L L G T L G Y:S E O T S U:M S H P N P M F D N P P: A D W R D A R D C:G O A P E G R O E A R E: B G O D E O E T: H N Y H Y A:N T U N T U R: L N T E L T J:E L O S O E S O L 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 H:Q G R E B H B Q O U H B G O L: S K S I K S K: Y M A M S M S:A R F O A T R T D:O E R H O L E R L X:H S P H W I P W M: S I T D I D I O:T U N N T A R U N W: A R I R O E R V: S O B E E R S E B N: S E F S B: M I N E T M F: D O A F O A We observe that there are two groups of rows. Each group has 13 rows. In each group, one column contains an half-alphabet. Here are these two half-alphabets (cyclics):
Q..AOHKTLWPD. YFUBSM.G.INREHere are the two groups of row indexes: GIZQYUPCETARJ HLKSDXMOWVNBF 4 - Find the alphabets (inner, outer) of the KryhaThe two groups of ciphertext letter indices and the two half-alphabets do not directly provide the machine's alphabets (inner and outer). We must use the decimation operation we have already encountered (see Known Plain Text Attack). Up to this point, we have discussed decimation in a context where the gap between the alphabets was constant. In fact, in the present case, the gaps are equal to the sector values. Thus, here, the decimation value corresponds to the average of the sectors. Furthermore, we know the value must be even because we have two sets of indices. In conclusion, the most likely decimal values are only 4, 6, 8, 10, and 12. For each value, we try to find the sector values and perform the encryption operations. If there are no contradictions, we have found the correct decimation value, as well as the alphabets and sectors of the wheel. In short, the complete key. In fact, it's not that easy. We don't find the values of the different sectors in sequence, but only a portion of them. An example is given below. Fortunately, having identical alphabets imposes constraints on the sum of certain sectors. We are fortunate; after testing the values 4 and 6, the value 8 gives us consistent results. Inner Alphabet (two half-alphabets): GIZQYUPCETARJ HLKSDXMOWVNBFIf we decimate every 8 letters, we obtain two cyclic groups: 1a) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. 1b) H.N.O.D.L.B.W.X.K.F.V.M.S.Outer Alphabet (two half-alphabets): .INREYFUBSM.G Q..AOHKTLWPD.Decimation (8): 2a) Y.N.G.S.F.R.?.M.U.E.I.?.B. 2b) Q.P.T.O.?.D.L.H.?.?.W.K.A. 5 - Reassemble a part of the wheelTo find the value of the sectors, we shift the found alphabets. Here is the beginning of the first cryptogram and its deciphering: Cryptogram: OCEGE HBJYM FHJSI OILJZ TE... Plain text: TOBEO RNOTT OBETH ATIST HE...Note: other cryptogram/plaintext pairs will also be used in determining the sectors. For the first pair, the initial shift is zero. We align two half-alphabets, one inside, the other outside: 1st pair (encrypted letter / plaintext letter): O/T, H/Q, U/M Pair 1b-2b: O/T H.N.O.D.L.B.W.X.K.F.V.M.S. Q.P.T.O.?.D.L.H.?.?.W.K.A.Pair 1a-2a: U/M G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B.2nd pair: C/O, P/A, R/L, I/D, Pair 1a-2b G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.Pair 1b-2a: V/S, S/R, O/U H.N.O.D.L.B.W.X.K.F.V.M.S. Y.N.G.S.F.R.?.M.U.E.I.?.B.Y.N.G.S.F.R.?.M.U.E.I.?.B.It does not correspond to the previous alphabets, so the offset is unknown. 3rd pair: E/B, Pair 1a-2a (+12 from the first pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B.4th pair: G/E, Pair 1a-2a (+6 from the last pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B.5th pair: E/O, Pair 1a-2b (+18 from the 2nd pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.6th pair: H/R, U/H, Pair 1a-2b (+6 from the last pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.7th pair: B/N, Q/O, Pair 1a-2b (+8 from the last pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.8th pair: J/O, O/N Pair 1b-2a (+6 from the last pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.9th pair: Y/T Pair 1b-2a (+10 from the last pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.10th pair: T/N, Pair 1a-2a (+16 from the 3rd pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Y.N.G.S.F.R.?.M.U.E.I.?.B.Y.N.G.S.F.R.?.M.U.E.I.?.B.
11th pair: C/E,
Pair 1a-2a (+6 from the last pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Y.N.G.S.F.R.?.M.U.E.I.?.B.Y.N.G.S.F.R.?.M.U.E.I.?.B.
12th pair: H/B, Z/T,
Pair 1a-2b (+16 from the 9th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.
13th pair: J/E, U/M,
Pair 1a-2a (+18 from the 10th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B.14th pair: S/T, E/E , Pair 1a-2a (+6 from the last pair) G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B.15th pair: I/H, Pair 1a-2b (+18 from the 12th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.
16th pair: O/A, B/T, U/F
Pair 1a-2a (+14 from the 14th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B.Y.N.G.S.F.R.?.M.U.E.I.?.B.17th pair: I/T, Pair 1a-2b (+16 from the 15th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.
18th pair: C/O,
Pair 1a-2b (+6 from the last pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.
19th pair: J/S
Pair 1a-2a (+20 from the 16th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Y.N.G.S.F.R.?.M.U.E.I.?.B.Y.N.G.S.F.R.?.M.U.E.I.?.B.
20th pair: Z/T,
Pair 1a-2b (+12 from the 18th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.
21th pair: T/H, V/B
Pair 1a-2b (+6 from the last pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.
22th pair: E/E,
Pair 1a-2a (+18 from the 19th pair)
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
Y.N.G.S.F.R.?.M.U.E.I.?.B.Y.N.G.S.F.R.?.M.U.E.I.?.B.
6 - SummaryAfter the previous analyses, we obtained the values for several sectors: l[2] = 6 l[6] = 6 l[12] = 6 l[4] = 6 l[7] = 10 l[16] = 6 l[5] = 8 l[9] = 6 l[19] = 6But we also know certain relationships between several sectors: l[0]+l[1] = 12 l[1]+l[2]+l[3] = 18, and l[2] = 6, then l[1]+l[3] = 12 l[8]+l[9]+l[10] = 16, and l[9] = 6, then l[8]+l[10] = 10 l[10]+l[11] = 12 l[13]+l[14] = 14 l[14]+l[15] = 16 l[17]+l[18] = 12 l[19]+l[20]+l[21] = 18, and l[20] = 6, then l[19]+l[21] = 12On the other hand, several columns were encrypted with the same alphabet, from which new relationships between sectors can be deduced: Columns 11 and 19 l[11]+...+l[18] = 0 modulo 26 l[11]+l[12]+l[13] = 18, l[15]+l[16]+l[17] = 20, then l[14]+l[18] = 26 – (18+20) = 26 – 12 = 14 Because of the use of half-alphabets, where each letter is spaced one letter apart, the measured gaps are even. These gaps correspond to one sector: 6, 8, 10, or to several sectors: 12, 14, 16, … The remaining sectors necessarily have odd values. Let's try to determine them. We start with the equation l[8] + l[10] = 10. We can deduce that each sector has the value 5: l[8] = l[10] = 5. Indeed, the values must be odd and greater than 4 (systematic addition). Note: The preceding deduction takes into account the workings of Kryha. We could have imagined a slightly different version where the pairs 3 and 7 or 1 and 9 were plausible. In that case, it would have been necessary to test these different pairs. If l[8] = l[10] = 5, we can deduce: l[10]+l[11] = 12, then l[11] = 7 l[11]+l[13] = 12, then l[13] = 5 l[13]+l[14] = 14, then l[14] = 9 l[0]+...+l[11] = 0, l[2]=6, l[4]+...+l[11] = 6+10+5+6+5+7 = 13, l[0]+l[1] = 12, then l[3] = 26 -6 -13 = 7 l[1]+l[3] = 12, then l[1] = 5 l[0]+l[1] = 12, then,l[0] = 7 l[14]+l[15] = 16, then l[15] = 7 l[14]+l[18] = 14, then l[18] = 5 l[15]+l[16]+l[17] = 20, then l[17] = 20 - 13 = 7 Finally, we obtain the values for the different sectors. x 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20 l[x] 7, 5, 6, 7, 6, 8, 6,10, 5, 6, 5, 7, 6, 5, 9, 7, 6, 7, 5, 6, 7The repetition of the first sectors (7,5,6,7) at the end suggests that the number of sectors is 17. This will need to be verified. Returning to decimation: If we average the 21 values found, we obtain the value 6.5. Since the value is a whole number, we obtain 7, but because the value must be even, the value becomes 8. 6 - Reassemble the alphabetsWe know the sectors, so we can deduce the alphabets: 1st Pair 1b-2b: O/TH.N.O.D.L.B.W.X.K.F.V.M.S. Q.P.T.O.?.D.L.H.?.?.W.K.A.Pair 1a-2a: U/M G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Y.N.G.S.F.R.?.M.U.E.I.?.B. 2nd Pair : C/O : 1a-2b : +7G.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A. 3nd Paira) 1a-2b : +5 from the last pairG.A.C.Y.I.R.E.U.Z.J.T.P.Q. Q.P.T.O.?.D.L.H.?.?.W.K.A.b) 1b-2b : +12 from the 1st pair H.N.O.D.L.B.W.X.K.F.V.M.S. Q.P.T.O.?.D.L.H.?.?.W.K.A.Q.P.T.O.?.D.L.H.?.?.W.K.A.We add 1a and 1b !
G.A.C.Y.I.R.E.U.Z.J.T.P.Q.
H.N.O.D.L.B.W.X.K.F.V.M.S.
CHYNIORDELUBZWJXTKPFQVGMASC
1st pair : O/TCHYNIORDELUBZWJXTKPFQVGMASC Q.P.T.O.?.D.L.H.?.?.W.K.A. 2nd pair : (+7) : C/O, O/U
CHYNIORDELUBZWJXTKPFQVGMASC
Q.P.T.O.?.D.L.H.?.?.W.K.A.
Y.N.G.S.F.R.?.M.U.E.I.?.B.
We add 2b and 2a :
QFPRT?OM?UDELIH??B?YWNKGAS In short, here is the reconstructed key:
$ echo OCEGEHBJYMFHJSIOILJZTE | python3 kryha_tui.py -o \ -s 7,5,6,7,6,8,6,10,5,6,5,7,6,5,9,7,6 \ -i CHYNIORDELUBZWJXTKPFQVGMAS \ -e QSPFTROCJMDULEHIVXZBWYKNAG -a OT -d TOBEORNOTTOBETHATISTHE Reference
|