Key establishment (and other protocols) Vašek Matyáš PV079 Agenda 1. Introduction to key establishment protocols 2. Attacks 3. Time-variant parameters 4. An example of protocol review/design 5. Involvement of trusted third parties 6. Generation from biometrics 7. Conclusions Protocol ˇ A multi-party algorithm, defined by a sequence of steps precisely specifying the actions required of two or more parties in order to achieve a specified objective [HoC] ˇ Security / cryptography protocols objectives ­ Confidentiality (secrecy), authentication of origin, entity authentication, integrity, key establishment, non-repudiation... Key establishment protocols ˇ Shared secret becomes available to two or more parties, for subsequent cryptographic use ˇ Key transport ­ one party (securely) transfers a secret value to other(s) ˇ Key agreement ­ shared secret is derived by two (or more) parties based on data contributed by, or associated with, each of these, and (ideally) that no party can pre-determine the resulting value Key establishment concepts ˇ Key authentication (implicit) ­ assurance to one party that no-one except the specific other party could have gained access to a given key ˇ Key confirmation ­ assurance to one party that another party actually has a given key ˇ Explicit key authentication ­ both above hold ˇ Entity authentication ­ assurance to one party of the identity of another party actively involved in a protocol KE protocol characteristics ˇ Key freshness ˇ Key control ­ Can any party control or predict the key value? ˇ Efficiency ­ Number of message exchanges (passes) ­ Volume of data exchanged ­ Complexity of computation ­ Possibility of pre-computation ˇ Material pre-distribution (system setup, certificates...) ˇ Third party involvement ˇ Non-repudiation Types of KE protocols ˇ Key transport based on symmetric techniques ˇ Key transport based on asymmetric techniques ˇ Key agreement based on symmetric techniques ˇ Key agreement based on asymmetric techniques ˇ Secret sharing ˇ Conference keying Attacker can... ˇ Record messages ˇ Replay them later ­ Possibly in different order ­ Some repeatedly ­ Some not at all ˇ Modify a part of or whole message Types of attacks on protocols ˇ Man-in-the-middle ˇ Replay ˇ Reflection ˇ Interleave ˇ Oracle (chosen-text) ˇ Forced delay ˇ ... Effects of key compromise ˇ Perfect forward secrecy ­ compromise of long-term secret keys doesn't compromise past session keys ˇ Known-key attack resistance ­ past session keys don't enable ­ Passive adversary to compromise future session keys ­ Active adversary to impersonate another party in the future Knowledge of secret key ­ authentication ˇ For shared-key crypto based on ­ trust in the party the key is shared with ­ Authentication ~ Ability to en-/de-crypt (or MAC...) ˇ For public-key crypto based on ­ trust in the party possessing the private key and ­ trust in link between the public key and other data ­ Authentication ~ Ability to sign or decrypt messages Entity authentication ˇ Unilateral / mutual ˇ Secret-based authentication ­ Weak ­ Challenge-response ­ Zero-knowledge Use of session (short-term) keys ˇ To limit volume of ciphertext (under one key) for cryptanalytic attack ˇ To limit the window of exposure (time and data volume) in the event of key compromise ˇ To avoid storing large number of distinct keys by creating keys only when actually needed ˇ To create independence across sessions and/or applications Establishing a session key ˇ Direct distribution ˇ Key transport center A BEKAB (KS,...) TTP - C A B EKBC (KS) EKAC (KS) Establishing a session key, cont'd TTP-managed TTP - C A B Direct (pull/push) TTP - C A B EKAC (KS) EKBC (KS) EKAC (KS, EKBC (KS)) EKBC (KS) Key distribution center Key transport successful? ˇ Key authentication (implicit) ­ assurance to one party that no-one except the specific other party could have gained access to a given key ˇ Key confirmation ­ assurance to one party that another party actually has a given key ˇ Key receipt indication ­ indication to one party that another party received the key Zero-knowledge protocols ˇ Proof of knowledge ­ interactive proof with ­ Completeness ­ honest parties succeed with proof of acceptable probability for prover's claim ­ Soundness ­ dishonest prover cannot convince honest verifier without revealing the secret ˇ Zero-knowledge ­ when the communication between prover and verifier can be simulated without access to the secret knowledge Zero-knowledge protocols ˇ A B : witness ˇ A B : challenge ˇ A B : response ˇ Zero-knowledge ­ when the communication between prover and verifier can be simulated without access to the secret knowledge Time-variant parameters (nonces) ˇ Random numbers (select from a uniform distribution), challenge-response ­ freshness ˇ Sequence numbers ­ Greater-by-one or only monotonic increase check ­ Counter maintenance, reset policy ˇ Timestamps ­ Acceptance window ­ Secure, synchronized & distributed time info (clocks) Key transport ­ symmetric techniques ˇ A B : EK(rA , TVP* , A* , B*) ˇ A B : nB ˇ A B : EK(rA , nB , A* , B*) Shamir's no-key protocol ˇ A B : EKA(X) ˇ A B : EKB(EKA(X)) ˇ A B : EKB(X) ˇ Use of a commutative cipher (not Vernam's ) Fiat-Shamir identification protocol ˇ A trusted center T selects and publishes RSA-like modulus n = p q , keeps p and q secret ˇ A selects secret s (coprime with n, 1 s n-1), computes v = s2 mod n. This v is the public key of A. ˇ One round of A's authentication to B has three steps: ­ A B: x = r2 mod n ­ A B: e, e {0, 1} ­ A B: y = r se mod n ˇ These steps are iterated t-times, then the probability of A successfully cheating is 2-t. Diffie-Hellman protocol Alice x Bob x mod p y y mod p xy mod p xy mod p Man-in-the-middle attack Alice x Bobx mod p y y mod p xy' mod p x'y mod p Eve x' x' mod p y' y' mod p x'y mod p xy' mod p COMSET protocol ˇ A B : rB , PA(rB , rA , KB) ˇ A B : rA ˇ Unilateral authentication of A to B ˇ Key transfer from B to A ˇ Role of rB is to convince A of B's knowledge of the encrypted message R-COMSET ˇ A B : r1A , PB(A, KA , r1A , r2A , TVPA) (1) ˇ A B : r1B , r2A , PA(B, KB , r1B , r2B , TVPB) (2) ˇ A B : r2B (3) ˇ Mutual authentication of A and B ˇ Confidential exchange of two key parts ˇ Final key to be calculated as a one-way function of the two keys (XOR prone to attacks ­ Burmester'94) R-COMSET interleaving attack ˇ A B : r1A , PB(A, KA , r1A , r2A , TVPA) (1) ˇ C B : r1B , r2A , PA(B, KB , r1B , r2B , TVPB) (2) ˇ C A : r1B , PA(B, KB , r1B , r2B , TVPB) (i) ˇ C A : r1C , r2A , PA(B, KC , r1C , r2C , TVPC) (2') ˇ C A : r' 1A , r2B , PB(A, K' A , r' 1A , r' 2A , TVP' A) (ii) ˇ C B : r2B (3') ˇ "Communication problem" (iii) RRC (Revised R-COMSET) ˇ A B : r1A , PB(A*, KA , r1A , r2A , TVP* A) (1) ˇ A B : PA(B*, KB , r2A , rB , TVP* B) (2) ˇ A B : rB (3) ˇ A does not behave like an oracle ˇ Can consider (3) to be a one-way function of rB Helsinki protocol ˇ A B : PB(A, KA , rA , TVP* A) (1) ˇ A B : PA(B*, KB , rA , rB , TVP* B) (2) ˇ A B : rB (3) ˇ r1A eliminated ­ redundancy/integrity check by A ­ yet recall the original role "to convince about knowledge of the encrypted message" ˇ Effectively a modification of Needham-Schroeder public-key protocol Quarter of a century... ˇ R. Needham & M. Schroeder ­ "Using encryption for authentication in large networks of computers", Comm. ACM, vol. 21, no. 12, pp. 993-999, 1978. ˇ Introduced both public- and shared-key protocols ˇ Predicted use of hybrid cryptosystems ˇ Raised the issue of subtle problems in protocols and argued for their analysis/verification http://lambda.cs.yale.edu/cs422/doc/needham.pdf Needham-Schroeder public-key protocol ˇ A B : PB(KA , A) (1) ˇ A B : PA(KA , KB) (2) ˇ A B : PB(KB ) (3) ˇ A's private key compromise affects both KA , KB and therefore also the final session key, unlike the protocols studied before ˇ To detect replay, session keys (or at least images) have to be kept ISO/IEC 11770 (1999) ˇ Information technology ­ Security techniques ­ Key Management ˇ Part 1: Key management framework ˇ Part 2: Mechanisms using symmetric techniques ˇ Part 3: Mechanisms using asymmetric techniques ISO/IEC 11770-3 ˇ Secret key agreement (7 mechanisms) ˇ Secret key transport (6 mechanisms) ˇ Public key transport ­ Without a TTP (2 mechanisms) ­ Using a CA (1 mechanism) Involvement of trusted parties ˇ For system setup and/or any protocol run ­ Off-line, on-line, in-line ˇ Key transport and/or generation ˇ Trust to keep secrets vs. trust to certify data ˇ Assumptions of following the course of action prescribed by the protocol, not knowingly collaborating with attackers, etc. Identity-based systems ˇ Users don't have explicit public keys ˇ Yet in all approaches at some stage a trusted third party involvement is required to provide a link between users' identities (or other public information) and their private keys The Global Trust Register www.cl.cam.ac.uk/Research/Security/Trust-Register Global Trust Register ˇ Paper-based Register (off-line top-level CA) ˇ Keys and other info (URL, address, phone...) ˇ Keys verified and rated D C B A (highest) ˇ Reliable, convenient, free press privilege ˇ Top-level X.509 CAs (and secure websites) ˇ Important PGP keys ˇ EDI and Entrust/Solo(X.509) keys Global Trust Register ­ lessons ˇ Importance of revocation ­ critical ˇ High-level certificates stable ˇ Problems (e.g., user interface) with browser and e-mail client software ˇ Split of confidentiality and authentication keys ˇ CA operations expensive Biometrics and cryptographic material ˇ Biometrics ­ automated methods of identity verification or identification based on measurable biological characteristics ˇ Biometrics almost never match at 100%!!! ˇ Threshold-based decision introduces the errors of false acceptance and rejection ­ Zero-effort or active bypassing? ­ User group size vs. accuracy ˇ Verification vs. identification? Key-generation attempts ˇ User provides her/his biometric sample and her/his key can be generated from this sample ˇ Attractive benefits ­ Key (re-)generated "on the fly" ­ Key is used only with its owner present ­ Can be used and then destroyed Simplistic approach ˇ Find an invariant part of a biometric characteristic that with a very high probability ­ will be same for the right user being measured ­ will be different for an imposter ˇ Add a secret value (biometric data is not secret) and process these two values (e.g., hash function) ˇ This approach (with some twists) has been suggested in dozens of papers. The issue is that the secret value and not the biometric data is the critical basis of the key. Fruitful approaches ˇ D. Wheeler ­ Error correction ­ Deriving faultless data ("keys") from faulty data (analogue measurements, e.g. biometric ones) ­ Error-correction bits involved in the protocol, both parties must possess results of a measurement ­ Both sender and receiver have same bit-string after the protocol execution ˇ F. Monrose et al. ­ Thresholding ­ Spoken passphrase ­ secrecy of the passphrase and its speech pattern (similar work for keystroke dynamics) ­ Based on secret sharing (t of n shares) operations with this secret (key) are enabled Aspects of real generation ˇ Major problems ­ Biometrics are not secret!!! ˇ Can/should secret be added? ˇ How do we protect, store, and use that secret? ˇ What are the chances of exhaustive search? ­ Key-space ˇ Limited by measurable characteristics ˇ Probability of different values? ˇ Minor problems ­ Compromised key ­ key change? ­ Organ damaged ­ key loss? ­ Implementation issues, e.g. dependence on the reader The building blocks ˇ Secure primitives necessary, yet not sufficient ˇ Playing it safe ­ precise specification of ­ what shall and shall not be done ­ before, during and after the protocol run ­ with restrictions on use of a given protocol ˇ Assumptions of critical importance! ˇ Protocol analysis tools useful, yet not foolproof and also not designing protocols