Cryptanalysis of Chaocipher and solution of Exhibit 6. Issue 6 (1st November 2016) - Lasry, George; Rubin, Moshe; Kopal, Nils; Wacker, Arno
ABSTRACT: 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.