TLS Working Group Pascal Urien Internet Draft Telecom ParisTech Intended status: Experimental July 2010 Expires: January, 2011 TLS Tripartite Diffie-Hellman Key Exchange draft-urien-tls-dh-tripartite-00 Abstract Most of privacy exchanges over the Internet rely on the TLS protocol. According to this protocol two entities the client and the server computes a master secret from which are deduced cryptographic keys used for data privacy and security. Digital transactions may deal with critical information (payments ...) that need to be recorded for traceability issues or for legal requirements. However messages are secured by the TLS protocol, so it is not possible for a third party that logs packets to perform decryption operations upon legitimate requests. The goal of this draft is to support a Trusted Third Party (TTP) that could recover the protected information when needed. The proposed protocol uses the Tripartite Diffie-Hellman (tdh) algorithm based on bilinear pairings over elliptic curves. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on January 2011. Urien Expires January 2011 [Page 1]

TLS tripartite Diffie-Hellman Key Exchange June 2010 Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Urien Expires January 2011 [Page 2]

TLS tripartite Diffie-Hellman Key Exchange June 2010 Table of Contents Abstract........................................................... 1 Requirements Language.............................................. 1 Status of this Memo................................................ 1 Copyright Notice................................................... 2 Table of Contents.................................................. 3 1 Overview......................................................... 4 2 About Bilinear Pairing........................................... 5 2.1 Symmetric Bilinear Pairing.................................. 5 2.2 Asymmetric Bilinear Pairing................................. 6 2.3 The Bilinear Diffie-Hellman (BDH) problem................... 6 2.4 Practical properties........................................ 6 2.4.1 Symmetric Pairing .................................... 6 2.4.2 Asymmetric pairing ................................... 7 3. Bilinear pairing operations overview......................... 8 4. Bilinear Pairing Operations details............................. 9 4.1 TLS Extension............................................... 9 4.1.1 Supported Pairing Scheme ............................. 9 4.2 Key Exchange................................................ 9 4.2.1 Trusted-Third-Party list ............................. 9 4.2.1 Server Key Exchange ................................. 10 4.2.2 Client Key Exchange ................................. 10 4.3 PreMasterSecret computing.................................. 10 4.3.1 Hash function for the Weil pairing .................. 11 4.4 CipherSuites............................................... 11 5. Example of pairings............................................ 11 5.1 Symmetric pairing.......................................... 11 6. Security Considerations........................................ 12 7. IANA Considerations............................................ 13 8 References...................................................... 13 8.1 Normative references....................................... 13 8.2 Informative references..................................... 13 Author's Addresses................................................ 13 Urien Expires January 2011 [Page 3]

TLS tripartite Diffie-Hellman Key Exchange June 2010 1 Overview Most of privacy exchanges over the Internet rely on the TLS protocol. According to this protocol two entities the client and the server computes a master secret from which are deduced cryptographic keys used for data privacy and security. Digital transactions may deal with critical information (payments ...) that need to be recorded for traceability issues or for legal requirements. However messages are secured by the TLS protocol, so it is not possible to a third party that logs packets to perform decryption operations upon legitimate requests. The idea of this proposal is to support a Trusted Third Party (TTP) that could recover the protected information when needed. The Tripartite Diffie-Hellman (tdh) idea was initially introduced in [TDH]. Toady cryptography provides efficient software tools [PBC] computing bilinear pairing over elliptic curve. The [TLS-ECC] standard already supports cryptographic operations based on elliptic curves, mainly for key exchange based on ECDH (Elliptic Curve Diffie Hellman) or the ECDSA (Elliptic Curve Digital Signature Algorithm) signature. The Weil pairing for example works with classical elliptic curves; server and client are equipped with DH public and private keys. The classical TLS pre-master-secret is computed according to the relation pre-master-secret = abP (or g^ab with multiplicative notations) Where P is a point of an elliptic curve point (a generator) defined over a Fq field, aP and bP are respectively the server and client DH public keys, and a,b their private keys. If the client and the server agree to use a TTP, identified by an attribute ttp-name and owning a DH public key cP, the pre-master- secret is computing according to the following relation: Sclient = e(aP,cP)^b Sserver = e(bP,cP)^a Sttp = e(aP,bP)^c, S = Sserver = Sclient = Sttp = shared-secret S is an element of F(q^k), with k integer Urien Expires January 2011 [Page 4]

TLS tripartite Diffie-Hellman Key Exchange June 2010 pre-master-secret = h(S), h a hash function producing p bits In other words each entity (client, server, TTP) computes a shared secret S by using its private DH key and the two other public DH keys. The master-secret is thereafter produced: master_secret = PRF(pre-master-secret, "master secret", ClientHello.random + ServerHello.random). The master secret is computed by the client and the server without a dialog with the TTP. But the TTP will be able to recover the master secret from the TLS session logs. Client Server (ec, P, b, bP) (ec, P, a, aP) <==aP bP==> S= e(aP,cP)^b S= e(bP,cP)^a master-secret master-secret ! ! !<===Protected Data Exchange===>! ! ! TTP (ec, P, c, cP) S= e(aP,bP)^c master-secret Data Decryption Figure 1. Illustration of TTP use in a TLS session 2 About Bilinear Pairing 2.1 Symmetric Bilinear Pairing Z is the set of integer. r is a prime integer Let (G1,+) be a cyclic group of order r, (with additive operation +) Let (G2,*) be a cyclic group of order r, (with multiplicative operation x). Let e a non-degenerate bilinear map, G1 x G1 -> G2 A non-degenerate bilinear pairing satisfies the following conditions: - Bilinear: for P,Q elements of G1, a,b elements of Z, e(aP,bP)=e(P,Q)^ab Urien Expires January 2011 [Page 5]

TLS tripartite Diffie-Hellman Key Exchange June 2010 - Non-Degenerate: e(P,P)#1 is a generator of G2 The Weil pairing [ECC] has been defined for elliptic curve [ECC] over finite field of prime characteristic p (Fp) - ECC is an elliptic curve over Fp - G1 is a subgroup in ECC(Fp), whose order is r - G2 is a subgroup in F(p^k), k an integer 2.2 Asymmetric Bilinear Pairing In that case the bilinear map works with two different groups G1, whose order is r, and G1', where each element has order dividing r. e is a non-degenerate bilinear map, G1 x G1' -> G2 For P elements of G1, Q element of G1', a,b elements of Z : e(aP,bQ)=e(P,Q)^ab The Tate pairing [ECC] has been defined for elliptic curve [ECC] over finite field of prime characteristic p (Fp). - ECC is an elliptic curve over Fp - G1 is a subgroup in ECC(Fp), whose order is r - G1' is a subgroup in ECC(Fp^k), with k integer (k is the elliptic curve embedding degree) - G2 is a subgroup in F(p^k) 2.3 The Bilinear Diffie-Hellman (BDH) problem. P is a generator of G1 a,b,c are elements of Zr* BDH: Knowing P, aP, bP, cP the computation of e(P,P)^abc is 'impossible' Furthermore the classical computational Diffie Hellman (CDH) assumption is assumed for the group G1. CDH: Knowing P, aP, bP the computation of abP is 'impossible' 2.4 Practical properties 2.4.1 Symmetric Pairing We suppose three entities A (server), B (client), C (ttp) equipped with three pairs of public and private keys, associated with a group G1 and a generator P. Urien Expires January 2011 [Page 6]

TLS tripartite Diffie-Hellman Key Exchange June 2010 aP and a, are respectively the public and the private keys for A bP and b, are respectively the public and the private keys for B cP and c, are respectively the public and the private keys for C A shared secret (S) may be computed by these three entities, according to the following scenario: - A computes S = e^a(bP,cP) = e(P,P)^abc - B computes S = e^b(aP,cP) = e(P,P)^abc - C computes S = e^c(aP,bP) = e(P,P)^abc In other word each entity computes a shared secret key, deduced from its private key and the two other public key. If A is a client, B a server and C a trusted party, all security properties such as encrypted packets exchanged between client and server may be recovered by the trusted party. 2.4.2 Asymmetric pairing We suppose three entities A (server), B (client), C (ttp) equipped with pairs of public and private keys, associated with the group G1 (generator P) and the group G1' (generator P'). aP, aP' and a, are respectively the public and the private keys for A bP and b, are respectively the public and the private key for B cP, cP' and c, are respectively the public and the private keys for C A shared secret (S) may be computed by these three entities, according to the following scenario - A computes S = e^b(bP,cP') = e(P,P')^abc - B computes S = e^b(aP,cP') = e(P,P')^abc - C computes S = e^c(aP,bP') = e(P,P')^abc Urien Expires January 2011 [Page 7]

TLS tripartite Diffie-Hellman Key Exchange June 2010 3. Bilinear pairing operations overview Client Server ------ ------ ClientHello --------> extension {pairing-scheme} extension {elliptic-curves} extension {ec_point-formats} ServerHello extension {pairing-scheme} extension {elliptic-curves} extension {ec_point-formats} Certificate* ServerKeyExchange* select (KeyExchangeAlgorithm) { case ec_bilinear-pairing: ServerECDHParams params; Signature signed_params; TTP-List ttp-list } ServerKeyExchange; CertificateRequest*+ <-------- ServerHelloDone Certificate*+ ClientKeyExchange struct { select (KeyExchangeAlgorithm) { case ec_bilinear-pairing: ClientECDiffieHellmanPublic; TTP-Name: ttp-name } exchange-keys; } ClientKeyExchange; CertificateVerify*+ [ChangeCipherSpec] Finished --------> [ChangeCipherSpec] <-------- Finished Application Data <-------> Application Data Figure 2. Overview of the TLS bilinear pairing operations. Urien Expires January 2011 [Page 8]

TLS tripartite Diffie-Hellman Key Exchange June 2010 The TLS dialog is illustrated by figure 2. A new extension is used both by client and server in order to negotiate a pairing scheme. The TTP is selected thanks attributes exchanged in the ServerKeyExchange and ClientKeyExchange messages. Elliptic curve and DH parameter are specified according to [TLS-ECC]. 4. Bilinear Pairing Operations details 4.1 TLS Extension A new TLS extension is defined in this specification: the pairing- scheme extension. The general structure of TLS extensions is described in [TLS 1.1], and this specification adds one new item to ExtensionType. enum { pairing-scheme(xx)} ExtensionType; The client negotiates the pairing-scheme via the corresponding extension inserted in the client hello message The server selects one of the proposed items and inserts it in the server hello message. Two other extensions are imported from [TLS-ECC]: - elliptic-curves(10), - ec_point-formats(11); 4.1.1 Supported Pairing Scheme Supported Pairing Scheme enum { Weil-Pairing (1) } NamedScheme; 4.2 Key Exchange A new KeyExchange Algorithm is defined: ec-bilinear-pairing 4.2.1 Trusted-Third-Party list Each trusted third party (TTP) is identified by a name. A DH public key is implicitly deduced from its identifier. Urien Expires January 2011 [Page 9]

TLS tripartite Diffie-Hellman Key Exchange June 2010 Structure of this message: opaque TTP-Name<1..2^24-1>; struct { TTP-Name ttp-name-list<0..2^24-1>; } TTP-List; 4.2.1 Server Key Exchange The ServerKeyExchange message is extended as follows. enum { ec-bilinear-pairing } KeyExchangeAlgorithm; select (KeyExchangeAlgorithm) { case ec_bilinear-pairing: ServerECDHParams params; Signature signed-params; TTP-List ttp-list } ServerKeyExchange; The attributes ServerECDHParams and Signature are imported from [TLS- ECC] 4.2.2 Client Key Exchange The ClientKeyExchange message is extended as follows. struct { select (KeyExchangeAlgorithm) { case ec_bilinear-pairing: ClientECDiffieHellmanPublic; TTP-Name: ttp-name } exchange-keys; } ClientKeyExchange; The attribute ClientECDiffieHellmanPublic is imported from [TLS-ECC]. 4.3 PreMasterSecret computing aP and bP are respectively the server and the client DH public values (with additive notations) cP is the trusted third party (ttp) public value, (with additive notations). h is a digest function producing p bytes. Urien Expires January 2011 [Page 10]

TLS tripartite Diffie-Hellman Key Exchange June 2010 On the server side: PreMasterSecret = h(e(bP,cP)^a) On client side: PreMasterSecret = h(e(aP,cP)^b) On the ttp side PreMasterSecret = h(e(aP,bP)^c) 4.3.1 Hash function for the Weil pairing For the Weil pairing, G2 is a subgroup of Fq^2, if the output of e is expressed as the tuple (a0,a1) with x and y elements of Fq h = sha1(a0 || a1), a0 and a1 are values of exactly q bits. 4.4 CipherSuites To be done. 5. Example of pairings This example has been computed with the Pairing-Based Cryptography Library [PBC] [BL]. 5.1 Symmetric pairing The elliptic curve (ECC) is chosen as: y^2 = x^3 + x, with x, y elements of a Field Fq q is a prime number, with q = 3 modulus 4 G1 is a subgroup of ECC(Fq) G2 is a subgroup of Fq^2 There are q+1 points on the ECC curve, i.e. #ECC(Fq) = q+1 r = order of G1 = prime factor of q+1. h = cofactor = #ECC(Fq) / r q=8780710799663312522437781984754049815806883199414208211028653399266 475630880222957078625179422662221423155858769582317459277713367317481 324925129998224791. h=1201601226489114607938882136674053420480295440125131182291961513104 7207289359704531102844802183906537786776 r= 730750818665451621361119245571504901405976559617 Urien Expires January 2011 [Page 11]

TLS tripartite Diffie-Hellman Key Exchange June 2010 Generator P= 764213932795790385166146156484628185710738246136731223594607305863197 148904107335230752866953232919510098156557991388877251113225844051396 9390781514106884, 841053126166803064145349163706237513167951671763744795990943027230354 098248702951019958048685849729494818612964151563063433969126677448023 4634049031935396 a = 321231739573260508064943282038854866624801566274 aP = 301901600464207748384853072909292823401500311348346356764859754747703 064669197258898445749044213480292759568257999990157011471277891932048 3502179821202747, 622130912004388536645426112375868421081814378272661695953772580311048 821974186212677634483766383564352093956376894422864585155448402243584 2060112859040085 b = 591069617759232948334516538341133684003963967541 bP = 489872625336582550697622917901310968712983470168986006826993590244144 534124000070208650497397931419729729097601618783404569928023315742260 1733989063260044, 715768020641988338757762409522925702707172363082968385844449919698450 610626853008028585471746136204506517503675925750751323255279155813951 061482849469617 c = 332790059747456431829511198714114673843901104395 cP = 361673235446634950587227148388584900737947568189969047494313829915613 165227389313929815513580932571550613336307696480151992816947356553291 3077259306029100, 591927063716469042674124332635453987072498361375371305395310139261168 079986151403557597760872949800149313292665777504365718007945299529892 7247712148590792 S= f(aP,bP)^c = f(bP,cP)^a= f(cP,aP)^b = 411874021818983935494518378468671897765968395058497750231537284872046 634607045530820852050427874577949368791925702115715036551400857093954 2202145179250626, 792272713616191570585463230096947246676587164343554480144379956667402 825333387256294430771484207666103108581680992251414596583914923441539 9681428439428268 6. Security Considerations To be done. Urien Expires January 2011 [Page 12]

TLS tripartite Diffie-Hellman Key Exchange June 2010 7. IANA Considerations To be done 8 References 8.1 Normative references [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [TLS 1.0] Dierks, T., C. Allen, "The TLS Protocol Version 1.0", RFC 2246, January 1999 [TLS 1.1] Dierks, T., Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.1", RFC 4346, April 2006 [TLS 1.2] Dierks, T., Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.1", draft-ietf-tls-rfc4346-bis-10.txt, March 2008 [TLS-ECC] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)", RFC 4492, May 2006. 8.2 Informative references [ECC] Joseph H.Silverman, "The Arithmetic of Elliptic Curves", Second Edition, Springer, 2008 [PBC] http://crypto.stanford.edu/pbc/ [TDH] A.Joux, "A one round protocol for tripartite Diffie-Hellman", Lecture Notes in Computer Science, Springer, Volume 1838, 2000 [BL] Benn Lynn, "On the implementation of paring-based cryptosystems", PHD dissertation, Stanford University, 2007 Author's Addresses Pascal Urien Telecom ParisTech 37/39 rue Dareau, 75014 Paris, France Email: Pascal.Urien@telecom-paristech.fr Urien Expires January 2011 [Page 13]