Hidden Markov Models for Vigenere Cryptanalysis - Techniques and Tests

Hidden Markov Models for Vigenere Cryptanalysis Mark Stamp, Fabio Di Troia, Miles Stamp, and Jasper Huang HMM for Vigenere Cryptanalysis 1

Classic Ciphers (Again) Simple substitution is monoalphabetic substitution o Also true of homophonic substitution Vigenere cipher is elementary example of polyalphabetic cipher Can we break a polyalphabetic cipher using HMM? o Let s consider a Vigenere cipher HMM for Vigenere Cryptanalysis 2

Vigenere Cipher Vigenere cipher is a series of shifts Shifts are indexed by a keyword For example, suppose keyword is CAT To encrypt attackatdawn Ciphertext is ctmccdctwcwg HMM for Vigenere Cryptanalysis 3

Classic Cryptanalysis of Vigenere Cipher Hard part is to find length of keyword o Once keyword length is known, just a series of shift ciphers How to determine keyword length? o Classic Friedman test or Kasiski test We discuss Friedman test here Friedman test is based on index of coincidence (IC) HMM for Vigenere Cryptanalysis 4

Friedman Test IC measures repeat rate Let nabe number of a , nbnumber of b , , nzthe number of z , and N = na+...+nz Then repeat rate or IC given by o Where c is num of symbols, i.e., c = 26 HMM for Vigenere Cryptanalysis 5

Friedman Test For generic English text, we have While for random text The longer the Vigenere keyword, the closer ciphertext is to random text o In the sense of the repeat rate... HMM for Vigenere Cryptanalysis 6

Friedman Test Suppose the keyword is of length L Probability of selecting 2 letters from same shift: Probability of selecting 2 letters from different shifts: Therefore, ciphertext repeat rate is HMM for Vigenere Cryptanalysis 7

Friedman Test Let c be the IC for a Vigenere cipher o Easily computed from a given ciphertext Again, L is the length of Vigenere key Solve formula at bottom of previous page for L gives approx keyword length Assuming typical English plaintext HMM for Vigenere Cryptanalysis 8

Generative Adversarial Network (GAN) Recent work used generative adversarial network (GAN) to break Vigenere cipher o GAN is a type of neural network GAN results did not seem impressive o Requires lots of data, results not clear o Claimed advantage is that GAN can handle large vocabulary of up to 200 symbols Large vocabulary makes little sense here o Classic techniques work better HMM for Vigenere Cryptanalysis 9

HMM Let s try HMM on Vigenere cipher!!! What do we expect will happen? o How might results compare to simple substitution? o How will results compare to homophonic substitution? o Is it reasonable to think that HMM can deal with polyalphabetic substitution? HMM for Vigenere Cryptanalysis 10

HMM Experiment 1 Keyword CAT (note that length is 3) Try HMM with N = 3, M = 26, T = 1000 Converged A and matrices What does this tell us? HMM for Vigenere Cryptanalysis 11

HMM Experiment 1 Converged B matrix Does this tell us anything useful? HMM for Vigenere Cryptanalysis 12

HMM Experiment 1 For same data, with N = 2 and N = 4 And for N = 6 HMM for Vigenere Cryptanalysis 13

More HMM Experiments Different keyword lengths, 100 random restarts in each case HMM for Vigenere Cryptanalysis 14

Future Work Try HMM on other classic ciphers o Other polyalphabetic ciphers Maybe HMM for WWII ciphers o Enigma, Purple, TypeX, Sigaba, etc. HMM for transposition ciphers??? o This is the Holy Grail o If we can handle transposition ciphers, door is open to interesting Z340 attacks HMM for Vigenere Cryptanalysis 15

References M. Stamp, F. Di Troia, M. Stamp, and J. Huang, Hidden Markov models for Vigenere cryptanalysis, International Conference on Historical Cryptology (HistoCrypt 2018), Uppsala, Sweden, June 18 20, 2018 William F. Friedman, The Index of Coincidence and Its Applications in Cryptography, Aegean Park Press, 1987 HMM for Vigenere Cryptanalysis 16