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, 10) is generated by the parent
SKIA of level n-1. The public part is (Id[A],r[A]), the secret
part is (s[A]).
User A is automatically SKIA A:
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
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".
Danisch Informational [Page 16]
RFC 1824 TESS August 1995
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.
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.
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):
- Bob reliably learned the (p,g,y) of Alice's root SKIA S(0).
- 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.
- 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].
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.
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.
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.
Danisch Informational [Page 17]
RFC 1824 TESS August 1995
5.3. Example: A DNS-based public key structure
Here is a simple example of the usage of the hierarchical SKIA scheme
within the DNS name space:
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.
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".
The public key of danisch@ira.uka.de would look like:
( "danisch@ira.uka.de", r[danisch@ira.uka.de] ,
"ira.uka.de" , r[ira.uka.de] ,
"uka.de" , r[uka.de]
)
For the reasons described in the previous subsection, this key is
self-certified and does not need any further signature.
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.
Someone who reliably learned the (p,g,y) of the root domain .de
(Germany) can now build the chain:
"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]
Thus it is possible to reliably obtain the Y[danisch@ira.uka.de].
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.
The whole world could also be based on a single root SKIA; in this
case a single (p,g,y) is needed only.
Danisch Informational [Page 18]
RFC 1824 TESS August 1995
In a more realistic example the Id[danisch@ira.uka.de] could contain:
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=
Security Considerations
- 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.
- Attention should be paid to the security considerations of the
underlying mechanisms (ElGamal, DSA, Diffie-Hellman, etc.).
- 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.
- It is the SKIA's duty to give the s[A] only to the user the
Identity Descriptor belongs to.
- Since the very same procedure is used for signing messages and
generating user keys, it is important to distinguish between
messages and keys.
- 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.
Danisch Informational [Page 19]
RFC 1824 TESS August 1995
References
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).
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).
3. B. Klein, H.-J. Knobloch, "ElGamal-Signatur" in
Sicherheitsmechanismen, ed. Fries, Fritsch, Kessler, Klein, pp.
171-176, Oldenburg, Muenchen (1993).
4. C. G. Guenther, "An Identity-Based Key-Exchange Protocol" in
Advances in Cryptology, Proceedings of Eurocrypt '89, pp. 29-37,
Springer (1990).
5. B. Klein, H.-J. Knobloch, "KATHY" in Sicherheitsmechanismen, ed.
Fries, Fritsch, Kessler, Klein, pp. 252-259, Oldenburg, Muenchen
(1993).
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).
7. F. Bauspiess, "SELANE - An Approach to Secure Networks" in
Abstracts of SECURICOM '90, pp. 159-164, Paris (1990).
8. Th. Beth, "Efficient zero-knowledge identification scheme for
smart cards" in Advances in Cryptology, Proceedings of Eurocrypt
'88, pp. 77-84, Springer (1988).
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).
10. W. Diffie, M. Hellman, "New directions in cryptography," IEEE-
Trans. Information Theory, 22, pp. 644-654 (1976).
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).
Danisch Informational [Page 20]
RFC 1824 TESS August 1995
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).
13. "The Digital Signature Standard," Communications of the ACM, Vol.
35, pp. 36-40 (July 1992).
14. Bruce Schneier, Applied Cryptography, John Wiley & Sons (1994).
Author's Address
Dipl.-Inform. Hadmut Danisch
European Institute for System Security (E.I.S.S.)
Institut fuer Algorithmen und Kognitive Systeme (IAKS)
University of Karlsruhe
D-76128 Karlsruhe
Germany
Phone: ++49 721 96400-18
Fax: ++49 721 696893
EMail: danisch@ira.uka.de
WWW: http://avalon.ira.uka.de/personal/danisch.html
Danisch Informational [Page 21]
RFC, FYI, BCP