Network Working Group                                         H. Danisch
Request for Comments: 1824                                 E.I.S.S./IAKS
Category: Informational                                      August 1995


                 The Exponential Security System TESS:
                An Identity-Based Cryptographic Protocol
                     for Authenticated Key-Exchange
                        (E.I.S.S.-Report 1995/4)

Status of this Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   This informational RFC describes the basic mechanisms  and  functions
   of  an identity based system for the secure authenticated exchange of
   cryptographic keys, the generation of signatures, and  the  authentic
   distribution of public keys.

Table of Contents

   1.  Introduction and preliminary remarks . . . . . . . . . . . . .  2
       1.1.  Definition of terms/Terminology  . . . . . . . . . . . .  2
       1.2.  Required mechanisms  . . . . . . . . . . . . . . . . . .  4
   2.  Setup  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  5
       2.1.  SKIA Setup . . . . . . . . . . . . . . . . . . . . . . .  5
       2.2.  User Setup . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Authentication . . . . . . . . . . . . . . . . . . . . . . . .  7
       3.1.  Zero Knowledge Authentication  . . . . . . . . . . . . .  7
       3.2.  Unilateral Authentication  . . . . . . . . . . . . . . .  8
       3.3.  Mutual Authentication  . . . . . . . . . . . . . . . . .  9
       3.4.  Message Signing  . . . . . . . . . . . . . . . . . . . . 10
   4.  Enhancements . . . . . . . . . . . . . . . . . . . . . . . . . 10
       4.1.  Non-Escrowed Key Generation  . . . . . . . . . . . . . . 11
       4.2.  Hardware Protected Key . . . . . . . . . . . . . . . . . 11
       4.3.  Key Regeneration . . . . . . . . . . . . . . . . . . . . 12
       4.4.  r ^ r  . . . . . . . . . . . . . . . . . . . . . . . . . 13
       4.5.  Implicit Key Exchange  . . . . . . . . . . . . . . . . . 13
       4.6.  Law Enforcement  . . . . . . . . . . . . . . . . . . . . 13
       4.7.  Usage of other Algebraic Groups  . . . . . . . . . . . . 14
             4.7.1  DSA subgroup SKIA Setup . . . . . . . . . . . . . 14
             4.7.2  Escrowed DSA subgroup User Setup  . . . . . . . . 14
             4.7.3  Non-Escrowed DSA subgroup User Setup  . . . . . . 15
             4.7.4  DSA subgroup Authentication . . . . . . . . . . . 15



Danisch                      Informational                      [Page 1]

RFC 1824                          TESS                       August 1995


   5.  Multiple SKIAs . . . . . . . . . . . . . . . . . . . . . . . . 15
       5.1.  Unstructured SKIAs . . . . . . . . . . . . . . . . . . . 15
       5.2.  Hierarchical SKIAs . . . . . . . . . . . . . . . . . . . 16
       5.3.  Example: A DNS-based public key structure  . . . . . . . 18
   Security Considerations  . . . . . . . . . . . . . . . . . . . . . 19
   References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.  Introduction and preliminary remarks

   This RFC describes The Exponential Security System TESS [1].  TESS is
   a toolbox set system of different but cooperating cryptographic
   mechanisms and functions based on the primitive of discrete
   exponentiation. TESS is based on asymmetric cryptographical protocols
   and a structure of self-certified public keys.

   The most important mechanisms TESS is based on are the ElGamal
   signature [2, 3] and the KATHY protocols (KeY exchange with embedded
   AuTHentication), which were simultaneously discovered by Guenther [4]
   and Bauspiess and Knobloch [5, 6, 7].

   This RFC explains how to create and use the secret and public keys of
   TESS and shows a method for the secure distribution of the public
   keys.

   It is expected that the reader is familiar with the basics of
   cryptography, the Discrete Logarithm Problem, and the ElGamal
   signature mechanism.

   Due to the ASCII representation of this RFC the following style is
   choosen for mathematical purposes:

   -  a  ^  b  means the exponentiation of a to the power of b, which is
      always used within a modulo context.

   -  a[b] means a with an index or subscription of b.

   -  a = b means equality or congruency within a modulo context.

1.1.  Definition of terms/Terminology

   Key pair

      A key pair is a set of a public and a secret key which belong
      together.  There are two distinct kinds of key pairs, the SKIA key
      pair and the User key pair. (As will be shown in the section about
      hierarchical SKIAs, the two kinds of keys are not really distinct.
      They are the same thing seen from a different point of view.)



Danisch                      Informational                      [Page 2]

RFC 1824                          TESS                       August 1995


   User

      Any principal (human or machine) who owns, holds and uses a User
      key pair and can be uniquely identified by any description (see
      the Identity Descriptor below).

      In this RFC example users are referred to as A, B, C or Alice and
      Bob.

   SKIA

      SKIA is an acronym for "Secure Key Issuing Authority". The SKIA is
      a trusted local authority which generates the public and secret
      part of a User key pair. It is the SKIA's duty to verify whether
      the identity encoded in the key pair (see below) belongs to the
      key holder.  It has to check passports, identity cards, driving
      licenses etc. to investigate the real world identity of the key
      owner.  Since every key has an implicite signature of the SKIA it
      came from, the SKIA is responsible for the correctness of the
      encoded identity.

      Since the SKIA has to check the real identity of users, it is
      usually able to work within a small physical range only (like a
      campus or a city).  Therefore, not all users of a wide area or
      world wide area network can get their keys from the same SKIA with
      reasonable expense.  There is the need for multiple SKIAs which
      can work locally. This implies the need of a web of trust levels
      and trust forwards.  Communication partners with keys from the
      same SKIA know the public data of their SKIA because it is part of
      their own key.  Partners with keys from different SKIAs have to
      make use of the web to learn about the origin, the trust level,
      and the public key of the SKIA which issued the other key.

   Id[A] Identity Descriptor

      The Identity Descriptor is a part of the public User key. It is a
      somehow structured bitstring describing the key owner in a certain
      way. This description of the key owner should be precise enough to
      fully identify the owner of a User key. The description depends on
      the nature of the owner. For a human this could be the name, the
      address, the phone number, date of birth, size of the feet, color
      of the eyes, or anything else. For a machine this could be the
      hostname, the hostid, the internet address etc., for a fax machine
      or a modem it could be the international phone number.

      Furthermore, the description bitstring could contain key
      management data as the name of the SKIA (see below) which issued
      the key, the SKIA-specific serial number, the expiry date of the



Danisch                      Informational                      [Page 3]

RFC 1824                          TESS                       August 1995


      key, whether the secret part of the key is a software key or
      hidden in a hardware device (see section Enhancements), etc.

      Note that the numerical interpretation (the hash value) of the
      Identity Descriptor is an essential part of the mathematical
      mechanism of the TESS protocol. It can not be changed in any way
      without destroying the key structure.  Therefore, knowing the
      public part of a user key pair always means knowing the Identity
      Descriptor as composed by the SKIA which issued this key. This is
      an important security feature of this mechanism.

      The contents of the Identity Descriptor have to be verified by the
      issuing SKIA at key generation time. The trust level of the User
      Key depends on the trust level of the SKIA. A certain Identity
      Descriptor must not be used more than once for creating a User
      Key.  There must not exist distinct keys with the same Identity
      Descriptor.  Nevertheless, a user may have several keys with
      distinct expiration times, key lengths, serial numbers, or
      security levels, which affect the contents of the Identity
      Descriptor.

      However, it is emphasized that there are no assumptions about the
      structure of the Identity Descriptor.  The SKIA may choose any
      construction method depending on its purposes.

      The Identity Descriptor of a certain user A is referred to as
      Id[A].  Whereever the Identity Descriptor Id[A] is used in a
      mathematical context, its cryptographical hash sum H(Id[A]) is
      used.

   Encrypt(Key,Message)
   Decrypt(Key,Message)

      Encryption and Decryption of the Message with any common cipher.

1.2.  Required mechanisms

   The protocols described in this RFC require the following
   submechanisms:

   -  A random number generator of cryptographic quality

   -  A prime number generator of cryptographic quality

   -  A hash mechanism H() of cryptographic quality

   -  An encryption mechanism (e.g. a common block cipher)




Danisch                      Informational                      [Page 4]

RFC 1824                          TESS                       August 1995


   -  An arithmetical library for long unsigned integers

   -  A method for checking network identities against real-world
      identities (e.g. an authority which checks human identity cards
      etc.)

2.  Setup

   This section describes the base method for the creation of the SKIA
   and the User key pairs. Enhancements and modifications are described
   in subsequent sections.

   The main idea of the protocols described below is to generate an
   ElGamal signature (r,s) for an Identity Descriptor Id[A] of a user A.
   Id[A] and r form the user's public key and s is the users secret key.
   The connection between the secret and the public key is the
   verification equation for the ElGamal signature (r,s). Instead of
   checking the signature (r,s), the equation is used in 'reverse mode'
   to calculate r^s from public data without knowledge of the secret s.

   The authority generating those signatures is the SKIA introduced
   above.

2.1.  SKIA Setup

   By the following steps the SKIA key pair is created:

   -  p: choose a large prime p of at least 512 bit length.

   -  g: choose a primitive root g in GF(p)

   -  x: choose a random number x in the range 1 < x < p-1

   -  y:= ( g ^ x )  mod p

   The public part of the SKIA is the triple (p,g,y), the secret part is
   x.

   Since the public triple (p,g,y) is needed within the verification
   equation for the signatures created by the SKIA, this triple is also
   an essential part of all user keys generated by this SKIA.

2.2.  User Setup

   The User Setup is the generation of an ElGamal signature on the
   user's Identity Descriptor by the SKIA. This can be done more than
   once for a specific User, but it is done only once for a specific
   Identity Descriptor.



Danisch                      Informational                      [Page 5]

RFC 1824                          TESS                       August 1995


   To create a User key pair for a User A, the SKIA has to perform the
   following steps:

   -  Id[A]: Describe the key owner A in any way (name, address,  etc.),
      convert this description into a bit- or byte-oriented
      representation, and concatenate them to form the Identity
      Descriptor Id[A].

   -  k[A]: choose a random number k[A] with gcd(k[A],p-1) = 1. k[A]
      must not be revealed by the SKIA.

   -  r[A] := ( g ^ k[A] ) mod p

   -  s[A] := ( H(Id[A])  - x * r[A] ) *  ( k[A] ^ -1 )    mod (p-1)

   The calculated set of numbers fulfills the equation:

      x * r[A] + s[A] * k[A] = H(Id[A])  mod (p-1).

   The public part of the generated key of A consists of Id[A] and r[A],
   referenced to as (Id[A],r[A]) in the context of the triple (p,g,y).
   (Id[A],r[A]) always implicitely refers to the triple (p,g,y) of its
   parent SKIA.

   The secret part of the key is s[A].

   k[A] must be destroyed by the SKIA immediately after key generation,
   because User A could solve the equation and find out the SKIAs secret
   x if he knew both the s[A] and k[A].  The random number k must not be
   used twice. s[A] must not be equal to 0.

   Since (r[A],s[A]) are the ElGamal signature on Id[A], the connection
   between the SKIA public key und the User key pair is the ElGamal
   verification equation:

      r[A] ^ s[A] =  ( g ^ H(Id[A]) ) * ( y ^  (-r[A]) )  mod p.

   This equation allows to calculate r[A] ^ s[A] from public data
   without knowledge of the secret s[A].  Since this equation is used
   very often, and for reasons of readability, the abbreviation Y[A] is
   used for this equation.

   Y[A] means to calculate the value of r[A] ^ s[A] which is

      ( g ^ H(Id[A]) ) * ( y ^ (-r[A]) )  mod p.






Danisch                      Informational                      [Page 6]

RFC 1824                          TESS                       August 1995


   Note that a given value of Y[A] is not reliable. It must have been
   reliably calculated from (p,g,y) and (Id[A],r[A]).  Y[A] is to be
   understood as a macro definition, not as a value.

   Obviously both the SKIA and the User know the secret part of the
   User's key and can reveal it, either accidently or in malice
   prepense.  The enhancements section below shows methods to avoid
   this.

3.  Authentication

   This section describes the basic methods of applying the User keys.
   They refer to online and offline communication between two users
   A(lice) and B(ob).

   The unilateral and the mutual authentications use the KATHY protocol
   to generate reliable session keys for further use as session
   encryption keys etc.

3.1.  Zero Knowledge Authentication

   The "Zero Knowledge Authentication" is used if Alice wants to
   authenticate herself to Bob without need for a session key.

   Assuming that Bob already reliably learned the (p,g,y) of the SKIA
   Alice got her key from, the steps are:

   1. Alice generates a large random number t, 1