New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Kathleen Cartwright


Kathleen Cartwright
GPA 3.73


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Computer Information Technology

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.

Similar to CIS551 at Penn

Popular in Computer Information Technology




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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.