Article | Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium | A Practical Meet-in-the-Middle Attack on SIGABA Linköping University Electronic Press Conference Proceedings
Göm menyn

Title:
A Practical Meet-in-the-Middle Attack on SIGABA
Author:
George Lasry: The CrypTool Team
Download:
Full text (pdf)
Year:
2019
Conference:
Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium
Issue:
158
Article no.:
005
Pages:
41-49
No. of pages:
9
Publication type:
Abstract and Fulltext
Published:
2019-06-12
ISBN:
978-91-7685-087-9
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Series:
NEALT Proceedings Series
Publisher:
Linköping University Electronic Press, Linköpings universitet


Export in BibTex, RIS or text

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.



Keywords: SIGABA cryptanalysis cipher machines meet-in-the-middle attack known-plaintext attack WWII

Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium

Author:
George Lasry
Title:
A Practical Meet-in-the-Middle Attack on SIGABA
References:

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.

Proceedings of the 2nd International Conference on Historical Cryptology, HistoCrypt 2019, June 23-26, 2019, Mons, Belgium

Author:
George Lasry
Title:
A Practical Meet-in-the-Middle Attack on SIGABA
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment


Responsible for this page: Peter Berkesand
Last updated: 2019-10-02