RFC 1824

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

📅 published August 1995, from ietf

RFC 1824: The Exponential Security System TESS 🎀

Okay bestie, the title block first 💅 This one is The Exponential Security System TESS: An Identity-Based Cryptographic Protocol for Authenticated Key-Exchange, also filed as E.I.S.S.-Report 1995/4. It's from the Network Working Group, written by H. Danisch at E.I.S.S./IAKS, and it's an Informational RFC dated August 1995 🌸 The header doesn't list anything it obsoletes or updates.

Status of This Memo 📜

Let's get the boring-but-important bit out of the way 🙈 This memo provides information for the Internet community. It does not specify an Internet standard of any kind, so it's not a standard, periodt. Distribution of this memo is unlimited.

Abstract 💜

This informational RFC explains the basic mechanisms and functions of an identity based system. The system is for three things: the secure, authenticated exchange of cryptographic keys, the generation of signatures, and the authentic distribution of public keys. Iconic energy 👑

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

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 ✨

So this RFC describes The Exponential Security System TESS [1]. TESS is a toolbox set system of different but cooperating cryptographic mechanisms and functions, all based on the primitive of discrete exponentiation. It's built on asymmetric cryptographic protocols and a structure of self-certified public keys 🧚

The big mechanisms TESS is built on are the ElGamal signature [2, 3] and the KATHY protocols (KeY exchange with embedded AuTHentication). They were discovered at the same time, by Guenther [4] and by Bauspiess and Knobloch [5, 6, 7]. Two discoveries at once, main character energy 🌟

This RFC explains how to create and use the secret and public keys of TESS. It also shows a method for distributing the public keys securely 🔐

You're expected to already know the basics of cryptography, the Discrete Logarithm Problem, and the ElGamal signature mechanism. No pressure lol 💀

Because this RFC is written in ASCII, the math notation is a bit special 🦋 Here's how it works:

  • 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 that belong together. There are two distinct kinds of key pairs: the SKIA key pair and the User key pair. (As you'll see in the section about hierarchical SKIAs, the two kinds of keys aren't really distinct. They're the same thing seen from a different point of view 👀)

User

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

In this RFC, example users are called A, B, C or Alice and Bob 🎀

SKIA

SKIA stands for "Secure Key Issuing Authority". The SKIA is a trusted local authority that generates the public and secret part of a User key pair. It's the SKIA's job to verify whether the identity encoded in the key pair (see below) belongs to the key holder. That means checking passports, identity cards, driving licenses and so on, to confirm the real world identity of the key owner. Since every key has an implicit signature from the SKIA it came from, the SKIA is responsible for the correctness of the encoded identity 🫶

Since the SKIA has to check real identities, it can usually only work within a small physical range (like a campus or a city). So not all users of a wide area or worldwide network can get their keys from the same SKIA without it costing a fortune 😭 That means you need multiple SKIAs that can work locally. This implies the need for a web of trust levels and trust forwards.

Partners with keys from the same SKIA already know the public data of their SKIA, because it's part of their own key. Partners with keys from different SKIAs have to use the web to learn about the origin, the trust level, and the public key of the SKIA that issued the other key 🕸️

Id[A] Identity Descriptor

The Identity Descriptor is part of the public User key. It's a somehow structured bitstring that describes the key owner in a certain way. The description should be precise enough to fully identify the owner of a User key. What goes in it depends on the nature of the owner. For a human, it 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, it could be the hostname, the hostid, the internet address and so on. For a fax machine or a modem, it could be the international phone number 📠

The description bitstring can also hold key management data, like the name of the SKIA (see below) that issued the key, the SKIA-specific serial number, the expiry date of the key, and whether the secret part of the key is a software key or hidden in a hardware device (see section Enhancements). Lots of info, all in one spot 💖

Here's the big deal: the numerical interpretation (the hash value) of the Identity Descriptor is an essential part of the mathematical mechanism of the TESS protocol. It cannot be changed in any way without destroying the key structure. So knowing the public part of a user key pair always means knowing the Identity Descriptor as composed by the SKIA that issued the key. That's 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 to create a User Key. There must not be distinct keys with the same Identity Descriptor. That said, a user can have several keys with different expiration times, key lengths, serial numbers, or security levels, since those affect the contents of the Identity Descriptor 🍓

It's also really emphasised that there are no assumptions about the structure of the Identity Descriptor. The SKIA can choose any construction method it likes, depending on its purposes 🌈

The Identity Descriptor of a certain user A is written as Id[A]. Wherever Id[A] shows up in a mathematical context, its cryptographic hash sum H(Id[A]) is used instead.

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

These mean encrypting and decrypting the Message with any common cipher ✨

1.2. Required mechanisms 🔐

The protocols in this RFC need 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)
  • An arithmetical library for long unsigned integers
  • A method for checking network identities against real-world identities (e.g. an authority that checks human identity cards etc.)

2. Setup 🛠️

This section covers the base method for creating the SKIA and the User key pairs. Enhancements and modifications come in later sections 🦋

The main idea behind the protocols 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 user's secret key. The link 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 run in "reverse mode" to calculate r^s from public data, without knowing the secret s. Galaxy brain 🧠✨

The authority that generates those signatures is the SKIA introduced above.

2.1. SKIA Setup 🔑

These steps create the SKIA key pair:

  • 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), and the secret part is x.

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

2.2. User Setup ✨

okay bestie, the User Setup is when the SKIA makes an ElGamal signature on the user's Identity Descriptor 💅 it can happen more than once for a specific User, but only once for a specific Identity Descriptor 🎀

so to make a User key pair for a User A, the SKIA has to run through these steps 🫶

  • Id[A]: describe the key owner A in any way you want (name, address, etc.), turn that description into a bit- or byte-oriented representation, and smoosh them together to form the Identity Descriptor Id[A] 🧚
  • k[A]: pick 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 numbers you get out of that fulfill this equation, and it's giving math perfection ✨

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

the public part of A's key is Id[A] and r[A], which we call (Id[A],r[A]) when we're talking about the triple (p,g,y). (Id[A],r[A]) always implicitly 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 SKIA's secret x if they knew both s[A] and k[A] 💀 the random number k MUST NOT be used twice. s[A] MUST NOT be equal to 0. no exceptions, periodt 💅

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

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

this equation lets you calculate r[A] ^ s[A] from public data without ever knowing the secret s[A] 🌸 since we use it SO often, and for readability, we just call it Y[A]. ✨

Y[A] means calculating the value of r[A] ^ s[A], which is

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

ngl this is a big one: 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 a macro definition, not a value, so don't treat it like one 🙅‍♀️

obviously both the SKIA and the User know the secret part of the User's key, and either one can reveal it by accident or on purpose 😭 the enhancements section below shows ways to avoid this 🛡️

3. Authentication ✨

this section is all about the basic ways to use the User keys 🔑 they cover online and offline chats between two users, A(lice) and B(ob) 💬

the unilateral and mutual authentications both use the KATHY protocol to make reliable session keys for later stuff, like session encryption keys etc. 🔐

3.1. Zero Knowledge Authentication ✨

the "Zero Knowledge Authentication" is for when Alice wants to prove she's Alice to Bob without needing a session key 💖

assuming Bob already reliably learned the (p,g,y) of the SKIA Alice got her key from, here's the flow:

  1. Alice generates a large random number t, 1<t<p-1, where t SHOULD have approximately the same length as p-1.
  2. a := r[A] ^ t mod p
  3. Alice sends her public key (Id[A],r[A]) and the number a to Bob.
  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.
  5. Alice calculates c' := (c * s[A] + t) mod (p-1) and sends c' to Bob.
  6. Bob verifies whether r[A] ^ c' = (Y[A] ^ c) * a mod p.

this is the Beth-Zero-Knowledge protocol [8], which is built on self-certified public keys and is an upgrade of the DLP-Zero-Knowledge identification protocol from Chaum, Evertse, and van de Graaf [9] 🧠✨

3.2. Unilateral Authentication ✨

the "Unilateral Authentication" (or "Half Authentication") works in these cases:

  • Alice wants to prove she's Alice to Bob without Bob having to prove himself to Alice.
  • Bob wants to send an encrypted message that only Alice can read (offline encryption) 📨

a shared key gets made with the following protocol, and only Alice and Bob can know this key 🤍

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

  1. Alice sends her public key (Id[A],r[A]) to Bob if he doesn't already know it.
  2. Bob chooses a random number 1 < z[A] < p-1 and calculates v[A] := r[A] ^ z[A] mod p
  3. Bob sends v[A] to Alice.
  4. Alice and Bob calculate the session key:
    • Alice: key[A] := v[A] ^ s[A] mod p
    • Bob: key[A] := Y[A] ^ z[A] mod p

apply the equations from the User Key Setup section to Bob's equation and you'll see Alice and Bob get the very same key in step 4 🥰

key[A] = r[A] ^ ( s[A] * z[A] ) mod p

a third party can't calculate key[A], because they have neither s[A] nor z[A] 🙅‍♀️ so Bob can trust that only Alice can know key[A], as long as nobody else knows her secret s[A] 🫶

this protocol is based on the Diffie-Hellman scheme [10], but it dodges the weakness of public keys that have no proof of authenticity 🙌

in this protocol, Bob never checked whether Alice actually knew her s[A] and could calculate key[A]. so a final challenge-response step SHOULD be performed for online communication (see the subsection below) 🔥

for encrypted messages, Bob can run step 4 before step 3, use key[A] to encrypt the message, and send the encrypted message together with v[A] in step 3 💌

3.3. Mutual Authentication ✨

the "Mutual Authentication" is for online connections where both Alice and Bob want to authenticate to each other 👯‍♀️

in this description, it's assumed that Alice and Bob have keys from the same SKIA and use the same triple (p,g,y). otherwise, each step has to use the triple that belongs to the user key it's being applied to 🧃

the steps go like this. the first four steps are basically the "Unilateral Authentication" done twice, and steps 5-9 are a mutual challenge-response to find out whether the other side really got the key 🎀

  1. Alice sends her (Id[A],r[A]) to Bob. Bob sends his (Id[B],r[B]) to Alice.
  2. Bob chooses a random number z[A] < p-1 and calculates v[A] := r[A] ^ z[A] mod p. Alice chooses a random number z[B] < p-1 and calculates v[B] := r[B] ^ z[B] mod p.
  3. Bob sends v[A] to Alice. Alice sends v[B] to Bob.
  4. Alice and Bob calculate the session keys:
    • Alice: key[A] := v[A] ^ s[A] mod p and key[B] := Y[B] ^ z[B] mod p
    • Bob: key[B] := v[B] ^ s[B] mod p and key[A] := Y[A] ^ z[A] mod p
  5. Alice chooses a random number R[B]. Bob chooses a random number R[A].
  6. Alice sends Encrypt(key[B],R[B]) to Bob. Bob sends Encrypt(key[A],R[A]) to Alice.
  7. Alice and Bob decrypt the received messages to R'[A] and R'[B].
  8. Alice sends Encrypt(key[A],T(R'[A])) to Bob. Bob sends Encrypt(key[B],T(R'[B])) to Alice.
  9. Alice and Bob decrypt the received messages to R''[A] and R''[B].
  10. Alice verifies whether T(R[B]) = R''[B]. Bob verifies whether T(R[A]) = R''[A].

T() is a simple bijective transformation function, e.g. increment(). 🔢

after step 4, Alice can trust that only Bob and herself can know key[B], but she still doesn't know if she's really talking to Bob 👀 so she makes Bob use his key in steps 5-9. now Alice has checked that she really is talking to Bob ✅ and since the scheme is symmetrical, Bob also knows he's talking to Alice 💖

3.4. Message Signing ✨

to sign a message m (where H(m) is a cryptographic hash value of the message), the message author A makes an ElGamal signature, using their r[A] as the generator and their s[A] as the secret:

  • A generates a random number K with gcd(K,p-1) = 1.
  • R := r[A] ^ K mod p
  • S := ( H(m) - s[A] * R ) * (K ^ -1) mod (p-1)

the calculated set of numbers fulfills this equation:

( s[A] * R + K * S ) = H(m) mod(p-1)

the signed message consists of (m,Id[A],r[A],R,S) 📬

the receiver checks the message's authenticity by calculating the hash value H(m) and verifying this equation:

r[A] ^ H(m) = ( Y[A] ^ R )  * ( R ^ S )  mod p

4. Enhancements ✨

this section covers a bunch of enhancements and modifications to the base protocol, plus some other comments 💅

4.1. Non-Escrowed Key Generation ✨

during the normal User Setup for a User A, the SKIA learns the secret key s[A] 😬 the SKIA could use that key to fake signatures or decrypt messages, or let others do it too. not it 🙅‍♀️

to avoid this, a slight modification of the User Setup procedure MAY be applied. the SKIA Setup stays the same as in the base protocol 🌈

in the User Setup, the SKIA doesn't use its primitive element g. instead, it uses a generator the User makes 🧚

the modified scheme looks like this:

  • User A generates a random number a with gcd(a,p-1)=1
  • User A calculates g' := g^a mod p and forwards g' to the SKIA.
  • The SKIA generates Id[A] and k[A] as in the base protocol
  • 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)
  • The SKIA forwards (Id[A],r[A],s'[A]) to the user A
  • The user A calculates his s[A] := s'[A] * (a^-1) mod (p-1)

the SKIA can't find out A's secret key s[A] 🔒 this protocol is based on the idea of the 'testimonial' [11].

BUT the SKIA can still make a second key with the same Identity Descriptor (identical, or at least with the same contents), just with different r[A] and s[A] 😱 if that second key ever gets used for authentication or message signing, the real key owner can use their own key to prove that two different keys exist with identical (equivalent) Descriptors. if two keys like that exist, the SKIA can't be trusted anymore 🚫

if the key is generated this way, it SHOULD be mentioned in the Identity Descriptor. this lets any communication partners look up, in the public part of a key, whether the secret part is known to the SKIA 🔍

4.2. Hardware Protected Key ✨

the protocol in the previous subsection guaranteed that the SKIA doesn't know the user's secret key 🛡️

but the SKIA might want the user also to not know their own secret key 👀 this could be needed because the user could otherwise reveal their secret key by accident or on purpose. especially if untrusted hardware or software, or an environment without trusted process protection, is used, the secret key can get spied on 😨 for high-level security apps, that might not be acceptable. the key owner MUST be able to use their key without being able to read this key. this contradiction can be solved by hiding the secret part of the User Key inside a protected hardware device 🔐

within the SELANE project, the protocols in this RFC were implemented for SmartCards. the User Key is made with the non-escrowed key generation procedure from the previous section, changed so that the random number is generated inside the card 💳 the secret s[A] only exists inside the card and never gets outside 🤐 the SmartCard can run every part of the algorithms that need access to the secret key. to use the SmartCard, an additional password is required 🔑

if the key is hidden in a hardware device like this, it SHOULD be mentioned in the Identity Descriptor. this lets any communication partners look up, in the public part of a key, whether the key is hardware protected 🎀

4.3. Key Regeneration 🔁

Okay bestie, so if BOTH of the protection methods from the last bits are used to lock up the key, then neither the SKIA nor the User themselves knows the secret key anymore 😳. That sounds super secure, but it's kinda risky for the User if the hardware device gets lost or damaged, because then they could be totally unable to decrypt messages that were encrypted with their public key 💀.

To stop that kind of denial of service (aka getting locked out of your own messages 😭), there are two methods:

  • If the protection factor a was chosen by the User, the User can deposit the factor a somewhere safe, like giving it as a shared secret to their 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 that's equivalent to the first one 👯.
  • 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) ✨.

Okay, real talk though: recreating a User key kind of defeats the whole "this key exists only once" vibe 🦋. So the SKIA should restrict this to special cases only 🚫. Furthermore, it should only happen after the end of the key's lifetime, if its lifetime was limited ⏳.

4.4. r ^ r 🪞

A lil tweak to the base protocol speeds up the key exchange ⚡. Here's the glow-up:

  • The SKIA is created as in the base protocol 🏗️
  • For the User Setup the SKIA solves this equation:
x * s[A] + r[A] * k[A] = H(Id[A]) mod (p-1)

It's giving base protocol, but r and s got swapped 🔀.

  • The public key lets you calculate y ^ s[A] = ( g ^ H(Id[A]) ) * ( r[A] ^ -r[A] ) mod p without knowing s[A] 🤯. The term ( r[A] ^ -r[A] ) can be precalculated for speedup, which is so smart 🧠.
  • Bob calculates the following, and Alice gets her key from it 🔑:
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])

This protocol is similar to the AMV modification by Agnew et al. [12] 💜.

4.5. Implicit Key Exchange 🤝

If the r ^ r protocol from the previous section is used, Alice and Bob can calculate an implicit shared key using the Diffie-Hellman scheme 🫧:

  • 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

where key[A,B] = key[B,A] = y ^ (s[A] * s[B]) 🥹.

This can not be used with Non-escrowed keys 🙅‍♀️.

4.6. Law Enforcement ⚖️

Ooh, this one's getting its own separate RFC, so stay tuned 📜.

4.7. Usage of other Algebraic Groups 🧮

In this RFC, the math was based on one specific algebraic group: the multiplicative group of integers modulo a prime number p (which is also the multiplicative group of a finite field GF(p)) 🔢. BUT, and this is a big but 💅, any cyclic finite group with a strong discrete logarithm problem can be used. Think a subgroup of the multiplicative group, or elliptic curves 🌈.

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 📚.

4.7.1. DSA subgroup SKIA Setup 🔐

  • 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).
  • Choose a primitive root h in GF(p).
  • g:= h^((p-1)/q). Note that g generates a subgroup G with |G|=q 🌸.
  • x: a random number of about 160 bit.
  • y:= ( g ^ x ) mod p

The public key of the SKIA is (p,g,y,q). (q is required for speedup only.) The secret key of the SKIA is x 🤫.

4.7.2. Escrowed DSA subgroup User Setup 🗝️

  • k[A]: a random number of 160 bit length with gcd(k[A],q)=1
  • r[A]:= ( g ^ k[A] ) mod p
  • s[A]:= (H(Id[A]) + x * r[A]) * (k[A] ^ -1) mod q

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) 🧁.

4.7.3. Non-Escrowed DSA subgroup User Setup 🙈

  • User A generates a random number h of 160 bit length.
  • User A calculates a := g^h mod p and sends a to the SKIA.
  • The SKIA generates the user key with the secret key s'[A].
  • User A calculates s[A]:= s'[a] * (h^-1) mod q

4.7.4. DSA subgroup Authentication ✍️

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 🖊️.

The abbreviation Y[A] still stands for r[A] ^ s[A], which is now (the sign of r[A] was changed for speedup):

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

and it can be calculated in a faster way as:

u1 * u2 mod p

where:

u1 := g ^ ( H(Id[A])  mod q )  mod p
u2 := y ^ ( r[A] mod q ) mod p.

5. Multiple SKIAs 🌍

In the preceding sections, it was assumed that everybody learned the (p,g,y) triple of a SKIA reliably 🤞.

By default, a User reliably learns only the (p,g,y) of the SKIA which generated their own key. That's because they get the triple along with their key, and they can verify the triple with the signature verification equation ✅.

If the User wants to communicate with someone whose key was generated by a different SKIA, they need a method for authenticating the (p,g,y) of that other SKIA 🕵️‍♀️.

5.1. Unstructured SKIAs

This will be subject of a separate RFC 📜.

5.2. Hierarchical SKIAs 🌳

If there is a hierarchy between the SKIAs, their keys can be generated hierarchically 🪜:

  • 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 🔢.
  • Each SKIA except the root SKIA is also a User, and each User can be a SKIA 🔄.
    • A SKIA of level n generates keys for Users of level n+1.
    • A User of level n is also a SKIA of level n.
  • 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 🪪.

Thus, the parent() function allows you to find the path to the root SKIA for every node of the tree forming the hierarchy 🛤️.

The root SKIA may also have an Identity Descriptor.

  • The root SKIA creates itself as in the base protocol 🌱.
  • 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]), and 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 SKIA A can be calculated by everyone from the public data of 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 "SKIA A" is identical to the secret of "User A" 👯.

Since User A uses the very same data to act as either a user or 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 precede 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 only need to know the public data (p,g,y) of each other's root SKIA. 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's 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 in 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 the challenge response step in case of mutual authentication 🙈.

5.3. Example: A DNS-based public key structure ✨

okay so this section is the example that makes the hierarchical SKIA idea click 🌸 bestie, let's go!! 💖 Every domain is also a SKIA, and the root domain is a root SKIA. The Identity Descriptor for any object in the name space is just its name: the domain name for domains, the host name for machines, and the mail address for humans and services. 🦋

So a user with the mail address "danisch@ira.uka.de" got their key from the SKIA of the domain "ira.uka.de". That 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. 💅 No extra stamp required, periodt!

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. 🌍 Like, no middleman?? iconic.

The whole world could also be based on a single root SKIA; in this case a single (p,g,y) is needed only. 👑

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=        <digitized compressed portrait>

Security Considerations 🔥

Okay bestie, this part is SERIOUS, so read it carefully 😭🙈 These are the security considerations, and they stay complete:
  • The strength of TESS depends on the strength of the discrete logarithm 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. 💀 Major red flag energy if the origin is shady.
  • 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. ⏰ Expiry dates are not optional vibes, bestie.

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).
  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

That's the whole thing, bestie!! 🌈💜 TESS, SKIAs, and self-certified keys, all wrapped up. You're literally a networking legend now 👑🦋✨

📦 where this page comes from