Report

ELEC5616 computer and network security matt barrie [email protected] CNS2010 lecture 6 :: key management 1 key management • Suppose we have a symmetric key network: kab Alice Bob kad kbd kac kbc Carol • • kcd Alice, Bob, Carol and Dave want to talk to each other For secure communication, for n parties, we require n 2 ( ) • Dave = n(n-1) 2 keys Key distribution and management becomes a major issue! CNS2010 lecture 6 :: key management 2 definitions • Key establishment is any process whereby a shared secret becomes available to two or more parties, for subsequent cryptographic use. • Key management is the set of processes and mechanisms which support key establishment and the maintenance of ongoing keying relationships between parties, including replacing older keys with newer ones: – key agreement – key transport CNS2010 lecture 6 :: key management 3 key distribution centre • Naïve solution: Alice ka kc Bob kb KDC kd Carol • (1) (2) (3) (4) • All parties share a key with the KDC Dave Protocol: Alice → KDC KDC → Alice Alice → Bob Bob : : : : “want to talk with Bob” KDC picks random key kab, sends Eka[kab], Ekb[kab, “ticket a-b”] Alice decrypts Eka[kab], sends ticket to Bob Bob decrypts ticket Alice and Bob now share secret key kab. CNS2010 lecture 6 :: key management 4 problems with naïve approach • Naïve solution: Alice ka kc Bob kb KDC kd Carol • All parties share a key with the KDC Dave Problems: – – – – CNS2010 Single point of failure, the KDC (a juicy target to attack) No authentication Poor scalability Slow lecture 6 :: key management 5 merkle’s puzzles • • • Ralph Merkle (Stanford, 1974) Merkle’s puzzles are a way of doing key exchange between Alice and Bob without the need for a KDC Protocol: (1) Alice creates lots of puzzles Pi = Epi[“This is puzzle #Xi”, ki] where i = 1 .. 220, |pi| = 20 bits (weak), |ki| = 128 bits (strong) Xi, pi and ki are chosen randomly and different for each i. (2) Alice sends all puzzles Pi to Bob. (3) Bob picks a random puzzle j є {1 … 220} and solves Pj by brute force (i.e. search on key pj). This recovers Xj and kj from the puzzle. (4) Bob sends Xj to Alice in the clear. (5) => Alice looks up the index j of Xj (from a table) to get kj. Alice and Bob now both share a secret key kj. CNS2010 lecture 6 :: key management 6 merkle’s puzzles P6 P2 P7 P5 P11 Alice Makes 220 puzzles P1 P13 P3 P4 P12 Bob P14 P9 Picks a random puzzle Pj and breaks it. Pi = Epi[“This is puzzle #Xi”, ki] Sends Xj back to Alice Alice looks up Xj Shared secret is kj Eve ??? Shared secret is kj Only knows the puzzles and Xj CNS2010 lecture 6 :: key management 7 attack on merkle’s puzzles • Eve must break on average half the puzzles to find Xj (hence kj) – Time required to do so for 220 puzzles = 219 x 219 = 238 • If Alice and Bob can try 10,000 keys/second : – It will take a minute for each of them to perform their steps (219 for Bob) – Plus another minute to communicate the puzzles on a 1.544MB (T1) link • With comparable resources, it will take Eve about a year to break the system. • Note: Merkle’s Puzzles uses a lot of bandwidth (impractical!) CNS2010 lecture 6 :: key management 8 diffie-hellman key exchange • • • Diffie-Hellman (Stanford, 1976) Worldwide standard used in smart cards, etc. Protocol: Consider the finite field Zp = <0, … p-1> where p is prime (p is about 300 digits long) Let g є Zp (the generator) (1) (2) (3) (4) (5) Alice Bob Alice → Bob Bob → Alice Alice and Bob : : : : : Alice chooses a random large integer a є Zp Bob choses a random large integer b є Zp Alice sends Bob ga (mod p) Bob sends Alice gb (mod p) compute gab : Alice computes (gb)a = gab (mod p) : Bob computes (ga)b = gab (mod p) => Alice and Bob now share secret gab CNS2010 lecture 6 :: key management 9 diffie-hellman key exchange Alice p, g, ga (mod p) Bob gb (mod p) Computes gab (mod p) Computes gab (mod p) Eve ??? Only knows p, g, ga, gb CNS2010 lecture 6 :: key management 10 strength of diffie-hellman • The strength of Diffie-Hellman is based upon two issues: – given p, g, ga, it is difficult to calculate a (the discrete logarithm problem) – given p, g, ga, gb it is difficult for Eve to calculate gab (the Diffie-Hellman problem) – we know that DL DH but it is not known if DH DL. • Essentially, the strength of the system is based on the difficulty of factoring numbers the same size as p. • The generator, g, can be small • Do not use the secret gab directly as a session key – it is better to either hash it or use it as a seed for a PRNG – not all bits of the secret have a flat distribution CNS2010 lecture 6 :: key management 11 references • Handbook of Applied Cryptography – read §1, §2-2.4.4, §2.5 - 2.5.3 • Stallings (3rd Ed) – 6.3 – 6.4 CNS2010 lecture 6 :: key management 12