Cryptography CSE 40622
Popular in Course
Popular in Computer Science and Engineering
This 0 page Class Notes was uploaded by Mrs. Damaris Hyatt on Sunday November 1, 2015. The Class Notes belongs to CSE 40622 at University of Notre Dame taught by Marina Blanton in Fall. Since its upload, it has received 46 views. For similar materials see /class/232739/cse-40622-university-of-notre-dame in Computer Science and Engineering at University of Notre Dame.
Reviews for Cryptography
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/01/15
Cryptography and Data Security CSE 4062260622 Fall 2009 Lecture 15 Discrete Logarithms and ElGamal Encryption Department of Computer Science and Engineering University of Notre Dame WW 0 So far we looked at a publickey encryption scheme modulo a composite the dif culty of breaking it lies in factoring and computing roots modulo a composite 0 Now we are going to study a publickey encryption scheme modulo a prime discrete logarithms Dif eHellman problem ElGamal encryption CSE 4062260622 Fall 2009 Marina Blanton 2 K Terminology Recap 0 Recall that group G is a set of elements together with a binary operation for which the associative law holds and the set is closed under that operation a unique identity element and unique inverses for each element a of G o The multiplicative group modulo m is denoted by Zin o A cyclic group is one that contains an element at whose powers ofquot and a i make up the entire group 0 An element a with such property is called a generator of the group CSE 4062260622 Fall 2009 Marina Blanton 3 r ElGamal Encryption o The idea behind ElGamal encryption we are given a multiplicative group G let m E G be an arbitrary element if g is an element of G chosen uniformly at random then so is 9 9 m 39 given 9 all messages m are equally likely we want 9 to be pseudorandom 39 g is computable using the private key 5k and can t be guessed otherwise CSE 4062260622 Fall 2009 Marina Blanton 4 K Discrete Logarithm Problem 0 Discrete logarithms we are given a cyclic group G of order q then there exists an element 9 E G such that Gltggtgioz q 1 for each h E G there is a unique 1 such that 95 such a is called the discrete logarithm of h with respect to g and we use a logg h many properties of regular logarithms apply logg 1 O 39 loggh1 h2 Iogghl Iogg h2 mOd q CSE 4062260622 Fall 2009 Marina Blanton 5 K Discrete Logarithm Problem o The discrete logarithm problem in a cyclic group G with given generator 9 compute unique logg h for a random element h E G 0 Let PPT algorithm Set 1k output a cyclic group G of order q and generator 9 E G o The discrete logarithm experiment DLogA75 tk 1 Run G q 9 lt Set1k and choose random h E G 2 A is given G q 9 h and outputs 13 E Z1 3 the experiment outputs 1 if 95 h and 0 otherwise CSE 4062260622 Fall 2009 Marina Blanton 6 K Discrete Logarithm Problem 0 We say that the discrete logarithm problem is hard relative to Set if for all PPT A there exists negl such that PrDLogA75 tk 1 g negk c When is the discrete logarithm problem hard most often a multiplicative group modulo prime p ZZ or its subgroup is used the choice of parameters is driven by known algorithms for solving the discrete logarithm problem CSE 4062260622 Fall 2009 Marina Blanton 7 K Discrete Logarithm Problem o Is the discrete logarithm problem generally hard it is hard in Z5 using proper parameters how about Zn 39 let gcdg n 1 so 9 is a generator of Zn now 95 mod n in multiplicative groups translates to gas mod n 39 the discrete logarithm problem is then gas E h mod n 39 but since gcdg n 1 we can compute 9 1 mod n now a loggh hg l mod n are there other cases when logg h is hard CSE 4062260622 Fall 2009 Marina Blanton 8 K Discrete Logarithm Problem 0 Algorithms for solving discrete log there are generic algorithms that work for every cyclic group 39 eg Shanks method Pollard rho method PohligHellman algorithm there are algorithms that work for certain groups only they rely on particular representation of the group 39 they are faster and will require larger security parameters 39 eg general number eld sieve for z with prime p there are no better attacks than generic algorithms for certain groups 39 eg groups over elliptic curves CSE 4062260622 Fall 2009 Marina Blanton 9 r Algorithms for Discrete Logarithm Problem o Shanks babystepgiantstep algorithm the algorithm requires steps for groups of order q giant steps are of size and baby steps are of size 1 algorithm steps on input G g and h E G 1 set t 2 fort O to Lqt compute g g 3 sort pairs i 91 by second value 4 fort O to t compute hi 2 h hi if hi 2 gj for some j return jt i mod q taking into account sorting and mod exponentiations amp multiplications overall complexity is O polylogq CSE 4062260622 Fall 2009 Marina Blanton 10 r Algorithms for Discrete Logarithm Problem o PohligHellman algorithm works when factorization of group order q is known or can be computed reduces the problem of computing discrete log in groups of order q q1 12 to discrete log in groups of order Q1 and q2 it uses a variant of the Chinese remainder theorem thus group order q must always contain at least one large factor CSE 4062260622 Fall 2009 Marina Blanton l l r Discrete Logarithm Problem 0 Discrete logarithm problem groups of prime order are a popular choice because PohligHellman algorithm is not effective 39 nding a generator is easy each element is a generator 39 exponent manipulation is easier each exponent has an inverse 39 other security assumptions are more likely to hold 0 How do we produce a group of prime order or with a large factor in the group order CSE 4062260622 Fall 2009 Marina Blanton 12 K Discrete Logarithm Problem o A subgroup of a group is a subset of the group that forms a group with the same binary operation for example powers ofquot in a multiplicative group can hit only a subset of the group elements 0 A group Zg for primep has order p 1 o Subgroups of z can have any order q that divides p 1 we often might want p 2g 1 for prime p and q or we can have p 2qt 1 for reasonably large prime q and some t CSE 4062260622 Fall 2009 Marina Blanton 13 K Discrete Logarithm Problem o How do we generate a subgroup let order of some group G be q q1 12 to obtain generator of subgroup of order ql we often can pick a E Gandsetg of o How do we generate proper prime p we want to generate primes p and q such that q p 1 to do so we need to know the factorization of p 1 approach 1 generate a random prime p and then factor p 1 approach 2 generate a random q rst and then choose 7 such that p 2rq 1 is prime CSE 4062260622 Fall 2009 Marina Blanton 14 K Discrete Logarithm Problem o The choice of parameters for group Z113 p needs to be large enough for discrete log to be hard to solve 2 3 39 fastest algorithm runs on average in 20k1339Og k time this requires p of at least 1024 hits the group order must have at least one large factor to prevent exhaustive search 39 eg 160bit value is a common choice if the group order is prime it can be relatively short same 160 bits this can improve performance CSE 4062260622 Fall 2009 Marina Blanton 15 r ElGamal PublicKey Encryption o ElGamal encryption a publickey encryption published in 1985 by ElGamal its security relies on the discrete logarithm problem being hard the encryption operation is randomized a ciphertext is twice as long as the original message the idea 39 the plaintext m is masked by multiplying it by by 39 another value 99 is transmitted as part of the ciphertext 39 knowing the private key one can compute by from 99 and unmask the message CSE 4062260622 Fall 2009 Marina Blanton l6 r ElGamal PublicKey Encryption 0 Key generation choose a cyclic group G of order q and a generator 9 E G choose a random 1 from Z1 and compute h 95 public key pk G qg h private key 5k 2 a o Encryption to encrypt a message m E G using public key pk G q 9 h choose a random number y E Zq compute the ciphertext as C EnCpkW 6162 99771 hy CSE 4062260622 Fall 2009 Marina Blanton l7 ElGamal PublicKey Encryption o Decryption given a ciphertext c c1 c2 and keys pk G q 9 h 5k 2 a decrypt the ciphertext as m Decskc CQCf o Correctness we show that DecskEncpkm m the decryption is C2 mhy 7719533 m Ci 9 9x9 Fall 2009 j 18 CSE 4062260622 Marina Blanton r ElGamal PublicKey Encryption 0 Example key generation 39 letp 2579 andg 2 39 suppose we choose a 765 and compute h 2765 mod 2579 949 39 the public key is pk 2579 2 949 the secret key is 5k 765 encryption 39 to encrypt m 1299 suppose we choose y 853 39 to encrypt rst compute c1 2853 mod 2579 435 and Q 1299 949853 mod 2579 2396 CSE 4062260622 Fall 2009 Marina Blanton 19 r ElGamal PublicKey Encryption 0 Example cont encryption 39 the ciphertext is c 435 2396 decryption 39 given 6 c1 c2 we decrypt the message by computing CQCf mod p m 2396 435765 1 mod 2579 1299 0 Security of ElGamal encryption depends on the discrete logarithm problem in G being infeasible but it is based on a different hardness assumption CSE 4062260622 Fall 2009 Marina Blanton 20 r ElGamal PublicKey Encryption o On parameter choice in ElGamal if g is a generator of z 39 p should have several hundred digits for the discrete logarithm to be hard 39 p 1 should have at least one large prime factor if 9 does not generate z 39 the order of 9 can be smaller than p 1 for instance prime order q of length 160 bits is suf cient the group doesn t have to be z other choices are possible eg groups de ned over elliptic curves CSE 4062260622 Fall 2009 Marina Blanton 21 r ElGamal PublicKey Encryption o On parameter choice in ElGamal sharing parameters 39 unlike in cryptosystems that use composite modulus here the same p and 9 can be used in many keys 39 when modulus n 2 pg is used its factorization is often the private key or allows to compute the private key 39 here both p and g are public 39 that makes this encryption secure is the knowledge of the secret value a a fresh value of y should be picked for each encryption CSE 4062260622 Fall 2009 Marina Blanton 22 K DiffieHellman Key Exchange o Dif eHellman key exchange protocol Alice and Bob want to compute a shared key which must be unknown to eavesdroppers Alice and Bob share public parameters a group G of order q and a generator 9 Alice randomly chooses a E Z1 and sends 95 to Bob A g gt B y Bob randomly chooses y E Z1 and sends 99 to Alice A lt9 B the shared secret is set to 9533 Alice computes it as 99 9x9 39 Bob computes it as gin git CSE 4062260622 Fall 2009 Marina Blanton 23 K DiffieHellman Key Exchange o Dif eHellman key exchange protocol Alice and Bob are able to establish a shared secret with no prior relationship it is believed to be infeasible for an eavesdropper to compute 9533 given 95 and 99 o Dif eHellman problem Computational Dif eHellman CDH problem given g 95 and 99 it is dif cult to compute gxy Decision Dif eHellman DDH problem iven 5 99 and 92 determine whether my 2 z modulo q g 9 9 CSE 4062260622 Fall 2009 Marina Blanton 24 r DiffieHellman Problem c As before CDH DDH problem is hard if any PPT adversary A has at most negligible probability in solving it o Dif e Hellman problem DDH is a stronger assumption than CDH breaking CDH implies breaking DDH but the converse is not true discrete log is at least as hard as CDH security of the Dif eHellman key exchange protocol is based on the CDH assumption CSE 4062260622 Fall 2009 Marina Blanton 25 F Security of ElGamal Encryption 0 Going back to ElGamal if the CDH assumption holds ElGamal is oneway 39 ie if you can solve the CDH problem you will be able to decrypt if the DDH assumption holds ElGamal is secure in the sense of indistinguishability o Formally if the DDH problem is hard relative to Set then the ElGamal encryption scheme has indistinguishable encryptions under a chosenplaintext attack CSE 4062260622 Fall 2009 Marina Blanton 26 F Security of ElGamal Encryption 0 Care must be taken when mapping messages to group elements CSE 4062260622 one least signi cant bit of discrete logarithm is easy to compute we say that an element y E z is a quadratic residue QR modulo p if there exists a E z such that y 512 mod p given a ciphertext an adversary can tell whether the underlying plaintext was a QR modulo p or not to ensure indistinguishability we need to make sure that all values we use will have the same value for that bit 2 thus we encode messages as a mod p only Fall 2009 j 27 Marina Blanton r ElGamal Encryption o More on quadratic residues a is called a quadratic residue QR modulo m is 512 E a mod m has solutions a is called a quadratic nonresidue QNR otherwise there are the same number p 1 2 of QRs and QNRs modulo prime p among numbers 1 p 1 if a is a QRN modulo prime p its square roots are b mod p 39 then one solution is g p 1 2 and the other one is not square roots are ef ciently computable CSE 4062260622 Fall 2009 Marina Blanton 28 ElGamal Encryption o Encryption with ElGamal becomes given a message m interpret it as a integer between 1 and q where q p 12 compute m m2 mod p and encrypt m upon decryption 39 obtain m 39 compute square roots m1 m2 of m modulo p 39 set m to the unique 1 g mi g q CSE 4062260622 Fall 2009 Marina Blanton 29 o The discrete logarithm problem is considered hard in groups modulo a large prime 0 Many constructions rely on it o ElGamal is an example of encryption that assumes hardness of discrete logarithm problem 0 Dif eHellman key exchange is built using similar assumptions two types of hardness assumptions are known as computational and decision Dif eHellman problems 0 ElGamal is CPAsecure under the DDH assumption CSE 4062260622 Fall 2009 Marina Blanton 30 Cryptography and Data Security CSE 4062260622 Fall 2009 Lecture 21 Authentication and Secure Communication in Practice 11 Department of Computer Science and Engineering University of Notre Dame F Secure Communication in Practice 0 Last time Secure Shell SSH Secure Socket Layer SSL and Transport Layer Security TLS protocols 0 Today Internet Security IPSec and Internet Key Exchange IKE protocols 39 provides authentication and encryption mechanisms at low network layer Kerberos a network authentication tool used in Windows operating system CSE 4062260622 Fall 2009 Marina Blanton 2 r Authentication Protocols for Internet Security 0 Many cryptographic techniques we study for protecting transmitted messages are thought of to be used at application level 0 Can protection at low level be effective for securing communication over the Internet if we can protect packet addressing information we can prevent manipulation of this information o The suite of authentication protocols standardized for internet security at IP level is called Internet Key Exchange IKE CSE 4062260622 Fall 2009 Marina Blanton 3 r Communications at Internet Protocol Layer 0 Internet is a huge open network of computers and devices called nodes 0 Each node is assigned a unique network address 0 A protocol that processes the transmission of messages using the network addresses is the Internet Protocol IP 0 Communications at the IP layer take the form of IP packets each packet has a xed size the data to be transmitted is partitioned into short chunks in an IP packet there is an IP header followed by the upperlayer data CSE 4062260622 Fall 2009 Marina Blanton 4 r Communications at Internet Protocol Layer 0 An unprotected IP packet IP header IP header source destination upper layer elds IP address IP address data V 1P packet o The upperlayer data contains speci cation of the protocol in the immediate upper layer eg transmission control protocol TCP data which are transmitted by the IP packet o Often an IP address is mapped to a domain name CSE 4062260622 Fall 2009 Marina Blanton 5 r Communications at Internet Protocol Layer 0 Example consider email communication let jamesb0nd121121121121 and missmoneypenny76767676 be two email addresses an email from Miss Moneypenny to James Bond at packet level looks like IPheader 76767676 121121121121 DearJames elds suppose they want to conduct con dential communications by using endtoend encryption with either a shared or public keys CSE 4062260622 Fall 2009 Marina Blanton 6 r Communications at Internet Protocol Layer o If endtoend encryption operates at the application level then information in the IP header is the subject of attacks which include IP spoo ng masquerading by using a fake source IP address snif ng eavesdropping session hijacking combination of masquerading and snif ng to take over a legitimate party s communication session 0 Virtually all active attacks that we ve seen so far require Mallory to perform manipulation at the IP level message interception parallel sessions maninthemiddle etc CSE 4062260622 Fall 2009 Marina Blanton 7 r Internet Protocol Security lPSec 0 Internet Protocol Security IPSec standard has been developed to add cryptographic protection to the IP header it stipulates a mandatory authentication protection for IP header it also allows for optional con dentiality protection for the endpointidentity information 0 With IPSec many active attacks are now prevented c To use IPSec for authentication there will be an additional header called the Authentication Header AH it is positioned between the IP header and the higherlayer data CSE 4062260622 Fall 2009 Marina Blanton 8 r Internet Protocol Security lPSec o The authentication header guarantees data integrity and data origin authentication of an IP packet authentication covers the IP payload and all IP header elds that do not change in transit unauthenticated elds are timetolive TTL header checksum etc o Authentication header diagram 8 bits 8 bits 16 bits Next header Payload length Reserved Security Parameters Index SP1 Sequence number Authentication data multiple of 32 bits CSE 4062260622 Fall 2009 Marina Blanton 9 r Internet Protocol Security lPSec o Authentication header elds Next header identi es the protocol of the transferred data Payload length contains the size of the AH Security Parameter Index SPI identi es the cryptographic algorithm and parameters used for authentication Sequence number is a monotonically increasing number used to prevent replay attacks Authentication data contains the integrity check value ICV CSE 4062260622 Fall 2009 Marina Blanton 10 r Internet Protocol Security lPSec 0 Con dentiality protection in IPSec con dentiality encryption is optional for IPSec for that purpose datagrams called Encapsulating Security Payload ESP are speci ed an ESP can follow an AH in an IP packet ESP also supports authentication 39 it can be invoked in encryptiononly authenticationonly modes or using both encryption and authentication unlike AH ESP does not protect the IP packet header CSE 4062260622 Fall 2009 Marina Blanton l l r Internet Protocol Security lPSec o ESP diagram 8 bits l 8 bits l 8 bits l 8 bits Security Parameters Index SP1 Sequence number Payload data multiple of 32 bits Padding 0 255 bytes Pad length Next header Authentication data multiple of 32 bits CSE 4062260622 Fall 2009 Marina Blanton 12 r Internet Protocol Security lPSec o ESP elds Security Parameters Index SPI now speci es the encryption algorithm and its parameters Sequence number has the same meaning as in the AH Payload data is the ciphertext of the con dential data Padding bytes are initialized with a series of increasing integer values 0x01 0x02 to bring the datagram length to a multiple of 32 bits Authentication data has a similar meaning to that of AH in ESP it is for integrity of data and is optional in AH it is for integrity of IP packet and is mandatory CSE 4062260622 Fall 2009 Marina Blanton 13 r Internet Protocol Security lPSec 0 Security associations CSE 4062260622 the notion of Security Association SA is central to IPSec an SA is uniquely identi ed by a triple SPI IP destination address Service Identi er 39 Service Identi er is either Authentication or ESP two nodes need to negotiate at least one SA for authentication and optionally a second one for con dentiality they also need to negotiate cryptographic keys this negotiation is achieved using the Internet Key Exchange IKE protocol Fall 2009 j 14 Marina Blanton r Internet Protocol Security lPSec 0 Internet Key Exchange IKE protocol IKE is the current IETF standard that includes authentication and authenticated key exchange protocols for IPSec it allows to negotiate 39 the mode and the corresponding services for it eg perfect forward secrecy for session keys endpoint identity hiding and mutual authentication 39 security attributes and parameters 39 authentication mechanisms 39 cryptographic algorithms these are collectively called Security Associations SAs CSE 4062260622 Fall 2009 Marina Blanton 15 r Internet Protocol Security lPSec o The IKE protocol consists of two phases Phase 1 39 assumes each participant has an identity the other party knows 39 associated with that identity is some cryptographic capability ie a preshared symmetric key or a reliable copy of a public key 39 this phase attempts to achieve mutual authentication and establish a shared session key Phase 2 39 can be invoked multiple times after Phase 1 relies on the shared key negotiated in Phase 1 can be used to setup multiple connections with different security properties and to secure higherlevel communications CSE 4062260622 Fall 2009 Marina Blanton l6 r Internet Protocol Security lPSec o IKE Phase 1 has several variants it includes protocols using preshared symmetric keys public keys for encryption and public keys for signature veri cation there are six message exchanges in the main mode 3 messages from the initiator and 3 messages from the responder a protocol based on authenticated Dif e Hellman and SIGMA is part of the speci cation 39 it s been criticized for a minor authentication failure deniability feature as in SKEME was added in IKEvZ CSE 4062260622 Fall 2009 Marina Blanton l7 r Internet Protocol Security lPSec o IPSec and IKE have been criticized the biggest critique is the complexity and lack of clarity the speci cation contains two many options and too much exibility it allows similar results to be achieved in different ways this makes it dif cult to evaluate it and easy to miss weaknesses furthermore some con gurations lead to an attack possibility nally integrity checking in ESP should be mandatory 39 most encryption algorithms cannot provide proper con dentiality protection without integrity protection CSE 4062260622 Fall 2009 Marina Blanton 18 F 0 Today a user might need to access various resources for related purposes suppose Alice is a member of an enterprise at work she has access to her projects at a project server she also can manage her own HR related issues at the HR server additionally she manages her patent ling at an intellectual property server etc o It is infeasible to require her to maintain different credentials for each task eg remember many passwords or carry many smartcards o A suitable network solution for this environment is the Kerberos Authentication Protocol CSE 4062260622 Fall 2009 Marina Blanton l9 F 0 Recall that Kerberos is a session key distribution scheme based on symmetric keys each user shares a longterm secret key with a trusted third party when Alice would like to talk to Bob she requests a session key from that trusted party 0 Windows 2000 XP 2003 Vista 7 uses Kerberos as its network authentication basis it uses Kerberos version 5 which is a free software it can be downloaded from httpwebmitedukerberoswww the exportation restrictions on cryptographic software make it available only in the US CSE 4062260622 Fall 2009 Marina Blanton 20 F o The Kerberos Authentication Protocol consists of a suite of subprotocols called exchanges 0 Three subprotocols are used for authentication the Authentication Service AS exchange 39 runs between a client C and an authentication server AS the TicketGranting Service TGS exchange runs between C and a ticket granting server TGS after the AS exchange the clientserver Authentication Application AP exchange 39 runs between C and an application server 539 after the TGS exchange CSE 4062260622 Fall 2009 Marina Blanton 21 F c There are ve principals participating in the exchanges with the following roles U a human user who gives instructions to her client process U appears in the protocols only as a message 39 each user memorizes a password as her singlesignon credential for Kerberos C a client process that requests network service on behalf of user in the authentication service exchange C will need U s Kerberos system credential 39 this credential is given to C by prompting U for her password CSE 4062260622 Fall 2009 Marina Blanton 22 F o Kerberos principals cont KDC key distribution center is a collective name for the following two authentication servers AS an authentication server 39 it receives authentication service request ASREQ from C 39 it responds with a ticket granting ticket TGT which will be used by C in a subsequent TGS exchange 39 a TGT sent to a client has two parts one part is for C to use encrypted under a key derived from a user s singlesignon password another part is for a ticket granting server TGS to use encrypted with the user s longterm key CSE 4062260622 Fall 2009 Marina Blanton 23 o Kerberos principals cont AS authentication server cont 39 both parts of the reply contain a ticket session key koyTGS to be shared between C and a ticket granting server TGS a ticket granting server 39 it receives a ticket granting request TGSREQ from C in a TGS exchange it responds with a ticket TKT with allows C to use it in a subsequent AP exchange with an application server 539 TKT has two parts one part is for C to use encrypted under the session key koyTGS another part is for S to use encrypted under longterm K SIG S CSE 4062260622 Fall 2009 Marina Blanton 24 F o Kerberos principals cont TGS ticket granting server cont 39 both parts of a TKT contain a new application session key 9075 to be shared between C and S in an AP exchange 539 an application server which provides an application resource to C 39 it receives an application request APREQ from C in an AP exchange it responds with application reply APREP which entitles C to an application service 0 KDC is divided into AS and TGS to give exibility for very large networks and achieve single signon capabilities CSE 4062260622 Fall 2009 Marina Blanton 25 r Kerberos o Kerberos exchanges 3 TGSREQ 4 TKT RG1 5 APREQ 1 ASREQ 6 APREP CSE 4062260622 Fall 2009 Marina Blanton 26 F The Kerberos Exchanges o Authentication Service AS exchange ASREQ C sends to AS U TGS L1 71 0 indicates that U would like to communicate to TGS L1 is lifetime for bookkeeping and random r1 freshness information TGT AS sends to C U TQTGS TGTC where TCTGS EnCKAsyTGSW C7TGS kCTGSa t1 t2 TGTC39 EnCKUCPGSa kCTGSa t1 752 T1 t1 is start time t2 is end time 39 if all validation checks succeed C accepts the ticket session key kC7TGS and the ticket TQTGS CSE 4062260622 Fall 2009 Marina Blanton 27 F The Kerberos Exchanges o TicketGranting Service TGS exchange the format is similar to AS exchange except a request now contains an authenticator TGSREQ C sends to TGS 8 L2 r2 TQTGS AQTGS TKT TGS sends to C U T075 TKTC where TQS EnCKsyTGSW 0 3 160571517752 TKTC EanQTGSQS39a k0757t17t27r2 AQTGS EanQmAQ t3 the use of authenticator shows to TGS that the client used the ticket session key kQTGS 39 TGS checks its local time to con rm that the difference is allowable CSE 4062260622 Fall 2009 Marina Blanton 28 F The Kerberos Exchanges 0 Application Service AP exchange C uses the key 075 and the ticket T075 to obtain an application service from an application server 539 APREQ C sends to S T0755 A075 APREP 8 sends to C A 570 where AQS EanQSw 7i4 Asp EanQSt4 0 Data integrity of all ciphertexts in the key exchanges must be preserved and veri ed CSE 4062260622 Fall 2009 Marina Blanton 29 o IPSec and IKE IP packet level integrity and con dentiality o SSL and TLS socket level secure channel for all applications 0 Kerberos network authentication framework that allows for single signon 0 Secure Shell secure remote login and le transfer CSE 4062260622 Fall 2009 Marina Blanton 30 Cryptography and Data Security CSE 4062260622 Fall 2009 Lecture 6 Digital Encryption Standard DES Department of Computer Science and Engineering University of Notre Dame p A K Lecture Outline 0 Previously we talked about de ning security for encryption using theoretical models for encryption o In this lecture move to practical constructions learn about design principles of block ciphers learn about how DES works CSE 4062260622 Fall 2009 Marina Blanton 2 F Symmetric Encryption 0 Block ciphers are used in practice to implement pseudorandom permutations it is desirable to base secure encryption on weaker assumptions than existence of pseudorandom permutations o All block ciphers are heuristics no proofs of security 0 Such algorithms are normally very fast can be used as primitives in more complex cryptographic protocols CSE 4062260622 Fall 2009 Marina Blanton 3 r Block Ciphers o The algorithm maps an nbit plaintext block to an nbit ciphertext block 0 Most modern block ciphers are product ciphers we sequentially apply more than one obfuscation technique to the message 0 A common design for an algorithm is to proceed in iterations one iteration is called a round each round consists of similar operations iterations are used to amplify obfuscation CSE 4062260622 Fall 2009 Marina Blanton 4 r Design Principles of Block Ciphers o Specifying a random permutation on an nbit block requires huge amount of storage there are 2quot permutations each can be encoded in Iog2n m n2quot bits how do we achieve similar effect with reasonable resources 0 Confusiondiffusion paradigm split a block into small chunks de ne a permutation on each block separately confusion mix outputs from different chunks by rearranging bits diffusion repeat to strengthen the result CSE 4062260622 Fall 2009 Marina Blanton 5 r Design Principles of Block Ciphers o Substitutionpermutation networks since a permutation on a block can be speci ed as a lookup table this is called substitution instead of having substitutions de ned by the key such functions are xed and applied to messages and keys mixing algorithm is called mixing permutation CSE 4062260622 Fall 2009 Marina Blanton 6 Design Principles of Block Ciphers o For this type of algorithm to be reversible each operation needs to be invertible CSE 4062260622 Fall 2009 Marina Blanton 7 F Design Principles of Block Ciphers 0 Let s denote one iteration or round by function g o The initial state so is the message m itself 0 In round 139 g s input is round key by and state 5141 g s output is state Si 0 The ciphertext c is the nal state 51W where N 7 is the number of rounds o Decryption algorithm applies 9 1 iteratively the order of round keys is reversed set 51W 2 c compute 5141 9 109 51 CSE 4062260622 Fall 2009 Marina Blanton 8 r Design Principles of Block Ciphers 0 Another way to realize confusiondiffusion paradigm is through Feistel network in Feistel network each state is divided into halves of the same length Li and Bi in one round 39 Li Ri l 39 R Li l EB fUCz Ri l o Are there any advantages over the previous design CSE 4062260622 Fall 2009 Marina Blanton 9 r Design Principles of Block Ciphers 0 Operations no longer need to be reversible as the inverse of the algorithm is not used reverse one round s computation as R141 2 Li and Li l R 613 fatty Ri l CSE 4062260622 Fall 2009 Marina Blanton 10 r Design Principles of Block Ciphers o In both types of networks the substitution and permutation algorithms must be carefully designed choosing random substitutionpermutation strategies leads to signi cantly weaker ciphers each bit difference in Sbox input creates at least 2bit difference in its output mixing permutation ensures that difference in one Sbox propagates to at least 2 S boxes in next round CSE 4062260622 Fall 2009 Marina Blanton l l r Block Ciphers 0 Larger key size means greater security for 71bit keys brute force search takes 2 2 time on average 0 More rounds often provide better protection the number of rounds must be large enough for proper mixing 0 Larger block size offers increased security security of a cipher also depends on the block length CSE 4062260622 Fall 2009 Marina Blanton 12 r Data Encryption Standard DES o In 1973 NIST published a solicitation for cryptosystems o NIST stands for the National Institute of Standards and Technology previously the National Bureau of Standards was founded in 1901 within technology administration of the US Commerce Department develops and promotes standards and technology cryptographic standards are published in the Federal Information Processing Standards FIPS CSE 4062260622 Fall 2009 Marina Blanton 13 F o DES was developed by IBM as a modi cation of an earlier system Lucifer o DES was adopted as a standard in 1977 o It was expected to be used as a standard for 10 15 years 0 Was replaced only in 2001 with AES Advanced Encryption Standard 0 DES characteristics key size is 56 bits block size is 64 bits number of rounds is 16 CSE 4062260622 Fall 2009 Marina Blanton l4 W o DES uses Feistel network Feistel network is used in many block ciphers such as DES RC5 etc not used in AES in DES each Li and Bi is 32 bits long ki is 48 bits long 32 bits 32 bits Li l V 32 bits x 32 bits V 32 bits w w m CSE 4062260622 Fall 2009 Marina Blanton 15 F o DES has a xed initial permutation I P prior to 16 rounds of encryption o The inverse permutation I P 1 is applied at the end CSE 4062260622 Fall 2009 Marina Blanton l6 W o The f function fk R141 1 rst expands R141 from 32 to 48 bits ki is 48 bits long XORs expanded R141 with ki applies substitution to the result using Sboxes JAMN and nally permutes the value CSE 4062260622 Fall 2009 Marina Blanton l7 DES f Function 32 bits iRzgl E 48 bits v c 9239 7 48 bits 48 bits 1 6 bits t 4 bits 32 bits 32 bits CSE 4062260622 Fall 2009 Marina Blanton 18 0 Example 5391 they are crucial for the security of the cipher Sboxes are the only nonlinear elements in DES design W c There are 8 Sboxes Marina Blanton 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 input to each Sbox is 6 bits b1b2b3b4b5b6 row 91196 column b2b3b4b5 output is 4 bits CSE 4062260622 Fall 2009 j 19 W o More about Sboxes some of the design choices of S boxes weren t public which triggered criticism in late 1980s early 1990s differential cryptanalysis techniques were discovered it was then revealed that DES S boxes were designed to prevent such attacks IBM researchers knew about such cryptanalysis almost 20 years before the techniques were discovered by others CSE 4062260622 Fall 2009 Marina Blanton 20 r DES Key Schedule 0 Key computation consists of Ci l Di l o 28 bits i i 28 bits clrcular shlft Left shift Left shift permutation contraction kl 48 b1ts v v 0239 Di CSE 4062260622 Fall 2009 Marina Blanton 21 W 0 Why does decryption work round function g is invertible 39 compute L141 R fki Li 39 compute R141 2 Li in the beginning apply I P and at the end apply I P 1 round keys 1916 k1 and the f function are computed as before CSE 4062260622 Fall 2009 Marina Blanton 22 K Attacks on DES o The key size is 56 bits is this too small 0 Is the design nonlinear enough to be hard to break 0 Are there cryptanalysis techniques that we can use against DES two techniques exist linear and differential cryptanalysis CSE 4062260622 Fall 2009 Marina Blanton 23 K DES Weak Keys o The master key k is used to generate 16 round keys 0 Some keys result in the same round key to be generated in more than one round this reduces complexity of the cipher 0 Solution check for weak keys at key generation 0 DES has 4 weak keys 0000000 0000000 0000000 FFFFFFF FFFFFFF 0000000 FFFFFFF FFFFFFF CSE 4062260622 Fall 2009 Marina Blanton 24 K Attacks on DES o Brute force attack try all possible 256 keys timeconsuming but no storage requirements 0 It was conjectured in 1970s that a cracker machine could be built for 20 million 0 In 1990s RSA Laboratories called several DES challenges Challenge II2 was announced in 1998 39 the winner was Electronic Frontier Foundation EFF 39 they built a DES Cracker machine for less than 250000 it found the key in 56 hours and searched 88 billion keys per second CSE 4062260622 Fall 2009 Marina Blanton 25 K Attacks on DES 0 RSA Laboratories called Challenge 111 in 1999 was solved in a record time cooperative effort of the DES Cracker and a worldwide network of 100000 computers the key was found in 22 hours 15 minutes over 245 billion keys were tested per second httpwwwdistributednetdes CSE 4062260622 Fall 2009 Marina Blanton 26 K Attacks on DES 0 Differential Cryptanalysis complex technique that tracks the behavior of pairs of text blocks evolving along each round setAmm1m2andAc c162 distribution of Ac s given Am s may reveal information about the key 0 Not effective against DES attack on 8round DES requires 238 known plaintext ciphertext pairs attack on 16round DES requires 247 chosen plaintexts CSE 4062260622 Fall 2009 Marina Blanton 27 K Attacks on DES 0 Linear Cryptanalysis a more recent technique 1993 based on nding linear approximations to describe DES transformations the goal is to nd some bits of the key 0 How does DES do the attack has no practical implication on the cipher attack on 8 round DES requires 221 known plaintexts attack on 16round DES requires 243 known plaintexts CSE 4062260622 Fall 2009 Marina Blanton 28 r Increasing Security of DES o The best attack against DES is brute force search DES uses a 56bit key and this raised concerns 0 One proposed solution is double DES apply DES twice by using two different keys k1 and k2 encryption c Ek2Ek1 decryption m Dkl Df2 o The resulting key is 2 56 1 12 bits so it is more secure is it really CSE 4062260622 Fall 2009 Marina Blanton 29 K MeetintheMiddle Attack o The goal of the attack is given pairs m 6 nd keys k1 and kg 0 It is based on the observation that C Ek2Ek1m and Ek1m Dk2C 0 Thus the idea is to try all possible 256 keys for k1 and all possible keys for k2 until a match is found CSE 4062260622 Fall 2009 Marina Blanton 30 K MeetintheMiddle Attack o c Eb and Ekl Dk2c 0 Algorithm steps encrypt m with all possible 256 keys k1 store all pairs k1 Ekl sorted by Ekl decrypt c with all possible 256 keys kg for each decrypted result D k2 c check to see if there is a match Dk2C Elem when a match is found verify the keys on another pair 771 c if the second pair matched accept the keys k1 and kg 0 The overall effort is on the order of 256 CSE 4062260622 Fall 2009 Marina Blanton 31 K MeetintheMiddle Attack 0 Why do we need the second pair CSE 4062260622 block size is 64 bits so for a given m there are 264 potential ciphertexts with two 56bit keys there are 21 12 potential double keys that can map m to c for a single pair m c the number of double keys k1 k2 that produce 6 Ek2Ek2 is 2112264 248 thus 248 false alarms for a single pair are expected with one more pair 771 6 extra 64 bits of known text the alarm rate goes down to 248264 2 1216 Fall 2009 j 32 Marina Blanton