|
Home Page Hebern's machines Home Page Hebern 1 rotor Home Page Cryptanalysis, Home Page
|
IntroductionIn this page, we will use the Friedman interval statistical method. This method has already been described but in the context of its use to break a 5-rotors Hebern machine (link). Here we will use it in a simple case: a Hebern machine 1 rotor where only the rotor is unknown. The permutations Keyboard and Lampboard being equal to the identity permutation (ABC...Z). On the other hand, we will use the first version of Friedman's method. This one tries to find one or more basic cipher-text sequences. We will see that if we know the Lampboard permutation, the knowledge of only one of these sequences allows you to reconstruct the rotor wiring. A simplified example1) Creating the ciphertextRemarks:
C:\H1_TOOLS> python hebern1_tui.py -R p17 < MSGS\baskerville.pln > MSGS\basker.cry C:\H1_TOOLS> python groupe.py < MSGS\basker.cry QVOHC YAUQK EJXMC ZPIFC DDVGW PMZZO GHWKA GYJJQ QURXA SNZMZ FHEZZ QQVSG UZZZQ LCITH IFNQM NSCUT SFJWT GWXZQ MXMMH WQERI DBBPW TSBBC MIMCN CJZVF DZIAL VYEBP KZOFS RRYLT HWXBD JOXAO RJKZS NKOAL ITYXW HEJPB DINIL SLJHI NNQMV UVKSK ZKZQF TETJK GTXMS DENBT ZPRRI GDHDJ PRFVQ HDOZD HDXYB PVTGD MNLRI YVXUB ZBGAO FRDSU VTKVG WXPIG DNLNQ MMYQP CKYYS PRJCV JGQKU KFOTQ FFGXU NSJHM FZIXV MHTTY IZBJX KQMQN SPIJV JADRS YBDXN GQJIO ISWFW ZKISO HBCZQ JABEU JVOVH YNGMH JSQZD MDXLD RKBKE NANZZ BYTXY TZKXM IJVWP BOSEJ ITYXW FZBDK QHQNM IRDZF RZKRG BCBZW MUGKD HLFGB GNCCC TBPMC AZSRH FHFUS HIDZN HVACB JUMPV UCLTV ... 2) Using the Friedman method with an interval of index 5First, we use a 5-letters index interval. In my program, each column corresponds to a plain text letter. However, we don't know which one. The ordinate indicates the external key (the position of the right rotor). The program analyzes the cryptogram in increments of 26 letters. For each slice, it increments the statistics. The columns for which the sum is the greatest correspond to the plain text letters the most frequent (E, T, A, ...). So in the following example, column V corresponds without a shadow of a doubt to the letter E. A priori, for an interval of index 5 (X=0,....,Y=5), if the effective key is A (the real key being Z), we have two elements from the basic cipher-text sequence of the letter E (V and Y separated by 4 letters):
V....Y....
Note: if we analyze a cryptogram produced by the 5-rotors machine, you must know the initial position of the right rotor to carry out correctly dividing it into sections of 26 letters.
C:\H1_TOOLS> python friedman_h1.py -I 5 < MSGS\basker.cry
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A: 1 1 0 0 0 5 0 0 0 1 1 1 1 0 2 0 0 1 0 1 0 1 1 0 0 1
B: 0 2 0 0 1 5 0 4 4 4 6 5 8 2 7 3 1 4 0 2 1 9 7 1 0 2
C: 5 9 0 0 2 6 0 4 4 5 7 9 6 5 7 1 3 5 0 1 0 13 4 3 0 0
D: 3 10 0 0 1 8 0 2 1 2 8 6 12 2 6 0 2 5 2 1 0 10 5 1 0 0
E: 1 2 0 0 1 4 0 1 2 2 1 1 1 4 1 2 2 1 0 3 0 3 2 0 0 1
F: 1 6 0 0 4 11 0 3 5 1 8 6 3 7 6 2 6 8 0 1 4 11 5 2 0 1
G: 0 10 0 0 2 7 0 5 1 1 13 4 4 8 9 4 3 10 1 1 1 13 8 1 0 1
H: 0 1 0 0 0 3 0 0 0 0 1 3 3 1 4 1 2 3 0 1 3 5 4 0 0 1
I: 0 2 0 0 0 5 0 1 0 1 3 0 6 0 2 0 0 3 0 0 0 4 1 2 0 0
J: 0 4 0 0 0 4 0 1 0 1 1 4 0 1 1 0 2 6 0 0 0 6 2 0 0 1
K: 2 3 0 0 0 2 0 4 0 1 2 2 2 2 2 0 1 0 1 0 0 4 1 0 0 0
L: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
M: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
N: 0 1 0 1 0 2 0 1 1 1 4 1 1 1 3 3 0 4 0 0 0 3 4 1 0 0
O: 1 4 0 0 0 4 0 0 1 0 0 3 2 1 0 2 0 3 0 1 1 2 1 2 0 2
P: 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 2 0 0 0 1
Q: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
R: 0 6 1 0 0 7 0 2 0 4 6 5 3 1 5 1 6 7 0 1 2 3 6 0 0 2
S: 0 1 0 0 2 1 0 1 0 2 1 2 1 0 1 0 2 0 0 0 1 2 2 0 0 1
T: 1 6 0 0 1 5 0 1 1 2 2 3 2 1 5 2 1 1 1 1 0 4 3 2 0 0
U: 1 13 0 0 1 9 0 0 5 8 10 14 17 5 9 6 3 12 1 1 2 10 11 3 0 2
V: 6 10 0 0 1 10 1 8 3 5 10 5 7 7 2 2 1 21 0 1 0 19 5 2 0 0
W: 3 10 0 0 2 8 0 7 4 6 11 10 8 3 6 3 4 8 0 1 4 12 6 1 0 5
X: 1 5 0 0 0 5 0 0 1 1 2 4 3 3 8 1 2 3 0 1 0 6 4 1 0 3
Y: 5 13 0 0 2 12 0 7 3 7 18 15 12 5 14 7 3 12 1 4 2 22 13 4 0 3
Z: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
31119 1 1 20124 1 52 36 55115103102 59101 40 44118 7 22 21165 95 26 0 27
3) We test other intervals to reconstruct the sequenceWe proceed in the same way by trying all the intervals in order to find the "basic chipher-text sequence" corresponding to the most frequent letter (presumably the letter "E"). Key 1th letter interval 2nd letter frequency of 2nd letters A V 3 J J(25),K(20),L(18) A V 4 C C(19),S(18),K(15) A V 5 Y Y(22),V(19),G(13) A V 6 M M(20),J(17),S(16) A V 7 R R(20),F(15),G(15) A V 8 L L(19),Z(18),U(12) A V 9 C C(27),H(17),X(8) A V 10 H H(18),J(16),W(14) A V 11 O O(21),J(14),A(12) A V 12 T T(20),P(18),Q(17) A V 13 B B(20),Y(16),G(15) Partial reconstitution: V..JCYMRLCHBTB........... In the end, we obtain: VZVJCYMRLCHBTBFMNXQOVJDSK Notes:
How to correct errors? Friedman gives us the answer. We take a key different from “A” and we check if the column corresponding to “E” corresponds to the one found as well as the letter corresponding to the interval. Key 1th letter interval 2th letter Freq des 2th lettre V D 9 S S(33),C(26),D(12) W J 8 S S(16),S(16),G(15) X D 7 S S(15),C(14),G(12) Y S 6 S S(23),C(20),A(12)We can conclude that the 5th letter of the sequence is an "S" (not a “C”). Note: The first letter for the key "X" is actually a "W", this error is consistent with the fact that the frequency differences (15, 15, 12) are very small. We try to confirm (or refute) in the same way the other letters in the sequence. We obtain the following solution: VZVJSYMGZCHJQBWMZNQNFDJWSK We have reconstituted the "basic cipher-text sequence" for the letter E (the most common). We can also reconstruct the sequences to other frequent letters: "T" and "A". They correspond respectively to columns "B" and "F" when the key is "A". These reconstructions can confirm the sequence for the letter "E" but also become essential if we ignores the wiring of the lampboard (see the following chapters). 4) Rebuilding the machineAs the lampboard and keyboard correspond to the permutation identity, the final solution is simple. Here is the reconstruction from the encryption table (the abscissa: the plain text letter, the ordinate: the key):
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A V M
B Z L
C V K
D J
E I S
F H Y
G G M
H F G
I Z
J C
K H
L J
...
And so on. Finally, we obtain the table:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A F T Q J V A X M W D S N H L R U C O K B P E I G Z Y B S P I U Z W L V C R M G K Q T B N J A O D H F Y X E C O H T Y V K U B Q L F J P S A M I Z N C G E X W D R D G S X U J T A P K E I O R Z L H Y M B F D W V C Q N E R W T I S Z O J D H N Q Y K G X L A E C V U B P M F F V S H R Y N I C G M P X J F W K Z D B U T A O L E Q G R G Q X M H B F L O W I E V J Y C A T S Z N K D P U H F P W L G A E K N V H D U I X B Z S R Y M J C O T Q I O V K F Z D J M U G C T H W A Y R Q X L I B N S P E J U J E Y C I L T F B S G V Z X Q P W K H A M R O D N K I D X B H K S E A R F U Y W P O V J G Z L Q N C M T L C W A G J R D Z Q E T X V O N U I F Y K P M B L S H M V Z F I Q C Y P D S W U N M T H E X J O L A K R G B N Y E H P B X O C R V T M L S G D W I N K Z J Q F A U O D G O A W N B Q U S L K R F C V H M J Y I P E Z T X P F N Z V M A P T R K J Q E B U G L I X H O D Y S W C Q M Y U L Z O S Q J I P D A T F K H W G N C X R V B E R X T K Y N R P I H O C Z S E J G V F M B W Q U A D L S S J X M Q O H G N B Y R D I F U E L A V P T Z C K W T I W L P N G F M A X Q C H E T D K Z U O S Y B J V R U V K O M F E L Z W P B G D S C J Y T N R X A I U Q H V J N L E D K Y V O A F C R B I X S M Q W Z H T P G U W M K D C J X U N Z E B Q A H W R L P V Y G S O F T I X J C B I W T M Y D A P Z G V Q K O U X F R N E S H L Y B A H V S L X C Z O Y F U P J N T W E Q M D R G K I Z Z G U R K W B Y N X E T O I M S V D P L C Q F J H A The 1st line corresponds to the rotor wiring: FTQJVAXMWDSNHLRUCOKBPEIGZY It is easy to read the beginning of the cryptogram: QVOHC YAUQK EJXMC ZPIFC DDVGW PMZZO GHWKA GYJJQ QURXA SNZMZ FHEZZ QQVSG UZZZQ LCITH IFNQM NSCUT SFJWT GWXZQ MXMMH WQERI DBBPW TSBBC MIMCN CJZVF DZIAL VYEBP KZOFS RRYLT HWXBD JOXAO RJKZS NKOAL ITYXW HEJPB DINIL SLJHI NNQMV UVKSK ZKZQF TETJK ... CHAPTERMRSHERLOCKHOLMESMRSHERLOCKHOLMESWHOWASUSUALLYVERYLATE INTHEMORNINGSSAVEUPONTHOSENOTINFREQUENTOCCASIONSWHENHEWAS UPALLNIGHTWASSEATEDATTHEBREAKFASTTABLEISTOODUPONTHEHEARTHRUGAND PICKEDUPTHESTICKWHIC... ConclusionThe Friedman v1 method works for a 1-rotor Hebern machine. But although the cryptogram was about 40,000 characters long, I had some difficulties (it was not "straightforward"). Friedman estimated that this version of his method required 169,000 characters. Because I applied his method to a 1-rotor Hebern machine, I needed a lot less data. A priori I think that his method can work with only 20,000 characters (in the case of Hebern 1 rotor machine). The main reason that far fewer characters are needed is that a column always corresponds to the same plain text letter. In the case of the Hebern 5 rotor machine, we have the same letter ...but only for a slice of 26 letters! We will see the method v2 requires only 2,000 characters.
|