Immerda has an invite system for its services. This means you have to be invited by an immerda user to get an account. The person who invited you is then your trust-relation to us. E.g. he can perform password resets on your behalf.

We had this system for quite some time and are happy with it since we see ourselves as kind of peer-group isp.

What is addressed

The problem remains how to store those trust-relations to be able to verify if password resets are legitimate. And most important: how to store this information in such a way that it is only visible to the people belonging to a certain trust relation.

The following ideas can be applied to any kind of social graph that has to be (partially) stored:

First of all we want to assure that this sensitive information cannot be used to do any kind of data mining. It should be relatively hard to decypher a certain relation, for people that don’t take part in it.

Furthermore we want our users to be able to change their trust links. (Because they might not trust the inviting person anymore.)

And we also thought of providing the possibility to have multiple trust links. With this feature we could either make more than one person having to agree to a password reset or we could have multiple persons beeing able to request a password reset.

What makes it hard

The basic idea is to store this information in a database that is cryptographically designed to prevent that kind of mapping. But with this database it should nevertheless be possible to verify the authenticity of a request.

But what needs to be stored? In order for a user to be able to manage his trust-relations, it must be possible for him to see, which people he trusts. So we obviously need to store this information. But of course in such a way that only he or she can access this information.

Then we need the people that are trusted by others to be able to prove that in case they need to. This part of the relation has to be initiated by one person, provable by the second person that is trusted and not guessable by an outstanding person.

Then we have the following issue: How do you cope with changes in the trust relations? E.g. if A wants to cancel/add a trust relation to B? Can this be achieved without B having to first accept this relation and therefore without the need of storing this relation temporarily in plaintext?

Our proposal

We propose a modell that tries to address those issues and make reasonable tradeoffs between ease of use and privacy. To implement this schema each user has to have some sort of public/private keypair. (And we intend to use the normal login password as passphrase for the privatekey.)

We’d like to explain this modell by providing all the relevant datastructures and the usecases:

terminology

  • trusted user : user entitled to be able to perform a password reset
  • trusting user: user who trusts the trusted user
  • encX(blob): means that blob is encrypted with the publickey of X

Our trust database would look like this:

relations database:

trusting-user trusted-user reset token hash
A encA( B ) encB( randomData ) hash( randomData )
A encA( C ) encC( randomData2 ) hash( randomData2 )

usecases:

1.  If A wants to add a trust-relation to B:

  • Just insert the corresponding entry into the database:
  • Store the trusted-user (B) encrypted with A’ publickey.
  • Encrypt a random string R with the public key of B as reset-token.
  • Store a hashed version of R to be able to verify the reset-token.

2.  If B wants to reset the pw of A:

  • Decrypt all the possible reset tokens of A (where A is the trusting-user) with the private key of B.
  • If one of those decrypted plaintexts correlates with the hash the request is legitimate.
  • We can now reset the password and generate a new keypair for A since he lost acces to his old privatekey too.
  • When A logs in with his new password: He has to reenter his trusted-users since the old entries are lost since his privatekey has changed.
  • A particular problem persists at this point: All the relations where A is the trusted-user are not valid anymore (since he lost the correct privatekey) and have to be rebuilt. Therefore:

3.  Each time a user logs in:

  • Go through all the trust-relations where he is the trusting-user and regenerate the reset-tokens and the hashs with new random strings. This is needed since the keypair of the trusted-user could have changed in the meantime.

Plans

The provided schema is a general approach to store this kind of sensitive information. With it you can lay all the power of those trust links directly into the users hands.

We hope to implement such a system in our planned user account management interface.

And of course we’d love to hear other suggestions to this problem or also comments on our idea.