Can Sequence-to-Sequence Models Crack Substitution Ciphers?

Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, pages 7226–7235 August 1–6, 2021. ©2021 Association for Computational Linguistics 7226 Can Sequence-to-Sequence Models Crack Substitution Ciphers? Nada Aldarrab and Jonathan May University of Southern California Information Sciences Institute {aldarrab,jonmay}@isi.edu Abstract Decipherment of historical ciphers is a chal- lenging problem. The language of the tar- get plaintext might be unknown, and cipher- text can have a lot of noise. State-of-the-art decipherment methods use beam search and a neural language model to score candidate plaintext hypotheses for a given cipher, as- suming the plaintext language is known. We propose an end-to-end multilingual model for solving simple substitution ciphers. We test our model on synthetic and real historical ci- phers and show that our proposed method can decipher text without explicit language identi- fication while still being robust to noise. 1 Introduction Libraries and archives have many enciphered doc- uments from the early modern period. Example documents include encrypted letters, diplomatic correspondences, and books from secret societies (Figure 1). Previous work has made historical ci- pher collections available for researchers (Petters- son and Megyesi, 2019; Megyesi et al., 2020). De- cipherment of classical ciphers is an essential step to reveal the contents of those historical documents. In this work, we focus on solving 1:1 substitu- tion ciphers. Current state-of-the-art methods use beam search and a neural language model to score candidate plaintext hypotheses for a given cipher (Kambhatla et al., 2018). However, this approach assumes that the target plaintext language is known. Other work that both identifies language and deci- phers relies on a brute-force guess-and-check strat- egy (Knight et al., 2006; Hauer and Kondrak, 2016). We ask: Can we build an end-to-end model that deciphers directly without relying on a separate language ID step? The contributions of our work are: • We propose an end-to-end multilingual de- cipherment model that can solve 1:1 substi- tution ciphers without explicit plaintext lan- guage identification, which we demonstrate on ciphers of 14 different languages. • We conduct extensive testing of the proposed method in different realistic decipherment conditions; different cipher lengths, no-space ciphers, and ciphers with noise, and demon- strate that our model is robust to these condi- tions. • We apply our model on synthetic ciphers as well as on the Borg cipher, a real historical cipher.1 We show that our multilingual model can crack the Borg cipher using the first 256 characters of the cipher. 2 The Decipherment Problem Decipherment conditions vary from one cipher to another. For example, some cleartext might be found along with the encrypted text, which gives a hint to the plaintext language of the cipher. In other cases, called known-plaintext attacks, some de- coded material is found, which can be exploited to crack the rest of the encoded script. However, in a ciphertext-only attack, the focus of this paper, the cryptanalyst only has access to the ciphertext. This means that the encipherment method, the plaintext …

Content truncated to 500 words