home *** CD-ROM | disk | FTP | other *** search
/ Handbook of Infosec Terms 2.0 / Handbook_of_Infosec_Terms_Version_2.0_ISSO.iso / text / rfcs / rfc1824.txt < prev    next >
Text File  |  1996-05-07  |  44KB  |  713 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                         H. Danisch Request for Comments: 1824                                 E.I.S.S./IAKS Category: Informational                                      August 1995 
  8.  
  9.                   The Exponential Security System TESS:                 An Identity-Based Cryptographic Protocol                      for Authenticated Key-Exchange                         (E.I.S.S.-Report 1995/4) 
  10.  
  11. Status of this Memo 
  12.  
  13.    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. 
  14.  
  15. Abstract 
  16.  
  17.    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. 
  18.  
  19. Table of Contents 
  20.  
  21.    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 
  22.  
  23.  
  24.  
  25. Danisch                      Informational                      [Page 1] 
  26.  RFC 1824                          TESS                       August 1995 
  27.  
  28.     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 
  29.  
  30. 1.  Introduction and preliminary remarks 
  31.  
  32.    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. 
  33.  
  34.    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]. 
  35.  
  36.    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. 
  37.  
  38.    It is expected that the reader is familiar with the basics of    cryptography, the Discrete Logarithm Problem, and the ElGamal    signature mechanism. 
  39.  
  40.    Due to the ASCII representation of this RFC the following style is    choosen for mathematical purposes: 
  41.  
  42.    -  a  ^  b  means the exponentiation of a to the power of b, which is       always used within a modulo context. 
  43.  
  44.    -  a[b] means a with an index or subscription of b. 
  45.  
  46.    -  a = b means equality or congruency within a modulo context. 
  47.  
  48. 1.1.  Definition of terms/Terminology 
  49.  
  50.    Key pair 
  51.  
  52.       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.) 
  53.  
  54.  
  55.  
  56. Danisch                      Informational                      [Page 2] 
  57.  RFC 1824                          TESS                       August 1995 
  58.  
  59.     User 
  60.  
  61.       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). 
  62.  
  63.       In this RFC example users are referred to as A, B, C or Alice and       Bob. 
  64.  
  65.    SKIA 
  66.  
  67.       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. 
  68.  
  69.       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. 
  70.  
  71.    Id[A] Identity Descriptor 
  72.  
  73.       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. 
  74.  
  75.       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 
  76.  
  77.  
  78.  
  79. Danisch                      Informational                      [Page 3] 
  80.  RFC 1824                          TESS                       August 1995 
  81.  
  82.        key, whether the secret part of the key is a software key or       hidden in a hardware device (see section Enhancements), etc. 
  83.  
  84.       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. 
  85.  
  86.       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. 
  87.  
  88.       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. 
  89.  
  90.       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. 
  91.  
  92.    Encrypt(Key,Message)    Decrypt(Key,Message) 
  93.  
  94.       Encryption and Decryption of the Message with any common cipher. 
  95.  
  96. 1.2.  Required mechanisms 
  97.  
  98.    The protocols described in this RFC require the following    submechanisms: 
  99.  
  100.    -  A random number generator of cryptographic quality 
  101.  
  102.    -  A prime number generator of cryptographic quality 
  103.  
  104.    -  A hash mechanism H() of cryptographic quality 
  105.  
  106.    -  An encryption mechanism (e.g. a common block cipher) 
  107.  
  108.  
  109.  
  110.  Danisch                      Informational                      [Page 4] 
  111.  RFC 1824                          TESS                       August 1995 
  112.  
  113.     -  An arithmetical library for long unsigned integers 
  114.  
  115.    -  A method for checking network identities against real-world       identities (e.g. an authority which checks human identity cards       etc.) 
  116.  
  117. 2.  Setup 
  118.  
  119.    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. 
  120.  
  121.    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. 
  122.  
  123.    The authority generating those signatures is the SKIA introduced    above. 
  124.  
  125. 2.1.  SKIA Setup 
  126.  
  127.    By the following steps the SKIA key pair is created: 
  128.  
  129.    -  p: choose a large prime p of at least 512 bit length. 
  130.  
  131.    -  g: choose a primitive root g in GF(p) 
  132.  
  133.    -  x: choose a random number x in the range 1 < x < p-1 
  134.  
  135.    -  y:= ( g ^ x )  mod p 
  136.  
  137.    The public part of the SKIA is the triple (p,g,y), the secret part is    x. 
  138.  
  139.    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. 
  140.  
  141. 2.2.  User Setup 
  142.  
  143.    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. 
  144.  
  145.  
  146.  
  147. Danisch                      Informational                      [Page 5] 
  148.  RFC 1824                          TESS                       August 1995 
  149.  
  150.     To create a User key pair for a User A, the SKIA has to perform the    following steps: 
  151.  
  152.    -  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]. 
  153.  
  154.    -  k[A]: choose a random number k[A] with gcd(k[A],p-1) = 1. k[A]       must not be revealed by the SKIA. 
  155.  
  156.    -  r[A] := ( g ^ k[A] ) mod p 
  157.  
  158.    -  s[A] := ( H(Id[A])  - x * r[A] ) *  ( k[A] ^ -1 )    mod (p-1) 
  159.  
  160.    The calculated set of numbers fulfills the equation: 
  161.  
  162.       x * r[A] + s[A] * k[A] = H(Id[A])  mod (p-1). 
  163.  
  164.    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. 
  165.  
  166.    The secret part of the key is s[A]. 
  167.  
  168.    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. 
  169.  
  170.    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: 
  171.  
  172.       r[A] ^ s[A] =  ( g ^ H(Id[A]) ) * ( y ^  (-r[A]) )  mod p. 
  173.  
  174.    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. 
  175.  
  176.    Y[A] means to calculate the value of r[A] ^ s[A] which is 
  177.  
  178.       ( g ^ H(Id[A]) ) * ( y ^ (-r[A]) )  mod p. 
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  Danisch                      Informational                      [Page 6] 
  185.  RFC 1824                          TESS                       August 1995 
  186.  
  187.     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. 
  188.  
  189.    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. 
  190.  
  191. 3.  Authentication 
  192.  
  193.    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). 
  194.  
  195.    The unilateral and the mutual authentications use the KATHY protocol    to generate reliable session keys for further use as session    encryption keys etc. 
  196.  
  197. 3.1.  Zero Knowledge Authentication 
  198.  
  199.    The "Zero Knowledge Authentication" is used if Alice wants to    authenticate herself to Bob without need for a session key. 
  200.  
  201.    Assuming that Bob already reliably learned the (p,g,y) of the SKIA    Alice got her key from, the steps are: 
  202.  
  203.    1. Alice generates a large random number t, 1<t<p-1, where  t  should       have approximately the same length as p-1. 
  204.  
  205.    2. a := r[A] ^ t  mod p 
  206.  
  207.    3. Alice sends her public key (Id[A],r[A]) and the number a to Bob. 
  208.  
  209.    4. Bob  generates a large random number c, c<p-1, where c should have       approximately the same length as p-1, and sends c to Alice. 
  210.  
  211.    5. Alice calculates       c' := (c * s[A] + t) mod (p-1)       and sends c' to Bob. 
  212.  
  213.    6. Bob verifies whether       r[A] ^ c' = (Y[A] ^ c) * a    mod p. 
  214.  
  215.    This is the Beth-Zero-Knowledge protocol [8] which is based on self-    certified public keys and an improvement of the DLP-Zero-Knowledge    identification protocol from Chaum, Evertse, and van de Graaf [9]. 
  216.  
  217.  
  218.  
  219.  Danisch                      Informational                      [Page 7] 
  220.  RFC 1824                          TESS                       August 1995 
  221.  
  222.  3.2.  Unilateral Authentication 
  223.  
  224.    The "Unilateral Authentication" (or "Half Authentication") can be    used in those cases: 
  225.  
  226.    - Alice wants to authenticate herself to Bob without Bob      authenticating himself to Alice. 
  227.  
  228.    - Bob wants to send an encrypted message to Alice readable by her      only (offline encryption). 
  229.  
  230.    A shared key is generated by the following protocol. This key can be    known by Alice and Bob only. 
  231.  
  232.    Assuming that Bob already reliably learned the (p,g,y) of the SKIA    Alice got her key from, the steps are: 
  233.  
  234.    1. Alice sends her public key (Id[A],r[A]) to Bob if he does not       already know it. 
  235.  
  236.    2. Bob chooses a random number 1 < z[A] < p-1 and calculates       v[A] := r[A] ^ z[A] mod p 
  237.  
  238.    3. Bob sends v[A] to Alice. 
  239.  
  240.    4. Alice and Bob calculate the session key: 
  241.  
  242.       Alice: key[A] := v[A] ^ s[A] mod p       Bob:   key[A] := Y[A] ^ z[A] mod p 
  243.  
  244.    Apply the equations of the User Key Setup section to Bob's equation    to see that Alice and Bob get the very same key in step 4: 
  245.  
  246.       key[A] = r[A] ^ ( s[A] * z[A] ) mod p 
  247.  
  248.    A third party cannot calculate key[A], because it has neither s[A]    nor z[A]. Therefore, Bob can trust in the fact that only Alice is    able to know the key[A] (as long as nobody else knows her secret    s[A]). 
  249.  
  250.    This protocol is based on the Diffie-Hellman scheme [10], but avoids    the weakness of the missing authenticity of the public keys. 
  251.  
  252.    In this protocol Bob did not verify whether Alice really knew her    s[A] and was able to calculate key[A]. Therefore, a final challenge-    response step should be performed in case of online communication    (see the subsection below). 
  253.  
  254.  
  255.  
  256.  Danisch                      Informational                      [Page 8] 
  257.  RFC 1824                          TESS                       August 1995 
  258.  
  259.     In case of sending encrypted messages, Bob can execute step 4 before    step 3, use the key[A] to encrypt the message, and send the encrypted    message together with v[A] in step 3. 
  260.  
  261. 3.3.  Mutual Authentication 
  262.  
  263.    The "Mutual Authentication" is used for online connections where both    Alice and Bob want to authenticate to each other. 
  264.  
  265.    Within this protocol description it is assumed that Alice and Bob    have keys of the same SKIA and use the same triple (p,g,y). Otherwise    in each step the triple has to be used which belongs to the user key    it is applied to. 
  266.  
  267.    The steps are as follows (where the first four steps are exactly    twice the "Unilateral Authentication" and steps 5-9 form a mutual    challenge-response step to find out whether the other side really got    the key): 
  268.  
  269.    1. Alice sends her (Id[A],r[A]) to Bob.       Bob sends his (Id[B],r[B]) to Alice. 
  270.  
  271.    2. Bob chooses a random number z[A] < p-1       and calculates v[A] := r[A] ^ z[A] mod p 
  272.  
  273.       Alice chooses a random number z[B] < p-1       and calculates v[B] := r[B] ^ z[B] mod p 
  274.  
  275.    3. Bob sends v[A] to Alice.       Alice sends v[B] to Bob. 
  276.  
  277.    4. Alice and Bob calculate the session keys: 
  278.  
  279.       Alice: key[A] := v[A] ^ s[A] mod p              key[B] := Y[B] ^ z[B] mod p 
  280.  
  281.       Bob:   key[B] := v[B] ^ s[B] mod p              key[A] := Y[A] ^ z[A] mod p 
  282.  
  283.    5. Alice chooses a random number R[B]       Bob   chooses a random number R[A] 
  284.  
  285.    6. Alice sends Encrypt(key[B],R[B]) to Bob.       Bob   sends Encrypt(key[A],R[A]) to Alice. 
  286.  
  287.    7. Alice and Bob decrypt the received messages to R'[A] and R'[B]. 
  288.  
  289.  
  290.  
  291.  
  292.  
  293. Danisch                      Informational                      [Page 9] 
  294.  RFC 1824                          TESS                       August 1995 
  295.  
  296.     8. Alice sends Encrypt(key[A],T(R'[A])) to Bob.       Bob   sends Encrypt(key[B],T(R'[B])) to Alice. 
  297.  
  298.    9. Alice and Bob decrypt the received messages to R''[A] and R''[B] 
  299.  
  300.   10. Alice verifies whether T(R[B]) = R''[B].       Bob   verifies whether T(R[A]) = R''[A]. 
  301.  
  302.     T()  is a simple bijective transformation function, e.g. increment(). 
  303.  
  304.    After step 4 Alice can trust in the fact that only Bob and herself    can know key[B], but she still does not know whether she is really    talking to Bob. Therefore, she forces Bob to make use of his key    within steps 5-9. Alice now has checked whether she really talks to    Bob. Since the scheme is symmetrical, Bob also knows that he talks to    Alice. 
  305.  
  306. 3.4.  Message Signing 
  307.  
  308.    To sign a message m (where H(m) is a cryptographic hash value of the    message), the message author A generates an ElGamal signature by    using his r[A] as the generator and the s[A] as his secret: 
  309.  
  310.    -  A generates a random number K with gcd(K,p-1) = 1. 
  311.  
  312.    -  R := r[A] ^ K mod p 
  313.  
  314.    -  S := ( H(m) - s[A] * R ) * (K ^ -1)   mod (p-1) 
  315.  
  316.    The calculated set of numbers fulfills the equation: 
  317.  
  318.       ( s[A] * R + K * S ) = H(m) mod(p-1) 
  319.  
  320.    The signed message consists of (m,Id[A],r[A],R,S). 
  321.  
  322.    The receiver of the message checks the authenticity of the message by    calculating the hash value H(m) and verifying the equation: 
  323.  
  324.       r[A] ^ H(m) = ( Y[A] ^ R )  * ( R ^ S )  mod p 
  325.  
  326. 4.  Enhancements 
  327.  
  328.    This section describes several enhancements and modifications of the    base protocol as well as other comments. 
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  Danisch                      Informational                     [Page 10] 
  335.  RFC 1824                          TESS                       August 1995 
  336.  
  337.  4.1.  Non-Escrowed Key Generation 
  338.  
  339.    Within the normal User Setup procedure for a User A, the SKIA gains    knowledge about the secret key s[A]. The SKIA could use this key to    fake signatures or decrypt messages, or to allow others to do so. 
  340.  
  341.    To avoid this situation, a slight modification of the User Setup    procedure may be applied. The SKIA Setup is the same as in the base    protocol. 
  342.  
  343.    Within the User Setup the SKIA does not use its primitive element g,    but a generator created by the User instead. 
  344.  
  345.    The modified scheme looks like this: 
  346.  
  347.    -  User A generates a random number a with gcd(a,p-1)=1 
  348.  
  349.    -  User A calculates g' := g^a mod p and forwards g' to the SKIA. 
  350.  
  351.    -  The SKIA generates Id[A] and k[A] as in the base protocol 
  352.  
  353.    -  The SKIA sets r[A] := ( g' ^ k[A] ) mod p and       s'[A] := ( H(Id[A])  - x * r[A] ) *  (k[A] ^ -1)    mod (p-1) 
  354.  
  355.    -  The SKIA forwards (Id[A],r[A],s'[A]) to the user A 
  356.  
  357.    -  The user A calculates his s[A] := s'[A] * (a^-1) mod (p-1) 
  358.  
  359.    The SKIA is not able to find out the secret key s[A] of A.  This    protocol is based on the idea of the 'testimonial' [11]. 
  360.  
  361.    The SKIA is still able to create a second key with the same Identity    Descriptor (identical or at least having same contents), but with    different r[A] and s[A]. If such a second key was successfully used    for authentication or message signing, the real key owner can use his    own key to proof the existence of two different keys with identical    (equivalent) Descriptors. The existence of such two keys shows that    the SKIA cannot be trusted any longer. 
  362.  
  363.    If the key is generated by this method, it should be mentioned in the    Identity Descriptor. This allows any communication partners to look    up in the public part of a key whether the secret part is known to    the SKIA. 
  364.  
  365. 4.2.  Hardware Protected Key 
  366.  
  367.    The protocol of the previous subsection guaranteed that the SKIA does    not know the user's secret key. 
  368.  
  369.  
  370.  
  371. Danisch                      Informational                     [Page 11] 
  372.  RFC 1824                          TESS                       August 1995 
  373.  
  374.     On the other hand, the SKIA may wish that the user himself does not    know his own secret key. This may be necessary because the user could    otherwise reveal his secret key accidently or intentionally.    Especially if untrusted hard- or software or an environment without    trusted process protection is used, the secret key can be spied out.    For high-level security applications this might not be acceptable.    The key owner must be able to use his key without being able to read    this key. This contradiction can be solved by hiding the secret part    of the User Key within a protected hardware device. 
  375.  
  376.    Within the SELANE project, the protocols described in this RFC were    implemented for SmartCards. The User Key is created using the non-    escrowed key generation procedure described in the previous section,    modified such that the random number is generated inside the card.    The secret s[A] exists only inside the card and does not get outside.    The SmartCard is able to execute all parts of the algorithms which    need access to the secret key.  To make use of the SmartCard an    additional password is required. 
  377.  
  378.    If the key is hidden in such a hardware device, it should be    mentioned in the Identity Descriptor. This allows any communication    partners to look up in the public part of a key whether the key is    hardware protected. 
  379.  
  380. 4.3.  Key Regeneration 
  381.  
  382.    If both methods of the previous subsections are used to protect the    key, neither the SKIA nor the User himself knows the secret key. This    could be harmful for the User if the hardware device is lost or    damaged, because the User could become unable to decrypt messages    encrypted with the public key. 
  383.  
  384.    To prevent such a denial of service, there are two methods: 
  385.  
  386.    - If the protection factor 'a' was choosen by the User, the User      can deposit the factor 'a' in a secure way, e.g. give it as a      shared secret to his friends. The SKIA can do the same and      deposit s'[A] somewhere else.  If the SKIA and the User      cooperate, they are able to create a second hardware device      equivalent to the first. 
  387.  
  388.    - If the protection factor a was generated inside of the hardware      device, the device itself may give out the s[A] or the a in a      secure way (e.g. as a shared secret). 
  389.  
  390.    Since the recreation of a User key defeats the property of such a key    to exist only once, the SKIA should restrict this to special cases    only.  Furthermore it should be done only after the end of the 
  391.  
  392.  
  393.  
  394. Danisch                      Informational                     [Page 12] 
  395.  RFC 1824                          TESS                       August 1995 
  396.  
  397.     lifetime of the key, if its lifetime was limited. 
  398.  
  399. 4.4.  r ^ r 
  400.  
  401.    A slight modification of the base protocol allows some speedup in the    key exchange: 
  402.  
  403.    -  The SKIA is created as in the base protocol 
  404.  
  405.    -  For the User Setup the SKIA solves the equation       x * s[A] + r[A] * k[A] = H(Id[A]) mod (p-1)       which differs from the base protocol in that r and s were swapped. 
  406.  
  407.    -  The public key allows to calculate       y ^ s[A] = ( g ^ H(Id[A]) ) * ( r[A] ^ -r[A] )  mod p       without knowing s[A]. Here the term  (  r[A]  ^  -r[A]  )  can  be       precalculated for speedup. 
  408.  
  409.    -  Bob calculates key[A] := ( g ^ H(Id[A]) * r[A] ^ -r[A] ) ^ z[A]                and     v[A] := y ^ z[A] mod p       Alice gets     key[A] := v[A] ^ s[A] mod p       where key[A] = y ^ (s[A] * z[A]) 
  410.  
  411.    This protocol is similar to the AMV modification by Agnew et al.    [12]. 
  412.  
  413. 4.5.  Implicit Key Exchange 
  414.  
  415.    If the r ^ r protocol of the previous section is used, an implicit    shared key can be calculated for Alice and Bob by using the Diffie-    Hellman scheme: 
  416.  
  417.    -  Alice: key[A,B] = ( g ^ H(Id[B]) * r[B] ^ -r[B] ) ^ s[A] mod p     -  Bob:   key[B,A] = ( g ^ H(Id[A]) * r[A] ^ -r[A] ) ^ s[B] mod p 
  418.  
  419.    where key[A,B] = key[B,A] = y ^ (s[A] * s[B]). 
  420.  
  421.    This can not be used with Non-escrowed keys. 
  422.  
  423. 4.6.  Law Enforcement 
  424.  
  425.    This will be subject of a separate RFC. 
  426.  
  427.  
  428.  
  429.  
  430.  
  431.  
  432.  
  433.  Danisch                      Informational                     [Page 13] 
  434.  RFC 1824                          TESS                       August 1995 
  435.  
  436.  4.7.  Usage of other Algebraic Groups 
  437.  
  438.    Within this RFC calculations were based on a specific algebraic    group, the multiplicative group of integers modulo a prime number p    (which is the multiplicative group of a finite field GF(p)). However,    any cyclic finite group with a strong discrete logarithm problem can    be used, e.g., a subgroup of the multiplicative group or elliptic    curves. 
  439.  
  440.    As an example the subgroup used by the DSA (Digital Signature    Algorithm) of length N can be used instead of the full multiplicative    group of GF(p) for speedup (in this case the Secure Hash Algorithm    SHA is recommended as the hash algorithm).  See [13, 14] for a    description of DSA and SHA. 
  441.  
  442. 4.7.1.  DSA subgroup SKIA Setup 
  443.  
  444.    -  Generate  large  primes  p  and  q such that p is at least 512 bit       long, q is 160 bit long, and q is a factor of (p-1). 
  445.  
  446.    -  choose a primitive root h in GF(p) 
  447.  
  448.    -  g:= h^((p-1)/q)       Note that g generates a subgroup G with |G|=q 
  449.  
  450.    -  x: a random number of about 160 bit. 
  451.  
  452.    -  y:= ( g ^ x ) mod p 
  453.  
  454.    The public key of the SKIA is (p,g,y,q). (q is required for speedup    only.) 
  455.  
  456.    The secret key of the SKIA is x. 
  457.  
  458. 4.7.2.  Escrowed DSA subgroup User Setup 
  459.  
  460.    -  k[A]: a random number of 160 bit length with gcd(k[A],q)=1 
  461.  
  462.    -  r[A]:= ( g ^ k[A] ) mod p 
  463.  
  464.    -  s[A]:= (H(Id[A]) + x * r[A]) * (k[A] ^ -1)  mod q 
  465.  
  466.    Again, (Id[A],r[A]) is the public key and s[A] is the secret key.    Note that r[A] has the length of p and s[A] has the length of q (160    bit). 
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  Danisch                      Informational                     [Page 14] 
  473.  RFC 1824                          TESS                       August 1995 
  474.  
  475.  4.7.3.  Non-Escrowed DSA subgroup User Setup 
  476.  
  477.    -  User A generates a random number h of 160 bit length. 
  478.  
  479.    -  User A calculates a := g^h mod p and sends a to the SKIA. 
  480.  
  481.    -  The SKIA generates the user key with the secret key s'[A]. 
  482.  
  483.    -  User A calculates s[A]:= s'[a] * (h^-1) mod q 
  484.  
  485. 4.7.4.  DSA subgroup Authentication 
  486.  
  487.    The protocols for authentication are the same as described above,    except that wherever the modulus (p-1) was used the smaller modulus q    is used instead, and DSA is used for message signing. 
  488.  
  489.    The abbreviation Y[A] still stands for r[A] ^ s[A], which is now (the    sign of r[A] was changed for speedup) 
  490.  
  491.       ( g ^ H(Id[A])) * ( y ^ r[A] ) mod p 
  492.  
  493.    and can be calculated in a faster way as 
  494.  
  495.       u1 * u2 mod p 
  496.  
  497.    where 
  498.  
  499.       u1 := g ^ ( H(Id[A])  mod q )  mod p       u2 := y ^ ( r[A] mod q ) mod p. 
  500.  
  501. 5.  Multiple SKIAs 
  502.  
  503.    In the preceding sections it was assumed that everybody learned the    (p,g,y) triple of a SKIA reliably. 
  504.  
  505.    By default, a User reliably learns only the (p,g,y) of the SKIA which    generated his own key, because he gets the triple with his key and    can verify the triple with the signature verification equation. 
  506.  
  507.    If the User wants to communicate with someone whose key was generated    by a different SKIA, a method for authenticating the (p,g,y) of the    other SKIA is needed. 
  508.  
  509. 5.1.  Unstructured SKIAs 
  510.  
  511.    This will be subject of a separate RFC. 
  512.  
  513.  
  514.  
  515.  
  516.  
  517. Danisch                      Informational                     [Page 15] 
  518.  RFC 1824                          TESS                       August 1995 
  519.  
  520.  5.2.  Hierarchical SKIAs 
  521.  
  522.    If there is a hierarchy between the SKIAs, their keys can be    generated hierarchically: 
  523.  
  524.    -  Every SKIA and every User has a level  (expressed  as  a  cardinal       number).  The root SKIA has level 0. All Users and all other SKIAs       have levels greater than 0. 
  525.  
  526.    -  Each SKIA except the root SKIA is also a User, and each  User  can       be a SKIA. 
  527.  
  528.       A SKIA of level n generates keys for Users of level n+1. 
  529.  
  530.       A User of level n is also a SKIA of level n. 
  531.  
  532.    -  Since  every SKIA (except the root SKIA) is also a User, each SKIA       has an Identity Descriptor describing its Identity and perhaps its       level  and  its  parent  SKIA. There is a function parent(A) which       finds the parent SKIA for every user  A.  This  function  may  use       informations stored in the Identity Descriptor. 
  533.  
  534.       Thus,  the  parent()  function allows to find the path to the root       SKIA for every node of the tree forming the hierarchy. 
  535.  
  536.       The root SKIA may also have an Identity Descriptor. 
  537.  
  538.    -  The root SKIA creates itself as in the base protocol. 
  539.  
  540.    -  The key for a User A of level n (n>0) is generated by  the  parent       SKIA  of  level  n-1.  The public part is (Id[A],r[A]), the secret       part is (s[A]). 
  541.  
  542.       User A is automatically SKIA A: 
  543.  
  544.       p[A] := p[parent(A)]  = p of the root SKIA       g[A] := r[A]       x[A] := s[A]       y[A] := g[A] ^ x[A] = r[A] ^ s[A] = Y[A] =              ( g[parent(A)] ^ H(Id[A]) ) * ( y[parent(A)] ^ -r[A]) mod p 
  545.  
  546.       Therefore, the public data (p,g[A],y[A]) of  the  SKIA  A  can  be       calculated  by everyone from the public data of the User A and the       public data of its parent SKIA. The SKIA  A  itself  may  use  the       faster  method  to  get  y[A]  by  calculating  r[A] ^ s[A], while       everybody else has to use the slower but public method as  in  the       lower  equation.  The  secret  of the "SKIA A" is identical to the       secret of the "User A". 
  547.  
  548.  
  549.  
  550. Danisch                      Informational                     [Page 16] 
  551.  RFC 1824                          TESS                       August 1995 
  552.  
  553.        Since a User A uses the very same data to act as either a user  or       as a SKIA, and since message signing (subsection 3.4.) is the very       same procedure as generating a User key (in fact it  is  the  same       thing),   a  user  should  not  sign  a  message  which  could  be       misunderstood  as  an  Identity  Descriptor.  An  attacker   could       intercept  the  message  and  its signature and abuse it as a User       key. This can be avoided by the use of tags  which  preceed  every       set  of  data  being signed and show whether it is a message or an       Identity Descriptor. 
  554.  
  555.    This scheme allows any two users (even users of distinct hierarchies)    to communicate reliably. They need to know the public data (p,g,y) of    each other's root SKIA only. There is no need for online key servers. 
  556.  
  557.    The communication is the same as in the base protocols but with an    extension to the method of finding Y[A] (again with Alice and Bob): 
  558.  
  559.    -  Bob reliably learned the (p,g,y) of Alice's root SKIA S(0). 
  560.  
  561.    -  Where Alice presented (Id[A],r[A]) only in the first step, she now       presents (Id[S],r[S]) for each SKIA/User node S in her path to her       root SKIA S(0).  Since  this  information  does  not  need  to  be       reliable  or  signed,  it  can  be  provided  by any simple server       mechanism. 
  562.  
  563.    -  Bob iteratively calculates the public data (p,g,y) of each SKIA in       the  path,  starting  with  Alice's  root  SKIA, until he gets the       (p,g,y) of Alice where y is Y[Alice]. 
  564.  
  565.    Note that Bob did not have to verify anything within the iteration.    After the iteration he has a set of public SKIA data (p,g,y) to be    used with Alice public key, but he still does not know whether he was    spoofed with wrong data of Alice or her parent SKIAs. 
  566.  
  567.    Since the iteration Bob calculated is a chain of nested signatures,    the correctness of the (p,g,y) he gets depends on every single step.    If there is at least one step with a bad Id[S] or r[S], Bob will get    a wrong Y[S] in this step and all following steps, and the chain    doesn't work. 
  568.  
  569.    If the chain calculated by Bob was not completely correct for any    reason, Alice cannot make use of her key: her signatures do not    verify, she cannot decrypt encrypted messages and she cannot answer    to the challenge response step in case of mutual authentication. 
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576.  
  577. Danisch                      Informational                     [Page 17] 
  578.  RFC 1824                          TESS                       August 1995 
  579.  
  580.  5.3.  Example: A DNS-based public key structure 
  581.  
  582.    Here is a simple example of the usage of the hierarchical SKIA scheme    within the DNS name space: 
  583.  
  584.    Let every domain also be a SKIA, and let the root domain be a root    SKIA. Let the Identity Descriptor of any object within the name space    be its name: the domain name for domains, the host name for machines,    the mail address for humans and services. 
  585.  
  586.    Consequently, a user with the mail address "danisch@ira.uka.de" got    his key from the SKIA of the domain "ira.uka.de". This SKIA was    authorized by the SKIA of "uka.de", which was authorized by the SKIA    of "de", which is the root SKIA of Germany. It is assumed that    everybody reliably learned the public key of the german root domain    "de". 
  587.  
  588.    The public key of danisch@ira.uka.de would look like: 
  589.  
  590.       (  "danisch@ira.uka.de", r[danisch@ira.uka.de] ,          "ira.uka.de"        , r[ira.uka.de]         ,          "uka.de"            , r[uka.de]       ) 
  591.  
  592.    For the reasons described in the previous subsection, this key is    self-certified and does not need any further signature. 
  593.  
  594.    The key can be presented by danisch@ira.uka.de within online    communications, be appended to signed messages, or simply be    retrieved by the domain name server of ira.uka.de. 
  595.  
  596.    Someone who reliably learned the (p,g,y) of the root domain .de    (Germany) can now build the chain: 
  597.  
  598.       "de"                        (p,g,y)[de]       "uka.de"                    (p,g,y)[uka.de]       "ira.uka.de"                (p,g,y)[ira.uka.de]       "danisch@ira.uka.de"        (p,g,y)[danisch@ira.uka.de] 
  599.  
  600.    Thus it is possible to reliably obtain the Y[danisch@ira.uka.de]. 
  601.  
  602.    To communicate with the whole world, knowledge of the public keys of    all root domain SKIAs only is needed. These keys can be stored within    some tens of KBytes.  No third party is needed for doing an    authenticated key exchange. 
  603.  
  604.    The whole world could also be based on a single root SKIA; in this    case a single (p,g,y) is needed only. 
  605.  
  606.  
  607.  
  608. Danisch                      Informational                     [Page 18] 
  609.  RFC 1824                          TESS                       August 1995 
  610.  
  611.     In a more realistic example the Id[danisch@ira.uka.de] could contain: 
  612.  
  613.       creator=      ira.uka.de       created=      1-Jun-1995       expiry=       31-Dec-1999       protection=   non-escrowed, smartcard       type=         human       name=         Hadmut Danisch       email=        danisch@ira.uka.de       phone=        +49 721 9640018       fax=          +49 721 696893       photo=        <digitized compressed portrait> 
  614.  
  615. Security Considerations 
  616.  
  617.    -  The strength of TESS depends  on  the  strength  of  the  discrete       logarith  problem,  the strength of the ElGamal signature, and the       confidentiality of the SKIAs. 
  618.  
  619.    -  Attention should be paid to the  security  considerations  of  the       underlying mechanisms (ElGamal, DSA, Diffie-Hellman, etc.). 
  620.  
  621.    -  Since  the  SKIA  creates  itself  under  normal circumstances, an       attacker could create his own SKIA and use it to create a User Key       with  an  arbitrary  Identity  Descriptor.  This  shows  that  the       Identity Descriptor is as reliable as the  origin  of  the  triple       (p,g,y) of the SKIA it came from. The User Key creation process is       a signature process  for  the  Identity  Descriptor  and  strongly       depends on the trustworthyness of the signing SKIA. 
  622.  
  623.    -  It  is  the  SKIA's  duty  to  give  the s[A] only to the user the       Identity Descriptor belongs to. 
  624.  
  625.    -  Since the very same procedure is used  for  signing  messages  and       generating  user  keys,  it  is  important  to distinguish between       messages and keys. 
  626.  
  627.    -  The authentication protocols work  without  an  online  authority.       Therefore,  there  is  no  simple  way for revoking keys. For this       reason keys should  have  an  expiration  date  mentioned  in  the       Identity  Descriptor.  In  case  of  the hierarchical scheme a key       expires if any key in the path to the root SKIA expires. 
  628.  
  629.  
  630.  
  631.  
  632.  
  633.  
  634.  
  635.  
  636.  
  637. Danisch                      Informational                     [Page 19] 
  638.  RFC 1824                          TESS                       August 1995 
  639.  
  640.  References 
  641.  
  642. 1.    Th. Beth, F. Bauspiess, H.-J. Knobloch,  S.  Stempel,  "TESS  -  A       Security  System  based  on Discrete Exponentation," Computer       Communcations Journal, Vol. 17, Special Issue, No.  7, pp.       466-475 (1994). 
  643.  
  644. 2.    T.  ElGamal,  "A  Public  Key  Cryptosystem and a Signature Scheme       Based on  Discrete  Logarithm,"  IEEE-Trans.  Information  Theory,       IT-31, pp. 469-472 (July 1985). 
  645.  
  646. 3.    B.  Klein, H.-J. Knobloch, "ElGamal-Signatur" in       Sicherheitsmechanismen, ed. Fries, Fritsch, Kessler, Klein, pp.       171-176, Oldenburg, Muenchen (1993). 
  647.  
  648. 4.    C.  G.  Guenther, "An Identity-Based Key-Exchange Protocol" in       Advances in Cryptology, Proceedings of Eurocrypt '89,  pp.  29-37,       Springer (1990). 
  649.  
  650. 5.    B.  Klein,  H.-J. Knobloch, "KATHY" in Sicherheitsmechanismen, ed.       Fries, Fritsch, Kessler, Klein, pp. 252-259,  Oldenburg,  Muenchen       (1993). 
  651.  
  652. 6.    F. Bauspiess, H.-J. Knobloch, "How to keep authenticity alive in a       computer network" in Advances in Cryptology, Proceedings of       Eurocrypt '89, pp. 38-46, Springer (1990). 
  653.  
  654. 7.    F.  Bauspiess,  "SELANE  -  An  Approach  to  Secure  Networks" in       Abstracts of SECURICOM '90, pp. 159-164, Paris (1990). 
  655.  
  656. 8.    Th. Beth,  "Efficient  zero-knowledge  identification  scheme  for       smart  cards"  in Advances in Cryptology, Proceedings of Eurocrypt       '88, pp. 77-84, Springer (1988). 
  657.  
  658. 9.    D. Chaum, J. H. Evertse, J. van de Graaf,  "An  improved  protocol       for demonstrating possesion of discrete logarithms and some       generalizations" in Advances in Cryptology, Proceedings of       Eurocrypt '87, pp. 127-141, Springer (1988). 
  659.  
  660. 10.   W.  Diffie,  M.  Hellman,  "New directions in cryptography," IEEE-       Trans. Information Theory, 22, pp. 644-654 (1976). 
  661.  
  662. 11.   Th. Beth, H.-J. Knobloch, "Open network authentication without  an       online  server"  in  Proc.  Symposium on Comput. Security '90, pp.       160-165, Rome, Italy (1990). 
  663.  
  664.  
  665.  
  666.  
  667.  
  668.  Danisch                      Informational                     [Page 20] 
  669.  RFC 1824                          TESS                       August 1995 
  670.  
  671.  12.   G. B. Agnew, R. C. Mullin, S. A. Vanstone, "Improved digital       signature scheme based on discrete exponentation," Electron.       Lett., 26, pp. 1024-1025 (1990). 
  672.  
  673. 13.   "The Digital Signature Standard," Communications of the ACM,  Vol.       35, pp. 36-40 (July 1992). 
  674.  
  675. 14.   Bruce Schneier, Applied Cryptography, John Wiley & Sons (1994). 
  676.  
  677. Author's Address 
  678.  
  679.    Dipl.-Inform. Hadmut Danisch    European Institute for System Security (E.I.S.S.)    Institut fuer Algorithmen und Kognitive Systeme (IAKS) 
  680.  
  681.    University of Karlsruhe    D-76128 Karlsruhe    Germany 
  682.  
  683.    Phone: ++49 721 96400-18    Fax:   ++49 721 696893    EMail: danisch@ira.uka.de    WWW:   http://avalon.ira.uka.de/personal/danisch.html 
  684.  
  685.  
  686.  
  687.  
  688.  
  689.  
  690.  
  691.  
  692.  
  693.  
  694.  
  695.  
  696.  
  697.  
  698.  
  699.  
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708.  
  709.  
  710.  
  711.  Danisch                      Informational                     [Page 21] 
  712.  
  713.