[PDF] Learning Cryptography by Doing It Wrong: Cryptanalysis of the

View - Download Learning Cryptography by Doing It Wrong: Cryptanalysis of the

Previous PDF

Next PDF

Global Information Assurance Certification Paper

Copyright SANS Institute

Author Retains Full Rights

This paper is taken from the GIAC directory of certified professionals. Reposting is not permited without express written permission.Interested in learning more?

Check out the list of upcoming events offering

"Hacker Tools, Techniques, and Incident Handling (Security 504)" at http://www.giac.org/registration/gcih

Learning Cryptography by Doing It Wrong:

Cryptanalysis of the Vigenère Cipher

GIAC uGCIHi Gold Certification

uutzVr7 gqrqQy krujOe T&rujO.HQ~jXaEVQ u&vjsVr7 WzrjstV#zqr (~XYqre WRDD_e WWRDAe BWLke B(Lw uEEq#tq&7 ,mlm,plf u%str~Et (zqO stu&yjOH EVQ#Xqx j&q~se jt Q~y zqX# tV %qHjO wjtz ~ sjQ#Xqr qx~Q#Xq tV %qttqr uO&qrst~O& jts EVOEq#tsa SV&qrO Ery#tVHr~#zy ~O& Ery#t~O~Xysjs ~rq qxEq#tjVO~XXy EV

Q#Xqxe sV ~ E~sq stu&y

jqsa Rt js OVOxtrjvj~X tV Ery#t~O~Xyzqe V""qrjOH ~ strqtEz HV~X "Vr %qHjOOqrse %ut OVt jQ#Vssj%Xq #rVvj&qs #r~EtjEq V" QuXtj#Xq tqEzOjaeuqs suEz ~s st~tjstjE~X ~O~Xysjse zjstVHr~Qse ~O& RO&qx V" WVjOEj&qOEqa Dt~tjstjE~X #rV#qrtjqs V" "jXqs %q"Vrq ~O& ~"tqr qOEry#tjV

O E~O %q EVQ#~rq& tV szVw

~ttrj%utqs tz~t ~XXVw qOEry#tq& "jXqs tV %q &qtqEtq&a u QqtzV& V" &qtqEt jOH tzq qOEry#tjVO Yqy qEVvqr tzq Yqy "Vr g_LB qOEry#tq& "jXqs wjXX %q &qQVOstr~tq&a MV zqX# tzq rq~&qr "VXXVw tzj s ~O~Xysjse V#qO sVurEq sV"tw~rq wjXX %q #rVvj&q& tz~t #qr"VrQs qOEry#tjVOe &qEry#tjVOe ~O& Ery#t~O~Xysjsa wqsj&qs Xq~rOjOH ~%Vut EX~ssjE~X Ej#zqrs ~O& z~vjOH "uOe wq wjXX rqjO"VrEq tzq j

Q#Vrt~OEq V" #rV#qr

Ej#zqr EzVjEq "Vr tzq QV&qrO RO"VDqE #rV"qssjVO~Xa

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

2 gt -ntroduction Cryptography, the art and science of secret writing (Merriam-Webster, 2017), is a vast and complex topic. Cryptography includes cryptanalysis techniques, the practice of deciphering or decoding encrypted messages (Collins English Dictionary, 2012). Some practical understanding of cryptanalysis techniques is important for cyber security practitioners. While advanced cryptanalysis is difficult to learn without significant time and talent, classical cryptographic ciphers are within reach of the non-professional. Specifically, simple substitution and polyalphabetic ciphers provide an introduction into cryptanalysis and demonstrate the importance of proper implementation. Modern ciphers are significantly more advanced than the classical Vigenère cipher. A study of Vigenère is not an analog to taking on strong ciphers such as Advanced Encryption Standard (AES). The underlying cryptosystem, its mechanisms and therefore appro ach to attack are different (NOVER, 2004). However, Vigenère provides a good opportunity to explore and practice cryptanalysis techniques. Vigenère is non-trivial to cryptanalyze and was once widely considered unbreakable (Norman, 2017). Yet by combining multiple techniques and employing computers, Vigenère can be broken by persistent amateurs. Two tools are provided to allow the reader to follow the examples provided in this paper. One provides encryption and decryption of files using a Vigenère ciph er. The second tool, a frequency analyzer, performs statistical analysis, can determine the Vigenère encryption key length, and decrypt a file given the key. The analysis begins by comparing files before and after encryption. Statistic properties that indicate potentially weak encryption are noted. It will be shown how a Vigenère cipher can be broken if the length of the encryption key i s found. Further investigation will present a method to determine the key length. Finally, the key will be recovered. st kverview Monoalphabetic ciphers pick a key from a single alphabet. A single key is used to encrypt each character of plaintext. This leaves the ciphertext vulnerable to cr yptanalysis via frequency analysis (Daniel Rodriguez-Clark, 2013). A form of these simple substitution ciphers was used

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

3 by the armies of Julius Caesar as early as 50 B.C. (Simmons, 2009). The monoalphabetic cipher with key = 3 is called a "Caesar Cipher" as a result. Polyalphabetic ciphers such as Vigenère use an independent key to encrypt each character of plaintext until the end of the key is reached. At this poin t, the key is reused for the next block of plaintext characters (Math Explorers Club, 2003). The Vigenère cipher, a polyalphabetic cipher, is attributed to Blaise de Vigenère (Simmons, 2009) in 1586 but may have been reinvented multiple times (Norman, 2017). Leon Battista Alberti documented the general polyalphabetic cipher in 1467 although this version did not switch encry ption alphabets with each letter of plaintext (University of Babylon, 2011). Giovan Battista Bellaso is credited with another variant as early as 1564 (Bellaso, 1552). Although Vigenère was considered unbreakable for some time (Simmons, 2009), it was cracked well before computers became available (Singh, 2001). Charles Babbage decrypted a letter enciphered in Vigenère in 1846 and later solved a double-enciphered message (Kahn,

1967). However, Babbage's work was not made public (Salomon, 2003). An officer in the

Prussian army, Kasiski, published a method similar to Babbage's for breaking Vigenère in 18 63
(Kahn, 1967). Nonetheless, the cipher was considered secure in the popular press as late as 1917 (The Oxford Math Center, 2018). Given a cryptographic key, a cipher can change "plaintext" into "ciphertext" (Migure g). The term "text" is used loosely to refer to any data. Ciphers may either use a single key for both encryption and decryption operations; or uses pairs of keys--one each for encryption and decryption.

Symmetric ciphers reuse the same key for both

encryption and decryption while asymmetric ciphers require a pair.

Symmetric ciphers can use

substitution or transposition cipher primitives to transform the data. Substitution ciphers replace characters in the plaintext to generate ciphertext.

Examples include "s

boxes" in the Data Encryption

Standard (DES)

(Gargiulo, 2002) and rotors in the

Figure 1: Ciphers transform plaintext into

ciphertext and vice versa

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

4 German Enigma machine (Rijmenants, 2016). Transposition only permutes the plaintext thus "shuffles the deck". Enigma plug boards (Rijmenants, 2016) and DES "p-boxes" (Forouzan,

2007) are examples of transposition. Vigenère only uses substitution.

stgtgt Rubstitution ,ipher Jrimitives In simple substitution, the shift of the plaintext is consistent through out the encryption process. The Caesar cipher with its key of 3 shifts each letter of plaintext forward three positions in the alphabet. "a" becomes "d", "b" becomes "e" and so forth. The alphabet forms a ring such that "x" loops back around to "a", "y" to "b", etc. 1 . Another example using key = 1 is given (Figure 2). Figure 2: Using a key of 1, the phrase is encrypted by simple substitution These ciphers can be broken using frequency analysis (Daniel Rodriguez-Clark, 2013). Since each character is shifted the same amount, the relative popularity of characters is preserved in the ciphertext. This is true for overall frequency and contextual frequency. Assuming an English alphabet encrypted with a Caesar cipher, "e" is statistically the most likely character of plaintext overall so "h" will tend to show up most frequently in the ciphertext. A cryptanalyst studying some ciphertext may assume the most popular ciphertext character translates to "e", the second most popular "t", third "a", and so on (Oxford Math Center, 2018). Context also matters.

If position is preserved in the cipher text (i.e., spaces are not removed), then "t" is the most likely

character to start a word (Oxford Math Center, 2018). Also, if any ciphertext character is deciphered, then all other occurrences of that character are immediately known. In Figure 2, the letter "m" appears three times in the ciphertext. If any one of these is determined to be "l" (lowercase L), then all three are instantly recognized. 1 An online substitution cipher tool is available at https://learncryptogr aphy.com/tools/caesar- cipher

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

5 stgtst Jolyalphabetic ,ipher Jrimitives Polyalphabetic ciphers like Vigenère improve upon simple substitution by using a multi- character key. Polyalphabetic ciphers can be thought of as several simple substitution ciphers used in rotation. The length of the key determines how many characters o f plaintext can be encrypted before the key must be reused. In the following example, the key "sans" is highlighted in alternating colors to show the application of the key 2 Migure bè )xample of polyalphabetic encryption with key asansa

Wable gè Aey encoding used in example

Key Encoding

a b c d e f g h i j k l m 0

1 2 3 4 5 6 7 8 9 10 11 12

n o p q r s t u v w x y z 13

14 15 16 17 18 19 20 21 22 23 24 25

In contrast to the previous "hello world" example (Figure 2), the plaintext in the next example is the same (Figure 4), but the five-character key is 12345. Therefore, each of the first five characters of plaintext is shifted independently according to the k ey for that column. Because the key is five characters in length, it must be reused after the first five characters of plaintext. In this example, the key is reused for "world" (Figure 4). 2

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

6 Migure .è Ksing a key of gsb.Cm the phrase is encrypted with polyalphabetic substitution This method is more secure than the simple substitution cipher. In Migure sm all characters including the three occurrences of "l" (lowercase L) were shifted the same amount. The polyalphabetic key gsb.C in Migure . shifts the first occurrence of "l" (lowercase L) to "o" (lowercase O) and the second occurrence to "p". This behavior reduces the chance that popular letters will form highly predictable patterns in the ciphertext. However, it is important to note that the second "l" (lowercase L) in "hello" was shifted 4 spots to "p" exactly the same as the "l"

(lowercase L) in "world". This is a result of both letters being in the same position relative to the

key; the fourth position. This coincidence foreshadows the Vigenère cipher's demise.

2.1.3. One-time pad

Assuming the cryptanalyst has only the ciphertext, there exists an unbreakable cipher. If a random polyalphabetic key at least as long as the plaintext is used only once, a cryptanalyst cannot recover the plaintext 3 (RIJMENANTS, 2016). A cryptanalyst can discover some key that decrypts the ciphertext into an intelligible statement, but then find other keys that produce even more statements. There is no way to determine which message is correct since all are eq ually likely (RIJMENANTS, 2016). It is theoretically possible to generate Vigenère cipher keys that fulfill the requirements of a one-time pad, but these may not be practical. Putting aside the issues of generating truly random keys, sharing keys securely and having enough key material, transporting the key itself becomes overwhelming. Recall the key must be at least as long as the plaintext. A mobile phone 3 If the cryptanalyst is allowed other forms of attack such as coercion of an adversary or collusion with a dishonest agent, the assumption does not hold.

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

7 alone generates about 4GB of traffic per month (Heuveldop, 2017). Imagine the problems if this amount is doubled by the use of one-time pad. stst Roftware and West Miles To encrypt, decrypt and analyze data using a variety of ciphers, python 4 scripts are provided on GitHub in the "cryptography" repository 5 . The repository includes software needed to perform all operations and cryptanalysis demonstrated in this paper.

Also, test files can be

found in the "test-files" directory. The project includes scripts for many different cipher s and related utilities. Visionary.py and Freak.py are most applicable to this study. ststgt Yisionarytpy Script visionary.py encrypts/decrypts using a Vigenère cipher 6 . Unlike previous examples that were simplified for clarity, visionary.py works on all input bytes (i.e. a space character will be encrypted the same as any other). Character, binary and base64 input/output formats are supported. Input can be read from standard input 7 or a file. Important arguments include the following. -h, --help Show help -e, --encrypt Encrypt INPUT. This option requires a KEY. -d, --decrypt Decrypt INPUT. This option requires a KEY. -k KEY, --key KEY Encryption/Decryption key -v, --verbose Enables verbose output -i INPUT_FILE, --input-file INPUT_FILE Read INPUT from an input file

These are some examples of usage

8 4 Python 3 is required and available at https://www.python.org/downloads/ 5 6 The original cipher used only characters in the alphabet for keys. visio nary.py operates on bytes so values 0 - 255 are possible. 7 More information on standard input is available at 8 Scripts were tested with Python 3.6.0 on Windows 10 version 1709, Python

3.6.4rc1 on Kali

Linux 4.14.0 and Python 3.5.2 on Ubuntu 4.4.0

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

8 )ncrypt the phrase ahelloworlda with key gsb.C nMigure Cu python visionary.py --encrypt --key 12345 "helloworld" Figure 5: Encrypt the phrase "helloworld" with key 12345 wecrypt the phrase aigoptxqupia with key gsb.C nMigure yu python visionary.py --decrypt --key 12345 "igoptxqupi" Figure 6: Decrypt the phrase "igoptxqupi" with key 12345 Wake input from binary filem encryptm then redirect output to binary file nMigure pu python visionary.py --encrypt --key Password1 --input-format=binary --output- format=binary --input-file=funny-cat-1.jpg > enc-funny-cat-1.bin Figure 7: Take input from binary file, encrypt, then redirect output to binary f ile uvuvuv Freakvpy

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

9 Freak.py is a utility that calculates statistics useful for analysis. The script supports character, binary and base64 input formats. Analysis is performed on each byte of input. Like visionary.py, input can be read from standard input 9 or a file and four types of analysis are supported: histogram, statistics, index of coincidence and polyalphabetic columns (columnar) 10 A histogram is a graphical representation of the frequency of elements in a data set (Collins English Dictionary - Complete & Unabridged 10th Edition, 2010). Presented as a bar chart on a set of characters, the relative frequency of each character is denoted by the height of the bar.

The following options are helpful:

-c, --show-count Show count for each byte of input -p, --show-percent Show percent representation for each byte of input -m, --show-histogram Show histogram for each byte of input -a, --show-ascii Show ASCII representation for each byte of input -t TOP_FREQUENCIES, --top-frequencies TOP_FREQUENCIES

Only display top X frequencies

Generally, the most common switches used with the histogram feature are count, percentage, show-histogram and top-frequencies. The following example counts the occurrences of each byte-value in a file and creates a histogram to display relative popularity. Byte-values range from 0 (0X00) to 255 (0XFF). In the example below, byte value 0 is the most frequent character by a large margin so the respective bar is relatively longer. ,onsidering each byte in file funnyecategtjpgm show countm percent and histogram for top gl most common bytes nsorted by popularityu nMigure hu python freak.py -cpm -v -t 10 -i funny-cat-1.jpg 9 More information on standard input is available at 10 "Polyalphabetic columns" are discussed more once the relevance of the key length is established

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 0 Migure hè ,onsidering each byte in file funnyecategtjpgm show countm percent and histogram for top gl most common bytes nsorted by popularityu Calculating statistics is intuitive since the names of the arguments align directly with their function. -mean, --show-mean Show Arithmetic Mean (Average) -median, --show-median Show Median -mode, --show-mode Show Mode (Most popular byte) -antimode, --show-anti-mode Show Anti-Mode (Least popular byte) -variance, --show-variance Show Variance -stddev, --show-standard-deviation Show Standard Deviation -e, --show-entropy Show Shannon entropy -stats, --show-statistics Show mean, median, mode, variance, standard deviation and Shannon entropy for each byte of input Generally, freak.py is used to compute all available statistics on a file. As with other operations, calculations are made with respect to byte-value. The script also calculates Shannon entropy with a range of 0.0 to 8.0. This value is a relative indicator of how random the data appears (Ueltschi, 2006). Data that is encrypted well should be reasonably indistinguishable from random data. A strong cipher produces an even histogram and very high entropy (Lawlor, 2013). The histogram, mode and entropy are correlated. For data to appear rando m, the popularity of

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 1 each byte must be the same (on average). This results in a flat histogram and high entropy (VandenBrink, 2016). Mor each byte in file encryptedefunnyecategtjpgm show all statisticsè meanm medianm modem antiemodem variancem standard deviationm and Rhannon entropy nMigure Vu python freak.py --show-statistics --verbose -i funny-cat-1.jpg Figure 9: For each byte in file encrypted-funny-cat-1.jpg, show all statistics: mean, median, mode, anti-mode, variance, standard deviation, and Shannon entropy Index of Coincidence (IOC) indicates when bytes at a common offset are related. This statistical measure and related features of freak.py will be explained during the analysis of the key length. The IOC can be calculated using the -ioc, --show-ioc flag as seen in the following. wetermine the index of coincidence of file encryptedefunnyecategtjpg nMigure glu python freak.py -ioc --verbose --input-file=encrypted-funny-cat-1.bin

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 2 Migure glè wetermine the index of coincidence of file encryptedefunnyecategtjpg

2.2.3. Test Files

Four JPEG files are supplied for demonstration

11 . Three files are taken from photos of cats (Figures 11-13). The fourth is a bi-chromatic image of Twitter, Inc. logo Larry Bird 12 (Figure 14). The fourth image is provided as a counter-example. The cryptanalysis feature of freak.py does not perform well with images that are only 1-2 colors. Analysis will show the extreme lack of color variation throws off what is usually the most popular byte. 11 12 The small, blue bird ironically appears to have its name revealed in a t weet

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 3

Migure ggè funnyecategtjpg

Migure

gs

è funny

e cat e stjpg

Migure

gb

è funny

e cat e btjpg

Migure g.è twitterebirdtjpg

An encrypted copy of funny-cat-1.jpg is included with the other test files. This file will be used in remaining demonstrations that require an encrypted file. The command used to encrypt was the following. The password is intentionally obfuscated to allow the reader to attempt to learn the password using techniques presented 13 13 The command with clear text password is available at

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 4 python visionary.py --encrypt --key [password]--input-format=binary --output- format=binary --input-file=test-files\funny-cat-1.jpg > test-files\encrypted-funny-cat- 1.jpg visionary.py encrypts by iterating over each byte of the plaintext. As it proceeds, plaintext bytes are shifted into ciphertext bytes. Because the cipher is polyalphabetic, the amount of shift varies from byte to byte according to the password. Each byte of the key is used in succession from left to right to determine the shift for the respective plaintext byte. When the key bytes are exhausted, the key bytes are reused starting at the left most key byte again (Migure gC).

Migure gCè )ncryption function

To ensure the encryption process worked well, the file can be decrypted then compared to the original (Migure gy). python visionary.py --decrypt --key [password] --input-format=binary --output- format=binary --input-file=test-files\encrypted-funny-cat-1.jpg > test-files\decrypted- funny-cat-1.jpg fc /B test-files\funny-cat-1.jpg test-files\decrypted-funny-cat-1.jpg 14 15 14 15 /Bcomparesfileinbinarymode

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 5 Migure gyè Wo ensure the encryption process worked wellm the file can be decrypted the n compared to the original stbtgt 4n asideè Wraffic 4nalysis Before cryptanalysis can take place, reconnaissance is necessary to dete rmine what has been encrypted. Context such as the original file format, the cipher used and other information is needed to attack the encryption (or perhaps to know a cryptanalysis att ack is not likely to work). The communication patterns between systems can provide this background (Northcutt, 2007). Traffic Analysis seeks to answer questions such as "What encoding and encryption is usually used?", "What language is spoken?" and "What type of file is being transferred?". These and other conversational metrics may reveal the file type and encryption in play. stbtst Jotentially Kseful Rtatisticsè Knencrypted PJ)D Miles JPEG is a binary format (Hamilton, 1992). Byte-values range from 0 (0X00) to 255 (0xFF). If JPEG files contain no distinguishing characteristics with respect to frequency of byte- values, the expected value of the mean and median is 127.5. All byte-values would be the mode 16 and the Shannon Entropy would be 8.0. A series of statistics can be run on the test files to see if 16

Mode: Most popular value in a set

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 6 the byte values of JPEG files tend to have a prominent characteristic. f reak.py is able to calculate mean, median, mode, standard deviation and entropy on the top 10 most po pular bytes. The command is demonstrated here for file funny-cat-1.jpg and the same is run on the other three test files to generate the statistics. The results are summarized in Wable s. python freak.py -cpme -mean -median -mode -stddev -t 10 -v -i funny-cat-1.jpg

Migure gpè Rtatistics for funnyecategtjpg

python freak.py -cpme -mean -median -mode -stddev -t 10 -v -i funny-cat-2.jpg

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 7

Migure ghè Rtatistics for funnyecatestjpg

python freak.py -cpme -mean -median -mode -stddev -t 10 -v -i funny-cat-3.jpg

Cryptanalysis of the Vigenère Cipher |

JeremyDruin,jdruin@gmail.com

1 8

Migure gVè Rtatistics for funnyecatebtjpg

python freak.py -cpme -mean -median -mode -stddev -t 10 -v -i twitter-bird.jpg

Migure slè Rtatistics for twitterebirdtjpg

Wable sè Rtatistics for test files

Munny ,at g Munny ,at s Munny ,at b Sarry 0ird

Bean

123.53 119.68 121.92 105.24

Bedian 123 117.5 120.5 98

Bode

0 0 0 32

Rtandard

73.96 75.11 74.81 78.40

)ntropy 7.98 7.91 7.93 7.30 The figures show a byte-value of 0 is pronounced in all of the JPEG except Larry Bird. However, even in this counter-example, byte-value 0 makes up 7.76% of the file. This is well

Cryptanalysis of the Vigenère Cipher |

quotesdbs_dbs30.pdfusesText_36

[PDF] decoder vigenere sans clef

[PDF] chiffre de vigenere algorithme

[PDF] algorithme rsa exemple

[PDF] algorithme rsa pdf

[PDF] algorithme rsa exercice corrigé

[PDF] cryptage rsa exemple

[PDF] cryptographie asymétrique algorithme

[PDF] chiffrement asymétrique et symétrique

[PDF] chiffrement asymétrique exemple

[PDF] cryptographie exercices corrigés pdf

[PDF] les nombres en lettres pdf

[PDF] les nombres en lettres de 0 ? 1000

[PDF] ap seconde chiffres significatifs

[PDF] chiffres significatifs excel

[PDF] les chiffres significatifs cours