French Army C-36: The Vichy period () ()

Following the armistice, France was cut in two. The North was occupied by the Germans and the South and North Africa (Morocco, Algeria, and Tunisia) were under the control of a government based in Vichy. This government, led by Marshal Pétain, followed a policy of collaboration with the enemy.

Following the armistice with Germany, Vichy was authorized to encrypt its messages and to transmit them by radio, on the condition that they used methods and keys known to the Germans. Here are those methods:

• 1919 Type 2 code, five digits, using an superencipherment process.
• Colony code 1923B - using the CMAN superencipherment process.
• Four-digit SMC (Sahara-Maroc-Confins) code using the SAMA superencipherment process specific to North Africa, which can be used at all levels.
• System 1923 1A (simple column transposition).

However, Vichy also used other encryption methods, which were not communicated to the Germans, but only on a wired network.

In mainland France, some of these encryption methods existed before the armistice: the B-211, the 1919 5-digit Type 1 code, the DT Code, the G1 Code, the four-digit Code 70 (which replaces the Code 69), and C-36. The B-211 was the normal means of communication at staff level. Code DT served as a back-up. Code 70 and the C-36 were used only for instruction.

In North Africa (19th military region), the B-211 was mainly used for dialog between EM and with the mainland. The North African-specific ATM code was the main encryption tool. This was a four-digit code and it used superencipherment tables. The SD23 diagonal manual process was used between battalion and regimental commanders. Finally, the C-36 was used at division and regiment levels.

An operational network of C-36s covering the whole of North Africa was formed from April 1941 onwards (SHD-1P136 1942). This network was reserved for telegraphic communications between military commanders, generals commanding groups of subdivisions, major generals, and communications between the major generals and the superior commanding general:

     Secretary of War to the General Commander-in-Chief Delegate General of 
     the Government in French Africa. Vichy, March 8, 1941. 
     (SECRET stamp in red).
     In response to your letter N° 1108/EM of February 28, 1941, relating to 
     the use of C-36 cipher machines in North Africa and AOF [1]. I have the honor 
     to inform you of the existence in North Africa of a network of C-36 cipher
     machines. This network, formed during the war by the TOAFN [2] EM, is currently 
     operating under the leadership of the 19th region. I authorize you to 
     extend and modify it subject to your management (establishment and renewal 
     of keys). As the tables of endowment in the Bureau du Chiffre documents for 
     North Africa currently in preparation have to include the new owners of 
     these machines, you will kindly send me under this stamp [3] the diagram of 
     this encryption network and the numbers of the machines that you propose to 
     distribute. I would also like you to send me the key tables that you will
     put into service.

Several documents state the number of encryption means per unit. A summary reports the presence of 250 C-36s in North Africa. The mainland, which is divided into eight military regions or DMs (“Division Militaire”: Military Division), has, with schools, 155 machines in total. Hence, during the Vichy period, there was a total of 400 operational C-36s.

An ARCSI bulletin (Ribadeau-Dumas 1976) specified that during the withdrawal in June 1940, the Bureau du Chiffre hid cipher machines in several caches. If we assume that at least one in two machines was hidden, there were at least 900 machines. If we suppose that several dozen were lost, destroyed, or captured during the debacle of June 1940, we obtain a total number of 1,000 C-36s delivered to the French Army in 1940. This number corresponds to the order determined in 1937.

In fact, the number of machines delivered is more likely to have been 2,000 machines. Indeed, several endowment documents specify the serial numbers of the machines. Thus, in an inventory dated March 18, 1941, the serial numbers of the 49 machines then present in Morocco are indicated along with the units that hold them (SHD-1P136 1942). Here are some of the numbers: 5.003, 5.128, 6.482, and 6.709. In all cases, the numbers present are of the type 5.xxx or 6.xxx [1]. We can deduce with an extremely small margin of error that a maximum of 2,000 machines were delivered to France.

This number is also confirmed by an article from ARCSI concerning the history of French military cryptography (Ribadeau-Dumas 1975), which indicates that there were 115 B-211s and 2,000 C-36s in 1939 [2].

Footnotes:

• [1] Out of all the archives I have explored, I have been able to record over 100 machine numbers, including machines on the Continent. All of the numbers were in the 5,000–6,999 range. If C-36 owners (collectors, curators) sent me their machine numbers, I could publish an anonymous catalog of existing machines.
• [2] However, I think the date 1939 is wrong. It is more likely that in 1939 the C-36s were still being manufactured and it was only in 1940 that the total of 2,000 machines (or almost) was reached.

During the Vichy period (March 1941), the C-36s were only used on wired networks and the key change was obviously less frequent. The keys were valid for several months. Thus, Table A n ° 10, dating from December 27, 1940, was still in operation on March 26, 1941. In addition, it was valid for all units in North Africa. Tables A, B, and C of August 21, 1942 were not destroyed until January 22, 1943 after the fall of the Vichy government in Africa.

A document dated June 9, 1941 from the AOF staff in Dakar indicates the receipt of Tables A and B (n ° 3110/EM-CH) for the C -36, which must be put into service on June 15 from 4 p.m. We also learn that at this time the C-36 was considered safer than the SD 23 diagonal system. Finally, it was specified that the C-36 must only be used in exceptional cases and only on wire telegraphy (SHD-1P136 1942).

In 1941 when a unit received machines, the acknowledgment was encrypted with the machine using the exercise key contained in the manual. I deduced that in this manual there was an example key and an example message. I also learned that only an officer had the right to position the internal key (pins and slide; SHD-1P136 1942):

     2e Bureau of the troops of the AOF group - Memorandum - Subject: the cipher 
     machines C.36 - April 23, 1941. The installation of the internal secret 
     elements will be carried out obligatorily by an officer who will keep the 
     two keys for the opening of the machine casing in place. The operator, unless 
     he is an officer, must know only the starting key [1]; the holders will 
     acknowledge receipt using the key from the manual. The five letters used as 
     the starting key of this telegram will constitute the third group of the 
     message.

     Command-in-chief of the land and air forces in Africa - Confidential – 
     Bureau du Chiffre of the Army - Memento guide of the cipher clerk - Algiers, 
     January 15, 1943 ... 4° Conservation of documents ... Only open the cipher
     machines for the operations of encryption. Then close them with a key 
     during periods of non-use. Do not leave machines set to the current key 
     during transport. If a machine is involved in an accident, never entrust the 
     repair of a part to an unqualified person (civil worker, for example). 
     Request the exchange of the machine for a machine in good condition.

Footnote: [1] The starting key corresponds to the message key chosen by the operator.

In the archives of the military forces in Africa (SHD-1P136 1942), I found an extraordinary document: an authentic cryptogram encrypted in C-36 dated June 9, 1941. Normally, no cryptogram is kept. Indeed, as soon as a cryptogram is deciphered, it is destroyed. Accordingly, if the enemy captures the secret documents of the Bureau du Chiffre, they cannot possess the plain text and the corresponding cipher text at the same time.

Therefore, why does it appear here in the army archives? Because this message had been transmitted on the radio waves and intercepted by the Germans. They could not decipher it because it used a process that had not been authorized by the Armistice Commission. The Germans demanded from the French state of Vichy not only the plain message but also the process and the keys used. The war secretary addressed the German request to the Governor of French Africa because the message came from that region. Vichy also demanded that an investigation into this breach of the security rules be conducted and that sanctions be imposed against those responsible.

In the letter originating from the Vichy government and accompanying the cryptogram, two pieces of information concerning the procedures became apparent to me:

1. Judging from the last two groups of the cryptogram, the war secretary declared that it was encrypted by means of the C-36. To corroborate this assertion, one can read on the page containing the cryptogram, the text "NDKLE" written in pencil. This chain was presumably the key of the message. I knew the method used to encrypt the message key in May 1940. The method in 1941 must have been slightly different from that used previously because it allowed the machine that was used to be deduced (B-211 or C-36). Therefore, I think that, as before, the key was encrypted through two substitution alphabets but which were different for the B-211 and the C-36. Thus, if the decryption of the indicator gave the same key, we not only knew this key but also which machine was used [1].
2. The Secretary of War also requested that the keys of the C-36 machine be changed, that is, Tables A and B and the location of the key groups. Thus, I learned that this location was changeable. At a minimum, the groups were either at the start of the message (as at the start of the war), or at the end (as in the message), or perhaps still buried inside the cryptogram.

The verbatim cryptogram from the archives (at the bottom, handwritten in pencil: NDKLE):

      		de FVA à FVB 9/6/41 21 h 19
       Off Alger nr 152 W57 h 9 à 18 h 10 – Général Cdt 19 ème
       		région à Division Oran. - 
       0945-
       XOTKA YLRWH TMTIR ADRDB VHCCL WUCCA JGDBG ZFYNC
       ZRBKD WDSHA ELDZG DZVGM FOFMR LIHCF XFJSP YXMBD
       TWWXH OSQVO QJQOV LVCHO NUVGP RILRG UUVVG KDDUE
       TDXYO HNOEZ ZWWAI KSIAC ZLNLV RYSKF WBJUE TSODI
       MTYCS UADMS RKFCW WSKTX RFCJW IQFKD WIYZX TSDOE
       KTTNF MAPEN JKYRB POTVT GZEBC - ar.

To obtain the cryptogram solution described in the previous paragraph, I used the hill climbing approach but in the simplest way possible. At each step, I changed the value of a randomly chosen pin and calculated a score with bigrams as the fitness function. If the score improved, I kept the pin configuration. I repeated this step 200 times before abandoning my trials. I repeated the whole process for as long as the score improved. I calculated the frequencies of French bigrams from the work "The Battle of France" by Louis Madelin (Madelin 1920). In case of failure, I had planned to use a more accurate source based on the hundred or so raw decryptions of C-36 messages that I collected at the SHD (SHD-11P187 1944). Admittedly, these data dated from 1943 and the cryptogram from 1941, but they were better than those in Madelin’s book. It is undeniable that in extreme cases good statistics are vital.

Algorithm

     0. Set the maximum score to zero. 

     1. Generate initial random pin setting, decrypt and compute an initial
        score with the fitness function. Fix the high score to this initial 
        score.

     2. Repeat the following steps. Exit from this infinite loop if the 
        fitness function no longer improves the maximal score.

        2.1. For a predetermined number of loops (for example, 200).
               2.1.1. Randomly toggle a pin.
               2.1.2. Decrypt and compute the fitness function.
               2.1.3. If the score with the new pin setting is better
                      than the high score, fix the high score to the current
                      score. In addition, keep the new pin setting. Otherwise,
                      discard the new pin setting.
	2.2. If the high score is better than the maximal score, fix the
             maximal score to the new one and print this score, the key, and
             the beginning of the plain deciphered text.

     3. Repeat from Step 1, i.e., restart with new random pin setting. 
        Stop if the predetermined number of loops is reached (number of 
        shotgun restart).

After France was wiped out, German cryptologists had plenty of time to break the C-36 and B-211 systems. They could base their attempts to do so not only on the capture of these machines but also on many seized documents during Battle of France [1] As the C-36 and B-211 systems were not part of the encryption methods authorized on the airwaves by the Germans, they were unable to intercept their traffic, which was only wired, and therefore could not exploit them.

Here is the result of these studies, which are described in the document “OKW/Chi [2] Cryptanalytic Research on Enigma, Hagelin and Cipher Teleprinter Machines” (TICOM I-45 1945).

     … The different methods to break the C36 are as follows:

     1. Solution of messages of the same phase [3] in the case of C.36.
     2. Solution of C.36 from stereotyped beginnings.
     3. General solution of C.36 ...

Count Cipher Plain Diff. Key   Pin Settings Hypothesis (D,P)
  000      I     O    22   2  [ 0 1 0 0 0 ]
  001      N     R     4  10  [ ? ? ? 1 0 ]
  002      C     G     8  14  [ ? 0 0 0 1 ]
  003      X     A    23   3  [ ? ? ? 0 0 ] 
  004      L     N    24   4  [ 1 0 1 0 0 ]
  005      B     I     9  15  [ ? 1 0 0 1 ]
  006      I     Z     7  13  [ 1 1 1 1 0 ]
  007      S     A    18  24  [ ? 0 1 1 1 ]
  008      S     T    11  17  [ ? 0 1 0 1 ]
  009      D     I    11  17  [ ? 0 1 0 1 ]
  010      Q     O     4  10  [ ? ? ? 1 0 ]
  011      G     N    19  25  [ ? 1 1 1 1 ]
  012      Q     K     0   6  [ 1 1 1 0 0 ]
  013      L                  [           ]
  014      Z                  [           ]
  015      X                  [           ]
  016      J                  [           ]
  017      V                  [         0 ]
  018      G                  [         0 ]
  019      X                  [       0 1 ] 8,9,11,12   L,M,O,P  
  020      C                  [       1 0 ] 1-7         Z,A-F
  021      H                  [     0 0 0 ] 20-23       N,0,P,Q
  022      B                  [     ? 0 1 ] 8,9,11,12   H,I,K,L
  023      E                  [   1 0 0 0 ] 22,23       S,T
  024      A                  [   ? ? 0 1 ] 8,9,11,12   I,J,L,M   
  025      M                  [ 0 0 1 1 1 ] 18          G
  026      D                  [ ? ? 0 1 1 ] 12,13       M,N
  027      Y                  [ ? 0 1 0 0 ] 23,24       Z,A
  028      B                  [ ? 1 1 0 1 ] 12          L
  029      X                  [ 1 1 1 1 0 ] 7           K
  030      X                  [ ? 0 1 1   ] 4,5,8       H,I,L
  031      I                  [ 1 0 ? 0   ] 21,24,8,11  N,K,A,X
  032      E                  [ ? 0 1     ] 19,20,1,2,15T,U,A,B,P
  033      P                  [ ? ? 1     ]
  034      V                  [ ? 1       ]
Count Cipher Plain Diff. Key Pin Settings Hypothesis (D,P)

References

• Barker Wayne G., 1977. Cryptanalysis of the Hagelin cryptograph", Aegean Park Press
• Deavours, Cipher A., Kruh, Louis. 1985. Machine Cryptography and Modern Cryptanalysis – Cipher A. Deavours & Louis Kruh, Artech House, Inc, Boston, London.
• Ribadeau-Dumas, L. 1975. Essai d’historique du chiffre de l’armée de terre, 4ième partie (1919-1939), Bulletin de l’ARCSI, Nouvelle série N°3, p19–34
• Ribadeau-Dumas, L. 1976. Essai d’historique du chiffre de l’armée de terre, 5ième partie: la guerre 1939-1945, Bulletin de l’ARCSI, Nouvelle série N°4, p33–52
• SHD - 1 P 136. 1942. Délégation générale du gouvernement en Afrique française – 1941-1942
• SHD 11 P 187. 1944. 1er Division Blindée – Section du chiffre – E.M: 2e Bureau – Télégrammes expédiés 9-6-43 au 21-12-1944. 1943-1944.

Web Links