I I 3YSTEMS AND NTERNET NFRASTRUCTURE 3ECURITY ETWORK AND 3ECURITY 2ESEARCH ENTER EPARTMENT OF OMPUTER 3CIENCE AND NGINEERING 0ENNSYLVANIA 3TATE 5NIVERSITY 5NIVERSITY 0ARK 0 CMPSC443 Introduction to Computer and Network Security Module Cryptography Professor Patrick McDaniel Spring 2009 CMPSC443 Introduction to Computer and Network Security Page 1 A historical moment Mary Queen of Scots is being held by Queen Elizabeth and accused of treason All communication with co conspirators encrypted Cipher was unbreakable Walsingham needs to prove complicity CMPSC443 Introduction to Computer and Network Security Page 2 Intuition Cryptography is the art and sometimes science of secret writing Less well known is that it is also used to guarantee other properties e g authenticity and integrity of data This is an mathmatically deep and important field However much of our trust in cryptographic systems is based on faith particularly in efficient secret key algorithms ask Mary Queen of Scots how that worked out This set of lectures will provide the intuition and some specifics of modern cryptography seek others for additional details Menezes et al CMPSC443 Introduction to Computer and Network Security Page 3 Cryptography Cryptography cryptographer Creating ciphers Cryptanalysis cryptanalyst Breaking ciphers The history of cryptography is an arms race between cryptographers and cryptanalysts CMPSC443 Introduction to Computer and Network Security Page 4 An Encryption Algorithm Algorithm used to make content unreadable by all but the intended receivers Encrypt plaintext key ciphertext Decrypt ciphertext key plaintext Algorithm is public key is private Block vs Stream Ciphers Block input is fixed blocks of same length Stream stream of input bit wise CMPSC443 Introduction to Computer and Network Security Page 5 Hardness and security Functions Plaintext P Ciphertext C Encryption E key ke Decryption D key kd D E P ke kd P Computing P from C is hard computing P from C with kd Is easy for all Ps operation true for all inputs except in some vanishingly small number of cases CMPSC443 Introduction to Computer and Network Security Page 6 Example Caesar Cipher Every character is replaced with the character three slots to the right A B C D E F G H I J K L MN O P Q R S T U VWX Y Z D E F G H I J K L MN O P Q R S T U VWX Y Z A B C Q What is the key S E C U R I T Y A N D P R I V A C Y V H F X U L W B D Q G S U L Y D F B CMPSC443 Introduction to Computer and Network Security Page 7 Cyptanalyze this CFH ARGJBEX FRPHEVGL CMPSC443 Introduction to Computer and Network Security Page 8 Cryptanalysis of ROTx Ciphers Goal to find plaintext of encoded message Given ciphertext How simply try all possible keys Known as a brute force attack 1 T F D 2 U G E 3 W H F S E C V W X U S T U R J K L I U V W T Z A B Y B C D A M N Q N E F G D Q R S P S T U R J H L I W X Y V B C D A CMPSC443 Introduction to Computer and Network Security D E F C Z A B Y Page 9 Substitution Chipher A substitution cipher replaces one symbol for another in the alphabet Caesar cipher and rot13 are a specific kind rotation The most common is a random permutation cipher A B C D E F G H I J K L M C M T E F H P U D X N Z L N O P Q R S T U V W X Y Z O A J R Y I G W B S Q K CMPSC443 Introduction to Computer and Network Security V Page 10 Why are substitution ciphers breakable Substitution ciphers are breakable because they don t hide the underlying frequency of characters You can use this information if you know the target language frequency count For example in English e t a o i n s r h d l u c m f y w g p b v k x q j z 01 2 3 45 A 9 8 7 6 5 4 3 2 1 0 Q how do you exploit this CMPSC443 Introduction to Computer and Network Security Page 11 Using frequency Vg gbbx n ybg bs oybbq fjrng naq grnef gb trg gb jurer jr ner gbqnl ohg jr unir whfg ortha Gbqnl jr ortva va rnearfg gur jbex bs znxvat fher gung gur jbeyq jr yrnir bhe puvyqera vf whfg n yvggyr ovg orggre guna gur bar jr vaunovg gbqnl CMPSC443 Introduction to Computer and Network Security Page 12 Using frequency Vg gbbx n ybg bs oybbq It took a lot of blood fjrng naq grnef gb trg gb jurer jr ner gbqnl ohg jr unir whfg ortha Gbqnl jr ortva va rnearfg gur jbex bs znxvat fher gung gur jbeyq jr yrnir bhe puvyqera vf whfg n yvggyr ovg orggre guna gur bar jr vaunovg gbqnl sweat and tears to get to where we are today but we have just begun Today we begin in earnest the work of making sure that the world we leave our children is just a little bit better than the one we inhabit today r appears very frequently so very likely is one of the top frequency letters CMPSC443 Introduction to Computer and Network Security Page 13 Using frequency Vg gbbx n ybg bs oybbq It took a lot of blood fjrng naq grnef gb trg gb jurer jr ner gbqnl ohg jr unir whfg ortha Gbqnl jr ortva va rnearfg gur jbex bs znxvat fher gung gur jbeyq jr yrnir bhe puvyqera vf whfg n yvggyr ovg orggre guna gur bar jr vaunovg gbqnl sweat and tears to get to where we are today but we have just begun Today we begin in earnest the work of making sure that the world we leave our children is just a little bit better than the one we inhabit today Repeat this process picking out more letters then common words e g the CMPSC443 Introduction to Computer and Network Security which gives e to r g to t and u to h Page 14 Attacking a Cipher The attack mounted will depend on what information is available to the adversary Ciphertext only attack adversary only has the ciphertext available and wants to determine the plaintext encrypted Known plaintext attack adversary learns one or more pairs of ciphertext plaintext encrypted under the same key tries to determine plaintext based on a different ciphertext Chosen plaintext attack adversary can obtain the encryption of any plaintext tries to determine the plaintext for a different ciphertext Chosen ciphertext attack adversary can obtain the plaintext of any ciphertext except the one the adversary wants to decrypt CMPSC443 Introduction to Computer and Network Security Page 15 Other cryptanalysis Brute force cryptanalysis Just keep trying different keys and check result early breaks Linear cryptanalysis Construct linear equations relating plaintext ciphertext and …