CSC 316 Chapter 2a, Fall 2007

Chapter 2 Basic Encryption and Decryption csc316 computer security & their data 2 Encryption / Decryption encrypted transmission A B plaintext plaintext ciphertext encryption decryption � A: sender; B: receiver � Transmission medium � An interceptor (or intruder) may block, intercept, modify, or fabricate the transmission. csc316 computer security & their data 3 Encryption / Decryption � Encryption: A process of encoding a message, so that its meaning is not obvious. (= encoding, enciphering) � Decryption: A process of decoding an encrypted message back into its original form. (= decoding, deciphering) � A cryptosystem is a system for encryption and decryption. � Plain text: The original form of a message � Cipher text: The encrypted form of a message csc316 computer security & their data 4 Plaintext / ciphertext � P: plaintext � C: ciphertext � E: encryption � D: decryption � C = E (P) � P = D (C) � P = D ( E(P) ) csc316 computer security & their data 5 Cryptosystems � Symmetric encryption: P = D (Key, E(Key,P) ) � Asymmetric encryption: P = D (KeyD, E(KeyE,P) ) � Symmetric cryptosystem: A cryptosystem that uses symmetric encryption. � Asymmetric cryptosystem csc316 computer security & their data 6 Encryption Algorithms (contd.) Encryption Decryption Plaintext Ciphertext Original Plaintext KEY Encryption Decryption Plaintext Ciphertext Original Plaintext Encryption key KE Decryption key KD Symmetric Cryptosystem Asymmetric Cryptosystem csc316 computer security & their data 7 Keys � Use of a key provides additional security. � Exposure of the encryption algorithm does not expose the future messages ( as long as the key(s) are kept secret). csc316 computer security & their data 8 Terminology � Cryptography: The practice of using encryption to conceal text. (cryptographer) � Cryptanalysis: The study of encryption and encrypted messages, with the goal of finding the hidden meanings of the messages. (cryptanalyst) � Cryptology = cryptography + cryptanalysis csc316 computer security & their data 9 Cryptanalysis � A cryptanalyst may work with various data (intercepted messages, data items known or suspected to be in a ciphertext message), known encryption algorithms, mathematical or statistical tools and techniques, properties of languages, computers, and plenty of ingenuity and luck. 1. Attempt to break a single message 2. Attempt to recognize patterns in encrypted messages 3. Attempt to find general weakness in an encryption algorithm csc316 computer security & their data 10 Modular arithmetic � Known as mod n for example n=26 (since we have 26 English letters) � A .. Z: 0 .. 25 � Perform operations on letters for ex.: – A+3=D – D-3=a – A-1= Z csc316 computer security & their data 11 Two forms of encryption � Substitutions One letter is exchanged for another For example: ABCaDEF � Transpositions (= permutations) The order of the letters is rearranged For example: ABCaCBA csc316 computer security & their data 12 Simple Encryption Algorithms � Substitution – Monoalphabetic (Ceaser, Using a key, Random) – Polyalphabetic (two or more, Using a key, Perfect) � Permutation – Simple – Double csc316 computer security & their data 13 Ceaser Cipher The Caesar Cipher • Each letter is translated to the letter a fixed number of letters after it in the alphabet. • Uses a shift of 3 • Plain text pi is used to obtain cipher text ci as follows: ci = E(pi ) = pi + 3 csc316 computer security & their data 14 Ceaser Cipher – Example • Plain: This is the message • Cipher: wklv lv wkh phvvdjh b a z y w x v u t s r q p o m n l k j i h g f e d K L M N O P Q R S T U V W X Y J B C D E F G H I A c Z csc316 computer security & their data 15 Other monoalphabetic substitutions � Using Shift (permutation) – (lambda) = 25 – lambda � Using a key A key is a word that controls the ciphering. Example: The key is (key) Another Example Key is Juliette JULIETABCDFGHKMNOPQRSVWXYZ Note: • Use Large keys • Use Keys that contain letters from the end of the alphabet L M N O P Q R S T U V W X J E Y A B C D F G H I K K L M N O P Q R S T U V W X Y J B C D E F G H I A Z Z csc316 computer security & their data 16 Other monoalphabetic substitutions � Random monoalphabetic substitution � Example Note: Each letter should appear only once D V K X P B O L F R M N C S U H E Y T G W Z Q J A K L M N O P Q R S T U V W X Y J B C D E F G H I A I Z csc316 computer security & their data 17 Cryptanalysis example � Consider the following ciphertext: WKLV PHVVDJH LV QRW WRR KDUG WR EUHDN Try to make cryptanalysis to conclude the full or part of the original message csc316 computer security & their data 18 Comparaison of the security of all monoalphabetic ciphering � All easy to perform � All unsecure enough � In order of highest to lowest security – Random (need to know all letters substitutions) – Using a key (need to know all the key) – Ceaser or shift (need to know the size of the shift) csc316 computer security & their data 19 Weakness of the security of all monoalphabetic ciphering � Blanks are not encrypted (blanks remain blanks) � As English has few small words, the two and three letters words are easily guessed after few trials � The same two letters are encrypted as same two other letters and not all two letters are repeated. csc316 computer security & their data 20 Frequency distribution � It shows the counts and relative frequencies of letters in English. � For example the frequencies of Ceaser’s cipher are shifted three letters from the normal distribution � Frequencies in a sample cipher: Compare the sample cipher against the normal frequency distribution. csc316 computer security & their data 21 Frequency distribution csc316 computer security & their data 22 Another disadvantage of monoalphabetic cipher � It always has lot o peaks and valleys and � With comparison of the normal distribution the exact substitution can be guessed � To solve this we have Polyalphabetic cipher csc316 computer security & their data 23 Polyalphabetic substitutions � By combining distributions that are high with the ones that are low � Using multiple substitution tables � Example :One table for odd positions, One table for even positions csc316 computer security & their data 24 Polyalphabetic substitutions � EXAMPLE: – ABCDEFGHIJKLMNOPQRSTUVWXYZ � S1:DEFGHIJKLMNOPQRSTUVWXYZABC � S2: ZYXWVUTSRQPONMLKJIHGFEDCBA – P= IMPOSSIBLE – C= LNSLVHMYOV csc316 computer security & their data 25 Polyalphabetic substitutions (Vigenère Tableaux) � Table 2-1: p.51 � Example: p.50 � P= I am I exist that is certain � Key: Secure � C= aeocv pmunk zevej vitnr ar � Exercise: Complete the encryption of the following message – Plain: BUT SOFT WAS LIGHT – KEY: JULIETTE csc316 computer security & their data 26 csc316 computer security & their data 27 Cryptanalysis of Polyalphabetic cipher. � Find the number of alphabets used � Break cipher into chains that were ciphered with the same alphabet � Solve each piece as a monoalphabetic substitution – Two tools can help: • Kasiski method • Index of coincidence csc316 computer security & their data 28 Cryptanalysis of Polyalphabetic substitutions (kasiski method) � The Kasiski method: a method to find the number of alphabets used for encryption � Works on duplicate fragments in the ciphertext � The distance between the repeated patterns must be a multiple of the keyword length csc316 computer security & their data 29 Kasiski Method � Relies on regularity of English � Not only letters but also groupings – Ending: th, ing, ed, ion, tion, ation, etc. – Beginning: im, in, un, re, etc. – Patterns: eek, oot, our, etc. csc316 computer security & their data 30 Steps of The Kasiski Method � Identify all repeated patterns in the ciphertext � For each pattern: 1. Write down the starting position 2. Compute the distance between successive starting positions 3. The distance must be a multiple of key length 4. Determine all factors of difference (eg. 16 means the key is either 1, or 2 or 4 or 8 characters long) 5. Divide the cipher into chains (based on key length) 6. Columns in each chain must have been encrypted using the SAME key character 7. Use frequency distribution to determine the letter csc316 computer security & their data 31 Index of coincidence � A measure of the variation between frequencies in a distribution � To measure the nonuniformity of a distribution � To rate how well a particular distribution matches the distribution of letters in English csc316 computer security & their data 32 Index of Coincidence � Measure of roughness (or the variance): a measure of the size of the peaks and valleys. � The var of a perfectly flat distribution = 0. � The variance can be estimated by counting the number of pairs of identical letters and dividing by the total number of pairs possible csc316 computer security & their data 33 Index of Coincidence � IC (index of coincidence): a way to approximate variance from observed data. � 0.0384 (perfect) ≤ IC < 0.068 (English) csc316 computer security & their data 34 Combined use of IC with Kasiski method � All the chains from the Kasiski method, if the key length was correct, should have distributions close to 0.068. csc316 computer security & their data 35 Analyzing a polyalphabetic cipher 1. Use the Kasiski method to predict the likely numbers of enciphering alphabets. 2. Compute the IC to validate the predictions 3. (When 1 and 2 show promises) Generate chains and calculate IC’s for each chains csc316 computer security & their data 36 The “Perfect” Substitution Cipher � Use an infinite nonrepeating sequence of alphabets � A key with an infinite number of nonrepeating digits � Examples: one-time pads, the Vernam cipher, … csc316 computer security & their data 37 Vernam Cipher � Sample function: c = ( p + random( ) ) mod 26 � Example: p.42 � Binary Vernam Cipher p.43: How would you decipher a ciphertext encrypted by Binary Vernam Cipher? Ans.: p = (c – random( ) ) mod 26 Example (p.42): c = 19 (‘t’), random( ) = 76 p = (19-76) mod 26 = 21 csc316 computer security & their data 38 Random Number Generators � A pseudo-random number generator is a computer program that generates numbers from a predictable, repeating sequence. � Example: The linear congruential random number generator ri+1 = (a * ri + b) mod n Note: 12 is congruent to 2 (modulo 5), since (12-2) mod 5 = 0 � Problem? Its dependability; probable word attack csc316 computer security & their data 39 Breakability of an encryption � An encryption algorithm may be breakable, meaning that given enough time and data, an analyst could determine the algorithm. � Suppose there exists 1030 possible decipherments for a given cipher scheme. A computer performs 1010 operations per second. Finding the decipherment would require 1020 seconds (or roughly 1012 years). csc316 computer security & their data 40 Summary � Substitutions and permutations together form a basis for the most widely used encryption algorithms