Cipher Type Detection

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1769–1773, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Cipher Type Detection Malte Nuhn Human Language Technology and Pattern Recognition Group Computer Science Department RWTH Aachen University nuhn@cs.rwth-aachen.de Kevin Knight Information Sciences Institute University of Southern California knight@isi.edu Abstract Manual analysis and decryption of enci- phered documents is a tedious and error prone work. Often—even after spend- ing large amounts of time on a par- ticular cipher—no decipherment can be found. Automating the decryption of var- ious types of ciphers makes it possible to sift through the large number of en- crypted messages found in libraries and archives, and to focus human effort only on a small but potentially interesting sub- set of them. In this work, we train a clas- sifier that is able to predict which enci- pherment method has been used to gener- ate a given ciphertext. We are able to dis- tinguish 50 different cipher types (speci- fied by the American Cryptogram Associ- ation) with an accuracy of 58.5%. This is a 11.2% absolute improvement over the best previously published classifier. 1 Introduction Libraries and archives contain a large number of encrypted messages created throughout the cen- turies using various encryption methods. For the great majority of the ciphers an analysis has not yet been conducted, simply because it takes too much time to analyze each cipher individually, or because it is too hard to decipher them. Automatic methods for analyzing and classifying given ci- phers makes it possible to sift interesting messages and by that focus the limited amount of human re- sources to a promising subset of ciphers. For specific types of ciphers, there exist au- tomated tools to decipher encrypted messages. However, the publicly available tools often de- pend on a more or less educated guess which type of encipherment has been used. Furthermore, they often still need human interaction and are only restricted to analyzing very few types of ci- phers. In practice however, there are many differ- ent types of ciphers which we would like to an- alyze in a fully automatic fashion: Bauer (2010) gives a good overview over historical methods that have been used to encipher messages in the past. Similarly, the American Cryptogram Association (ACA) specifies a set of 56 different methods for enciphering a given plaintext: Each encipherment method Mi can be seen as a function that transforms a given plaintext into a ciphertext using a given key, or short: cipher = Mi(plain, key) When analyzing an unknown ciphertext, we are interested in the original plaintext that was used to generate the ciphertext, i.e. the opposite direction: plain = M−1 i (cipher, key) Obtaining the plaintext from an enciphered mes- sage is a difficult problem. We assume that the decipherment of a message can be separated into solving three different subproblems: 1. Find the encipherment method Mi that was used to create the cipher cipher → Mi . 2. Find the …

Content truncated to 500 words