CSC 316 Chapter 2a, Spring 2004

Basic Cryptography Chapter 2 V. Sawma, Computer Security Controls Encryption • The most powerful tool in providing computer security in coding. Methods of Defense • Encryption provides confidentiality of data. • It is important to know the situations in which encryption is useful and to use it effectively V. Sawma, Computer Security Software Controls Software program controls include the following: • Internal program controls • Operating system controls • Development controls Hardware Controls • Firewalls • Intrusion Detection Systems Methods of Defense (contd.) V. Sawma, Computer Security Effectiveness of Controls is very essential. Some factors that affect the effectiveness of controls are: • Awareness of Problem • Likelihood of Use • Overlapping Controls • Periodic Review Effectiveness of Controls V. Sawma, Computer Security Overlapping of Controls DATA Program Access Restrictions File Access Controls Physical Access Controls HARDWARE Physical Access Controls SOFTWARE File Access Controls Logical Access Controls V. Sawma, Computer Security Why Encryption? Secrecy or Confidentiality: Able to keep information secret Accuracy or Integrity: Certain type of encryption protect against forgery or tampering– malicious or inadvertent Authenticity: A type of encryption called digital signature can be used for unique financial or legal transactions and hard to forge. V. Sawma, Computer Security The study of encryption and decryption. “kryptos” meaning “hidden” and “graphia” meaning “writing”. Cryptography Cryptology: The study of secure communications, which encompasses both cryptography and cryptanalysis. Cipher: An algorithm for encryption and decryption. A cipher replaces a piece of message with another object. Cryptography: Legitimate study of encrypted messages to convert the messages to the normal form Cryptanalysis: Study of encrypted messages to break the encryption V. Sawma, Computer Security Terminology Sender (S) Receiver (R) Transmission Medium Outsider (O)  Interceptor  Intruder V. Sawma, Computer Security Encryption: Process of encoding a message so that its meaning is not obvious. Decryption: Process of transforming an encrypted message back into its normal form. Cryptosystem: A system for encryption and decryption. Plain text: The original form of a message Cipher text: The encrypted form of a message Encryption and Decryption V. Sawma, Computer Security Outsiders can: Block  Prevent transmission or receipt  Violate availability Intercept  Read / Listen  Violate confidentiality Modify  Change / Seize  Violate integrity Fabricate  Spoof  Violate integrity / accountability V. Sawma, Computer Security Cryptography Plain text vs Cipher text  Plain text: P  Cipher text: C Encryption  Encode / Encrypt  Denoted: C = E(P) Decryption  Decode / Decrypt  Denoted: P = (D(C)) V. Sawma, Computer Security Encryption Algorithms The basic idea is to use a key K Encryption: Cipher text can be obtained from plain text using a key C = E(K,P) Decryption: When the encryption and decryption keys are the same, then plain text can be obtained as P = D(K, E(K,P)) This type of encryption is called Symmetric encryption V. Sawma, Computer Security Encryption Algorithms (contd.) When the encryption and decryption keys are not similar then plain text can be obtained as: P = D(KD, e(KE,P)) where KE = Encryption key and KD = Decryption key This type of encryption is called Asymmetric encryption Encryption Decryption Plaintext Cipher- text Original Plaintext Basic Encryption V. Sawma, Computer Security Encryption Algorithms (contd.) Encryption Decryption Plaintext Cipher- text Original Plaintext KEY Encryption Decryption Plaintext Cipher- text Original Plaintext Encryption key KE Decryption key KD Symmetric Cryptosystem Asymmetric Cryptosystem V. Sawma, Computer Security Secret key (Symmetric system ) and Public Key (Asymmetric system) Secret Key: A particular key is shared between two users Key distribution is a major problem Public Key:  Works with two keys, public key and the private key  Public key is publicly available for encryption  The private key only decrypts the encrypted message  n (n-1)/2 keys are needed for n users to communicate V. Sawma, Computer Security Cryptanalysis Break an algorithm via:  Breaking a single message  Recognizing patterns  Learn algorithm (ex. Repeated patterns)  Finding weaknesses in encryption algorithm Works with any of the following:  Intercepted messages (cipher and/or plain)  Known encryption algorithms  Mathematics, statistics, language properties, etc.  Ingenuity and Luck!!! V. Sawma, Computer Security Modular Arithmetic Represent letters with numbers  A(0) B(1) C(2) D(3) E(4) F(5) Can perform calculations  A + 3 = D Circular  E + 3 = B Also known as mod n V. Sawma, Computer Security Monoalphabetic Ciphers Also known as substitutions  Uses a correspondence table  Each ONE cipher “corresponds” to ONE plain We will take TWO ciphers:  The Caesar Cipher  Named after Julius Caesar  Permutations V. Sawma, Computer Security Monoalphabetic Substitution Ciphers Substituting each character by another character or symbol is called monoalphabetic cipher or a simple substitution. 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 can be used to obtain cipher text ci as follows: ci = E(pi ) = pi + 3 Encrypt TREATY IMPOSSIBLE V. Sawma, Computer Security The Caesar Cipher 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 Example: Example: Plain: TREATY IMPOSSIBLE Cipher: wuhdwb lpsrvvleoh V. Sawma, Computer Security The Caesar Cipher Advantages  Easy to perform  Was protected b/c only FEW people could read   Pattern (pi + 3) is easy to remember Disadvantages  Pattern is easy to guess  Pattern repetition in Cipher Try breaking the following cipher:  wklv phvvdjh lv qrw wrr kdug wr euhdn V. Sawma, Computer Security Disadvantages of the Caesar Cipher • It is easily observable that blanks are not encrypted and are replaced by blanks itself. • As English has got few small words, the two letter words can be easily replaced with few guesses • Next the three letter words which have two continuous same letters can be determined as such patterned words are very few • The ciphertext letters uncovered are just three positions away from their plaintext counterparts. A cryptanalyst might try that same pattern on all the unmatched ciphertext. V. Sawma, Computer Security Permutations Alphabet is scrambled Each plaintext letter maps to a unique ciphertext letter Example: Plain: 1,2,3,4,5,6,7,8,9,10 Perm1: 1,3,5,7,9,10,8,6,4,2 Perm2: 10,9,8,7,6,5,4,3,2,1,0 V. Sawma, Computer Security Permutations (cont’d) Some permutations use keys Example: Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Perm1: KEYABCDFGHIJLMNOPQRSTUVWXZ Perm2: SPECTAULRBDFGHIJKMNOQVWXYZ V. Sawma, Computer Security Polyalphabetic Substitution Ciphers Monoalphabetic ciphers reflect PLAIN TEXT frequency distribution Polyalphabetic ciphers aim to provide a more flat distribution!!! One way to do so is to COMBINE monoalphabetic ciphers  Odd plain text letters use a Permutation  Even plain text letters use another Permutation V. Sawma, Computer Security Vigenère Tableaux V. Sawma, Computer Security Vigenère Tableaux (cont’d) Encrypt the following: Plain: BUT SOFT WHAT LIGHT Key: Juliet a r e x i s q c y s a e o k u j t e i l u j t e i l u j G I L T W H A T F O S B U T V. Sawma, Computer Security Cryptanalysis of Poly. Subs. # of alphabets used Break cipher into pieces that were ciphered with the same alphabet Solve each piece as a monoalphabet substitution  Two tools can help:  Kasiski method  Index of coincidence V. Sawma, Computer Security 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. V. Sawma, Computer Security Kasiski Method (cont’d) 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. Distance must be a multiple of key length 4. Determine all factors of difference (eg. 21 means the key is either 3 or 7 characters long) 5. Divide the cipher into blocks (based on key length) 6. Columns in each block must have been encrypted using the SAME key character 7. Use frequency distribution to determine the letter V. Sawma, Computer Security Kasiski Method Example Cipher text example:  afexddyzlskfjkwlkdfxskejfkkfexdjfieuyty  2 28  28 - 2 = 26  Key must be of length: 1, 2, 13, or 26 V. Sawma, Computer Security Index of Coincidence Def: Is a measure of the variation between frequencies in a distribution English has HIGH and LOW frequencies The more substitutions we use, the lower the HIGHs and the higher the LOWs This index allows us to predict the number of substitutions used V. Sawma, Computer Security Index of Coincidence (cont’d) - n denotes the number of letters used in cipher message, not 26!        z a n n freq freq IC     )1 ( )1 ( ) ( ) ( V. Sawma, Computer Security The “Perfect” Substitution Cipher Use many alphabets (infinite nonrepeating sequence if possible) Kasiski method fails because:  no repetition occurs  If a repetition occurs, it does not mean the end of the key  confusion V. Sawma, Computer Security One-time Pads Use key once and destroy Identical pads at both sides Problem:  Need for absolute synchronization  Need for unlimited number of keys V. Sawma, Computer Security One-Time Pads Long Random Number Sequences  Random numbers are NOT random!  They form a sequence with a VERY LONG period Vernam Cipher  Random numbers are generated from a tape  Safe as long as tape is not reused Binary Vernam Cipher  Rely on binary operations  Encrypts binary data using binary data  Produces binary data  Can be easily performed on computers (XOR) V. Sawma, Computer Security The Vernam Cipher It is a type of One-Time pad Immune to cryptanalytic attacks V. Sawma, Computer Security Book Cipher Select numbers from a book Telephone book, choose a number, apply mod 26 and then use Vigenere Tableau Phrase from a book, use it as a key and the use the Vigenere Tableau V. Sawma, Computer Security Cryptanalysis of Book Cipher The message and the key text are not evenly distributed The distributions cluster around high-frequency letters V. Sawma, Computer Security Random Number Generation (cont’d) Long sequences from books  Problem: Neither the message nor the key text is evenly distributed Dual Message Entrapment  Encrypt two messages at once  One message is real, the other is dummy  Even if decrypted, cryptanalyst cannot distinguish message from key!!! V. Sawma, Computer Security Summary: Substitutions & Transpositions Substitutions  Monoalphabetic Ciphers  Polyalphabetic Ciphers  These are called Stream Ciphers Transpositions  Permutation  These are Block Ciphers V. Sawma, Computer Security Summary: Mono-alphabetic Ciphers Caesar Cipher  Formula:  Treaty Impossible --> wuhdwb lpsrvvleoh  Advantages & Disadvantages  Easy to perform  Simple, so easy to predict the pattern  Repeat characters give clue to break Permutation Cipher  Use a key  ABCDE ………  k e ya b……….  Since key is short, most plaintext letters are only one or two positions off Time complexity of these algorithms -- linear in n where n is the no. of characters in plaintext 3 ) (    i i i p E p c V. Sawma, Computer Security Summary: Polyalphabetic Substitution Ciphers Main problem with monoalphabetic ciphers is the non-flat frequency distribution A flat distribution gives no information to cryptanalyst Flattening by combining distributions Two or more separate encryption alphabets for the same character of the plaintext Eg., one encryption for characters in odd positions and another for at even positions Reduces the repeat symbols in the ciphertext Makes it hard to break V. Sawma, Computer Security Summary: Vigenere Tableaux Need to smooth out peaks and valleys of frequency distribution Can be done by extending no. of permutations Extreme case -- extend to 26 permutations A 26 X 26 table is used Key word of length 3 is sufficient to smooth out the distribution Cryptanalysis of Polyalphabetic V. Sawma, Computer Security Summary: Perfect Substitution Cipher Requires an infinite non-repeating sequence of alphabets This will confound the cryptanalyst One-Time pads Vernam Cipher  Uses an arbitrarily long sequence of numbers Random Numbers  Middle digits of phone numbers in a residential directory