ADFGVX cipher

Last updated

In cryptography, the ADFGVX cipher was a manually applied field cipher used by the Imperial German Army during World War I. It was used to transmit messages secretly using wireless telegraphy. ADFGVX was in fact an extension of an earlier cipher called ADFGX which was first used on 1 March 1918 on the German Western Front. ADFGVX was applied from 1 June 1918 on both the Western Front and Eastern Front.

Contents

Invented by the Germans signal corps officers Lieutenant Fritz Nebel  [ de ] (1891–1977) [1] [2] and introduced in March 1918 with the designation "Secret Cipher of the Radio Operators 1918" (Geheimschrift der Funker 1918, in short GedeFu 18), the cipher was a fractionating transposition cipher which combined a modified Polybius square with a single columnar transposition.

The cipher is named after the six possible letters used in the ciphertext: A, D, F, G, V and X. The letters were chosen deliberately because they are very different from one another in the Morse code. That reduced the possibility of operator error.

Nebel designed the cipher to provide an army on the move with encryption that was more convenient than trench codes but was still secure. In fact, the Germans believed the ADFGVX cipher was unbreakable. [3]

Operation

For the plaintext message, "Attack at once", a secret mixed alphabet is first filled into a 5 × 5 Polybius square:

ADFGX
Abtalp
Ddhozk
Fqfvsn
Ggi/jcux
Xmrewy

i and j have been combined to make the alphabet fit into a 5 × 5 grid.

By using the square, the message is converted to fractionated form:

attackatonce
AFADADAFGFDXAFADDFFXGFXF

The first letter of each ciphertext pair is the row, and the second ciphertext letter is the column, of the plaintext letter in the grid (e.g., "AF" means "row A, column F, in the grid").

Next, the fractionated message is subject to a columnar transposition. The message is written in rows under a transposition key (here "CARGO"):

C A R G O _________ A F A D A D A F G F D X A F A D D F F X G F X F

Next, the letters are sorted alphabetically in the transposition key (changing CARGO to ACGOR) by rearranging the columns beneath the letters along with the letters themselves:

A C G O R _________ F A D A A A D G F F X D F A A D D F X F F G F   X

Then, it is read off in columns, in keyword order, which yields the ciphertext:

FAXDF ADDDG DGFFF AFAX AFAFX

In practice, the transposition keys were about two dozen characters long. Long messages sent in the ADFGX cipher were broken into sets of messages of different and irregular lengths to make it invulnerable to multiple anagramming. [3] Both the transposition keys and the fractionation keys were changed daily.

ADFGVX

In June 1918, an additional letter, V, was added to the cipher. That expanded the grid to 6 × 6, allowing 36 characters to be used. That allowed the full alphabet (instead of combining I and J) and the digits from 0 to 9. This mainly had the effect of considerably shortening messages containing many numbers.

The cipher is based on the 6 letters ADFGVX. In the following example the alphabet is coded with the Dutch codeword 'nachtbommenwerper'. This results in the alphabet: NACHTBOMEWRPDFGIJKLQSUVXYZ. Digits are inserted after the first occurrences of the letters A (1), B (2) to J (0). This creates the table below with the letters ADFGVX as column headings and row identifiers:

ADFGVX
ANA1C3H
D8TB2OM
FE5WRPD
G4F6G7I
V9J0KLQ
XSUVXYZ

The text 'attack at 1200am' translates to this:

ATTACKAT1200AM
ADDDDDADAGVGADDDAFDGVFVFADDX

Then, a new table is created with a key as a heading; the following example uses 'PRIVACY' as a key, but usually much longer keys or even phrases were used.

PRIVACY
ADDDDDA
DAGVGAD
DDAFDGV
FVFADDX

The columns are sorted alphabetically, based on the keyword, and the table changes to this:

ACIPRVY
DDDADDA
GAGDAVD
DGADDFV
DDFFVAX

Then, appending the columns to each other results in this ciphertext:
DGDD DAGD DGAF ADDF DADV DVFA ADVX

With the keyword, the columns can be reconstructed and placed in the correct order. When using the original table containing the secret alphabet, the text can be deciphered.

This cipher might be modified by transposing the rows as well as the columns, creating a harder but improved cipher.

Cryptanalysis

ADFGVX was cryptanalysed by French Army Lieutenant Georges Painvin, and the cipher was broken in early June 1918. [4] The work was exceptionally difficult by the standards of classical cryptography, and Painvin became physically ill during the process. His method of solution relied on finding messages with stereotyped beginnings, which would fractionate them and then form similar patterns in the positions in the ciphertext that had corresponded to column headings in the transposition table. (Considerable statistical analysis was required after that step had been reached, all done by hand.) It was thus effective only during times of very high traffic, but that was also when the most important messages were sent.

However, that was not the only trick that Painvin used to crack the ADFGX cipher. [3] He also used repeating sections of ciphertext to derive information about the likely length of the key that was being used. Where the key was an even number of letters in length he knew, by the way the message was enciphered, that each column consisted entirely of letter coordinates taken from the top of the Polybius Square or from the left of the Square, not a mixture of the two. Also, after substitution but before transposition, the columns would alternately consist entirely of "top" and "side" letters. One of the characteristics of frequency analysis of letters is that while the distributions of individual letters may vary widely from the norm, the law of averages dictates that groups of letters vary less. With the ADFGX cipher, each "side" letter or "top" letter is associated with five plaintext letters. In the example above, the "side" letter "D" is associated with the plaintext letters "d h o z k", and the "top" letter "D" is associated with the plaintext letters "t h f j r". Since the two groups of five letters have different cumulative frequency distributions, a frequency analysis of the "D" letter in columns consisting of "side" letters has a distinctively different result from those of the "D" letter in columns consisting of "top" letters. That trick allowed Painvin to guess which columns consisted of "side" letters and which columns consisted of "top" letters. He could then pair them up and perform a frequency analysis on the pairings to see if the pairings were only noise or corresponding to plaintext letters. Once he had the proper pairings, he could then use frequency analysis to figure out the actual plaintext letters. The result was still transposed, but to unscramble a simple transposition was all that he still had to do. Once he determined the transposition scheme for one message, he would then be able to crack any other message that was enciphered with the same transposition key. [3]

Painvin broke the ADFGX cipher in April 1918, a few weeks after the Germans launched their Spring Offensive. As a direct result, the French army discovered where Erich Ludendorff intended to attack. The French concentrated their forces at that point, which has been claimed to have stopped the Spring Offensive.

However, the claim that Painvin's breaking of the ADFGX cipher stopped the German spring offensive of 1918, while frequently made, [5] is disputed by some. In his 2002 review of Sophie de Lastours' book on the subject, La France gagne la guerre des codes secrets 1914-1918, in the Journal of Intelligence History, (Journal of Intelligence History: volume 2, Number 2, Winter 2002) Hilmar-Detlef Brückner stated:

Regrettably, Sophie de Lastours subscribes to the traditional French view that the solving of a German ADFGVX-telegram by Painvin at the beginning of June 1918 was decisive for the Allied victory in the First World War because it gave timely warning of a forthcoming German offensive meant to reach Paris and to inflict a critical defeat on the Allies. However, it has been known for many years, that the German Gneisenau attack of 11 June was staged to induce the French High Command to rush in reserves from the area up north, where the Germans intended to attack later on.

Its aim had to be grossly exaggerated, which the German High Command did by spreading rumors that the attack was heading for Paris and beyond; the disinformation was effective and apparently still is. However, the German offensive was not successful because the French had enough reserves at hand to stop the assault and so did not need to bring in additional reinforcements.

Moreover, it is usually overlooked that the basic version of the ADFGVX cipher had been created especially for the German Spring Offensive in 1918, meant to deal the Allies a devastating blow. It was hoped that the cipher ADFGX would protect German communications against Allied cryptographers during the assault, which happened.

Telegrams in ADFGX appeared for the first time on 5 March, and the German attack started on 21 March. When Painvin presented his first solution of the code on 5 April, the German offensive had already petered out.

The ADFGX and ADFGVX ciphers are now regarded as insecure.

Related Research Articles

<span class="mw-page-title-main">Cryptanalysis</span> Study of analyzing information systems in order to discover their hidden aspects

Cryptanalysis refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters, pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing the inverse substitution process to extract the original message.

<span class="mw-page-title-main">Transposition cipher</span> Method of encryption

In cryptography, a transposition cipher is a method of encryption which scrambles the positions of characters (transposition) without changing the characters themselves. Transposition ciphers reorder units of plaintext according to a regular system to produce a ciphertext which is a permutation of the plaintext. They differ from substitution ciphers, which do not change the position of units of plaintext but instead change the units themselves. Despite the difference between transposition and substitution operations, they are often combined, as in historical ciphers like the ADFGVX cipher or complex high-quality encryption methods like the modern Advanced Encryption Standard (AES).

<span class="mw-page-title-main">Caesar cipher</span> Simple and widely known encryption technique

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code, or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

<span class="mw-page-title-main">Vigenère cipher</span> Simple type of polyalphabetic encryption system

The Vigenère cipher is a method of encrypting alphabetic text where each letter of the plaintext is encoded with a different Caesar cipher, whose increment is determined by the corresponding letter of another text, the key.

<span class="mw-page-title-main">Tabula recta</span> Fundamental tool in cryptography

In cryptography, the tabula recta is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes Trithemius in 1508, and used in his Trithemius cipher.

In cryptography, coincidence counting is the technique of putting two texts side-by-side and counting the number of times that identical letters appear in the same position in both texts. This count, either as a ratio of the total or normalized by dividing by the expected count for a random source model, is known as the index of coincidence, or IC for short.

<span class="mw-page-title-main">Playfair cipher</span> Early block substitution cipher

The Playfair cipher or Playfair square or Wheatstone–Playfair cipher is a manual symmetric encryption technique and was the first literal digram substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair for promoting its use.

<span class="mw-page-title-main">Ciphertext</span> Encrypted information

In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. This process prevents the loss of sensitive information via hacking. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

A straddling checkerboard is a device for converting an alphanumeric plaintext into digits whilst simultaneously achieving fractionation and data compression relative to other schemes using digits. It also is known as a monôme-binôme cipher.

<span class="mw-page-title-main">Polybius square</span> Type of code

The Polybius square, also known as the Polybius checkerboard, is a device invented by the ancient Greeks Cleoxenus and Democleitus, and made famous by the historian and scholar Polybius. The device is used for fractionating plaintext characters so that they can be represented by a smaller set of symbols, which is useful for telegraphy, steganography, and cryptography. The device was originally used for fire signalling, allowing for the coded transmission of any message, not just a finite number of predetermined options as was the convention before.

In cryptography, a classical cipher is a type of cipher that was used historically but for the most part, has fallen into disuse. In contrast to modern cryptographic algorithms, most classical ciphers can be practically computed and solved by hand. However, they are also usually very simple to break with modern technology. The term includes the simple systems used since Greek and Roman times, the elaborate Renaissance ciphers, World War II cryptography such as the Enigma machine and beyond.

In cryptanalysis, Kasiski examination is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. It was first published by Friedrich Kasiski in 1863, but seems to have been independently discovered by Charles Babbage as early as 1846.

The trifid cipher is a classical cipher invented by Félix Delastelle and described in 1902. Extending the principles of Delastelle's earlier bifid cipher, it combines the techniques of fractionation and transposition to achieve a certain amount of confusion and diffusion: each letter of the ciphertext depends on three letters of the plaintext and up to three letters of the key.

<span class="mw-page-title-main">Rail fence cipher</span> Type of transposition cipher

The rail fence cipher is a classical type of transposition cipher. It derives its name from the manner in which encryption is performed, in analogy to a fence built with horizontal rails.

The four-square cipher is a manual symmetric encryption technique. It was invented by the French cryptographer Felix Delastelle.

The Two-square cipher, also called double Playfair, is a manual symmetric encryption technique. It was developed to ease the cumbersome nature of the large encryption/decryption matrix used in the four-square cipher while still being slightly stronger than the single-square Playfair cipher.

In the history of cryptography, a grille cipher was a technique for encrypting a plaintext by writing it onto a sheet of paper through a pierced sheet. The earliest known description is due to Jacopo Silvestri in 1526. His proposal was for a rectangular stencil allowing single letters, syllables, or words to be written, then later read, through its various apertures. The written fragments of the plaintext could be further disguised by filling the gaps between the fragments with anodyne words or letters. This variant is also an example of steganography, as are many of the grille ciphers.

<span class="mw-page-title-main">Georges Painvin</span> French cryptographer (1886–1980)

Georges Jean Painvin was a French geologist and industrialist, best known as the cryptanalyst who broke the ADFGX/ADFGVX cipher used by the Germans during the First World War.

With the rise of easily-intercepted wireless telegraphy, codes and ciphers were used extensively in World War I. The decoding by British Naval intelligence of the Zimmermann telegram helped bring the United States into the war.

References

  1. Friedrich L. Bauer: Decrypted Secrets, Methods and Maxims of Cryptology. Springer, Berlin 2007 (4. Aufl.), S. 173, ISBN   3-540-24502-2.
  2. Friedrich L. Bauer: Decrypted Secrets, Methods and Maxims of Cryptology. Springer, Berlin 2007 (4. Aufl.), S. 53, ISBN   3-540-24502-2.
  3. 1 2 3 4 "Codes and Codebreaking in World War I". Archived from the original on 3 May 2010. Retrieved 10 March 2010.
  4. Newton, David E. (1997). Encyclopedia of Cryptography. Santa Barbara California: Instructional Horizons, Inc. p. 6.
  5. "Painvin's manna had saved the French", wrote David Kahn, in The Codebreakers - The Story of Secret Writing, 1967, ISBN   978-0-684-83130-5, Chapter 9. Kahn also details the role that Painvin's decryption of German messages played in the French response to Operation Gneisenau.

Sources