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]