Breaking “Tirpitz”: Cryptanalysis of the Japanese-German joint naval cipher

This article gives the solutions of the only four messages known to still exist from the previously unbroken Japanese-German joint naval radio communications traffic in the system known as “Tirpitz,” which used the specially-designed model T Enigma machine. It also explains the methods used by the author to break the messages, and gives some background on the model T Enigma and its usages.     

Ciphertext-only cryptanalysis of Hagelin M-209 pins and lugs

The Hagelin M-209 was a mechanical encryption device used by the U.S. Army during World War II and the Korean War, as well as by other armies and in embassy settings. In this article, the authors present a four-stage hillclimbing algorithm for recovering the full key settings from ciphertext only. The first two stages are based on a divide-and-conquer approach developed by Geoff Sullivan. In the current performance evaluation, the authors show that their method is able to recover key settings from messages as short as 750 letters, compared to 2,000 – 2,500 letters with prior methods. With this method, they solved several M-209 ciphertext-only challenges, including the final exercises in W. Barker’s 1977 book, Cryptanalysis of the Hagelin Cryptograph.     

Cryptanalysis of Chaocipher and solution of Exhibit 6

Chaocipher is a manual encryption method designed by John F. Byrne in 1918. Until he passed away in 1960, Byrne fervently believed that his cipher system was unbreakable, regardless of the amount of material available to a cryptanalyst. For several decades, he tried (unsuccessfully), to propose the Chaocipher to government agencies. In 1953, he exposed his Chaocipher in his autobiography, Silent Years, providing several examples of texts encrypted with Chaocipher as challenges, but without divulging the inner workings of the cipher. Those were made public only in 2010, when Byrne’s family donated the entire corpus of Chaocipher papers to the National Cryptologic Museum (NCM) in Fort Meade.

A known-plaintext method for recovering the key settings, given sufficient matching plaintext and ciphertext, was published in 2010. However, to date, no method for the cryptanalysis of a single ciphertext-only Chaocipher message has been proposed, nor for the cryptanalysis of short messages “in-depth,” i.e., multiple messages generated with the same initial key settings.

In this article, the authors present a new hillclimbing algorithm for a ciphertext-only cryptanalysis of Chaocipher in-depth messages. This algorithm is based on a “divide-and-conquer” approach and the use of the Index of Coincidence. It takes advantage of a major weakness in the design of the cipher. This previously unknown weakness may have been the reason why William F. Friedman, the inventor of the Index of Coincidence, rejected Byrne’s offer for the use of Chaocipher by the U.S. government. Additionally, the authors present a known-plaintext attack for short in-depth messages, as well as the solution for Lou Kruh’s and Cipher Deavours’s alternate Exhibit 5, also known as “Exhibit 6.” Finally, the authors reevaluate the security of the Chaocipher in view of those findings, with the conclusion that in its classic form, as designed by Byrne, the Chaocipher was a relatively weak cipher, despite Byrne’s rather strong assertions to the contrary.     

Cryptanalysis of Enigma double indicators with hill climbing

The Enigma machines were a series of electromechanical rotor cipher machines developed in Germany and used in the first half of the twentieth century to protect commercial, diplomatic, and military communications. Until 1938, the German Army used the so-called double-indicator procedure to transmit Enigma-encoded messages. It was replaced in September 1938 by a new procedure also involving double indicators. Both procedures enabled a team of mathematicians from the Polish Cipher Bureau to recover the wiring of the rotors and to develop cryptanalytic methods for the recovery of the daily keys. The double-indicator procedure was discontinued by the German Army in May 1940, and new methods were developed by the British at Bletchley Park, who were assisted by the knowledge transferred to them by the Polish cryptanalysts. In this article, the authors introduce two new algorithms that build on the historical cryptanalytic attacks on the two variants of the double-indicator procedures. Those attacks are based on hill climbing, divide-and-conquer, and specialized scoring functions, and they can recover the daily key using a number of indicators significantly smaller than the number of indicators required for the historical methods. Unlike the historical methods, the new algorithms produce unique and unambiguous results, including for scenarios with turnover of the middle rotor, and they also fully recover the plugboard settings. With these algorithms we won an international Enigma contest organized in 2015 by the City of Poznan, in memory of the Polish Cipher Bureau mathematicians.     

MEMORIES OF THE PACIFIC: BOOK REVIEWS

Abstract

This article describes the importance of the Knox contribution to the breaking of the plugboard German Enigma through his early work on the commercial machine; as well as his invention of “rodding” and exploitation of the Saga method of “boxing.” It also covers the multi-turnover Abwehr machine through observation of the phenomenon of ‘crabs and lobsters’ in message indicators.     

The Turing Bombe Victory and the first naval Enigma decrypts

Victory was the name of the first prototype Bombe that was developed for breaking the German Enigma messages of World War II. It lacked the diagonal board and simultaneous scanning that was provided for all the later models, but these disadvantages were overcome by the ingenious use of a column menu (a special Bombe menu where the Enigma fast rotors are all in the same position) to break six days of naval traffic, 22–27 April 1940, following the pinch of material from an armed trawler Schiff 26 (Polares). These were the first naval decrypts of the War, and their solution took several months to complete. No further naval breaks occurred until November. This article examines the decryption process in some detail in order to explain the difficulties, highlight the role of Victory in this process, and provide detailed workings of the processes. It also sheds some light on the early development of the British Bombe.     

THE PAPER ENIGMA MACHINE

The Enigma Machine is a complex electromechanical device used by the Germans in World War II to achieve what they thought was complete communications security. While the original machine weighed over 20?lbs, the central mechanics of the machine can be simulated manually by manipulating strips of paper. A Paper Enigma is presented that can be cut out of a single sheet of paper. The resulting simulator is compatible with the electromechanical original in that messages can be encoded on one, and decoded on the other. Copies of The Paper Enigma can be downloaded from http://mckoss.com/crypto/enigma.htm.     

MODEL Z: A NUMBERS-ONLY ENIGMA VERSION

A review of pre-WWII documents in the Spanish Foreign Affairs Ministry has discovered a hitherto unknown Enigma modification, called “Model Z”, capable of encrypting numbers only. This model seems to be unknown to the Enigma community. The few known details concerning Enigma Z are here outlined.     

Recovering the military Enigma using permutations—filling in the details of Rejewski's solution

During the last few months of 1932, the Polish mathematician Marian Rejewski solved the problem of finding the internal connections of the rotors and reflector of the Enigma cipher machine used by the German army at that time. This allowed the Polish Cipher Bureau to construct an analogue of the machine, and subsequently to find effective methods for deciphering secret messages. Rejewski performed this feat virtually alone using cryptographic material provided by the Polish secret services. His knowledge of the theory of permutation groups was essential in solving this problem.

This article describes in detail how to find the complete wiring of the rotors and reflector of Enigma, as well as other specifics, using data that Rejewski had at his disposal, by systematically presenting the resolution of all cases that could have been encountered. Similarly, we complete those stages of the procedure that were only outlined by Rejewski.     

Early Work on Computers at Bletchley

Pioneering work on computers was carried out at Bletchley, England, during World War II, for the cryptanalysis of the messages enciphered on the German cryptographic machines, the Enigma and the Geheimschreiber. The work is discussed and thumbnail sketches of some of the people involved are included. The account is written in an autobiographical spirit, but some references to other sources are given.     

CIPHERTEXT-ONLY CRYPTANALYSIS OF ENIGMA

Enigma messages can be solved by recovering the message key settings, the ring settings, and the plug settings individually. Recovery of the message key setting is sensitive enough to distinguish the correct rotor order. The method is demonstrated on a 647-letter message, and its performance is estimated for different message lengths and numbers of plugs used.     

THE MARKET FOR ENCRYPTION

Abstract

In 1942, the United States Navy recognized that in the ranks of newly-enlisted WAVES lay the potential for much-needed assistance in processing German Navy Enigma messages that had been intercepted and deciphered. This is the improbable story of one of those WAVES.     

A GENERALIZATION OF THE KNAPSACK ALGORITHM USING GALOIS FIELDS

We prove a generalization of a theorem of Rejewski. This theorem shows how one can solve an equation of the form XY=α in a symmetric group, where α is a given permutation and X and Y are each of order two with a specified number of disjoint transpositions. The number of solutions is also part of the theorem. Using this theorem we outline what we believe was the Polish solution (or very close to it) to the Enigma assuming that one had no data from daily keys. With some assumptions on independence of events, we show that the Polish Cipher Bureau would probably have broken the Enigma in just over four years.     

GEHEIMSCHREIBER

World War II's “Fish” cipher was a British cover word for all kinds of encrypted German radio teleprinter messages. The GC&CS at Bletchley, Buckinghamshire, did not only attack successfully Enigma traffic (Morse signals on radio links) by the electromechanical deciphering machines called BOMBES. In addition, Bletchley's electronic text processor COLOSSUS broke the German “Tunny” ciphers, generated by TELEPRINTER ATTACHMENTS “SZ”, employed by the ‘Heer’ (Army) on HF radio links.     

Genuine French WWII M-209 cryptograms

Abstract

In the French Army archives three cryptograms encrypted by the M-209 were found. They date from 1944 and come from the 1st French Army. Since the security rules in the military require them to be destroyed, it is extremely rare to have access to this type of document.

This article aims to show the use of the M-209 in the French Army. It will first briefly describe the operation of the M-209 encryption machine and describe the cryptographic means used by the French Army during the Second World War, including the M-209 provided by the Americans. The three cryptograms found in the archives will then be studied. The various components of these messages are described, starting with the key groups (which provide the message key) and continuing to the main abbreviations as well as some codenames. The plaintexts will then become understandable. This article ends with the reconstruction of the keys (internal and external) of the first two messages. This reconstruction could not be completed for the third message: it is given as a challenge to the readers of Cryptologia. This is also the opportunity to balance the security of the M-209 with that of the Enigma.     

G-312: AN ABWEHR ENIGMA

G-312, an Abwehr Enigma in the collection of The Bletchley Park Trust is presented together with details of its internal mechanism and wheel wiring.     

Deciphering ADFGVX messages from the Eastern Front of World War I

In the last months of World War I (WW I), the German Army and diplomatic services used the ADFGVX hand-cipher system to encrypt radio messages between Germany and its outposts and stations in the Balkans, the Black Sea, and in the Middle East. Hundreds of cryptograms were intercepted from July to December 1918 by British and U.S. military intelligence, who were able to recover most of the keys and decipher most of the cryptograms using manual cryptanalysis methods. Fortunately, the original cryptograms have been preserved by James Rives Childs, the U.S. officer assigned to G.2 A.6, the SIGINT section of American Expeditionary Forces (AEF) in Paris, and they appear in his book, General Solution of the ADFGVX Cipher System, published by Aegean Press Park in 2000.

In this article, the authors present the results of an effort toward the complete cryptanalysis of the messages, and an analysis of their contents. The authors present a new computerized method for the ciphertext-only cryptanalysis of ADFGVX messages which they developed for that purpose. They also provide details on how all the keys were recovered and almost all the messages decrypted, despite the low quality of significant parts of the intercepted material.

The analysis of the messages in their historical context provides a unique insight into key events, such as the withdrawal of the German troops from Romania, and the impact of the Kiel Mutiny on communications. Both events had major political and military consequences for Germany in the Eastern Front. Cryptanalysis allowed the Entente Powers to closely monitor those events as well as others developments, also highlighting inherent weaknesses in German cryptographic and cryptanalytic capabilities. The authors plan to publish online all the decrypted messages.     

NAVAL ENIGMA: M4 AND ITS ROTORS

The wiring of rotors in the naval version of Enigma is given (including that of beta and gamma) and events leading to the introduction of Triton, a cipher for Atlantic U-boats, are described. It is shown that an alpha rotor did not enter service, and that Triton became operational in October 1941.     

The Design and Performance Evaluation of the DI-Multicomputer

In this paper, we propose a new multicomputer node architecture, theDI-multicomputerwhich uses packet routing on a uniform point-to-point interconnect for both local memory access and internode communication. This is achieved by integrating a router into each processor chip and eliminating the memory bus interface. Since communication resources such as pins and wires are allocated dynamically via packet routing, the DI-multicomputer is able to maximize the available communication resources, providing much higher performance for both intranode and internode communication. Multi-packet handling mechanisms are used to implement a high performance memory interface based on packet routing. The DI-multicomputer network interface provides efficient communication for both short and long messages, decoupling the processor from the transmission overhead for long messages while achieving minimum latency for short messages. Trace-driven simulations based on a suite of message passing applications show that the communication mechanisms of the DI-multicomputer can achieve up to four times speedup when compared to existing architectures.     

UMKEHRWALZE D: ENIGMA'S REWIRABLE REFLECTOR - PART II

Umkehrwalze D was a field-rewirable reflector for the German service Enigma machine, introduced primarily on German Air Force cipher networks late in the Second World War. The three parts of this article discuss the history of the device and the various techniques and machines developed by the British and American signals intelligence agencies to deal with it.