Popular in Course
Popular in Computer Information Technology
verified elite notetaker
This 32 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS551 at University of Pennsylvania taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/215374/cis551-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for COMP&NETWORKSEC
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
CIS 551 TCOM 401 Computer and Network Security Spring 2009 Lecture 15 Announcements Plan for Today Symmetric Key Cryptography Project 3 is due 6 April 2009 at 1159 pm Handout for SDES available in class today Please read the project description BEFORE looking at the code Two talks of interest Andreas Haeberlen Accountability for distributed systems 300pm TODAY in Wu amp Chen Auditorium Stefan Savage Spamalytics Exploring the Technical and Economic Underpinnings of Bulk Email Scams 300pm Thurs in Wu amp Chen Auditorium 31709 CISTCOM 551 Kinds of Industrial Strength Crypto Shared Key Cryptography Public Key Cryptography Cryptographic Hashes All of these aim for computational security Not all methods have been proved to be intractable to crack 31709 CISTCOM 551 Shared Key Cryptography Sender amp receiver use the same key Key must remain private Also called symmetric or secret key cryptography Often are blockciphers Process plaintext data in blocks Examples DES TripleDES Blowfish Twofish AES Rijndael For good detailed explanation of DES and AES see Cryptography and Network Security 4th Edition V lliam Stallings 31709 CISTCOM 551 Shared Key Notation Encryption algorithm E key x plain a cipher Notation Kmsg EK msg Decryption algorithm D key x cipher a plain D inverts E DK EK msg msg Use capital K for shared secret keys Sometimes E is the same algorithm as D 31709 CISTCOM 551 Secure Channel Shared Keys Alice Bart KABHeo KABHi 1 KAB KAB 31709 CISTCOM 551 Data Encryption Standard DES Adopted as a standard in 1976 Security analyzed by the National Security Agency NSA httpcsrcnistqovpublicationsfipsfips463fips46 3pdf Key length is 56 bits padded to 64 bits by using 8 parity bits Uses simple operators on up to 64 bit values Simple to implement in software or hardware Input is processed in 64 bit blocks Based on a series of 16 rounds Each cycle uses permutation amp substitution to combine plaintext with the key 31709 CISTCOM 551 DES Encryption DES follows the structure of a general class of encryption agorithms called Feiste ciphers Rounds of encryption Each round merges one half of the input ILi V with the other using w an f f J K PREOUTPUT Rp L15LlwllR15K Ll R5 CINVERSE INITIAL PERM l 31709 Ill 8 One Round of DES f of previous slide Perm uted choice of key Expansion 43 ans l H43 BITS 771 1 M 51 2 4 W 5x w LHH TM 1111 W HII Sbox Permutation EZIBHS 31 709 Types of Permutations in DES Permutation Permuted Choice Expansion Permutation I 31709 CISTCOM 551 10 DES S Boxes Substitution tables 6 bits of input replaced by 4 bits of output Implemented as a lookup table 8 S Boxes Each S Box has a table of 64 entries Each entry specifies a 4bit output SBox design is complex here is the black art of cryptography design Example desiderata No output put of any S Box should be close to a linear function of the inputs If two inputs to an S Box differ by exactly one bit the outputs must differ in at least two bits Each row of an S Box should contain all 16 possible bit combinations 31709 CISTCOM 551 11 DES Decryption Use the same algorithm as encryption but use k16 k1 instead of k1 k16 Proof that this works To obtain round j from j1 1 Lj Rj1 QampH mwh Rewrite in terms of round j1 n ag 2 Lj1 639 fRj1 kj Rj Lj1 639 fRj1 kj 639 fRj1 kj LJ1 RJ 6 fRJ1 kj LJ1 RJGD fL K J ae ahm 12 Problems with DES Key length too short 56 bits wwwdistributednet broke a DES challenge in 1999 in under 24 hours parallel attack Other problems Bitwise complementation of key produces bitwise complemented ciphertext Not all keys are good half 0 s half 1 s Differential cryptanalysis 1990 Carefully choose pairs of plaintext that differ in particular known ways eg they are complements But particular choice of S boxes is secure against this I developers of DES knew about differential cryptanalysis before it was publically known in the research community 31709 CISTCOM 551 13 Advanced Encryption Standard AES National Institute of Standards amp Technology NIST Computer Security Research Center CSRC htt9csrcnistgov Uses the Rijndael algorithm Invented by Belgium researchers Dr Joan Daemen amp Dr Vincent Rijmen Adopted May 26 2002 Key length 128 192 or 256 bits Block size 128 192 or 256 bits Not a Feistel cipher 10 rounds each consisting of SubBytes Shift Rows Mix ColumnsAdd Round Key 31709 CISTCOM 551 14 AES Operations am am a 3 AddRoundKey a1 2 a13 10 Add Round Key SubByEw bw q bw m3 b20 ban 31709 CISTCOM 551 15 AES Operations No change am am 02 303 8 01 am am a v3 ShiftRows Shift1a a a 313 a a a 11 12 13 aw Shi ROWS 323 KJ a a S s 330 31 32 333 MixCqumns cx 3x3 x2 x2 31709 CISTCOM 551 16 Block Cipher Modes of Operation Often want to encrypt large pieces of data but block ciphers only work on fixed small chunks Various Options Electronic Code Book each block of plaintext bits is encoded independently using the same key Cj KPj Cipher Block Chaining each block of plaintext is XORed with the preceding block of ciphertext starting with initialization vector CO Cj KPj 6 CH and CO is an initialization vector Other options Cipher Feedback to convert a block cipher to a streaming cipher Counter mode XOR an encryption counter with each block 31709 CISTCOM 551 17 Hash Algorithms Take a variable length string Produce a fixed length digest Typically 1281024 bits Hash IWIZI IWIZI Noncryptographic Examples Parity or bytewise XOR CRC cyclic redundancy check used in communications Ad hoc hashes used for hash tables Realistic Example The NIST Secure Hash Algorithm SHA takes a message of less than 264 bits and produces a digest of 160 bits 31709 CISTCOM 551 18 Cryptographic Hashes Create a hardtoinvert summary of input data Useful for integrity properties Sender computes the hash of the data transmits data and hash Receiver uses the same hash algorithm checks the result Like a checksum or error detection code Uses a cryptographic algorithm internally More expensive to compute Sometimes called a Message Digest History Message Digest MD4 invented by Rivest MD5 Secure Hash Algorithm 1993 SHAO Secure Hash Algorithm SHA1 SHA2 actually a family of hash algorithms with varying output sizes SHA3 currently being developed via a competition Attacks have been found against both SHA O and SHA 1 31709 CISTCOM 551 19 Uses of Hash Algorithms Hashes are used to protect integrity of data Virus Scanners Program fingerprinting in general Modification Detection Codes MDC Message Authenticity Code MAC Includes a cryptographic component Send msg hashmsg key Attacker who doesn t know the key can t modify msg or the hash Receiver who knows key can verify origin of message Make digital signatures more efficient we39ll see this later 31709 CISTCOM 551 20 Desirable Properties The probability that a randomly chosen message maps to an nbit hash should ideally be 12 Attacker must spend a lot of effort to be able to modify the source message without altering the hash value Hash functions h for cryptographic use as MDC s fall in one or both of the following classes Collision Resistant Hash Function It should be computationally infeasible to find two distinct inputs that hash to a common value ie hx hy One Way Hash Function Given a specific hash value y it should be computationally infeasible to find an input x such that hxy 31709 CISTCOM 551 21 Secure Hash Algorithm SHA Pad message so it can be divided into 512bit blocks including a 64 bit value giving the length of the original message Process each block as 16 32bit words called Wt fort from O to 15 Expand from these 16 words to 80 words by defining as follows for each tfrom 16 to 79 t Wt3 e Wt8 e Wt14 e Wt16 Constants HO H5 are initialized to special constants Result is final contents of HO H5 31709 CISTCOM 551 22 for each 16 w0rd block begin A 2 H0 B H1 C 2 H2 D H3 E H4 forI 5to 19 be in gt A TEMP z S5A B A C v B A D E WI 5A827999 E D D C C S30B B A A 2 TEMP end forl 20 to 39 begin TEMP z S5A B G C 43 D E WI 6ED9EBA1 E D D C C S30B B A A z TEMP end for I 40 to 59 begin TEMP S5A B A C v B A D v C A D E WI 8F1BBCDC E D D C C S30B B A A TEMP end forI 60 to 79 begin Shift A left 5 bits TEMP S5A B39 6 C 69 D E WI CA62C1D6 E D D C C 2 S30B B A A TEMP m end H0 H0A H1 H1B H2 H2C H3 2 H3D H4 2 H4E end Chaining Variables Attacks against SHA1 In early 2005 Riimen and Oswald published an attack on a reduced version of SHA1 53 out of 80 rounds which finds collisions with a complexity of fewer than 280 operations In February 2005 an attack by Xiaoyun Wang Yigun Lisa Yin and Hongbo Yu was announced The attacks can find collisions in the full version of SHAf requiring fewer than 269 operations brute force would require 280 In August 2005 same group lowered the threshold to 263 May lead to more attacks 31709 CISTCOM 551 24 DiffieHellman Key Exchange Problem with sharedkey systems Distributing the shared key Suppose that Alice and Bart want to agree on a secret Le a key Communication link is public They don t already share any secrets 31709 CISTCOM 551 25 DiffieHellman by Analogy Paint Alice Bart Let s use yellowquot OK yellowquot 7 l 1 Alice amp Bart decide on a public color and mix one liter of that color 2 They each choose a random secret color and mix two liters oftheir secret color 3 They keep one liter of their secret color and mix the other with the public color 31709 ClSTCOM 551 26 DiffieHellman by Analogy Paint Alice i Bart 4 They exchange the mixtures over the public channel 5 When they get the other person s mixture they combine it with their retained secret color 6 The secret is the resulting color Public Alice s Bart s 31709 ClSTCOM 551 DiffieHellman Key Exchange Choose a prime p publicly known Should be about 512 bits or more Pick g lt p also public g must be a primitive root of p A primitive root generates the finite field p Every n in 1 2 p1 can be written as gk mod p Example 2 is a primitive root of 5 201 212 224 233 mod5 lntuitively means that it s hard to take logarithms base g because there are many candidates 31709 CISTCOM 551 28 DiffieHellman Alice 1 Bart Let s use p a OK 0A mod p 03 mod 0 Alice amp Bart decide on a public prime p and primitive root 9 Alice chooses secret number A Bart chooses secret number B Alice sends Bart gA mod p The shared secret is gAB mod p 31 709 ClSTCOM 551 29 Details of DiffieHellman Alice computes gAB mod p because she knows A gAB mod p gB mod pA mod p An eavesdropper gets gA mod p and 9B mod p They can easily calculate gAB mod p but that doesn t help The problem of computing discrete logarithms to recover A from gA mod p is hard 31709 CISTCOM 551 30 Example Alice and Bart agree that q71 and 97 Alice selects a private key A5 and calculates a public key 9A a 75 a 51 mod 71 She sends this to Bart Bart selects a private key 812 and calculates a public key 9B 5 712 a 4 mod 71 He sends this to Alice Alice calculates the shared secret S E gBA E 45 E 30 mod 71 Bart calculates the shared secret S a gAB a 5112 a 30 mod 71 31709 ClSTCOM 551 31 Why Does it Work Security is provided by the difficulty of calculating discrete logarithms Feasibility is provided by The ability to find large primes The ability to find primitive roots for large primes The ability to do efficient modular arithmetic Correctness is an immediate consequence of basic facts about modular arithmetic 31709 CISTCOM 551 32
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'