1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor, SISLecture 10Nov 8, 2007Hash FunctionsKey Management2Objectives Understand/explain the issues related to, and utilize the techniques Hash functions Key management Authentication and distribution of keys Session key Key exchange protocols Kerberos Mechanisms to bind an identity to a key Generation, maintenance and revoking of keys3Quick ReCap4Confidentiality using RSAMessageSourceEncryptionMessageSourceDecryptionXYXAliceKey Source????Bob5Authentication using RSAMessageSourceEncryptionMessageSourceDecryptionXYXKey SourceAlice????Bob6Confidentiality + AuthenticationMessageSourceEncryptionMessageSourceDecryptionXKey SourceAlice????BobDecryptionYXEncryptionY????Key SourceZ7Hash Functions8Cryptographic Checksums Mathematical function to generate a set of kbits from a set of nbits (where k≤n).kis smaller then nexcept in unusual circumstances Keyed CC: requires a cryptographic keyh= CKey(M) Keyless CC: requires no cryptographic key Message Digest or One-way Hash Functionsh= H(M) Can be used for message authentication Hence, also called Message Authentication Code (MAC)9Mathematical characteristics Every bit of the message digest function potentially influenced by every bit of the function’s input If any given bit of the function’s input is changed, every output bit has a 50 percent chance of changing Given an input file and its corresponding message digest, it should be computationally infeasible to find another file with the same message digest value10Definition Cryptographic checksum function h: A→B:1. For any x∈A, h(x) is easy to compute– Makes hardware/software implementation easy2. For any y∈B, it is computationally infeasible to find x∈Asuch that h(x) = y–One-way property3. It is computationally infeasible to find x, x´∈Asuch that x≠x´and h(x) = h(x´)4. Alternate form: Given any x∈A, it is computationally infeasible to find a different x´ ∈Asuch that h(x) = h(x´).Collisions possible?Collisions possible?11Keys Keyed cryptographic checksum: requires cryptographic key DES in chaining mode: encipher message, use last nbits. keyed cryptographic checksum. Keyless cryptographic checksum: requires no cryptographic key MD5 and SHA-1 are best known; others include MD4, HAVAL, and Snefru12Hash Message Authentication Code (HMAC) Make keyed cryptographic checksums from keyless cryptographic checksumshbe keyless cryptographic checksum function takes data in blocks of bbytes and outputs blocks of lbytes. k´is cryptographic key of length bbytes (from k) If short, pad with 0s’ to make bbytes; if long, hash to length bipadis 00110110 repeated btimesopadis 01011100 repeated btimes HMAC-h(k, m) = h(k´ ⊕opad|| h(k´ ⊕ipad|| m)) ⊕ exclusive or, || concatenation13Protection Strength Unconditionally Secure Unlimited resources + unlimited time Still the plaintext CANNOT be recovered from the ciphertext Computationally Secure Cost of breaking a ciphertext exceeds the value of the hidden information The time taken to break the ciphertext exceeds the useful lifetime of the information14Average time required for exhaustive key search2.15 milliseconds232= 4.3 x 109325.9 x 1030years2168 = 3.7 x 10501685.4 x 1018years2128 = 3.4 x 103812810 hours256= 7.2 x 101656Time required at 106Decryption/µsNumber of Alternative KeysKey Size (bits)15Key Management16NotationX→Y: { Z|| W} kX,YXsends Ythe message produced by concatenating Zand Wenciphered by key kX,Y, which is shared by users Xand YA→T: { Z} kA|| { W} kA,TAsends Ta message consisting of the concatenation of Zenciphered using kA, A’s key, and Wenciphered using kA,T, the key shared by Aand Tr1, r2nonces (nonrepeating random numbers)17Interchange vs Session Keys Interchange Key Tied to the principal of communication Session key Tied to communication itself Example Alice generates a random cryptographic key ksand uses it to encipher m She enciphers kswith Bob’s public key kB Alice sends { m} ks{ ks} kB Which one is session/interchange key?18Benefits using session key In terms of Traffic-analysis by an attacker? Replay attack possible? Prevents some forward search attack Example: Alice will send Bob message that is either “BUY” or “SELL”. Eve computes possible ciphertexts {“BUY”} kBand {“SELL”} kB. Eve intercepts enciphered message, compares, and gets plaintext at once19Key Exchange Algorithms Goal: Alice, Bob to establish a shared key Criteria Key cannot be sent in clear Attacker can listen in Key can be sent enciphered, or derived from exchanged data plus data not known to an eavesdropper Alice, Bob may trust a third party All cryptosystems, protocols assumed to be publicly known Only secret data is the keys, OR ancillary information known only to Alice and Bob needed to derive keys20Classical Key Exchange How do Alice, Bob begin? Alice can’t send it to Bob in the clear! Assume trusted third party, Cathy Alice and Cathy share secret key kA Bob and Cathy share secret key kB Use this to exchange shared key ks21Simple Key Exchange ProtocolAliceCathy{ request for session key to Bob } kAAliceCathy{ ks}kA, { ks}kBAliceBob{ ks} kBAliceBob{m}ksWhat can an attacker, Eve, do to subvert it?What can an attacker, Eve, do to subvert it?22Needham-SchroederAlice CathyAlice || Bob || r1Alice Cathy{ Alice || Bob || r1|| ks||{ Alice || ks} kB} kAAlice Bob{ Alice || ks} kBAlice Bob{ r2} ksAlice Bob{ r2– 1 } ks23Questions How can Alice and Bob be sure they are talking to each other? Is the previous attack possible? Key assumption of Needham-Schroeder All keys are secret; What if we remove that assumption?24Needham-Schroeder with Denning-Sacco ModificationAlice CathyAlice || Bob || r1Alice Cathy{ Alice || Bob || r1|| ks|| { Alice || T || ks} kB} kAAlice Bob{ Alice || T || ks} kBAlice Bob{ r2} ksAlice Bob{ r2– 1 } ksOne solution to Needham-Schroeder problem: Use time stamp Tto detect replay!One solution to Needham-Schroeder problem: Use time stamp Tto detect replay!25Denning-Sacco Modification Needs synchronized clocks Weaknesses: if clocks not synchronized, may either reject valid messages or accept replays Parties with either slow or fast clocks vulnerable to replay Resetting clock
View Full Document