Cryptography Lecture Notes PDF

Cryptography CYS401 PSU, KSA  What is Encryption/Decription? Foundations of Cryptology Cipher Methods Cryptographic Algorithm, Cryptographic Tools, Protocols for secure communication, Attacks on cryptosystems Cryptography Cryptography, a word...

Cryptography CYS401 PSU, KSA  What is Encryption/Decription? Foundations of Cryptology Cipher Methods Cryptographic Algorithm, Cryptographic Tools, Protocols for secure communication, Attacks on cryptosystems Cryptography Cryptography, a word with Greek origins, means “secret writing.” However, we use the term to refer to the science and art of transforming messages to make them secure and immune to attacks. Encryption in a nutshell  Basic Concepts Encryption: converting original message into a form unreadable by unauthorized individuals.  allow two parties to establish confidential communication over an insecure channel that is subject to eavesdropping. Decryption: the process of converting the ciphertext message back into plaintext Communication Sender channel Recipient plaintext encryp decryp t t ciphertext plaintext plaintext shared shared secret secret key key Attacker (eavesdropping) 5 Some Basic plaintext - original message Terminology ciphertext - coded message cipher - algorithm for transforming plaintext to ciphertext key - info used in cipher known only to sender/receiver encipher (encrypt) - converting plaintext to ciphertext decipher (decrypt) - recovering ciphertext from plaintext cryptography - study of encryption principles/methods cryptanalysis (codebreaking) - study of principles/ methods of deciphering ciphertext without knowing key cryptology - field of both cryptography and cryptanalysis 6 Basic Concepts Data Encryption and Decryption Notation  Secret key K  Encryption function EK(P) = C  Decryption function DK(C) = P  Plaintext length typically the same as ciphertext length P encrypt C decrypt P K K 7 Basic Concepts Cryptography: process of making and using codes to secure transmission of information  Can protect confidentiality and integrity, but not availability Cryptology: science of encryption; combines cryptography and cryptanalysis  Cryptanalysis: process of obtaining the original message from encrypted message without access to the required secret information 8 Kerckhoffs's principle in cryptography Cryptography algorithm should be secure even if everyone knows how it works, the security of a cryptosystem should depend solely on the secrecy of the key and the private randomizer Based on Kerckhoff’s principle, one should always assume that the adversary, Eve, knows the encryption/decryption algorithm. The resistance of the cipher to attack must be based only on the secrecy of the key. In short:  Algorithm must be made public  Only the key is kept secret Cryptography We can characterize cryptographic system by:  Type of encryption operations used substitution transposition product  Number of keys used single-key or private two-key or public  Way in which plaintext is processed block stream 10 Cipher Classification Ciphers Symmetric Asymmetric Hash Classical Modern Substitution Block Transposition stream Product 11 Cryptosystem Types Symmetric Cryptosystem  Substitution: Replacing  Transposition: Change the positions Asymmetric Cryptosystem  Public key cryptosystems  Figure 5.1 General idea of symmetric-key cipher symmetric-key encipherment uses a single key for both encryption and decryption. The encryption and decryption algorithms are inverses of each other 3.13 If P is the plaintext, C is the ciphertext, and K is the key, We assume that Bob creates P1; we prove that P1 = P: 3.14 Figure 3.2 Locking and unlocking with the same key 3.15 Symmetric Cryptosystem Characteristics Efficiency  Functions EK and DK should have efficient algorithms  Symmetric key encryption is fast compared to public key encryption  How fast? Almost 30,000 times faster Consistency  Decrypting the ciphertext yields the plaintext  DK(EK(P)) = P 16 Substitution Ciphers: Caesar Cipher En(x) = (x + n) mod 26  E(a)=1+14 mod26 =15 = “o” Dn(x) = (x – n) mod 26 D(O)= 1-14 mod 26= 13 =“a” Caesar Cipher Shift =3  Caesar Cipher Example, let n=1 and plaintext: Dear, shall we have dinner at McD? Encryption: E(D) = (3 + 1) mod = 4 or E E(e) = (4 + 1) mod = 5 or f E(a) = (0 + 1) mod= 1 b Ciphertext: Efbs-!tibmm!xf!ibwf! ejoofs!bu!NdE@ Decryption: D(E) = (4 - 1) mod = 3 or D D(f) = (5 - 1) mod = 4 or e D(b) = (1 - 1) mode = 0 a First, build the mapping table with all the shifts to get it easier! 19 Public domain image from http://commons.wikimedia.org/wiki/File:Caesar3.svg Substitution Ciphers: ROT13 Each letter is uniquely replaced by another. There are 26! possible substitution ciphers. There are more than 4.03 x 1026 such ciphers. One popular substitution “cipher” is ROT13. Public domain image from http://en.wikipedia.org/wiki/File:ROT13.png Encrypt the sentence “We love PSU” 20  Substitution Ciphers : Keyword Ciphers Use a keyword or phrase as the basis of the encryption scheme. For example, let “PSU IS MY CHOICE” be the keyword. Remove repeated letters in the keyword and add in remaining letters of alphabet in order. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z E N D C P S U I M Y C H O E A B D F G J K L N Q R T V W X Z E R C Y R P Y T Encrypt DECRYPT P HELLO=HMBBG BPZX= Lazy T SMART= STUDYHARD= Public domain image from http://commons.wikimedia.org/wiki/File:Caesar3.svg 21 Examples Given “Zebras” as a keyword, Decrypt using the keyword cipher A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Z E B R A S C D F G H I J K L M N O P Q T U V W X Y S l A A Z Q L K B A V A Z O A R F P B L U A O A R ! Examples Given “Zebras” as a keyword, Decrypt using the keyword cipher A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Z E B R A S C D F G H I J K L M N O P Q T U V W X Y S l A A F L E E Z Q A T L K B A O N C E V A W E Z O A A R E R F P B L U A O A R D I S C O V E R E D Playfair Cipher  not even the large number of keys in a monoalphabetic cipher provides security  one approach to improving security was to encrypt multiple letters  the Playfair Cipher is an example  invented by Charles Wheatstone in 1854, but named after his friend Baron Playfair 24 Playfair Key Matrix  a 5X5 matrix of letters based on a keyword  fill in letters of keyword (sans duplicates)  fill rest of matrix with other letters  eg. using the keyword MONARCHY 25 Encrypting and Decrypting plaintext is encrypted two letters at a time 1. if a pair is a repeated letter, insert filler like 'X’ 2. if both letters fall in the same row, replace each with letter to right (wrapping back to start from end) 3. if both letters fall in the same column, replace each with the letter below it (wrapping to top from bottom) 4. otherwise each letter is replaced by the letter in the same row and in the column of the other letter of the pair 26 Playfair Encryption and Decryption HELLO -> HE LX LO M O N A R C H Y B D Encryption: E F G I/J K HE -> CF L P Q S T LX -> SU U V W X Z LO -> MP Decryption: CF -> HE SU -> LX MP -> LO 27 Security of Playfair Cipher  security much improved over monoalphabetic  since have 26 x 26 = 676 digrams  would need a 676 entry frequency table to analyse (verses 26 for a monoalphabetic)  and correspondingly more ciphertext  was widely used for many years  eg. by US & British military in WW1  it can be broken, given a few hundred letters  since still has much of plaintext structure 28  Vigenère Cipher (Encryption) Plaintext : GEEKSFORGEEKS Length = 13 Keyword : AYUSH The keyword "AYUSH" should be repeated to match the plain text length So, the key generated is "AYUSHAYUSHAYU“ The rows are the plain text The columns are the key The intersections are the cipher. Cipher is GCYCZFMLYLEIM 29 Public domain image from http://commons.wikimedia.org/wiki/File:Caesar3.svg  Vigenère Cipher (Decryption) Cipher is GCYCZFMLYLEIM the key is "AYUSHAYUSHAYU“ Using the same table Rows represent the key The intersection represent the cipher The corresponding column is the plain Plaintext : GEEKSFORGEEKS 30 Public domain image from http://commons.wikimedia.org/wiki/File:Caesar3.svg How to attack substitution: Frequency Analysis Letters in a natural language, like English, are not uniformly distributed. Knowledge of letter frequencies, including pairs and triples can be used in cryptologic attacks against substitution ciphers. 31 Substitution Ciphers: One- Time Pads There is one type of substitution cipher that is absolutely unbreakable.  The one-time pad was invented in 1917 by Joseph Mauborgne and Gilbert Vernam  We use a block of shift keys, (k1, k2,... , kn), to encrypt a plaintext, M, of length n, with each shift key being chosen uniformly at random. Since each shift is random, every ciphertext is equally likely for any plaintext. 32 Example En(x) = (x + n) mod 26 Dn(x) = (x – n) mod 26 Substitution Ciphers: Hill Cipher Developed by mathematician Lester Hill in 1929, the encryption algorithm takes m successive plaintext letters and substitutes with m ciphertext letters. Each letter is represented by a number modulo 26. (E.g. A = 0, B = 1,..., Z = 25) To encrypt a message, each block of n letters is multiplied by an invertible n × n matrix, modulus 26. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. 34 35 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 36  37 How to find the inverse key matrix Determinant Transposition Cipher Transposition Cipher In a transposition cipher, the characters retain their plaintext form but change their positions to create the ciphertext The text is organized into a two- dimensional table, and the columns are interchanged according to a key The key defines which columns should be swapped Example Example Example Example 3.44  MODERN BLOCK CIPHERS A symmetric-key modern block cipher encrypts an n-bit block of plaintext or decrypts an n-bit block of ciphertext. The encryption or decryption algorithm uses a k-bit key. 5.45 A modern block cipher 5.46 Block Ciphers  Block Ciphers In a block cipher:  Plaintext and ciphertext have fixed length b (e.g., 128 bits)  A plaintext of length n is partitioned into a sequence of m blocks, P, …, P[m1], where n  bm  n + b Each message is divided into a sequence of blocks and encrypted or decrypted in terms of its blocks. Requires padding with extra bits. Plaintext Blocks of plaintext 48 Padding Block ciphers require the length n of the plaintext to be a multiple of the block size b Padding the last block needs to be unambiguous (cannot just add zeroes) 49 Padding Example for b = 64 bits (8 bytes)  Plaintext: “Roberto” (7 bytes)  Padded plaintext: “Roberto9” (8 bytes), where 9 denotes the number and not the character We need to always pad the last block, which may consist only of padding 50 Block Ciphers in Practice Data Encryption Standard (DES)  Developed by IBM and adopted by NIST in 1977  64-bit blocks and 56-bit keys  Small key space makes exhaustive search attack feasible since late 90s https://page.math.tu-berlin.de/~kant/ teaching/hess/krypto-ws2006/des.htm 51 Block Ciphers in Practice Triple DES (3DES)  Nested application of DES with three different keys KA, KB, and KC  Effective key length is 168 bits, making exhaustive search attacks unfeasible  C = E (D (E (P))); P = D (E (D (C))) KC KB KA KA KB KC  Equivalent to DES when KA=KB=KC (backward compatible) 52 Triple DES 53 Block Ciphers in Practice Advanced Encryption Standard (AES)  Selected by NIST in 2001 through open international competition and public discussion  128-bit blocks and several possible key lengths: 128, 192 and 256 bits  Exhaustive search attack not currently possible International Data Encryption Algorithm (IDEA )  Uses a 128-bit key and is used in Pretty Good Privacy (PGP) encryption for e-mail systems RC5  Developed at MIT, and allows for variable length keys. Blowfish  Designed by Bruce Schneier in 1993 allows for variable length keys up to 448 bits 54 Block Cipher Modes A block cipher mode describes the way a block cipher encrypts and decrypts a sequence of message blocks. Electronic Code Book (ECB) Mode:  Block P[i] encrypted into ciphertext block C[i] = EK(P[i])  Block C[i] decrypted into plaintext block M[i] = DK(C[i]) 55  Cipher Block Chaining (CBC) Mode Cipher Block Chaining (CBC) Mode  The 1st block is XOR with an initialization vector  The previous ciphertext block is XOR the current plaintext block C[i] = EK (C[i 1]  P[i])  Decryption: P[i] = C[i 1]  DK (C[i]) CBC Encryption: CBC Decryption: P P P P P P P P V V EK EK EK EK DK DK DK DK C C C C C C C C 56  Cipher Feedback (CFB) Mode Cipher Feedback (CFB) Mode  Similar to Cipher-Block Chaining  Encrypt the current block with previous ciphertex block C[i] = EK (C[i 1])  P[i]  Decryption: P[i] = C[i]  EK (C[i-1]) V CFB Encryption: V CFB Decryption: EK EK EK EK EK EK EK EK P P P P C C C C C C C C P P P P 57  Output Feedback (OFB) Mode Output Feedback (OFB) Mode  Similar to one-time pad, but pad with generated cipher blocks V1=Ek(Vi-1) and begin with initialization vector V0.  Encrypt with Ci = Vi  Bi  Decryption with Bi = Vi  Ci V0 OFB Encryption: V0 OFB Decryption: V1 V2 V3 V1 V2 V3 EK EK EK EK EK EK EK EK P P P P C C C C C C C C P P P P 58 Counter (CTR) Mode Counter (CTR) Mode  Similar to OFB, but uses a seed s  Vi = Ek(s + i – 1)  CTR mode can be performed in parallel and can recover from dropped blocks 59  Symmetric Cryptosystem Attacks Attacker may have Plaintext Encryption Ciphertext Hi, Algorithm Hi, a. collection of ciphertexts (ciphertext only (a) Bob. Bob. Don’t Don’t invite attack): deduce the plaintext by guessing invite Eve to Eve to the key the key. the party! party! Love, Love, Alice Alice Eve Plaintext Encryption Ciphertext Algorithm b. collection of plaintext/ciphertext pairs for (b) Hi, Hi, Bob. Bob. Don’t plaintext selcted by attacker (known Don’t invite invite Eve to key plaintext attack): the goal is to know the Eve to the the party! party! key/algorithm Love, Love, Alice Alice Eve Plaintext Encryption Ciphertext ABCD Algorithm ABCD Selected collection of plaintext/ciphertext (c) EFG EFG c. HIJKL HIJKL MNO pairs (chosen plaintext attack): to get the MNO PQRS PQRS TUV key TUV key to be used to decrypt the rest of data. WXYZ. WXYZ. Eve Plaintext Encryption Ciphertext collection of plaintext/ciphertext pairs for IJCGA, Algorithm d. IJCGA, CAN CAN 001101 (d) DO ciphertexts selected by the attacker DO HIFFA HIFFA GOT key 110111 (chosen ciphertext attack) GOT TIME. TIME. Eve 60 Eve Brute-Force Attack Try all possible keys K and determine if DK(C) is a likely plaintext  Requires some knowledge of the structure of the plaintext (e.g., PDF file or email message) How to protect:  Key should be a sufficiently long random value to make exhaustive search attacks unfeasible 61 Thank you 62