Slide1: Reference: Cryptography and Information Security by Dr. Pachghare Prepared for Students, BE Computer Engineering Unit III: Public Key and Management
Slide2: Index Public Key Cryptography, RSA Algorithm Key Distribution Elliptic Curve: Arithmetic, Authentication methods, Message Digest, Kerberos, X.509 Authentication service, Standards (DSS) 02/12/16 2 Public Key and Management
Slide3: Encryption Methods
Slide4: Public-Key Cryptography probably most significant advance in the 3000 year history of cryptography uses two keys – a public & a private key asymmetric since parties are not equal uses clever application of number theoretic concepts to function 02/12/16 4 Public Key and Management
Slide5: Why Public-Key Cryptography? developed to address two key issues: key distribution – how to have secure communications in general without having to trust a KDC with your key digital signatures – how to verify a message comes intact from the claimed sender public invention due to Whitfield Diffie & Martin Hellman at Stanford Uni in 1976 known earlier in classified community 02/12/16 5 Public Key and Management
Slide6: Public-Key Cryptography public-key/two-key/asymmetric cryptography involves the use of two keys: a public-key , which may be known by anybody, and can be used to encrypt messages , and verify signatures a private-key , known only to the recipient, used to decrypt messages , and sign (create) signatures is asymmetric because those who encrypt messages or verify signatures cannot decrypt messages or create signatures 02/12/16 6 Public Key and Management
Slide7: Public-Key Cryptography 02/12/16 7 Public Key and Management
Slide8: Public-Key Characteristics Public-Key algorithms rely on two keys where: it is computationally infeasible to find decryption key knowing only algorithm & encryption key it is computationally easy to en/decrypt messages when the relevant (en/decrypt) key is known either of the two related keys can be used for encryption, with the other used for decryption (for some algorithms) 02/12/16 8 Public Key and Management
Slide9: Public-Key Cryptosystems 02/12/16 9 Public Key and Management
Slide10: Public-Key Applications can classify uses into 3 categories: encryption/decryption (provide secrecy) digital signatures (provide authentication) key exchange (of session keys) some algorithms are suitable for all uses, others are specific to one 02/12/16 10 Public Key and Management
Slide11: RSA by Rivest, Shamir & Adleman of MIT in 1977 best known & widely used public-key scheme based on exponentiation in a finite (Galois) field over integers modulo a prime uses large integers (eg. 1024 bits) security due to cost of factoring large numbers 02/12/16 11 Public Key and Management
Slide12: RSA Key Setup each user generates a public/private key pair by: selecting two large primes at random: p, q computing their system modulus n=p.q note ø(n)=(p-1)(q-1) selecting at random the encryption key e where 1<e<ø(n), gcd(e,ø(n))=1 solve following equation to find decryption key d e.d=1 mod ø(n) and 0 ≤ d ≤ n publish their public encryption key: PU={e,n} keep secret private decryption key: PR={d,n} 02/12/16 12 Public Key and Management
Slide13: RSA Use to encrypt a message M the sender: obtains public key of recipient PU={e,n} computes: C = M e mod n, where 0 ≤ M < n to decrypt the ciphertext C the owner: uses their private key PR={d,n} computes: M = C d mod n note that the message M must be smaller than the modulus n (block if needed) 02/12/16 13 Public Key and Management
Slide14: Why RSA Works because of Euler's Theorem: a ø(n) mod n = 1 where gcd(a,n)=1 in RSA have: n=p.q ø(n)=(p-1)(q-1) carefully chose e & d to be inverses mod ø(n) hence e.d=1+k.ø(n) for some k hence : C d = M e.d = M 1+k.ø(n) = M 1 .(M ø(n) ) k = M 1 .(1) k = M 1 = M mod n 02/12/16 14 Public Key and Management
Slide15: RSA Example - Key Setup Select primes: p =17 & q =11 Compute n = pq =17 x 11=187 Compute ø( n )=( p– 1)( q- 1)=16 x 10=160 Select e: gcd(e,160)=1; choose e =7 Determine d: de= 1 mod 160 and d < 160 Value is d=23 since 23 x 7=161= 10 x 16+1 Publish public key PU={7,187} Keep secret private key PR={23, 187} 02/12/16 15 Public Key and Management
Slide16: RSA Example - En/Decryption sample RSA encryption/decryption is: given message M = 88 (nb. 88<187) encryption: C = 88 7 mod 187 = 11 decryption: M = 11 23 mod 187 = 88 02/12/16 16 Public Key and Management
Slide17: Example This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 can probably even do it by hand). Select primes p=11, q=3. n = pq = 11.3 = 33 phi = (p-1)(q-1) = 10.2 = 20 Choose e=3 Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1), and check gcd(e, q-1) = gcd(3, 2) = 1 therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1 Compute d such that ed ≡ 1 (mod phi) i.e. compute d = e-1 mod phi = 3-1 mod 20 i.e. find a value for d such that phi divides (ed-1) i.e. find d such that 20 divides 3d-1. Simple testing (d = 1, 2, ...) gives d = 7 Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi. Public key = (n, e) = (33, 3) Private key = (n, d) = (33, 7). This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message m = 7, c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13. Hence the ciphertext c = 13. To check decryption we compute m = c^d mod n 02/12/16 17 Public Key and Management
Slide18: RSA Security possible approaches to attacking RSA are: brute force key search (infeasible given size of numbers) mathematical attacks (based on difficulty of computing ø(n), by factoring modulus n) timing attacks (on running of decryption) chosen ciphertext attacks (given properties of RSA) 02/12/16 18 Public Key and Management
Slide19: Key Managment
Slide20: Key Management public-key encryption helps to address key distribution problems have two aspects of this: distribution of public keys use of public-key encryption to distribute secret keys 02/12/16 20 Public Key and Management
Slide21: Distribution of Public Keys can be considered as using one of: public announcement publicly available directory public-key authority public-key certificates 02/12/16 21 Public Key and Management
Slide22: Public Announcement users distribute public keys to recipients or broadcast to community at large eg. append PGP keys to email messages or post to news groups major weakness is forgery anyone can create a key claiming to be someone else and broadcast it 02/12/16 22 Public Key and Management
Slide23: Publicly Available Directory can obtain greater security by registering keys with a public directory directory must be trusted with properties: contains {name,public-key} entries participants register securely with directory participants can replace key at any time directory is periodically published directory can be accessed electronically still vulnerable to tampering or forgery 02/12/16 23 Public Key and Management
Slide24: Public-Key Authority improve security by tightening control over distribution of keys from directory has properties of directory and requires users to know public key for the directory then users interact with directory to obtain any desired public key securely does require real-time access to directory when keys are needed 02/12/16 24 Public Key and Management
Slide25: Public-Key Authority 02/12/16 25 Public Key and Management
Slide26: Public-Key Certificates certificates allow key exchange without real-time access to public-key authority a certificate binds identity to public key usually with other info such as period of validity, rights of use etc with all contents signed by a trusted Public-Key or Certificate Authority (CA) can be verified by anyone who knows the public-key authorities public-key 02/12/16 26 Public Key and Management
Slide27: Public-Key Certificates 02/12/16 27 Public Key and Management
Slide28: Public-Key D istribution of Secret Keys use previous methods to obtain public-key can use for secrecy or authentication but public-key algorithms are slow so usually want to use private-key encryption to protect message contents hence need a session key have several alternatives for negotiating a suitable session 02/12/16 28 Public Key and Management
Slide29: Simple Secret Key Distribution proposed by Merkle in 1979 A generates a new temporary public key pair A sends B the public key and their identity B generates a session key K sends it to A encrypted using the supplied public key A decrypts the session key and both use problem is that an opponent can intercept and impersonate both halves of protocol 02/12/16 29 Public Key and Management
Slide30: Public-Key Distribution of Secret Keys if have securely exchanged public-keys: 02/12/16 30 Public Key and Management
Slide31: Hybrid Key Distribution retain use of private-key KDC shares secret master key with each user distributes session key using master key public-key used to distribute master keys especially useful with widely distributed users 02/12/16 31 Public Key and Management
Slide32: Diffie-Hellman Key Exchange
Slide33: Diffie-Hellman Key Exchange first public-key type scheme proposed by Diffie & Hellman in 1976 along with the exposition of public key concepts is a practical method for public exchange of a secret key used in a number of commercial products 02/12/16 33 Public Key and Management
Slide34: Diffie-Hellman Key Exchange a public-key distribution scheme cannot be used to exchange an arbitrary message used to exchange a common key known only to the two participants value of key depends on the participants (and their private and public key information) security relies on the difficulty of computing discrete logarithms (similar to factoring) – hard 02/12/16 34 Public Key and Management
Slide35: Diffie-Hellman Setup all users agree on global parameters: large prime integer q a being a primitive root mod q each user (eg. A) generates their key chooses a secret key (number): x A < q compute their public key : y A = a x A mod q each user makes public that key y A 02/12/16 35 Public Key and Management
Slide36: Diffie-Hellman Key Exchange shared session key for users A & B is K AB : K AB = a x A. x B mod q = y A x B mod q (which B can compute) = y B x A mod q (which A can compute) K AB is used as session key in private-key encryption scheme between Alice and Bob if Alice and Bob subsequently communicate, they will have the same key as before, unless they choose new public-keys attacker needs an x, must solve discrete log 02/12/16 36 Public Key and Management
Slide37: 02/12/16 37 Public Key and Management
Slide38: 02/12/16 38 Public Key and Management
Slide39: Diffie-Hellman Example users Alice & Bob who wish to swap keys: agree on prime q=353 and a =3 select random secret keys: A chooses x A =97, B chooses x B =233 compute respective public keys: y A = 3 97 mod 353 = 40 (Alice) y B = 3 233 mod 353 = 248 (Bob) compute shared session key as: K AB = y B x A mod 353 = 248 97 = 160 (Alice) K AB = y A x B mod 353 = 40 233 = 160 (Bob) 02/12/16 39 Public Key and Management
Slide40: Key Exchange Protocols users could create random private/public D-H keys each time they communicate users could create a known private/public D-H key and publish in a directory, then consulted and used to securely communicate with them both of these are vulnerable to a meet-in-the-Middle Attack authentication of the keys is needed 02/12/16 40 Public Key and Management
Slide41: Elliptic Curve Cryptography majority of public-key crypto (RSA, D-H) use either integer or polynomial arithmetic with very large numbers/polynomials imposes a significant load in storing and processing keys and messages an alternative is to use elliptic curves offers same security with smaller bit sizes newer, but not as well analysed 02/12/16 41 Public Key and Management
Slide42: Real Elliptic Curves an elliptic curve is defined by an equation in two variables x & y, with coefficients consider a cubic elliptic curve of form y 2 = x 3 + ax + b where x,y,a,b are all real numbers also define zero point O have addition operation for elliptic curve geometrically sum of Q+R is reflection of intersection R 02/12/16 42 Public Key and Management
Slide43: Real Elliptic Curve Example 02/12/16 43 Public Key and Management
Slide44: Finite Elliptic Curves Elliptic curve cryptography uses curves whose variables & coefficients are finite have two families commonly used: prime curves E p (a,b) defined over Z p use integers modulo a prime best in software binary curves E 2 m (a,b) defined over GF(2 n ) use polynomials with binary coefficients best in hardware 02/12/16 44 Public Key and Management
Slide45: Elliptic Curve Cryptography ECC addition is analog of modulo multiply ECC repeated addition is analog of modulo exponentiation need “hard” problem equiv to discrete log Q=kP, where Q,P belong to a prime curve is “easy” to compute Q given k,P but “hard” to find k given Q,P known as the elliptic curve logarithm problem Certicom example: E 23 (9,17) 02/12/16 45 Public Key and Management
Slide46: ECC Diffie-Hellman can do key exchange analogous to D-H users select a suitable curve E p (a,b) select base point G=(x 1 ,y 1 ) with large order n s.t. nG=O A & B select private keys n A <n, n B <n compute public keys: P A =n A G, P B =n B G compute shared key: K =n A P B , K =n B P A same since K =n A n B G 02/12/16 46 Public Key and Management
Slide47: ECC Encryption/Decryption several alternatives, will consider simplest must first encode any message M as a point on the elliptic curve P m select suitable curve & point G as in D-H each user chooses private key n A <n and computes public key P A =n A G to encrypt P m : C m ={kG, P m +kP b }, k random decrypt C m compute: P m + k P b – n B ( kG ) = P m + k ( n B G )– n B ( kG ) = P m 02/12/16 47 Public Key and Management
Slide48: ECC Security relies on elliptic curve logarithm problem fastest method is “Pollard rho method” compared to factoring, can use much smaller key sizes than with RSA etc for equivalent key lengths computations are roughly equivalent hence for similar security ECC offers significant computational advantages 02/12/16 48 Public Key and Management
Slide49: Comparable Key Sizes for Equivalent Security Symmetric scheme (key size in bits) ECC-based scheme (size of n in bits) RSA/DSA (modulus size in bits) 56 112 512 80 160 1024 112 224 2048 128 256 3072 192 384 7680 256 512 15360 02/12/16 49 Public Key and Management
Slide50: Message Authentication
Slide51: Message Authentication message authentication is concerned with: protecting the integrity of a message validating identity of originator non-repudiation of origin (dispute resolution) will consider the security requirements then three alternative functions used: message encryption message authentication code (MAC) hash function 02/12/16 51 Public Key and Management
Slide52: Security Requirements disclosure traffic analysis masquerade content modification sequence modification timing modification source repudiation destination repudiation 02/12/16 52 Public Key and Management
Slide53: Message Encryption message encryption by itself also provides a measure of authentication if symmetric encryption is used then: receiver know sender must have created it since only sender and receiver now key used know content cannot of been altered if message has suitable structure, redundancy or a checksum to detect any changes 02/12/16 53 Public Key and Management
Slide54: Message Encryption if public-key encryption is used: since anyone potentially knows public-key however if sender signs message using their private-key then encrypts with recipients public key have both secrecy and authentication again need to recognize corrupted messages 02/12/16 54 Public Key and Management
Slide55: Message Authentication Code (MAC) generated by an algorithm that creates a small fixed-sized block depending on both message and some key like encryption though need not be reversible appended to message as a signature receiver performs same computation on message and checks it matches the MAC provides assurance that message is unaltered and comes from sender 02/12/16 55 Public Key and Management
Slide56: Message Authentication Code 02/12/16 56 Public Key and Management
Slide57: Message Authentication Codes as shown the MAC provides authentication can also use encryption for secrecy generally use separate keys for each can compute MAC either before or after encryption is generally regarded as better done before why use a MAC? sometimes only authentication is needed note that a MAC is not a digital signature 02/12/16 57 Public Key and Management
Slide58: 02/12/16 58 Public Key and Management
Slide59: MAC Properties a MAC is a cryptographic checksum MAC = C K (M) condenses a variable-length message M using a secret key K to a fixed-sized authenticator is a many-to-one function potentially many messages have same MAC 02/12/16 59 Public Key and Management
Slide60: Requirements for MACs taking into account the types of attacks need the MAC to satisfy the following: MACs should be uniformly distributed MAC should depend equally on all bits of the message 02/12/16 60 Public Key and Management
Slide61: Hash Functions condenses arbitrary message to fixed size h = H(M) usually assume that the hash function is public and not keyed hash used to detect changes to message can use in various ways with message most often to create a digital signature 02/12/16 61 Public Key and Management
Slide62: Hash Functions & Digital Signatures 02/12/16 62 Public Key and Management
Slide63: 02/12/16 63 Public Key and Management
Slide64: 02/12/16 64 Public Key and Management
Slide65: Requirements for Hash Functions can be applied to any sized message M produces fixed-length output h is easy to compute h=H(M) for any message M 02/12/16 65 Public Key and Management
Slide66: Simple Hash Functions are several proposals for simple functions based on XOR of message blocks not secure since can manipulate any message and either not change hash or change hash also need a stronger cryptographic function 02/12/16 66 Public Key and Management
Slide67: Hash and MAC Algorithms Hash Functions condense arbitrary size message to fixed size by processing message in blocks through some compression function either custom or block cipher based Message Authentication Code (MAC) fixed sized authenticator for some message to provide authentication for message by using block cipher mode or hash function 02/12/16 67 Public Key and Management
Slide68: Hash Algorithm Structure 02/12/16 68 Public Key and Management
Slide69: Secure Hash Algorithm SHA originally designed by NIST in 1993 was revised in 1995 as SHA-1 US standard for use with DSA signature scheme RFC3174 the algorithm is SHA, the standard is SHS based on design of MD4 with key differences produces 160-bit hash values recent 2005 results on security of SHA-1 have raised concerns on its use in future applications 02/12/16 69 Public Key and Management
Slide70: Revised Secure Hash Standard NIST issued revision FIPS (federal information processing standard) 180-2 in 2002 adds 3 additional versions of SHA SHA-256, SHA-384, SHA-512 designed for compatibility with increased security provided by the AES cipher structure & detail is similar to SHA-1 hence analysis should be similar but security levels are rather higher 02/12/16 70 Public Key and Management
Slide71: Keyed Hash Functions as MACs want a MAC based on a hash function because hash functions are generally faster code for crypto hash functions widely available hash includes a key along with message original proposal: KeyedHash = Hash(Key|Message) some weaknesses were found with this eventually led to development of HMAC 02/12/16 71 Public Key and Management
Slide72: HMAC specified as Internet standard RFC2104 uses hash function on the message: HMAC K = Hash[(K + XOR opad)|| Hash[(K + XOR ipad)||M)]] where K + is the key padded out to size and opad, ipad are specified padding constants overhead is just 3 more hash calculations than the message needs alone any hash function can be used eg. MD5, SHA-1, RIPEMD-160, Whirlpool 02/12/16 72 Public Key and Management
Slide73: HMAC Overview 02/12/16 73 Public Key and Management
Slide74: HMAC Overview H = embedded hash function (e.g., MD5, SHA-1, RIPEMD-160) IV = initial value input to hash function M = message input to HMAC (including the padding specified in the embedded hash function) Yi i th block of M, 0 i (L – 1) L number of blocks in M b number of bits in a block n length of hash code produced by embedded hash function K secret key; recommended length is n; if key length is greater than b, the key is input to the hash function to produce an n-bit key 02/12/16 74 Public Key and Management
Slide75: HMAC Overview K+ K padded with zeros on the left so that the result is b bits in length ipad 00110110 (36 in hexadecimal) repeated b/8 times opad 01011100 (5C in hexadecimal) repeated b/8 times Then HMAC can be expressed as HMAC K = Hash[(K + XOR opad)|| Hash[(K + XOR ipad)||M)]] We can describe the algorithm as follows. 1. Append zeros to the left end of K to create a b-bit string K + (e.g., if is of length 160 bits and , then will be appended with 44 zeroes). 2. XOR (bitwise exclusive-OR) K + with ipad to produce the b-bit block S i 3. Append M to S i . 4. Apply H to the stream generated in step 3. 5. XOR K + with opad to produce the b-bit block S o . 6. Append the hash result from step 4 to S o . 7. Apply H to the stream generated in step 6 and output the result. 02/12/16 75 Public Key and Management
Slide76: HMAC Security proved security of HMAC relates to that of the underlying hash algorithm attacking HMAC requires either: brute force attack on key used birthday attack (but since keyed would need to observe a very large number of messages) choose hash function used based on speed verses security constraints 02/12/16 76 Public Key and Management
Slide77: Kerberos 02/12/16 Public Key and Management
Slide78: Kerberos trusted key server system from MIT provides centralised private-key third-party authentication in a distributed network allows users access to services distributed through network without needing to trust all workstations rather all trust a central authentication server two versions in use: 4 & 5 02/12/16 78 Public Key and Management
Slide79: Kerberos Requirements its first report identified requirements as: secure reliable transparent scalable implemented using an authentication protocol based on Needham-Schroeder 02/12/16 79 Public Key and Management
Slide80: Kerberos v4 Overview a basic third-party authentication scheme have an Authentication Server (AS) users initially negotiate with AS to identify self AS provides a non-corruptible authentication credential (ticket granting ticket TGT) have a Ticket Granting server (TGS) users subsequently request access to other services from TGS on basis of users TGT 02/12/16 80 Public Key and Management
Slide81: Kerberos v4 Dialogue obtain ticket granting ticket from AS once per session obtain service granting ticket from TGT for each distinct service required client/server exchange to obtain service on every service request 02/12/16 81 Public Key and Management
Slide82: Kerberos 4 Overview 02/12/16 82 Public Key and Management
Slide83: Kerberos Area a Kerberos environment consists of: a Kerberos server a number of clients, all registered with server application servers, sharing keys with server this is termed a area typically a single administrative domain if have multiple areas, their Kerberos servers must share keys and trust 02/12/16 83 Public Key and Management
Slide84: Kerberos Realms 02/12/16 84 Public Key and Management
Slide85: Kerberos Version 5 developed in mid 1990’s specified as Internet standard RFC 1510 provides improvements over v4 addresses environmental shortcomings encryption alg, network protocol, byte order, ticket lifetime, authentication forwarding, interrealm auth and technical deficiencies double encryption, non-std mode of use, session keys, password attacks 02/12/16 85 Public Key and Management
Slide86: X.509 Authentication Service part of CCITT X.500 directory service standards distributed servers maintaining user info database defines framework for authentication services directory may store public-key certificates with public key of user signed by certification authority also defines authentication protocols uses public-key crypto & digital signatures algorithms not standardised, but RSA recommended X.509 certificates are widely used 02/12/16 86 Public Key and Management
Slide87: X.509 Certificates issued by a Certification Authority (CA), containing: version (1, 2, or 3) serial number (unique within CA) identifying certificate signature algorithm identifier issuer X.500 name (CA) period of validity (from - to dates) subject X.500 name (name of owner) subject public-key info (algorithm, parameters, key) issuer unique identifier (v2+) subject unique identifier (v2+) extension fields (v3) signature (of hash of all fields in certificate) notation CA<<A>> denotes certificate for A signed by CA 02/12/16 87 Public Key and Management
Slide88: X.509 Certificates 02/12/16 88 Public Key and Management
Slide89: Obtaining a Certificate any user with access to CA can get any certificate from it only the CA can modify a certificate because cannot be forged, certificates can be placed in a public directory 02/12/16 89 Public Key and Management
Slide90: CA Hierarchy if both users share a common CA then they are assumed to know its public key otherwise CA's must form a hierarchy use certificates linking members of hierarchy to validate other CA's each CA has certificates for clients (forward) and parent (backward) each client trusts parents certificates enable verification of any certificate from one CA by users of all other CAs in hierarchy 02/12/16 90 Public Key and Management
Slide91: Digital Signatures Digital Signatures 02/12/16 Public Key and Management
Slide92: Digital Signatures have looked at message authentication but does not address issues of lack of trust digital signatures provide the ability to: verify author, date & time of signature authenticate message contents be verified by third parties to resolve disputes hence include authentication function with additional capabilities 02/12/16 92 Public Key and Management
Slide93: Direct Digital Signatures involve only sender & receiver assumed receiver has sender’s public-key digital signature made by sender signing entire message or hash with private-key can encrypt using receivers public-key important that sign first then encrypt message & signature security depends on sender’s private-key 02/12/16 93 Public Key and Management
Slide94: Arbitrated Digital Signatures involves use of arbiter A validates any signed message then dated and sent to recipient requires suitable level of trust in arbiter can be implemented with either private or public-key algorithms arbiter may or may not see message 02/12/16 94 Public Key and Management Digital Signature Properties
Slide95: Authentication Protocols used to convince parties of each others identity and to exchange session keys may be one-way or mutual key issues are confidentiality – to protect session keys timeliness – to prevent replay attacks published protocols are often found to have flaws and need to be modified 02/12/16 95 Public Key and Management
Slide96: Replay Attacks where a valid signed message is copied and later resent simple replay repetition that can be logged repetition that cannot be detected backward replay without modification countermeasures include use of sequence numbers (generally impractical) timestamps (needs synchronized clocks) challenge/response (using unique nonce) 02/12/16 96 Public Key and Management
Slide97: Using Symmetric Encryption as discussed previously can use a two-level hierarchy of keys usually with a trusted Key Distribution Center (KDC) each party shares own master key with KDC KDC generates session keys used for connections between parties master keys used to distribute these to them 02/12/16 97 Public Key and Management
Slide98: Needham-Schroeder Protocol original third-party key distribution protocol for session between A B mediated by KDC protocol overview is: 1. A->KDC: IDA || IDB || N1 2. KDC -> A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ] 3. A -> B: EKb[Ks||IDA] 4. B -> A: EKs[N2] 5. A -> B: EKs[f(N2)] 02/12/16 98 Public Key and Management
Slide99: Needham-Schroeder Protocol used to securely distribute a new session key for communications between A & B but is vulnerable to a replay attack if an old session key has been compromised then message 3 can be resent convincing B that is communicating with A modifications to address this require: timestamps (Denning 81) using an extra nonce (Neuman 93) 02/12/16 99 Public Key and Management
Slide100: Using Public-Key Encryption have a range of approaches based on the use of public-key encryption need to ensure have correct public keys for other parties using a central Authentication Server (AS) various protocols exist using timestamps or nonces 02/12/16 100 Public Key and Management
Slide101: One-Way Authentication required when sender & receiver are not in communications at same time (eg. email) have header in clear so can be delivered by email system may want contents of body protected & sender authenticated 02/12/16 101 Public Key and Management
Slide102: Using Symmetric Encryption can refine use of KDC but can’t have final exchange of nonces, vis: 1. A->KDC: IDA || IDB || N1 2. KDC -> A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ] 3. A -> B: EKb[Ks||IDA] || EKs[M] does not protect against replays could rely on timestamp in message, though email delays make this problematic 02/12/16 102 Public Key and Management
Slide103: Public-Key Approaches have seen some public-key approaches if confidentiality is major concern, can use: A->B: EPUb[Ks] || EKs[M] has encrypted session key, encrypted message if authentication needed use a digital signature with a digital certificate: A->B: M || EPRa[H(M)] || EPRas[T||IDA||PUa] with message, signature, certificate 02/12/16 103 Public Key and Management
Slide104: Digital Signature Standard (DSS) US Govt approved signature scheme designed by NIST & NSA in early 90's published as FIPS-186 in 1991 revised in 1993, 1996 & then 2000 uses the SHA hash algorithm DSS is the standard, DSA is the algorithm FIPS 186-2 (2000) includes alternative RSA & elliptic curve signature variants 02/12/16 104 Public Key and Management
Slide105: Digital Signature Algorithm (DSA) creates a 320 bit signature with 512-1024 bit security smaller and faster than RSA a digital signature scheme only security depends on difficulty of computing discrete logarithms variant of ElGamal & Schnorr schemes 02/12/16 105 Public Key and Management
Slide106: Digital Signature Algorithm (DSA)
Slide107: DSA Key Generation have shared global public key values (p,q,g): choose q, a 160 bit choose a large prime p = 2L where L= 512 to 1024 bits and is a multiple of 64 and q is a prime factor of (p-1) choose g = h(p-1)/q where h<p-1, h(p-1)/q (mod p) > 1 users choose private & compute public key: choose x<q compute y = gx (mod p) 02/12/16 107 Public Key and Management
Slide108: DSA Signature Creation to sign a message M the sender: generates a random signature key k, k<q nb. k must be random, be destroyed after use, and never be reused then computes signature pair: r = (gk(mod p))(mod q) s = (k-1.H(M)+ x.r)(mod q) sends signature (r,s) with message M 02/12/16 108 Public Key and Management