[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

  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]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/