#: 22954 S6/Crypto/Encryption 07-Jul-95 04:09:22 Sb: German Codes Part 2 Fm: Randy Nichols (SysOp) 75542,1003 To: Mich Kabay 75300,3232 (X) Mich: GERMAN REDUCTION CIPHERS Part II "Weh dem der leugt und Klartext funkt" - Lieutenant Jaeger German 5th Army. ["Woe to him who lies and radios in the clear"] Jaeger was a German code expert sent to stiffen the German Code discipline in France in 1918. Ironically, the double "e" in Jaeger's name gave US Army TA experts a fix on code changes in 1918. (8) ADFGVX ADFGVX, is one of the best known field ciphers in the history of cryptology. Originally a 5 x 5 matrix of just 5 letters, ADFGX, the system was expanded on June 1, 1918 to a 6th letter V. The letters were chosen for their clarity in Morse: A .-, D -.., F ..-., G --., V ...-, and X -..-. (9) W. F. Friedman describes one of the first traffic analysis charts regarding battle activity from May to August, 1918 at Marne, and Rheims, France. It was based solely on the ebb and flow of traffic in the ADFGVX cipher. This cipher was restricted to German High Command communications between and among the headquarters of divisions and army corps. (10) The ADFGVX cipher was considered secure because it combined both a good substitution (bipartite fractionation) and an excellent transposition in one system. During the eight month history of this cipher, only 10 keys were recovered by the Allies (in 10 days of heavy traffic) and fifty percent of the messages on these days were read. These intercepts effected the reverse of the German advances (15 divisions) under Ludendorff at Montdidier and Compiegne, about 50 miles North of Paris. Solution by the famed French Captain Georges Painvin was based on just two specialized cases. No general solution for the cipher was found by the Allies. In 1933, William Friedman and the SIS found a general solution. French General Givierge, of the Deuxieme Bureau also published a solution to the general case. (11), (12), (13), (14), (15) The June 3 message that Painvin cracked which changed the course of WWI: From German High Command in Remaugies: Munition-ierung beschleunigen Punkt Soweit nicut eingesehen auch bei Tag "Rush Munitions Stop Even by day if not seen." CT starts: CHI-126: FGAXA XAXFF FAFFA AVDFA GAXFX FAAAG This told the Allies where and when the bombardment preceding the next major German push was planned. ENCIPHERING 26 letters and 10 digits of the ADFGVX were placed into a 6 x 6 Bipartite Square: A D F G V X A F L 1 A O 2 D J D W 3 G U F C I Y B 4 P G R 5 Q 8 V E V 6 K 7 Z M X X S N H 0 T 9 PT: a l l q u i e t o n t h i s CT: AG AD AD GF DX FD GX XV AV XD XV XF FD XA PT: f r o n t t o d a y CT: AA GA AV XD XV XV AV DD AG FF The bilateral cipher which results is transposed with a keyed matrix, written in by row and removed by column. G E R M A N 3 2 6 4 1 5 A G A D A D G F D X F D G X X V A V X D X V X F F D X A A A G A A V X D X V X V A V D D A G F F and the final CT is: AFAXA XAFGF XDDAV DAGGX FGXDD XVVAV VGDDV FADVF ADXXX AXA Known decipherment was accomplished with the Key and possession of the original matrix. Fine and dandy but cryptanalsis in 1918, was another thing. CRYPTANALYSIS According to William Friedman, there were only three viable ways to attack this cipher. The first method required 2 or messages with identical plaintext beginnings to uncover the transposition. Under the second method, 2 or more messages with plaintext endings were required to break the flat distribution shield of the substitution part of the cipher. The German addiction to stereotyped phraseology (Nichols Part 1) was so prevalent in all German military communications that in each days traffic, messages with similar endings and beginnings were found (sometimes both). The third method required messages with the exact same number of letters. Painvin used the first two methods when he cracked the 5 letter ADFGX version in April, 1918. (17), (18) Lest we underestimate the difficulty of this cipher, I think we might step behind Painvin shoulders as he worked. At 4:30 am on March 21, 6000 guns opened fire on the Allied line at Somme. Five hours later, 62 German Divisions pushed forward on a 40 mile front. Radio traffic increased dramatically, Painvin had just a few intercepts in the ADFGX cipher and the longer ones had been split in three parts to prevent anagraming. Five letters, therefore, a checkerboard? Simple mono cipher -too flat a distribution. The German oddity of first parts of messages with identical bits and pieces of text larded in the same order in the cryptograms begin to show. Painvin feels the oddity could most likely have resulted from transposed beginnings according to the same key; the identical tops of the columns of the transposition tableau. Painvin sections the cryptograms by timeframe: chi-110: (1) ADXDA (2) XGFXG (3) DAXXGX (4) GDADFF chi-114: (1) ADXDD (2) XGFFD (3) DAXAGD (4) GDGXD He does this with 20 blocks to reconstruct the transposition key. Using the principle - long columns to the left, he finds segments 3,6,14, 18 to left. Balance clustered to right. Using other messages with common endings (repeated) He segments the columns to the left. Correctly? No. He uses 18 additional intercepts to juxtaposition 60 letters AA's, AD's, etc. Using frequency count, he finds a monoalphabetic substitution. He finds column 5-8 and 8-5 are inverted. Painvin sets up a skeleton checkerboard - he assumes correctly the order to be side-top: A D F G X A D e F G X Since the message was 20 letters, the order might be side-top, repeated, meaning side coordinates would fall on 1st, 3rd, 5th.. positions during encipherment, so he separates them by frequency characteristics. In 48 hours of incredible labor, Painvin pairs the correct letters and builds the checkerboard, solving the toughest field cipher the world had yet seen. A cipher that defends itself by fractionation - the breaking up of PT letters equivalents into pieces, with the consequent dissipation of its ordinary characteristics. The transposition further scatters these characteristics in a particularly effective fashion, while dulling the clues that normally help to reconstruct a transposition. (19), (20), (21), (22) REFERENCES 8) David Kahn, The Codebreakers, MacMillian, New York, 1967. 9) OP CIT. , D. Kahn. 10) Anonymous, The Friedman Legacy: A Tribute to William and Elizabeth Friedman, National Security Agency, Central Security Service, Center for Cryptological History, 1995. 11) IBID. 12) Fred B. Wrixon, Codes and Ciphers, Prentice Hall, New York, 1992. 13) W. F. Friedman, American Army Field Codes in the American Expeditionary Forces during the First World War. GPO, 1942. 14) W. F. Friedman, Field Codes used by the German Army During World War. 1919. 15) General Giverge, Cours de Cryptographie, 1925. 16) Capt. C. J. Mendelsohn, Studies in German Diplomatic Codes Employed During World War, GPO, 1937. 17) IBID, Kahn. 18) IBID, The Friedman Legacy 19) IBID, The Friedman Legacy 20) IBID, W. F. Friedman, Field Codes.. 21) IBID, D. Kahn. 22) R. Nichols, German Reduction Ciphers Part 1, 1995.