Seitan Tokens: Say No to TOFU

NOTE: We've enhanced the security of this protocol in V2, check out the doc for the latest and greatest!

When Alice wants to invite Bob into her team, and Alice only knows Bob's phone number, she can do so via Seitan Tokens. Typically, sharing of this form is TOFU, or "Trust On First Use". For example, Alice can ask a server to send an email, SMS or push-notification to Bob, and once Bob presents that token back to the server, Alice will let him into the team. Bob has proven ownership of whatever address the server sent the token to. However, in this example, Alice is trusting that the server doesn't send that token to Charlie instead. So Alice must trust the server does what it professes, and she doesn't have mechanism to detect malfeasance. Once Bob (or Charlie) is allowed in, then Alice can at least ensure that Bob (or Charlie) isn't switched out on her at a later date.

Seitan Tokens are better. Assuming Alice has a pre-authenticated channel open with Bob (via iMessage or Signal, let's say), then she can ensure that Bob is getting in, and the Keybase servers cannot coerce her to let Charlie in surreptitiously.

Seitan Tokens now power the "Invite Contacts to Team" features on the Keybase Mobile Apps.

High-Level Description

In a Seitan Token exchange, Alice comes up with a random token. She signs a statement of the form: "anyone who proves knowledge of this token can be admitted into the team." Alice need not be the one who allows the invitee into the team; Arnie can do it too if he is a team administrator.

Say that Alice and Arnie are admins of the team acme, and Alice wants to invite Bob into the team. The protocol at a high level is simply:

1. Alice picks a random 83-bit token (called an iKey), and computes some derived data
2. Alice signs the encryption of the iKey into acme's team signature chain
3. Alice sends the iKey to Bob over iMessage (or Signal, etc.)
4. Bob sends HMAC(token, bob) to the Keybase servers,
5. Alice or Arnie decrypts the encrypted iKey in acme's signature chain, and makes sure the HMAC that Bob sent verifies with that iKey.

Detailed Specification

Here is a more detailed specification of the above steps:

Step 1: iKey Generation and Token Derivation

Step 1a: iKey Generation

Alice generates a 17-character random string from the alphbabet abcdefghjkmnpqrsuvwxyz23456789, meaning all letters and numbers, save i, l, o, t, 0, and 1. Insert a + character at position 5 (0-indexed). This is called the iKey or "invitation-key". Examples look like: zmh6f+f2jv975gh56p or bxsnr+ddj882d9mmq9.

We include a + sign so these tokens can be distinguished from team names and email-based TOFU tokens. Any token with a + sign, at index >1, and with more than 5 characters is considered a seitan token by the Keybase client, so that mis-spelled or mangled tokens aren't accidentally sent to the server as team names or email tokens.

Step 1b: Stretch IKey to Discourage Server Brute-Force

The iKey generated in the previous step only has ~83 bits of entropy. It will eventually be transferred over iMessage or even SMS, so we're slightly space constrained here. Thus, Alice further stretches this key via scrypt to discourage brute-force exhaustion of the token space:

Alice computes siKey, meaning "Stretched Invitation Key": siKey = scrypt(ikey, C = 2¹⁰, R=8, P=1, Len=32)

Step 1c: Computed Derived "Invitation ID"

Whenever Alice wants to invite someone like Bob into a team, and Bob hasn't joined Keybase yet, Alice must generate an "invitation ID" to key her invitation. Usually this is done randomly, but in this case, it's derived from the siKey: inviteID = HMAC-SHA512(siKey, msgpack({ "stage" : "invite_id"})[0:15].

That is, the JSON blob {"stage" : "invite_id"} is Msgpack-encoded, and is the payload to an HMAC-SHA512 with the siKey as the MAC key. Then the first 15 bytes are used for the "invitation ID".

Step 2: Encryption and Signing of the iKey

Step 2a: Encrypt the iKey

Alice encrypts the iKey so that she (and other admins) can access it later, potentially on other devices. Alice also attaches a "label" to the iKey, which might correspond to Bob's iMessage handle or phone number. This way, if she wants to cancel the invitation later, she'll have a human-readable label to identify it by.

The data iKeyAndLabel is computed by packing the two fields into a SeitanIKeyAndLabel structure. To encrypt the iKeyAndLabel, Alice uses the team's secret key, with the symmetric key derivation string: "Keybase-Derived-Team-NaCl-SeitanInviteToken-1". The nonce is a 24-byte random, and the payload is iKeyAndLabel; these parameters are run though NaCl's crypto_secretbox. Call this key eiKey, for "encrypted iKey".

Step 2b: Pack the eiKey

Alice then versions and packs this ciphertext: peiKey = pack([1, g, nonce, eiKey]), which g is the "generation" of the team key used to encrypt the eiKey, since it is constantly rotating. This "packed encrypted invitation key" (peiKey) is then what Alice publishes to herself and the other admins, for future reference.

Step 2c: Sign the peiKey into the Team's Chain

Finally, Alice signs the peiKey generated in the previous step into her team's chain:

"invites": {
    "writer": [
        {
            "id": inviteID, // See Step 1c
            "name": peiKey, // See Step 2b
            "type": "seitan_invite_token"
        }
    ]
}

Step 3: Sending the iKey

Alice then sends the iKey generated in step 1a to Bob over any means at her disposal. Our iPhone app automatically uses iMessage.

Step 4: Bob Accepts the Invitation

When Bob receives the iKey from Alice, he stretches it to make an siKey, and then he can construct an "acceptance key" (aKey), and post it to the server, to claim ownership of his spot in the team. This is done simply via HMAC:

aKey = SHA-512(siKey, pack({"stage" : "accept", "uid" : uid, "eldest_seqno" : q, "ctime" : t})).

Bob substitutes the appropriate values for his uid, his eldest_seqno (so Alice can identify Bob modulo any account resets), and a UTC timestamp. He then posts this aKey to the server.

Step 5: Alice Completes the Protocol

Once Bob has claimed the spot in the team, the team admins get a message from the Keybase server that they should complete the Seitan protocol. They receive a message with (inviteID, aKey) and can read the corresponding peiKey out of their team's chain, indexing on iniviteID. The admins verify all important parts of the various keys:

• That the peiKey decrypts properly
• That the inviteID matches the ID in the aKey and the peiKey
• That the aKey is well-formed, given the seiKey recovered from peiKey

Assuming all of these cryptographic checks pass, then Alice (or Arnie or any other admin) adds Bob to the group.

Security Analysis

This protocol achieves three goals: (1) it shares a secret between the inviter (Alice) and the invitee (Bob); (2) it shares the secret among all other admins of the group; and (3) it allows Bob to prove knowledge of the secret to the admins who key him into the team. The security in Step (1) depends upon assumptions outside the scope of this system. For instance, if Alice shares the secret with Bob over iMessage, she is trusting that system's TOFU-based key exchange.