S olving H istorical D ictionary C odes with a N eural L anguage M odel (2020)

Abstract: We solve difficult word-based substitution codes by constructing a decoding lattice and searching that lattice with a neural language model. We apply our method to a set of enciphered letters exchanged between US Army General James Wilkinson and agents of the Spanish Crown in the late 1700s and early 1800s, obtained from the US Library of Congress. We are able to decipher 75.1% of the cipher-word tokens correctly.

## introduction cryptography has been used since antiquity to encode important secrets. there are many unsolved ciphers of historical interest, residing in national libraries, private archives, and recent corpora collection projects (megyesi et al., 2019; pettersson and megyesi, 2019). solving classical ciphers with automatic methods is a needed step in analyzing these materials. in this work, we are concerned with automatic algorithms for solving a historically-common type of book code, in which word tokens are systematically replaced with numerical codes. encoding and decoding are done with reference to a dictionary possessed by both sender and recipient. while this type of code is common, automatic decipherment algorithms do not yet exist. the contributions of our work are: table-based key book-based key cipher caesar cipher beale cipher (character) simple substitution zodiac 408 copiale cipher code rossignols' mexico-nauen code (word) grand chiffre scovell code wilkinson code (this work) 2 related work figure 1 gives a simplified typology of classical, substitution-based cryptosystems. @xcite table-based ciphers involve character-based substitutions. the substitution may take the form of a simple offset, as in the caesar substitution system, e.g., (@xmath0, (@xmath1, (@xmath2, etc. the caesar cipher can be easily solved by algorithm, since there are only 26 offsets to check. the algorithm need only be able to recognize which of the 26 candidate plaintexts form good english. since 25 of the candidates will be gibberish, even the simplest language model will suffice. a simple substitution cipher uses a substitution table built by randomly permuting the alphabet. since there are 26! ≈ 4 • 10 26 possible tables, algorithmic decipherment is more difficult. however, there are many successful algorithms, e.g., (hart, 1994; knight and yamada, 1999; hauer et al., 2014; olson, 2007; ravi and knight, 2008; corlett and penn, 2010). many of these systems 1 our typology is geared toward explaining our contribution in the context of related systems. for a fuller picture of classical cryptology, the reader is directly to kahn (1996) and singh (2000). for example, we do not discuss here systems in which a substitution key evolves during the encoding process, such as the vigenère cipher or the german enigma machine. more sophisticated ciphers use homophonic substitution, in which plaintext characters are replaced non-deterministically. by applying high nondeterminism to frequent characters, the cryptographer can flatten out ciphertext character frequencies. homophonic ciphers occur frequently in historical collections. the copiale cipher (knight et al., 2011) is a well-known example from a german secret society in the 1700s. these ciphers can also be attacked successfully by algorithm. for example, the homophonic zodiac 408 cipher can be solved with em with restarts (berg-kirkpatrick and klein, 2013), bayesian sampling (ravi and knight, 2011), or beam search (nuhn et al., 2014) (all with n-gram character language models). kambhatla et al. (2018) employ a more powerful character-based neural language model to break short ciphers more accurately. in the present work, we use a word-based neural language model. book-based ciphers increase homophony, and also avoid physical substitution tables that can be stolen or prove incriminating. in a book-based cipher, sender and recipient verbally agree up front on an innocuous-looking shared document (the "book"), such as the us declaration of independence, or a specific edition of the novel moby dick. when enciphering a plaintext letter token like f, the sender selects a random letter f from the shared document-if it is the 712th character in the document, the plaintext f might be enciphered as 712. the next plaintext f might be enciphered differently. nuhn et al. (2014) solve one of the most wellknown book ciphers, part two of the beale cipher (king, 1993). surprisingly, they treat the cipher as a regular homophonic cipher, using the same beam-search algorithm as for the table-based zodiac 408 cipher, together with an 8-gram character language model. one might imagine exploiting the fact that the book is itself written in en-glish, so that if ciphertext unit 712 is known to be f, then ciphertext unit 713 is probably not h, as fh is unlikely to appear in the book. nuhn et al. (2014)'s simple, effective algorithm ignores such constraints. other methods have been proposed for attacking book ciphers, such as crib dragging churchhouse (2002). codes, in contrast to ciphers, make substitutions at the whole-word level. @xcite a large proportion of the encrypted material in megyesi et al. (2019) consists of table-based codes. a famous example is antoine rossignol's grand chiffre, used during the reign of louis xiv. the sender and receiver each own copies of huge speciallyprepared tables that map words onto numbers (e.g., @xmath3. if the enciphering tables are kept secret, this type of code is very hard to break. one might guess that the most frequent cipher token stands for the word the, but it quickly becomes challenging to decide which number means practice and which means paragon. even so, dou and knight (2012) take on the task of automatically deciphering newswire encrypted with an arbitrary word-based substitution code, employing a slice-sampling bayesian technique. given a huge ciphertext of ∼50,000 words, they can decipher ∼50% of those tokens correctly. from one billion ciphertext tokens, they recover over 90% of the word tokens. however, this method is clearly inapplicable in the world of short-cipher correspondence. in the present work, we consider book-based codes. instead of using specially-prepared tables, the sender and receiver verbally agree to use an already-existing book as a key. because it may be difficult to find a word like paragon in a novel like moby dick, the sender and receiver often agree on a shared pocket dictionary, which has nearly all the words. if paragon were the 10,439th word in the dictionary, the sender might encode it as 10439. such codes have been popular throughout history, employed for example by george scovell during the napoleonic wars (urban, 2002), and by john jay during the us revolutionary war (blackwood, 2009). they were used as late as world war ii, when german diplomats employed the langenscheidt's spanish-german pocket dictionary as a key to communicate between the cities of chapultepec, mexico and nauen, germany (nsa, 2011). in that case, the us coast guard intercepted messages and was able to make a bit of headway in deciphering them, but the real breakthrough came only when they obtained the applicable dictionary (key). unfortunately, there appear to be no automatic algorithms for solving book-based codes without the key. @xcite according to dunin and schmeh (2020): "so far, there are no computer programs for solving codes and nomenclators available. this may change, but in the time being, solving a code or nomenclator message is mainly a matter of human intelligence, not computer intelligence." in this paper, we develop an algorithm for automatically attacking book-based codes, and we apply it to a corpus of historically-important codes from the late 1700s. ## wilkinson letters our cipher corpus consists of letters to and from us general james wilkinson, who first served as a young officer in the us revolutionary war. he subsequently served as senior officer of the us army (appointed by george washington) and first governor of the louisiana territory (appointed by thomas jefferson). wilkinson also figured in the aaron burr conspiracy (isenberg, 2008). long after his death, letters in a cuban archive revealed the famous wilkinson to be an agent of the spanish crown during virtually his entire service, and his reputation collapsed (linklater, 2009). ## encryption method as is frequent in book codes, there are two types of substitutions. some plaintext words are enciphered using a large shared table that maps words onto numbers (table-based code). other words are mapped with a shared dictionary (book-based code). despite serious efforts, we have not been able to obtain the dictionary used in these ciphers. in our transcription, we mark entries from the table portion with a caret over a single number, e.g., [123]ˆ. before [160]ˆ, the table seems to contain a list of people or place names; between [160]ˆ("a") and [1218]ˆ("your"), a list of common words in alphabetic order; and finally more common words. the last block was likely added after the initial table was constructed, suggesting that the table was used to avoid having to look up common words in the dictionary. the ciphertext for the dictionary code has two numbers that mark a word's dictionary page and row number, respectively, plus one or two bars over the second number indicating the page column. for example, 123.[4]= refers to the fourth row of the second column of the 123rd page in the dictionary. from the distribution of cipher tokens, the dictionary is about 780 pages long with 29 rows per column, totaling about 45,000 words. the cipher usually does not contain regular inflected forms of words, though inflections are sometimes marked with a superscript (e.g., +ing ). numbers and some words are left in plaintext. long horizontal lines mark the ends of sentences, but other punctuation is not marked. ## automatic decryption method as the corpus includes a handful of deciphered pages, we employ a known-plaintext attack (kahn, 1996). we first extract a small wordbank of known mappings, shown in figure 3 . next, we apply the wordbank to our held-out evaluation ciphertext. we find that 40.8% of word tokens can be deciphered, mainly common words. after this step, we render a ciphertext as: by ? ? from ? i have not ? ? to ? he ? the service that i [...] this is not yet a useful result. however, the wordbank also helps us to recover the rest of the plaintext. since both the table and dictionary are in alphabetical order, we use the wordbank to constrain the decipherment of unknown words. for example, given cipher word [163]ˆ, we know from figure 3 that its plaintext must lie somewhere between the two anchor-words [160]( which stands for "a") and [172]ˆ(which stands for "and"). moreover, it is likely to be closer to "a" than "and". repeating this for every cipher word in an undeciphered document, we construct a word lattice of all possible decipherments, shown in figure 4 . our goal is then to search for the most fluent path through this lattice. following are the details of our method: anchors. to propose candidate words between two anchors, we use a modern lemma-based dictionary with 20,770 entries. @xcite in this dictionary, for example, there are 1573 words between "attachment" and "bearer". probabilities. we assign a probability to each candidate based on its distance from the ideal candidate. for example, in the table code, [163]ˆis 30% of the way from [160]ˆto [172]ˆ(figure 5 ), so our ideal candidate decipherment of [172]ˆwill be 30% of the way between "a" and "and" in our modern dictionary. to apply this method to the dictionary code, we convert each cipher word's 5 www.manythings.org/vocabulary/lists/l (core esl) page/column/row to a single number n (the "index" in figure 3 ), which estimates that the cipher word corresponds to the nth word in the shared dictionary. we use a beta distribution for assigning probabilities to candidate words, because the domain is bounded. we parameterize the distribution b (x; m, β) with mode m and sharpness parameter β=5. this is related to the standard parameterization, b(x; α, β), by: the sample space (0 to 1) is divided equally between the m words in the modern dictionary, so the i th word gets probability: in our example, because [163]ˆis 30% of the way from [160]ˆto [172]ˆ, we have @xmath4.3. there are @xmath5, so the @xmath6, gets probability 0.00231. inflections. we expand our lattice to include inflected forms of words (e.g., "find" → "find", "found", "finding"). we generate inflections with the pattern library (de smedt and daelemans, 2012). some words are generated more than once, e.g., "found" is both a base verb and the past tense of "find". pattern inflects some uncommon words incorrectly, but such inflections are heavily penalized in the best-path step. inflections divide the probability of the original word equally. ## evaluation to evaluate, we hold out one deciphered document from wordbanking. some plaintext in that document is unreadable or damaged, so decryptions are added when known from the wordbank or obvious from context. the maximum we could get from further improvements to path-extraction is 91.3%, as 8.7% of correct answers are outside the lattice. this is due to unreadable plaintext, limitation of our modern dictionary, use of proper names [1]ˆto [159]ˆ, transcription errors, etc. figure 6 shows a portion of our solution versus the gold standard. for tokens where our system output does not match the original plaintext, we asked an outside annotator to indicate whether our model captures the same meaning. for example, when our system outputs "i am much sorry" instead of "i am very sorry," the annotator marks all four words as same-meaning. under this looser criterion, accuracy rises from 73.0% to 80.1%. we also decipher a wilkinson ciphertext letter for which we have no plaintext. transcription is less accurate, as we cannot confirm it using decipherment. the letter also includes phrases in plaintext french, which we translate to english before adding them to the lattice. despite these challenges, the model still outputs relatively fluent text, including, for example: ". . . as may tend most powerfully and most directly to dissolve the whole america of the first states from the east and to cease the intercourse of the west." this passage is consistent with wilkinson's plan to seek independence for parts of america. ## additional methods we experiment with three additional decipherment methods. weighted scoring. when scoring paths, we sum log probabilities from gpt and the lattice transitions, with the two sources equally weighted. this turns out to be optimal. iterative self-learning. we apply iterative selflearning to improve our decipherment. after extracting the best path using beam search, we take the words with the smallest increases in perplexity on the lattice and language models, and we add them to the wordbank. the new wordbank provides tighter anchor points. we then construct a new lattice (using the expanded wordbank), search it, and repeat. this further improves decoding accuracy to 75.1 (+1.9 for @xmath10. ## synthetic data experiments we next experiment with synthetic data to test the data efficiency of our method. to create arbitrary amounts of parallel plaintext-ciphertext data, we encipher a book from project gutenberg, foot_7 using a different machine readable dictionary. @xcite we build wordbanks from parallel documents and use them to decipher a separately-enciphered book by the same author. @xcite the results are shown in ## conclusion and future work in this work, we show that it is possible to decipher a book-based cipher, using a known-plaintext attack and a neural english language model. we apply our method to letters written to and from us general james wilkinson, and we recover 75.1% of the word tokens correctly. we believe word-based neural language models are a powerful tool for decrypting classical codes and ciphers. because they have much lower perplexities than widely-used n-gram models, they can distinguish between candidate plaintexts that resemble english at a distance, versus candidate plaintexts that are grammatical, sensible, and relevant to the historical context. ciphertext gold wordbank only unigram baseline our method [229]ˆ+ing being be be being [186]ˆat at at at [1049]ˆsuch such such such [160]ˆa a a a 212.[20]= distance distant distance [570]ˆfrom from from from [90]ˆnorth carolina america america america [172]ˆand and and and 286.[14]= for for for for [509]ˆfear father fear [804]ˆof of of of 446.[1]-+ing missing mistress missing [1218]ˆyour your your your 294.[20]= garrison from friend [1084]ˆthere therefore therefore 286.[14]= for for for for [1078]ˆthe the the the 153.[5]-conveyance could convenience [804]ˆof of of of 678.[6]= this this this this [664]ˆi i i [177]ˆam any am 467.[24]-+d obliged of obliged [1106]ˆto to to to [1206]ˆwrite write written write [1106]ˆto to to to [1216]ˆyou you you you [807]ˆin on in in [160]ˆa a a a 349.[1]= hurry i hurry 572.[5]-+ing resuming said requiring 251.[6]= every every every every [852]ˆpoint people precaution