Identity/AttachedServices/KeyServerProtocol

PiCL Key Server / IdP Protocol

NOTE: This specification is under active development (27-Jun-2013). Several pieces are not yet complete. If you write any code based on this design, keep a close eye on this page and/or contact me (warner) on the #picl IRC channel to learn about changes. Eventually this will be nailed down and should serve as a stable spec for the PICL keyserver/IdP protocol.

Email+Password -> SignToken/ResetToken

The first interaction with the keyserver takes an email+password pair and receives back (kA, wrap(kB), token). This starts by using key-stretching to transform the email+password into a "masterKey", then feeds this into an SRP protocol to get a session key. It uses this session key to decrypt a bundle of encrypted data from the keyserver, resulting in three values: kA, wrap(kB), and the signToken (or resetToken). The masterKey is also used to derive the key that will decrypt wrap(kB) into the actual kB value.

This same protocol is used, with slightly different methods and constants, to obtain the "resetToken".

The protocol is optimized to minimize round-trips and to enable parallelism. As a result, the two messages it sends (getToken1 and getToken2) each perform multiple jobs.

getToken1

As soon as the user finishes typing in the email address, the client should send it in the "getToken1" message to the keyserver. The response will include a set of parameters that are needed for key-stretching (described below), and the common parameters used by both sides of the SRP protocol to follow. These are simply looked up in a database entry for the client, along with an account-id. It must also include an allocated session-id that is used to associate this request with the subsequent getToken2 request. Finally, the response also includes the server's contribution to the SRP protocol ("srpB"), which is calculated on the server based upon a random value that it remembers in the session.

Proof-Of-Work

To protect the server's session table memory and CPU usage for the initial SRP calculation, the server might require clients to perform busy-work before calling getToken1(). The server can control how much work is required.

The getToken1() call looks for a "X-PiCL-PoW:" HTTP header. Most of the time, clients don't supply this header. But if the server responds to the getToken1() call with an error that indicates PoW is required, clients must create a valid PoW string and include it as the value of an "X-PiCL-PoW:" header in their next call to getToken1().

The server's error message includes two parameters. The first is a "prefix string": the client's PoW string is required to begin with this prefix. The second is a "threshold hash". SHA256(PoWString) is required to be lexicographically earlier than the thresholdHashString (i.e. the numerical value of its hash must be closer to zero than the threshold). The client is expected to concatenate the prefix with a counter, then repeatedly increment the counter and hash the result until they meet the threshold, then re-submit their getToken1() request with the combined prefix+counter string in the header. If the client has spent more than e.g. 10 seconds doing this, the client should probably help the user cancel the operation and try again.

When a server is under a DoS attack (either via some manual configuration tool or sensed automatically), it should start requiring valid unique X-PiCL-PoW headers. The server should initially require very little work, by using a threshold hash with just a few leading zero bits. If this is insufficient to reduce the attack volume, the threshold should be lowered, requiring even more work (from both the attacker and legitimate clients).

The server should create a prefix string that contains a parseable timestamp and a random nonce (e.g. "%d-%d-" % (int(time.time()), b32encode(os.urandom(8)))). The server should also decide on a cutoff time (perhaps ten minutes ago). Each server must then maintain a table of "old PoW strings" to prevent replay attacks (these do not need to be shared among all servers: an in-RAM cache is fine).

When the server receives a proposed PoW string, it first splits off the leading timestamp, and if the timestamp is older than the cutoff time, it rejects the string (either by dropping the connection, or returning a new "PoW required" error if it's feeling nice). Then it hashes the whole string and compares it against the threshold, rejecting those which fail to meet the threshold. Finally, for strings that pass the hash threshold, it checks the "old strings" table, and rejects any that appear on that list.

If the PoW string makes it past all these checks, the server should add the string to the "old strings" table, then accept the request (i.e. compute an srpB value and add a session-id table entry for the request).

The old-strings table check should be optimized to reject present strings quickly (i.e. if we are under attack, we should expect to see lots of duplicates of the same string, and must minimize the work we do when this occurs).

The server can remove values from the old-strings table that have timestamps older than the cutoff time. The server can also discard values at other times (to avoid consuming too much memory), without losing anything but protection against resource consumption.

Other notes:

The server-side code for this can be deferred until we care to have a response to a DoS attack. However the client-side code for this must be present from day one, otherwise we won't be able to turn on the defense later without fear of disabling legitimate old clients.

The server should perform as little work as possible before rejecting a token. Every extra CPU cycle it spends in this path is increasing the DoS attack amplification factor.

The nonce in the prefix string exists to make sure that two successive clients get different prefixes, and thus do not come up with the same counter value (and inadvertently create identical strings, looking like a replay attack). If this proved annoying or expensive, we could instead obligate clients to produce their own nonce.

TBD: Is this worth it? Should the PoW string go into an HTTP header? (I want it to be cheap to extract, and not clutter logs). Should the error response be a distinctive HTTP error code so our monitoring tools can easily count them? We can also use this feature to slow down online guessing attacks (i.e. trigger it either when getToken1 is called too much or when getToken2 produces too many errors). Since getToken1() includes an email address, we could also requires PoWs for some addresses (e.g. those we know to be under attack) but not others.

Client-Side Key Stretching

The current stub does no stretching. It just performs a single HKDF operation, combining the user's email address, their password, and a "stretchSalt" retrieved from the server's getToken1() response.

A later version of the protocol will replace this with the PBKDF2+scrypt+PBKDF2 protocol described in Identity/CryptoIdeas/01-PBKDF-scrypt. This stretching is expected to take a second or two. The client can optimistically start this process (using default parameters) before receiving the getToken1() response, and then check that it used the right parameters afterwards (repeating the operation if not). (We'll want to build the stretching function with periodic checkpoints so that we don't have to lose all progress if the parameters turn out to be wrong). The "stretchSalt" is added *after* the stretching, to enable this parallelism (at a tiny cost in security).

After "masterKey" is derived, a second HKDF call is used to derive "unwrapKey" and "srpPW" which will be used later.

Client-Side SRP Calculation

(TBD) This.. is kind of crazy so far. The picture is incomplete and needs more detail.

The server should use Jed's SRP module from https://github.com/jedp/node-srp .

The basic idea is that we're using the main-KDF output "srpPW" as a password for the SRP calculation. We use the email address for "identity", and a server-provided string for "salt". (We could safely leave them blank, since equivalent values are already folded into the password-stretching process, but it's less confusing to follow the SRP spec and fill them in with something sensible).

The SRP "g" (generator) and "N" (prime modulus) should use the 2048-bit value from RFC 5054 Appendix A, which is also used in SRP. Clients should not accept arbitrary g/N values (to protect against small primes, non-primes, and non-generators). In the future we might allow alternate parameter sets, in which case the server's first response should indicate which parameter set to use.

The server creates its "B" value according to the SRP protocol and includes it in the response to getToken1.

The client does its entire SRP calculation in a single step, after receiving the server's "B" value. It creates its "A" value, computes the shared secret S, and the proof-of-knowledge M1. It sends both "A" and "M1" in the same message (getToken2).

The server receives "A", computes the shared secret "S", computes M1, checks that the client's M1 is correct, then derives the shared session key K. It then allocates a token (of the requested type) and encrypts kA+wrap(kB)+token as described below, returning the encrypted/MACed bundle in the response to getToken2.

getToken2

This method has two flavors, one for obtaining "signing tokens", the other for getting "reset tokens". TBD: either we'll have two different method names / API endpoints (getToken2Sign and getToken2Reset), or we'll pass an argument to a single "getToken2" method that indicates either "sign" or "reset". (using different endpoints would make it easier to monitor server load).

The client-side SRP calculation results in two values that are sent to the server in the "getToken2()" message: "srpA" and "srpM1". "A" is the client's contribution to the SRP protocol. "M1" is an output of this protocol, and proves (to the server) that this client knew the right password.

The server feeds "A" into its own SRP calculation and derives (hopefully) the same "S" value as the client did. It can then compute its own copy of M1 and see if it matches. If not, the client (or a man-in-the-middle) did not get the right password, and the server will return an error and increment it's "somebody is trying to guess passwords" counter (which will be used to trigger defenses against online guessing attacks). If it does match, then both sides can derive the same "K" session key.

The server then allocates a token for this device, and encrypts kA/wrap(kB)/token with the session key. The server returns a success message with the encrypted bundle.

Future variants (e.g. to fetch a third kind of token) might put additional values in the response to getToken2.

Decrypting the getToken2 Response

The SRP session key ("srpK") is used to derive two other keys: respHMACkey and respXORkey.

The respXORkey is used to encrypt the concatenated kA/wrap(kB)/token string, by simply XORing the two. This ciphertext is then protected by a MAC, using HMAC-SHA256, keyed by respHMACkey. The MAC is appended to the ciphertext, and the whole bundle is returned to the client.

The client recomputes the MAC, compares it (throwing an error if it doesn't match), extracts the ciphertext, XORs it with the derived respXORkey, then splits it into the separate kA/wrap(kB)/token values.

Since the kA/wrap(kB)/signToken response is so similar to the kA/wrap(kB)/resetToken response, the same code can be used to check+decrypt both. However remember that the respXORkey/respHMACkey is derived differently for each (using different "context" values).

Signing Certificates

The current stub just submits (cert, signToken), and gets back a signed certificate. This will be replaced soon.

(TBD, future protocol)

The Sign Token is used to derive a "tokenID" and four additional keys:

• request XOR key
• request HMAC key
• response HMAC key
• response XOR key

The requestHMACkey is used in a HAWK (https://github.com/hueniverse/hawk/) request to provide integrity over the "signCertificate" request. It is used as credentials.key, while tokenID is used as credentials.id . HAWK includes the URL and the HTTP method ("POST") in the HMAC-protected data, and will optionally include the HTTP request body (payload) if requested.

HAWK provides one thing: integrity/authentication for the request contents (URL, method, and optionally the body). It does not provide confidentiality of the request, or integrity of the response, or confidentiality of the response. We must provide these three other properties ourselves.

We might not need request confidentiality for signCertificate(). We do need it for resetAccount(). And we do need response confidentiality and integrity for both. To achieve these, the HAWK response is defined to be HMAC'ed (using responseHMACkey) and encrypted (XORed with the responseXORkey). XOR is safe and appropriate because the key is single-use and the data we're protecting is short and fixed-length.

Resetting the Account

The current stub just submits (newPassword, wrap(kB), resetToken). This will be replaced soon.

Creating the Account

To create the account in the first place, the client starts with email+password, then does the following steps:

• decide upon stretching parameters (perhaps consulting the keyserver for recommendations, but imposing a minimum strength requirement)
• decide upon a stretchSalt (remembering this should be unique, but is not secret)
• decide upon SRP parameters (generally fixed)
• perform key-stretching, derive masterKey
• create kA and kB, combining entropy from the local OS with more from the keyserver's getEntropy()
• create wrap(kB), using unwrapKey (derived from masterKey)
• create srpVerifier, using srpPW and the SRP parameters
• deliver many values to the keyserver: parameters for stretching and SRP, kA, wrap(kB), and the srpVerifier

Crypto Notes

Strong entropy is needed in the following places:

• (client) initial creation of kA and kB
• (client) creation of private "a" value inside SRP
• (server) creation of private "B" value inside SRP
• (server) creation of signToken and resetToken

On the server, code should get entropy from /dev/urandom via a function that uses it, like "crypto.randomBytes()" in node.js or "os.urandom()" in python. On the client, code should combine local entropy with some fetched from the keyserver via getEntropy(), to guard against failures in the local entropy pool. Something like HKDF(SKM=localEntropy+remoteEntropy, salt="", context=KW("mergeEntropy")).

An HKDF-based stream cipher is used to protect the response for getToken2(), and the request for resetAccount(). HKDF is used to create a number of random bytes equal to the length of the message, then these are XORed with the plaintext to produce the ciphertext. An HMAC is then computed from the ciphertext, to protect the integrity of the message.

HKDF, like all KDFs, is defined to produce output that is indistinguishable from random data ("The HKDF Scheme", http://eprint.iacr.org/2010/264.pdf , by Hugo Krawczyk, section 3). XORing a plaintext with a random keystream to produce ciphertext is a simple and secure approach to data encryption, epitomized by AES-CTR or a stream cipher (http://cr.yp.to/snuffle/design.pdf). HKDF is not the fastest way to generate such a keystream, but it is safe, easy to specify, and easy to implement (just HMAC and XOR).

Each keystream must be unique. SRP is defined to produce a random session key for each run (as long as at least one of the sides provides a random ephemeral key). We define resetToken to be a single-use randomly-generated value. Hence our two HKDF-XOR keystreams will be unique.

A slightly more-traditional alternative would be to use AES-CTR (with the same HMAC-SHA256 used here), with a randomly-generated IV. This is equally secure, but requires implementors to obtain an AES library (with CTR mode, which does not seem to be universal). An even more traditional technique would be AES-CBC, which introduces the need for padding and a way to specify the length of the plaintext. The additional specification complexity, plus the library load, leads me to prefer HKDF+XOR.