John F. Byrne's Chaocipher Revealed: An Historical and Technical Appraisal

Abstract

Chaocipher is a method of encryption invented by John F. Byrne in 1918, who tried unsuccessfully to interest the US Signal Corp and Navy in his system. In 1953, Byrne presented Chaocipher-encrypted messages as a challenge in his autobiography Silent Years. Although numerous students of cryptanalysis attempted to solve the challenge messages over the years, none succeeded. For 90 years, the Chaocipher algorithm was a closely guarded secret known only to a handful of persons. Following fruitful negotiations with the Byrne family during the period 2009–2010, the Chaocipher papers and materials have been donated to the National Cryptologic Museum in Ft. Meade, MD. This paper presents a comprehensive historical and technical evaluation of John F. Byrne and his Chaocipher system.     

Modern breaking of Enigma ciphertexts

“Breaking German Army Ciphers” is the title of a Cryptologia article from 2005, describing the lucky survival of several hundred authentic Enigma messages of World War II, and an account of a ciphertext-only cryptanalysis of a large number of these messages, leaving only a few (mostly short messages) unbroken. After reviewing the work done, and investigating the reasons for both lucky breaks and close misses, the modern ciphertext-only attack on Enigma messages is improved, especially on genuine ones with short lengths and/or many garbles. The difficulties of a proper measure for the candidate’s closeness to a plaintext are clarified. The influence on the decryption process of an empty plugboard and one with only a few correct plugs is examined. The method is extended by a partial exhaustion of the plugboard combined with an optimized hillclimbing strategy. The newly designed software succeeds in breaking formerly unbroken messages.     

Cryptanalysis of columnar transposition cipher with long keys

The classical columnar transposition cipher was the most popular type of transposition cipher. It was in use mainly during the second half of the nineteenth century and the first half of the twentieth century. It also served as a building block for more complex ciphers, such as the ADFGVX cipher and the double transposition cipher. Pen-and-paper as well as computerized methods for the cryptanalysis of the columnar transposition cipher have been published, but those apply mainly to the easier cases of short keys and complete transposition rectangles. In this article, a novel approach for the cryptanalysis of the columnar transposition cipher (when used with long keys) is presented. It is based on a two-phase hill climbing algorithm, a two-dimensional fitness score, and special transformations on key segments. This ciphertext-only method allows for the recovery of transposition keys with up to 1,000 elements, and up to 120 elements for worst case transposition rectangles.     

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.     

Lester Hill Revisited

Abstract

Lester Sanders Hill (1890–1961) is best known for the Hill cipher which he published in 1929. However, there seem to be four periods of Hill's career. First, in 1926 and 1927, Hill published a series of papers on mathematical error-detection. Hill's ideas for error-detection are similar to the ideas he used in his cipher. Next, in 1929 and 1931, Hill published two papers that describe the Hill cipher. The third period of Hill's career, from 1927 until 1960, was the time he served on the mathematics faculty of Hunter College. During his time at Hunter College, Hill seems to have had a relationship with the Navy in which he served during World War I. Finally, while teaching at Hunter College, in the 1950s, Hill wrote his “later papers” on cryptography, which were not published but were sent to Naval Communications.     

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.     

物联网环境中LED轻量级密码算法的统计故障分析研究

LED算法是于2011年密码硬件与嵌入式系统国际会议(CHES)中提出的一种典型轻量级密码算法,用于在物联网环境下保护RFID标签以及智能卡等设备的通信安全.故障分析凭借其攻击速度快、实现简单和难以防御等特点,已成为评测轻量级密码算法安全性的一种重要手段.提出了针对LED算法的新型统计故障分析方法,采用面向半字节的故障模型,分别使用SEI区分器、GF区分器和GF-SEI双重区分器对算法进行统计分析.实验结果表明：在较短时间内以99%的成功概率恢复出LED算法的64b和128b原始密钥.该攻击方法不仅可以在唯密文攻击条件下实现,而且提升了故障攻击效率,降低了故障数,为物联网环境下其他轻量级密码的安全性分析提供了重要参考.     

CRYPTANALYSTS' CORNER

Abstract

The Hill cipher, also known as matrix encryption, is a polygraphic substitution cipher, developed by the mathematician Lester S. Hill in 1929. While various attacks had been known on the Hill cipher, the ciphertext-only attack without assumptions about the encryption matrix or probable plaintext words was introduced only recently by Bauer and Millward. They obtained high efficiency of attack by recovering the decryption matrix row by row rather than all rows at once. In this paper, we extend their ciphertext-only attack in two ways. First, we present a better scoring system for cryptanalysis based on the goodness-of-fit statistics. Specifically, we reduce the average number of candidate rows from 24.83 to 7.00 for 3 × 3 matrix and from 4027.78 to 1220.38 for 4 × 4 matrix. Second, we show how to apply our attacks to the Hill cipher without knowing the numeric equivalents of the letters of the plaintexts.     

WERFTSCHLÜSSEL A GERMAN NAVY HAND CIPHER SYSTEM PART I

During World War II the German Navy employed not only the Cipher Machine ENIGMA but also a number of hand cipher systems. The peculiar hand system in question here, the “Werftschlssel” though quite unknown to the public provided valuable intelligence for the British and supported the cryptanalysis of naval enigma traffic.     

THE MEMORIA TECHNICA CIPHER

A comprehensive analysis of the ciphers invented by Charles L. Dodgson (Lewis Carroll) and how he used them indicate that his Memoria Technica (1875), a variant of a mnemonic scheme first proposed by Richard Grey in 1730, is properly viewed as Dodgson's fifth cipher system. He used his Memoria Technica cipher as a tool in work that was never published, a projected book whose working title was “Logarithms by Lightning: A Mathematical Curiosity.” The logarithms project, a joint work with his colleague, Robert Edward Baynes, is examined in detail.     

FORTY ONE AND STRONG: ARLINGTON HALL STATION

Abstract

Dr. Donald H. Menzel is well known for his work in astronomy, but his cryptologic work has never received a thorough review. The present article describes how his interest in this area was first sparked and provides the details of the secret class he led in “Naval Communications” (really cryptanalysis) at Radcliffe College during World War II. This class served as a prototype and was copied elsewhere. A sketch of some of the classified work he carried out during the war, and after, as a consultant, is also included, along with a brief overview of Menzel's personality and other interests.     

Analyzing the Spanish strip cipher by combining combinatorial and statistical methods

According to historical reports, many telegrams that date from the Spanish Civil War (1936–1939) still remain undisclosed. It is believed that these telegrams were encrypted with a cryptosystem called the “Spanish Strip Cipher” (SSC).

During this civil war, SSC was the most used cryptographic algorithm. This method corresponds to a homophonic substitution cipher in which a plaintext letter can map to between three and five ciphertext symbols.

By means of cryptanalysis, the authors detect a weakness in the encryption process of the SSC. In this article, they describe how this vulnerability is exploited to efficiently reconstruct a plaintext from a relatively short ciphertext. The attack is based on combinatorial and statistical methods, and it is divided into three phases: homophones-table analysis, letter-frequency analysis, and dictionary search.

The attack was implemented in Java and tested on a laptop with an i7 processor and 4 GB of RAM. The tests were carried out with several real telegrams from the Spanish Civil War. In this article, the authors provide the results of one test that was successfully performed only using the first 201 ciphertext symbols of a Spanish telegram.     

THE CYLINDER-CIPHER

Questions Thomas Jefferson's attributed invention of the “cylinder cipher,” notes similar devices before and after his time, and introduces a “mystery device” of this nature in the National Cryptologic Museum, Fort George G. Meade MD.     

Vigenère scores for malware detection

Previous research has applied classic cryptanalytic techniques to the malware detection problem. Specifically, scores that are based on simple substitution cipher cryptanalysis have been considered. In this research, we analyze two malware scoring techniques based on the classic Vigenère cipher. Our first approach relies only on the index of coincidence (IC), which is used for example, to determine the length of the keyword in a Vigenère ciphertext. To compute the IC, we consider both the Kasisky Test and Friedman’s Test. We also consider a score based on a more complete cryptanalysis of a Vigenère cipher, where the IC calculation is the first step. We find that both of these scores outperform comparable malware scores in selected cases.     

对一个混沌伪随机序列发生器的已知明文攻击

伪随机序列发生器和基于它设计的混沌流密码的安全性都具有明显的信息泄漏规律,据此提出对二者的已知明文攻击和相关密钥攻击,证明了它们都是不安全的。在主频为2.5GHz的Pentium 4 PC机上,对密钥规模为64bits伪随机数发生器的已知明文攻击,平均攻击时间为48s,成功率为0.75;而应用相关密钥攻击方法,实现对具有64bits密钥的伪随机数发生器的攻击,平均需要39s,成功率为0.99,实现对密钥规模为128bits的混沌流密码的攻击,平均需要为2min7s,成功率为0.95。     

Aligning JN-25 messages in depth using weights when the code groups scan

By the end of 1943, US Navy mathematician/codebreaker Marshall Hall Jr. had developed a system of statistical weights to align JN-25 messages in depth. Although then-current methods of aligning JN-25 messages in depth were working satisfactorily, Hall developed his method “just in case.” On 1 December 1943, the Japanese changed the method of numbering the lines and columns of additives on pages of the JN-25 additive book, and Hall’s weights, which had been developed “just in case,” were needed immediately. This paper discusses both the mathematical idea that was the foundation of Hall’s weights and the construction of the weights. It also explores the navy’s use of the weights as well as their use at Bletchley Park. At the same time, the navy was exploring the use of two other systems of weights to align JN-25 messages in depth, and those systems of weights are also described.     

Physical-layer security analysis of PSK quantum-noise randomized cipher in optically amplified links

The quantitative security of quantum-noise randomized cipher (QNRC) in optically amplified links is analyzed from the perspective of physical-layer advantage. Establishing the wire-tap channel models for both key and data, we derive the general expressions of secrecy capacities for the key against ciphertext-only attack and known-plaintext attack, and that for the data, which serve as the basic performance metrics. Further, the maximal achievable secrecy rate of the system is proposed, under which secrecy of both the key and data is guaranteed. Based on the same framework, the secrecy capacities of various cases can be assessed and compared. The results indicate perfect secrecy is potentially achievable for data transmission, and an elementary principle of setting proper number of photons and bases is given to ensure the maximal data secrecy capacity. But the key security is asymptotically perfect, which tends to be the main constraint of systemic maximal secrecy rate. Moreover, by adopting cascaded optical amplification, QNRC can realize long-haul transmission with secure rate up to Gb/s, which is orders of magnitude higher than the perfect secrecy rates of other encryption systems.     

On the Possibility of Quantum Informational Structural Realism

In The Philosophy of Information, Luciano Floridi presents an ontological theory of Being qua Being, which he calls “Informational Structural Realism”, a theory which applies, he says, to every possible world. He identifies primordial information (“dedomena”) as the foundation of any structure in any possible world. The present essay examines Floridi’s defense of that theory, as well as his refutation of “Digital Ontology” (which some people might confuse with his own). Then, using Floridi’s ontology as a starting point, the present essay adds quantum features to dedomena, yielding an ontological theory for our own universe, Quantum Informational Structural Realism, which provides a metaphysical interpretation of key quantum phenomena, and diminishes the “weirdness” or “spookiness” of quantum mechanics.     

混沌序列密码算法OCMLE的分析

对Wang Shihong的“Chaos-based secure communication in a large community”一文提出的混沌序列密码算法进行了分析,发现该加密算法产生的加密乱数序列的前若干值对密钥低位比特的变化不敏感。据此利用已知明文攻击,对该算法提出了分割攻击方案,并分析了该攻击方案的成功率和计算复杂性。针对该加密算法存在的弱点给出了可能的改进措施,并证明了其有效性。     

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.