Thursday, August 28, 2008

Distributed Identity in Virtual Worlds

Thinking about managing identity across various distributed grids of virtual worlds, I am of course drawn immediately to OpenID as the current preeminent solution to that problem. Let me explain the problem a little bit, and discuss how OpenID might fit in.

The Problem

VWs suffer from the same problem as website with regard to multiple sign-on. However due to the central role Identity makes in VWs, the problem is much magnified in its implications. Having single identities for each website you visit is merely a clerical annoyance -- remembering each user name and password -- and one that can be quite acceptably fixed with a smart enough user agent keeping track of each password, as Firefox now does.

However in a VW, having a new Identity for each grid of VW means having to recreate yourself each time you change worlds. You have to redesign your avatar appearance, rebuild your inventory, rebuild your social network, etc. An unacceptably large burden that turns the "metaverse" into a series of "walled gardens".

What we need is a means of

  1. asserting a unique identity agreed to by all observers
  2. mapping of that identity to a common specification for appearance, inventory, etc.

For this post, we will only be considering how to enable item 1.

Thinking about solutions

The obvious means of asserting identity, at least for those of us who have followed any cryptographic developments within the past decade, is for the user agent in question to generate a asymmetric key pair, and use it to pass to the VW a digital signature.

However as we well know, an endpoint directly asserting a signature without a public third-party is vulnerable to a man-in-the-middle attack. However if there was a public third party from which he could receive your public key, then that could be avoided (so long as the third party is actually publicly trusted).

Also, the tools for generating, maintaining, and using an asymmetric key set are far from ubiquitous and user friendly. If we really want it to be something that everyone can agree on and use, is has to be practicable for the average computer user. If we wanted to use PKI directly, we would have to create a standard protocol for use in VWs, write a standard implementation, then convince everyone to use it. Otherwise we'd have nothing more than cryptographically secure walled gardens.

The simplest way to take the burden off the end-user from maintaining his own identity is to outsource it a third party as much as possible. Also we can increase the odds that various VWs might standardize on something third party.

An interesting security property of having a 3-way negotiation, is that if any one party feels that they might be being lied to by one other party, they can always verify with the third. So it takes two parties collaborating with each other to create a deception.

With special consideration towards having a protocol that could be standardized on, and already has existing implementations, we look at OpenID to see how it measures up to our criteria, and what flaws it possesses.

OpenID Protocol

I recommend you read for yourself here and here, however I will provide a brief overview of how it works.

Let us define:

User Agent: The end user's Web browser, which we will denote AliceFox.

Relying Party: A Web application that wants proof that the end user controls an Identifier, which we will denote BobBlog.

OpenID Provider: An OpenID Authentication server on which a Relying Party relies for an assertion of identity, which we will call CarolCert.

Identity: A URI that represents an identity that AliceFox will assert, and and CarolCert will corroborate. Notice that this identity is "for" AliceFox, but cannot exist outside the context of CarolCert. The two are inextricably tied. We will denote AliceFox's identity with CarolCert as


AliceFox (A) wishes to assert her identity (I) to (B) for the purpose of submitting a comment under that identity. She POSTs I to B through the comment form.

B GETs the URL I, which includes a "link" tag which points to (C). B redirects A to C, passing a "return to" parameter (R) and nonce (N) to C as GET parameters.

A and C confer amongst themselves is a manner undefined by the protocol in order to verify that A is in fact the entity known as I.

When C is satisfied of this fact, it prepares a reply to B by creating a secret key (K), a "handle" (H) that publicly identifies that secret key, and signs certain fields to ensure detection of tampering (S). C redirects A back to B with H and S attached as GET parameters.

If B carries state, B can negotiate (out of band??) the exchange of K with C using Diffie-Hellman key exchange, and use K to verify S.

If B is stateless, he merely echos A's message back to C to verify that A did not tamper with it en-route.

When B or C verifies S, B considers the identity successfully asserted, and associates A with I for the duration of the session.

What does OpenID Give

With that understanding in mind, what can we say about A and B, and what does I really mean to them?

It's important to point this out: all OpenID says from B's perspective is "A is an entity known to C as I". The delimiting context here is important to understand. A could have any multiple of identities with C, or any other OpenID provider. Moreover C could be anyone at all, even an untrustworthy party. OpenID says nothing about trust.

However, it is easy to create a trust-based system if one was to white list OpenID providers based on public reputation. It's certainly trivial to create a black list of known untrustworthy providers. This is certainly enough for our purposes as a distributed VW authentication system.

That said OpenID gives us much more. As we said above, its not hard to create our own simpler (and probably more secure) protocol. However that would entail writing an implementation, drafting a standard, ensuring it was practically deployable in working systems, and building critical mass for its adoption by all VW players. OpenID lets us skip that work, because its done already for us, and get straight to solving our own domain specific problems.

What does OpenID not Give

There is a well-known flaw in OpenID that can be used for phishing. If B is malicious, he can redirect A to his own copy-cat OpenID provider C', and if the user doesn't notice, C' can possibly steal A's credentials and allow a malicious party A' to impersonate A.

There are other means of misdirection as well. While a computer would always be able to tell that I and I' are different identities, humans might be confused if A and C are sufficiently similar looking to A' and C'.

The only solution to this is to white list known providers.

Another known problem with OpenID is the common reliance on passwords as a means of validating A with C. While that is no different from the password schemes currently in use on VWs or websites, I am sure a digital signature based protocol would be vastly superior from a technical standpoint.

My humble alternative protocol

Often the best way to judge a design is to consider how you would do it yourself, if you were tasked with making an alternative. I am happy to say that while what I started out with was quite different from OpenID, as I improved my protocol, I noticed that my decisions became more and more like those taken by OpenID, which is a good sign.

Warning: I am neither a security nor web expert, nor do I claim to be. Be gentle with your corrections.

This design also relies on cookies from one site being inaccessible from another. I have no idea how true this is in practice.

When A registers an identity I with C, A downloads an implementation of an asymmetric cipher in JavaScript that writes the private key K in a cookie, and the public key P in C's database.

A asserts identity I to B. Like OpenID, this is a URL that ties A to C, such as

Like OpenID, I contains a link to C, which B redirects A to, sending a return-to R and nonce N as GET parameters. Unlike OpenID, I also contains a link to P, which B downloads and associates with N.

C delivers to A a JavaScript program which opens K, encrypts N into a digital signature DS, then creates a message signature S to detect tampering. C then redirects A back to B, with N, DS, and S as GET parameters.

B verifies S, uses P to decrypt DS and verify it is the same as N. If so, B considers I successfully asserted.

Essentially C is nothing more than a repository for 1) public keys, 2) trusted JavaScript implementation of cryptographic algorithms.


No comments: