Lecture 2 Symmetric Encryption

Network Security Lecture 2: Symmetric encryption Outline     Symmetric encryption Block encryption algorithms Stream ciphers Cipher Block Modes Symmetric Encryption      or conventional / private-key / single-key sender and recipient share a common key all classical encryption algorithms are private-key was only type prior to invention of public-key in 1970’s and by far most widely used Crypto  Cryptology  The art and science of making and breaking “secret codes”  Cryptography  making “secret codes”  Cryptanalysis  breaking “secret codes”  Crypto  all of the above (and more) Some Basic Terminology  plaintext - original message  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 Simple Substitution   Plaintext: fourscoreandsevenyearsago Key: a b c d e f g h i j k l m n o p q r s t u v wx y z Plaintext DE F G H I J K L MN O P Q R S T U V WX Y Z A B C Ciphertext  Ciphertext: IRXUVFRUHDAGVHYHABHDUVDIR  Shift by 3 is “Caesar’s cipher” Ceasar’s Cipher Decryption  Suppose we know a Ceasar’s cipher is being used  Ciphertext: VSRQJHEREVTXDUHSDQWU a b c d e f g h i j k l m n o p q r s t u v wx y z Plaintext DE F G H I J K L MN O P Q R S T U V WX Y Z A B C Ciphertext  Plaintext: spongebobsquarepants Not-so-Simple Substitution    Shift by n for some n  {0,1,2,…,25} Then key is n Example: key = 7 a b c d e f g h i j k l m n o p q r s t u v wx y z Plaintext HI J K L MN O P Q R S T U V WX Y Z A B C D E F G Ciphertext Cryptanalysis I: Try Them All        A simple substitution (shift by n) is used But the key is unknown Given ciphertext: CSYEVIXIVQMREXIH How to find the key? Only 26 possible keys  try them all! Exhaustive key search Solution: key = 4 Even-less-Simple Substitution    Key is some permutation of letters Need not be a shift For example a b c d e f g h i j k l m n o p q r s t u v wx y z Plaintext J I C A X S E Y V D K WB Q T Z R H F MP N U L G O Ciphertext  Then 26! > 288 possible keys! Cryptanalysis II: Be Clever    We know that a simple substitution is used But not necessarily a shift by n Can we find the key given ciphertext: PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTF XQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPB FXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGV PPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTD PTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPB FIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVX EBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTA VWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA Cryptanalysis II  Can’t try all 288 simple substitution keys  Can we be more clever?  English letter frequency counts… 0.14 0.12 0.10 0.08 0.06 0.04 0.02 0.00 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 Cryptanalysis II   Ciphertext: PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXB VCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVW LBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOT HFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQP WTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOG HFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVA FXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTO FFA Decrypt this message using info below Ciphertext frequency counts: A B C D E F G H I J K L MN O P Q R S T U V WX Y Z 21 26 6 10 12 51 10 25 10 9 3 10 0 1 15 28 42 0 0 27 4 24 22 28 6 8 Comparison 60 50 40 Ser i es1 30 20 10 0 A B C D E F G H I I J J K L M N O P Q R S T U V W X Y Z 0. 14 0. 12 0. 10 0. 08 0. 06 0. 04 0. 02 0. 00 A B C D E F G H K L M N O P Q R S T U V W X Y Z 15 Try by yourself 16 Try by yourself 17 Try by yourself 18 Try by yourself 19 Try by yourself 20 Try by yourself 21 Try by yourself 22 Try by yourself https://www.youtube.com/watch?v=Hd2gY1cPDUw 23 Try by yourself 24 Try by yourself 25 Symmetric Cipher Model Requirements     two requirements for secure use of symmetric encryption: – a strong encryption algorithm – a secret key known only to sender / receiver mathematically have: Y = E(K, X) X = D(K, Y) assume encryption algorithm is known implies a secure channel to distribute key Cryptography  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 Cryptanalysis    objective to recover key not just message general approaches: – cryptanalytic attack – brute-force attack if either succeed all key use compromised Cryptanalytic Attacks      ciphertext only only know algorithm & ciphertext, is statistical, know or can identify plaintext known plaintext know/suspect plaintext & ciphertext chosen plaintext select plaintext and obtain ciphertext chosen ciphertext select ciphertext and obtain plaintext chosen text select plaintext or ciphertext to en/decrypt computationally secure encryption scheme  An encryption scheme: computationally secure if – The cost of breaking the cipher exceeds the value of information – The time required to break the cipher exceeds the lifetime of information Brute Force Search always possible to simply try every key most basic attack, proportional to key size assume either know / recognise plaintext    µs means microsecond (one million of second) Key Size (bits) Number of Alternative Keys Time required at 1 decryption/µs Time required at 106 decryptions/µs 32 232 = 4.3  109 231 µs = 35.8 minutes 2.15 milliseconds 56 256 = 7.2  1016 255 µs = 1142 years 10.01 hours 128 2128 = 3.4  1038 2127 µs = 5.4  1024 years 5.4  1018 years 168 2168 = 3.7  1050 2167 µs = 5.9  1036 years 5.9  1030 years 26! = 4  1026 2  1026 µs = 6.4  1012 years 6.4  106 years 26 characters (permutation) Feistel Cipher  A Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel who did pioneering research while working for IBM (USA); Feistel Cipher Algorithm Symmetric Block Cipher Algorithms    DES (Data Encryption Standard) 3DES (Triple DES) AES (Advanced Encryption Standard) Data Encryption Standard (DES)      most widely used block cipher in world adopted in 1977 by NBS (now NIST) – as FIPS PUB 46 encrypts 64-bit data using 56-bit key has widespread use has considerable controversy over its security Time to Break a DES Code (assuming 106 decryptions/s) DES algorithm   Description of the algorithm: – Plaintext is 64 bits in length – Key is 56 bits in length – Structure is a minor variation of the Feistel network – There are 16 rounds of processing – Process of decryption is essentially the same as the encryption process The strength of DES: – Concerns fall into two categories » The algorithm itself  Refers to the possibility that cryptanalysis is possible by exploiting the characteristics of the algorithm » The use of a 56-bit key