Can Sequence-to-Sequence Models Crack Substitution Ciphers? (2021)

Abstract: Decipherment of historical ciphers is a challenging problem. The language of the target plaintext might be unknown, and ciphertext 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, assuming 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 ciphers and show that our proposed method can decipher text without explicit language identification while still being robust to noise.

## introduction libraries and archives have many enciphered documents from the early modern period. example documents include encrypted letters, diplomatic correspondences, and books from secret societies (figure 1 ). previous work has made historical cipher collections available for researchers @xcite . decipherment of classical ciphers is an essential step to reveal the contents of those historical documents. in this work, we focus on solving 1:1 substitution ciphers. current state-of-the-art methods use beam search and a neural language model to score candidate plaintext hypotheses for a given cipher @xcite . however, this approach assumes that the target plaintext language is known. other work that both identifies language and deciphers relies on a brute-force guess-and-check strategy @xcite . 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: ## 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 decoded 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 language, and the key are all unknown. in this paper, we focus on solving 1:1 substitution ciphers. we follow @xcite and @xcite and use machine translation notation to formulate our problem. we denote the ciphertext as f n 1 = f 1 . . . f j . . . f n and the plaintext as e m the decipherment goal is to recover the plaintext given the ciphertext. ## decipherment model inspired by character-level neural machine translation (nmt), we view decipherment as a sequenceto-sequence translation task. the motivation behind using a sequence-to-sequence model is: we would like the model to have the ability to recover from that noise by inserting, deleting, or substituting characters while generating plaintext. sequence-to-sequence models seem to be good candidates for this task. ## data for training, we create 1:1 substitution ciphers for 14 languages using random keys. for english, we use english gigaword @xcite . we scrape historical text from project gutenberg for 13 other languages, namely: catalan, danish, dutch, finnish, french, german, hungarian, italian, latin, norwegian, portuguese, spanish, and swedish. 4 ## experimental evaluation to make our experiments comparable to previous work @xcite we create test ciphers from the english wikipedia article about history. 5 we use this text to create ciphers of length 16, 32, 64, 128, and 256 characters. we generate 50 ciphers for each length. we follow the same pre-processing steps to create training data. we carry out four sets of experiments to study the effect of cipher length, space encipherment/removal, unknown plaintext language, and transcription noise. finally, we test our models on a real historical cipher, whose plaintext language was not known until recently. as an evaluation metric, we follow previous literature @xcite and use symbol error rate (ser). ser is the fraction of incorrect symbols in the deciphered text. for space restoration experiments (section 5.2), we use translation edit rate (ter) @xcite , but on the character level. we define character-level ter as: ## anagram decryption to further test the capacity of our model, we experiment with a special type of noise. in this section, we address the challenging problem of solving substitution ciphers in which letters within each word have been randomly shuffled. anagramming is a technique that can be used to further disguise substitution ciphers by permuting characters. various theories about the mysterious voynich manuscript, for example, suggest that some anagramming scheme was used to encode the manuscript @xcite . @xcite propose a two-step approach to solve this problem. first, they use their 1:1 substitution cipher solver @xcite to decipher the text. the solver is based on tree search for the key, guided by character-level and word-level n-gram language models. they adapt the solver by relaxing the letter order constraint in the key mutation component of the solver. they then re-arrange the resulting deciphered characters using a word trigram language model. we try a one-step, end-to-end anagram decryption model. in our sequence-to-sequence formulation, randomly shuffled characters can confuse the training. we thus represent an input cipher as a bag of frequency-mapped characters, nominally presented in frequency rank order (figure 5 ). we use the english gigaword dataset to train a 256 character model on the sorted frequencies and test on the aforementioned test set of 50 ciphers (after applying random anagramming). following hauer and kondrak (2016), we report word accuracy on this task. our model achieves a word accuracy of 95.82% on the 50 wikipedia ciphers. @xcite report results on a test set of 10 long ciphers extracted from 10 wikipedia articles about art, earth, europe, film, history, language, music, science, technology, and wikipedia. ciphers have an average length of 522 characters. they use english europarl to train their language models @xcite . to get comparable results, we trained a model on ciphers of length 525 created from the english side of the spanish-english europarl dataset. our model achieved a word accuracy of 96.05% on hauer and kondrak's test set. training on english gigaword gave a word accuracy of 97.16%, comparable to the 97.72% word accuracy reported by @xcite . this shows that our simple model can crack randomly anagrammed ciphers, which hopefully inspires future work on other cipher types. ## related work deciphering substitution ciphers is a well-studied problem in the natural language processing community, e.g., @xcite @xcite @xcite @xcite . many of the recent proposed methods search for the substitution table (i.e. cipher key) that leads to a likely target plaintext according to a character n-gram language model. the current state-ofthe-art method uses beam search and a neural language model to score candidate plaintext hypotheses from the search space for each cipher, along with a frequency matching heuristic incorporated into the scoring function @xcite . this method, which is comparable in results to our method on longer ciphers and slightly weaker on shorter ciphers, assumes prior knowledge of the target plaintext language. our method, by contrast, can solve substitution ciphers from different languages without explicit language identification. recent research has looked at applying other neural models to different decipherment problems. @xcite find an lstm model can learn the decryption function of polyalphabetic substitution ciphers when trained on a concatenation @xmath0. our work looks at a different problem. we target a ciphertext-only-attack for short 1:1 substitution ciphers. @xcite propose ci-phergan, which uses a generative adversarial network to find a mapping between the character embedding distributions of plaintext and ciphertext. this method assumes the availability of plenty of ciphertext. our method, by contrast, does not require a large amount of ciphertext. in fact, all of our experiments were evaluated on ciphers of 256 characters or shorter. early work on language identification from ciphertext uses the noisy-channel decipherment model @xcite . specifically, the expectation-maximization algorithm is used to learn mapping probabilities, guided by a pretrained n-gram language model. this decipherment process is repeated for all candidate languages. the resulting decipherments are ranked based on the probability of the ciphertext using the learned model, requiring a brute-force guess-and-check approach that does not scale well as more languages are considered. @xcite use techniques similar to ours, incorporating character (1) t h e _ i n v e n t i o n _ o f _ w r i t i n g _ s y s t e m s (2) j c z _ m r b z r j m k r _ k f _ w u m j m r e _ a o a j z g a (3) c j z _ k z m r b r j m r _ f k _ e w u j m m r _ z g o a j a a (4) 6 0 3 _ 5 3 1 2 7 2 0 1 2 _ 8 5 _ 11 9 10 0 1 1 2 _ 3 13 12 4 0 4 4 (5) 0 3 6 _ 0 1 1 2 2 2 3 5 7 _ 5 8 _ 0 1 1 2 9 10 11 _ 0 3 4 4 4 12 13 (6) t h e _ i n v e n t i o n _ o f _ b r i t a i n _ s y s t e m s figure 5 : example anagram encryption and decryption process: (1) original plaintext (2) after applying a 1:1 substitution key (3) after anagramming (this is the ciphertext) (4) after frequency encoding (5) after sorting frequencies. this is fed to transformer (6) system output (errors are highlighted). ## conclusion and future work in this work, we present an end-to-end decipherment model that is capable of solving simple substitution ciphers without the need for explicit language identification. we use frequency analysis to make it possible to train a multilingual transformer model for decipherment. our method is able to decipher 700 ciphers from 14 different languages with less than 1% ser. we apply our method on the borg cipher and achieve 5.47% ser using the multilingual model and 3.91% ser using a monolingual latin model. in addition, our experiments show that these models are robust to different types of noise, and can even recover from many of them. to the best of our knowledge, this is the first application of sequence-to-sequence neural models for decipherment. we hope that this work drives more research in the application of contextual neural models to the decipherment problem. it would be interesting to develop other techniques for solving more complex ciphers, e.g. homophonic and polyalphabetic ciphers. 17-c-9116. the views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the odni, iarpa, or the u.s. government. the u.s. government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation thereon.