Enigma Replica – Cryptanalysis

Moreove

Substitution encryption Cryptanalysis How it works? Construction

In the transmission protocol, Germans used to send the initial rotor positions twice (these positions were composed of 3 letters). This 6-letter message had to strengthen security; however, it opened a breach in Enigma. While sending this 6-letter message, only the first rotor will turn: in fact, if the ring set for the second rotor rotation is not close to the initial position (less than 6 letters before), we can “forget” the other two rotors. Mathematically, a rotation of the first rotor means a probability of \frac{6}{26}\simeq 0.23.

Rotors internal connections

Let’s consider the following example:
rotors

In this schematic, following substitutions are performed:

  • A \Rightarrow I through rotor #1.
  • I \Rightarrow K through rotor #2.
  • K \Rightarrow B through rotor #3.
  • On the reflector side: B \Rightarrow P.
  • Return trip: P \Rightarrow U \Rightarrow H \Rightarrow F.

Now, let’s forget rotors #2 and #3: there is a new “virtual reflector” performing the combinations made by rotor #2 + rotor #3 + the actual reflector.  A given reflector is only defined by 13 substitutions. In the figure above, a partial definition would be the pair \{I,H\}.

Now, we consider that we have a large portion on the message (here A \Leftrightarrow I \Leftrightarrow H \Leftrightarrow F). If we have correctly identified the rotor #1 and the virtual reflector, we could only have 13 pairs in the reflector. However, if we don’t have the correct rotor #1, we will find more than 13 possible pairs and/or two opposing pairs (\{I,H\} and \{I,J\}). Nevertheless, we do not know the plaintext yet: we can verify but not discover. This hypothesis is the first search phase.

Permutations

In order to understand how mathematicians bypassed this issue, we must see Polish scientists who have studied the Enigma since 1929. Moreover, Marian Rejewski found a method to discover rotors connections.

Polish scientists started by buying a commercial Enigma, taking it to pieces and seeing if they could get to a military version. Rejewski determined 6 equations which uses permutations (more details can be found here):

A=(ENIGMA)_1=SPNP^{-1}MGRG^{-1}M^{-1}P^{-1}N^{-1}PS^{-1}\ldots

We set Q=MGRG^{-1}M^{-1}: this value is equivalent to the virtual reflector previously defined. Furthermore, these permutations are fixed during encryption. If we add an useless H interconnection, Enigma equations are:

A=SHP^{1}NP^{-1}QP^{1}N^{-1}P^{-1}H^{-1}S^{-1}
B=SHP^{2}NP^{-2}QP^{2}N^{-1}P^{-2}H^{-1}S^{-1}
C=SHP^{3}NP^{-3}QP^{3}N^{-1}P^{-3}H^{-1}S^{-1}
D=SHP^{4}NP^{-4}QP^{4}N^{-1}P^{-4}H^{-1}S^{-1}
E=SHP^{5}NP^{-5}QP^{5}N^{-1}P^{-5}H^{-1}S^{-1}
F=SHP^{6}NP^{-6}QP^{6}N^{-1}P^{-6}H^{-1}S^{-1}

Therefore, we have a set of equations with 4 unknowns (H, S, N and Q). We are in 1931, Rejewski is blocked: the equation set cannot be resolved…

How the French helped

In 1931, Gustave Bertrand travelled in Poland and discovered the Enigma in Rejewski’s team. Polishs were convinced that Germans would use the Enigma for military purposes. From that time, France started a collaboration with Poland and Rejewski.

One year later, Hans-Thilo Schmidt went to meet the Frenchs: he wanted to share information about the Enigma (not for free !). In november 1932, a first meeting is scheduled: Schmidt shared technical documents about Enigma construction but also daily keys. Schmidt will work for the next 10 years for Frenchs.

Nevertheless, French and British secret services were unable to use these information… On 8 December 1932, Gustave Bertrand decided to share those documents with Poland without telling them their origin. Rejewski took the keys of September and October 1932: permutations S and H were now uncovered and messages from these two months could be deciphered!

Polish did not want to decipher old messages, they wanted to decipher messages day by day. The only solution is to discover P and Q (rotors internal connections): unfortunately, it is not resolvable.

Rejewski’s trick

Nevertheless, we know that rotors positions are encrypted twice when a message is transmitted (for instance, a plaintext ZSFZSF).

If ZSFZSF is encrypted as TYUBGJ, it is known that T and B (after 3 rotations) represent the same plaintext letter (similarly for Y and G, U and J). Permutations can be written as follows:

A: ? \Rightarrow T, D: ? \Rightarrow B. B: ? \Rightarrow Y. E: ? \Rightarrow G. C: ? \Rightarrow U. F: ? \Rightarrow J

Combined permutations:

AD: T \Rightarrow U. F: ? \Rightarrow ? \Rightarrow U. F: ? \Rightarrow B. BE: Y \Rightarrow U. F: ? \Rightarrow ? \Rightarrow U. F: ? \Rightarrow G. CF: U \Rightarrow U. F: ? \Rightarrow ? \Rightarrow U. F: ? \Rightarrow J

Rejewski demonstrated that all alphabet letters are in all positions of the “message key” using only 80 messages or more. Here is a list of these 6 keys (extracted from Polish Mathematicians Finding Patterns in Enigma Messages by C. Christensen, http://www.matematiksider.dk/enigma/MAA%20article%20about%20Enigma%20.pdf):

AUQ AMN IND JHU PVJ FEG SJM SPO WTM RAO
BNH CHL JWF MIC QGA LYB SJM SPO WTM RAO
BCT CGJ JWF MIC QGA LYB SJM SPO WTM RAO
CIK BZT KHB XJV RJL WPX SUG SMF WKI RKK
DDB VDV KHB XJV RJL WPX SUG SMF XRS GNM
EJP IPS LDR HDE RJL WPX TMN EBY XRS GNM
FBR KLE LDR HDE RJL WPX TMN EBY XOI GUK
GPB ZSV MAW UXP RFC WQQ TAA EXB XYW GCP
HNO tdD MAW UXP SYX SCW USE NWH YPC OSQ
HNO tdD NXD QTU SYX SCW VII PZK YPC OSQ
HXV TTI NXD QTU SYX SCW VII PZK ZZY YRA
IKG JKF NLU QFZ SYX SCW VQZ PVR ZEF YOC
IKG JKF OBU DLZ SYZ SCW VQZ PVR ZSJ YWG

The same work is done as we know that all the first letters are encrypted with the same permutation: AD: A \Rightarrow A but also B \Rightarrow C, D \Rightarrow V… As all letters appear in all positions, the full permutation scheme can be written:

AD=ACBVIKZTJMXHUQDFLWSENPRGOY=(A)(BC)(DVPFKXGZYO)(EIJMUNQLHT)(RW)(S)

Cycle lengths are: 2*10 letters, 2*2 letters, 2*1 letter. Rejewski used these observations to break the Enigma.

Rejewski and classic permutations theorems

Definition: a reflection A is a permutation of all the alphabet letters. Furthermore, no letter can be encrypted by itself: the reflector achieves both features.

Definition: the conjugation of Q by X is XQX^{-1}.

Theorem: the cyclic structure is invariant compared to the conjugation. Proof: we suppose that Q(i)=j. PQP^{-1}(P(i)=PQ(P^{-1}P)(i)=PQ(i)=P(j); therefore: PQP^{-1}: P(i) \Rightarrow P(j).

If Q cycle is (a)(b)(c), the cycle when conjugated by P is: (P(a))(P(b))P(c))

Simplifying the equation

In the initial position: encrypt means applying permutation A then B, etc. After some simplifications, AD=SXS^{-1} with AD=SXS^{-1}. We can identify the form of a conjugation of X by S. AD has the same cycles as X: the plugboard does not add any security! AD known and SQS^{-1} will be equivalent and easily comparable.

Using the trick

Let’s write the equations of AD and BE:

AD=SHPNP^{-1}MGRG^{-1}M^{-1}PN^{-1}P^{3}NP^{-4}MGRG^{-1}M^{-1}P^{4}N^{-1}P^{-4}H^{-1}S^{-1}

BE=SHP^{2}NP^{-2}MGRG^{-1}M^{-1}P^{2}N^{-1}P^{3}NP^{-5}MGRG^{-1}M^{-1}P^{5}N^{-1}P^{-5}H^{-1}S^{-1}

We can already simplify: Q=MGRG^{-1}M^{-1}. We use the following theorem:

Theorem: if a permutation is even with an even number of equal length cycles, this permutation is the product of two permutations made of disjointed transpositions (cf. link).

Example: X=(a1a2)(a3a4)(a5a6) and Y=(a2a3)(a4a5)(a6a1). We can deduce that XY=(a1a3a5)(a2a6a4)

With the technique described above, we can obtain AD, BE and CF:

$AD=latex (a)(bc)(dvpfkxgzyo)(eijmunqlht)(rw)(s)&s=2$

$BE=latex (axt)(blfqveoum)(cgy)(d)(hjpswizrn)(k)&s=2$

$CF=latex (abviktjgfcqny)(duzrehlxwpsmo)b&s=2$

In AD: 2 cycles of length 1, 1 cycle of length 2 and 2 cycles of length 10.

In BE: 2 cycles of length 1, 2 cycles of length 3 and 2 cycles of length 9.

In CF: 2 cycles of length 13.

AD, BE and CF are in the alphabet permutations set (size equal to 26).Each permutation has the same number of cycles for each length. Therefore, it exists a permutation of length 2: A, D, B, E, C and F. From this remark, we can already establish that (as) belongs to A and D and (dk) belongs to B and E.

Now, cycles of length equal to 2: we should have (br)(cw) in A and (rc)(wb) in D or (bw)(cr) in A and (wc)(rb) in D. In we apply the theorem previously defined to our example: if (a1a3a5a7)(a8 a6a4a2) is in XY, therefore (a1a2)(a3a4)(a5a6)(a7a8) is in X and (a2a3)(a4a5)(a6a7)(a8 a1) is in Y.

Now, cycles of length equal to 10: if we set that A must perform x \Rightarrow i; then, g \Rightarrow e, z \Rightarrow t, etc. As we know AD, D must perform i \Rightarrow g; then, e \Rightarrow z, etc. Therefore, we have 10 possibilities. AD has 10*2 tests, BE 3*9 and CF 13: 7020 possibilities over 10^8, the progress is huge!

However, it is not the latest step. Germans used simple letters (AAA, ABC, QWE…).

If the enquiring reader asks how the cryptologist knows – before breaking the cipher – the preferences of the cryptographers, we can reply that the cryptologist does not know these preferences but he tries to compensate his ignorance with long tests, imagination, and sometimes with an once of luck. Rejewski, An Application of the Theory of Permutations inBreaking the Enigma Cipher, Applicationes Mathematicae, 1980.

Finally, Rejewski found the solution! We suppose that the key was aaa. In the above list, SYX appears quite often. If we write aA (a applied to A): aA=s, aB=y and aC=x.

CF is composed to 2 cycles of length 13: as a \Rightarrow x, C and F are known. For BE, A and Y belong to two different cycles of length 3. We obtain 6 elements of B and E. Using this method, we could obtain all permutations:

AUQ AMN sss IKG JKF ddd QGA LYB xxx VQZ PVR ert
BNH CHL rfv IND JHU dfg RJL WPX bbb WTM PAO ccc
BCT CGJ rtz JWF MIC ooo RFC WQQ bnm WKI RKK cde
CIK BZT wer KHB XJV lll SYX SCW aaa XRS GNM qqq
DDB VDV ikl LDR HDE kkk SJM SPO abc XOI GUK qwe
EJP IPS vbn MAW UXP yyy SUG SMF asd XYW GCP qay
FBR KLE hjk NXD QTU ggg TMN EBY ppp YPC OSQ mmm
GPB ZSV nml NLU QFZ ghj TAA EXB pyx ZZY YRA uvw
HNO tdD fff OBU DLZ jjj USE NWH zui ZEF YOC uio
HXV TTI fgh PVJ FEG tzu VII PZK eee ZSJ YWG uuu

Several message keys are quite simple as expected….

At this point, we know the characteristics of A, B, C, D, E and F. From December 1932, Polishs have the keys of the two previous months. Rejewskji rewrote equations as follows:

U=P^{-1}S^{-1}ASP^{1}=NP^{-1}QP^{1}N^{-1}

V=P^{-2}S^{-1}BSP^{2}=NP^{-2}QP^{2}N^{-1}

W=P^{-3}S^{-1}CSP^{3}=NP^{-3}QP^{3}N^{-1}

X=P^{-4}S^{-1}DSP^{4}=NP^{-4}QP^{4}N^{-1}

Y=P^{-5}S^{-1}ESP^{5}=NP^{-5}QP^{5}N^{-1}

Z=P^{-6}S^{-1}FSP^{6}=NP^{-6}QP^{6}N^{-1}

We can see similar factors in all these equations, we multiply consecutive terms:

UV=(NP^{-1}QPN^{-1})(NP^{-2}QP^{2}N^{-1})=NP^{-1}QP^{-1}QPPN^{-1}

VW=NP^{-2}QP^{-1}QPP^{2}N^{-1}

WX=NP^{-3}QP^{-1}QPP^{3}N^{-1}

QPQ^{-1}P appears several times. We can rewrite equations as:

VW=(NPN^{-1})^{-1}(UV)(NPN^{-1})

WX=(NPN^{-1})^{-1}(VW)(NPN^{-1})

We can identify the conjugation with NPN^{-1} and VW. A theorem can be used to prove the limited quantity of solutions. We can find quite fast NPN^{-1} in order to satisfy all the equations. It is also a conjugated of P: we found N, the first rotor!

The next step was to find the internal connections of rotor #2 and #3. Rotors positions were changed every 3 months: Polishs manged to get the internal rotors connections for rotor II.

The latest rotor was easy to identify as for the reflector. In Janaury 1933, Polish created a fully working replica of the Enigma in its military version. Polishs gave their replica and their results to the Frenchs and Englishs only in 1939. Regardng the security breach in the message keys, it had been fixed in 1938. However, internal connections were known, reducing the security of the Enigma encryption scheme.

Previous Next
Advertisements