Distributed Authentification Using Digital Signatures

From Armagetron

Overview

This proposal uses digital signatures to enforce uniqueness of names. It is a hierarchical and distributed system, but the actions of the root node are subject to public review and can be accepted/rejected individually.

We consider two players for purposes of explanation. Alice would like her name to be unique, and uses the authentification system to that purpose. Bob uses the authentification system to find out if the player who claims to be Alice really is Alice.

This system is based on trust. Both Alice and Bob trust the involved parts the auth system that only Alice may play under the name Alice. Since trust is a personal and subjective thing, both Alice and Bob can individually decide which server(s) in the authentification system they trust, and, by consequence, which server(s) in the authentification system are used.

The authentification system manages identities. Every identity has a name and a full name. An authority is an identity that can create new identities. A correct authority creates identities with identical names only if it is convinced that the requesting player is identical.

An identity's full name consists of its name followed by a reserved seperation character (for instance "." ) followed by the full name of the creating authority. (For instance, if the authority with full name "fe" created an identity named "meriton", the latter's full name would be "meriton.fe"). As a consquence, if all ancestors of an identity are correct, the identity has a unique full name.

Technical Description

Be sure to understand the concept of digital signatures before you proceed.

In public, an identity is represented using the name, the time of expiration, the public identity that created it and a public key, digitally signed by the creating identity. In private, an identity additionally knows the matching private key. A correct authority does not reveal private knowledge.

Alice can create an identity for herself using the following protocol:

  • Alice chooses a name, a time of expiration, a parent identity, a secret and a matching public key, and sends the name, the public key and any other information that may be required to her parent identity
  • the parent identity, if it choses to satisfy the request, sends Alice the signature she needs for her public identity

Note: A valid identity can only be created by the parent identity it mentions.

Bob verifies Alice's identity using the following protocol:

  • Bob chooses a random number and sends it along with her game id to Alice
  • Alice digitally signs the message using her private key and sends that signature along with her public identity to Bob
  • Bob verifies the signature using the public key in the shown public identity. In addition, he verifies the identity's validity by verifying all signatures and expiration times therin and that he trusts its root identity. If all checks succeed, he is satisfied.

If Alice's trust was not misplaced, i.e. all ancestor identities are correct, and Bob trusts Alice's oldest ancestor, Alice can convince Bob of her full name. If Alice's trust was not misplaced, only Alice can convince Bob of her full name.

Proof: That Alice can convince Bob should be obvious. Why can't Eve? Since Alice is correct, Eve does not know Alice's secret key, and therefore can only sign Bob's challenge if she can persuade Alice to help, which she can't [1]. Furthermore, Eve can not create a public identity bearing Alice's full name: Alice's identity ancestors are correct, and the root ancestor's identity is known to Bob. Eve can not impersonate them, and neither can she get them to cooperate.

Practical Considerations

  • The set of trusted identities is manually managed by the user. The installer copies a default set.
  • Anyone can create an identity that is its own root.
  • if Bob does not trust the root identity, his client marks the display name (if identity verification failed for another reason, the identity is forged and a message to Bob might be in order). Bob can define a standard root identity, whose contribution to display names is omitted in case a name collision can be ruled out.
  • a clan can manage its own namespace within the full names by hosting its own authority and narrow its acceptance criteria
  • there is no communication between Bob and any authority. (-> Privacy)
  • if a private key is leaked, there is no means of damage control short of asking players to remove the root key from the trusted set. By neccessity, any protocol where Bob does not contact a predefined server has that flaw.

Attack Vector

Proxy Attack (Resolved)

Like the phishing server, Eve could convince Bob that she really is Alice if she is in contact with Alice, but Bob isn't. Eve copies Alices public information and advertises it to Bob. Bob sends the challenge to Eve, Eve forwards the challenge to Alice, hoping that Alice signs it and she can forward the signature to Bob. This attack doesn't work because Alice will only sign the authentification challenge for a game-id if she is currently using or applying for.