Publicerad: 2019-06-12
ISBN: 978-91-7685-087-9
ISSN: 1650-3686 (tryckt), 1650-3740 (online)
The SIGABA is an electromechanical encryption device used by the US during WWII and in the 1950s. Also known as ECM Mark II, Converter M-134, as well as CSP-888/889, the SIGABA was considered highly secure, and was employed for strategic communications, such as between Churchill and Roosevelt. The SIGABA encrypts and decrypts with a set of five rotors, and implements irregular stepping, with two additional sets of rotors generating a pseudorandom stepping sequence. Its full keyspace, as used during WWII, was in the order of 295 ·6 . It is believed that the German codebreaking services were not able to make any inroads into the cryptanalysis of SI GABA (Mucklow, 2015; Budiansky, 2000; Kelley, 2001).
The most efficient attack on SIGABA published so far is a known-plaintext attack that requires at least 286·7 steps.1 Although it is more efficient than an exhaustive search, it is not practical, even with modem computing (Stamp and Chan, 2007; Stamp and Low, 2007).
In this paper, the author presents a novel meet-in-the-middle (MITM) known-plaintext attack. This attack requires 260·2 steps and less than 100 GB RAM, and it is feasible with modem technology. It takes advantage of a weakness in the design of SI GABA. With this attack, the author solved a MysteryTwister C3 (MCT3) Level III challenge (Stamp, 2010). The author also presents a series of new challenges, which will also appear in MTC3. 1To date, no ciphertext-only attack has been proposed, except for an attack that requires multiple messages in depth (Savard and Pekelney, 1999).
This paper is structured as follows: In Section 1, the SIGABA encryption machine is described, including a functional description and an analysis of its keyspace. In Section 2, prior attacks on SIGABA are surveyed, and a novel MITM known-plaintext attack is presented, including an analysis of its workfactor, and how it was used to solve MysteryTwister C3 (MCT3) challenges (Stamp, 2010). In Section 3 and in the Appendix, new challenges are presented, as well as the reference code for a SIGABA simulator used to create those challenges.
SIGABA
cryptanalysis
cipher machines
meet-in-the-middle attack
known-plaintext attack
WWII
Stephen Budiansky. 2000. Battle of wits: the complete story of codebreaking in World War II. Simon and Schuster.
Whitfield Diffie and Martin E Hellman. 1977. Exhaustive cryptanalysis of the NBS data encryption standard. Computer, 10(6):74-84.
John Gilmore. 1998. Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design. OReilly.
Stephen J. Kelley. 2001. Big Machines: Cipher Machines of World War II.
Michael Lee. 2003. Cryptanalysis of the SIGABA, Master’s Thesis. University of California, Santa Barbara.
Timothy Jones Mucklow. 2015. The SIGABA/ECM II Cipher Machine: "a Beautiful Idea". National Security Agency, Center for Cryptologic History.
Richard S. Pekelney. 1998. ECMApp – Emulation of ECM Mark II. https: //maritime. org/tech/ecmapp.txt, [Accessed: January, 18th, 2019].
John J. G. Savard and Richard S. Pekelney. 1999. The ECM Mark II: Design, History, and Cryptology. Cryptologia, 23(3):211-228.
Mark Stamp and Wing On Chan. 2007. SIGABA: Cryptanalysis of the Full Keyspace. Cryptologia, 31(3):201-222.
Mark Stamp and Richard M. Low. 2007. Applied Cryptanalysis: Breaking Ciphers in the Real World. John Wiley & Sons.
Mark Stamp. 2010. MysteryTwister C3 (MTC3), SIGABA Part 2 (Level III). https://www.mysterytwisterc3.org/en/challenges/level-iii/sigaba-part-2, [Accessed: December, 16th, 2018].
Geoff Sullivan. 2002a. CSG Sigaba (ECM Mark II) Simulator for Windows. http://cryptocellar.org/simula/sigaba/index.html, [Accessed: January, 18th, 2019].
Geoff Sullivan. 2002b. The ECM Mark II: some observations on the rotor stepping. Cryptologia, 26(2):97-100.
