WEP 115 Mongolian Crypto Scheme for Firefox Sync

• Champions: Zandr Milewski <zandr at mozilla dot com>
• Status: Draft
• Created: 13 Jun 2010
• WEP Index

The current username/password/secret phrase scheme used for Firefox Sync has desirable privacy properties. However, there are significant UX challenges and opportunities to improve security. This document attempts to distill several email conversations into a single proposal. It is deliberately aimed more at describing user experience than defining implementation details.

The name continues the "Where were we when Zandr asked a stupid question?" naming convention established by the Tahoe Project

Issues with the current scheme

“Secret Phrase” considered harmful

The current implementation uses a secret phrase to generate an encryption key to protect user data. The actual scheme is more complex than that, but at the end of the day, the secret to protect is this 256 bit key. This secret is never transmitted to to the server, which means the server cannot access user data. All well and good, but we haven’t been able to communicate this to the end user very well.

“A security question would work better.”

Users often think that the role of the secret phrase is to verify password recovery requests. There have been several messages on the mailing list about this, suggesting that account setup was too complex, and that security questions would be better.

“What do you mean you can’t tell me my secret phrase?”

Similarly, there have been messages on the list from users who have lost or forgotten their secret phrase, and thus cannot recover their data from the servers. While Sync was not designed or intended to be a backup service, 70% of our users have only one client. Backup is the only function Sync provides in this case.

User-generated long term secrets are often weak

Humans are pretty bad at picking passwords. UX concerns have prevented us from requiring a strong secret phrase, and we currently have a 12-character minimum with no further restrictions. Assuming a 94 character alphabet, the NIST guidelines estimate this at a mere 24 bits of entropy. PBKDF2 or not, this is a pretty poor protection for user data, and we can help the user do much better.

Design Goals

The server must not be able to read user data. This is the overriding design requirement, and is what sets Sync apart from the competition. The user need not trust the server. The practical implication of this is that we cannot enable any offline attack that is easier than a direct attack on the ciphertext.

Account setup should be simple

The current username/password/secret phrase triplet is confusing and should be simplified.

Account setup should provide strong secrets

The Sync client should generate (pseudo-)random secrets of sufficient length to provide good security.

Adding clients additional clients should be easy

Having good secrets is usually a pain to manage. To the extent possible, the Sync client should manage these secrets for the user, and make transferring them to new clients both easy and secure.

Recovery from loss of all clients should be possible

Competing with all of the above goals, we still need to be able to recover from a loss of all configured clients. This should be handled separately, as it really has nothing in common with the other use cases.

Proposal

Account Setup

Username

While not necessary for many of these use cases, for UX reasons this proposal retains the notion of a username. This is used for a couple of the transfer scenarios, but it’s account metadata, not a primary key.

Signing Key

Rather than using password to protect access to ciphertext on the server (most importantly, protecting deletion) we use a signing/verifying keypair. Using Elliptic Curve DSA for this allows the private key to be only 256-bits long, and NSS already supports the NIST 256p curve. At account setup, the client creates this keypair. The private, signing half of this key is the only credential that needs to be transferred to new clients. Storage on the server is indexed by a hash of the verifying key and a tag indicating the purpose of the hash. We will refer to this hash as the user ID.

CAPTCHA

To limit account creation to humans, the client will sent a creation request to a Ticket Server. The request contains the verifying key of the new user. The Ticket Server will will sign the request in exchange for a successful CAPTCHA, thus validating the humanity of the user. The client then presents this signed ticket to a storage server, which creates the storage pool under that user ID. As the creation request is idempotent, there is no requirement for a one-time nonce. Automated testers could sign account requests with a separate key which could be enabled on the web servers.

Encryption Key

Each client also generates a symmetric key for data encryption. Using a hash of the signing key, with a different tag, allows us to use a single 256-bit secret for the entire account. This means that adding a new client requires only this secret to completely configure the client.

Normal Operations

Once the account is created, all storage requests will be signed by the client. The client submits the request, the signature, and the verifying key. The server will then verify the signature and hash the verifying key to select the storage pool. This provides integrity checking of the requests, and restricts access to the holder of the signing key. A single-use nonce could be added here to prevent replay attacks if SSL (preventing recording of messages) is not considered sufficient protection against replays.

Adding a client

Once an account is set up and a client has been configured, all that is necessary to configure a new client is to transfer the signing and encryption keys.

Adding clients when one is already configured is facilitated using a PAKE protocol. For the purpose of prototyping, J-PAKE is convenient, though our security group has some questions that need resolution. There are other functionally equivalent PAKE protocols that are well understood, but may be patent encumbered.

These transfers take the following general form:

• Arm an existing client for the transfer. This creates the first key exchange message which is sent to the PAKE server. In addition, a small secret is created and displayed to the user. Very little entropy is required here, picking a word from a dictionary of 1000 or so words is sufficient. This word could be randomly selected, the user could pick a word from a list, or the user could enter one of their own choosing.
• On the new client, retrieve the first message from the PAKE server.
• Enter the secret word on the new client
• The new client and old complete a PAKE handshake. If the old client is online, this completes quickly. It is possible to complete the handshake without having both clients online simultaneously, but it requires 2 round trips to enable the new client.

It is important to note that protecting this key exchange is only protecting a fixed number of guesses at the secret word, potentially as few as one, though two or three might be desirable to tolerate typos without requiring the user to go back and re-arm the initiating machine. The initiating machine should log and alert the user to all failed guesses. As such, the passwords and nonces described below are not protecting the user credentials, only protecting the ability to attempt a key exchange.

Several forms of this system are described below. Some of them are easier than others, but if consistency is more desirable than each of use, the last form (“Memorized”) covers all use cases.

Email

This form uses a strong, single-use nonce to protect the key exchange.

Arming the client displays the secret word, and helps the user send a strong nonce by email.

At the new client, click a link in the email, or cut/paste the nonce into the client and enter the secret word.

The new client completes the PAKE transaction and receives the new credentials.

QR Code

If a mobile device has a camera, it is possible for a QR-code to contain all of the credentials. To avoid writing a QR reader ourselves, the QR-code could contain a URL of a custom scheme. This could be attacked by another app registering for that URL scheme, however. As an alternative, the QR code could be used to transfer a strong nonce as in the email case.

Once the user is satisfied that the legitimate Sync app is running, they enter the secret word.

The new client completes the PAKE transaction and receives the new credentials.

Nearby clients

If the two clients are nearby, as transferring credentials from a phone to a desktop machine, an email path is not required.

Instead of a strong nonce, a combination of a username and short nonce or username and password could be used to protect the key exchange. This password could be short or long term.

The user will arm a transfer on the phone, which will show a nonce or prompt for a password. It will then show the secret word.

The user enters the username, nonce or password, and secret word on the new client.

The new client completes the PAKE transaction and receives the new credentials.

Memorized

If email is infeasible, then a username/password pair can be used to protect the key exchange as in the “Nearby Clients” case above.

The user arms the transfer on the old client, which prompts for a password and displays the secret word.

Recovery

During account setup, we need to do a bit of user education. What makes Sync private and secure is that the server doesn't ever have the user's keys. What makes recovery challenging is that the server doesn't ever have the user's keys.

I think there should be a message something like “Would you like to create a backup of your Sync login?” with an offer to create an artifact that will allow account recovery. This should contain instructions to keep this artifact somewhere safe. The combination of the username and this artifact will allow configuration of a new client.

File

The simplest for most people, just put the credentials in a file that they can keep in a safe place such as a backup or thumb drive. This could be encrypted with a user password, but this creates something else for the user to forget.

QR Code

Back to QR codes again, but it’s a simple way to encode a big binary blob in a form that could be printed and stuck in a drawer. Comments about encrypting credentials in a file apply here as well.

Word List

Rather than give a user a long hex (or worse, base64) string to type back in when recovering, we could provide a list of words to print. PGPfone developed word lists for authenticating key exchanges, in which an English word represented 8 bits. These have the advantage of being human readable and easily typed. Alternating between two word lists protects against duplication and transposition, and there is sufficient redundancy to allow stemming and spellchecking to reduce the effect of typos. It seems somewhat absurd at first blush, but a 256-bit symmetric key would only be 32 words using those dictionaries. This is an interesting issue for localization, as the word lists were selected for maximum phonetic distance in English, and I'm not sure our localizers would appreciate generating similar lists.

System Changes

New components

Ticket Server

This basically replaces the registration server. Its sole purpose is to sign the new account ticket in exchange for a successful CAPTCHA. In fact, this function could be performed on the web front-ends. As the only additional capability present is signing tickets, separation from the normal webheads doesn’t increase security.

PAKE Server

This server is used to facilitate PAKE handshakes between clients. Using a server to mediate these transfers bypasses problems with firewalls, and allows exchanges between devices that are not online at the same time. As this does not require long-term persistence or bulk data storage, memcached running on the ticket server is probably sufficient. This document does not intend to provide a complete design for the PAKE server, but the basic operations required are just POST and GET. A lower-latency protocol like XMPP would be desirable, but is not required.

Removed components

LDAP

As the verification key is hashed to find a storage index, there is no specific authentication required.

Weaveserver-Registration

As noted above, the function of the registration server is replaced by the ticket server, and could easily be performed by the front-end webheads.

Weaveserver-Registration-Secure

The whole point of this server was to isolate powerful LDAP privileges from the net. As there is no LDAP, there is no need for an isolated server.

Back-end changes

Node Assignment

Distribution and management of storage pools is enough material for a separate WEP. As a sketch of a basic scheme, a mapping file could be published containing the DNS names of storage nodes and a range of user IDs served by each node. This file would be downloaded periodically by the clients, which would look up the server they should contact. Migration can be achieved by maintaining a table of user IDs to redirect on the old server pointing to the new location of that user's data. Once the migration has been completed, the mapping file can be updated and the redirection removed.

Authentication

The sync servers no longer authenticate against an external source. They should 404 any requests (other than pool creation with a valid ticket) that reference a non-existent pool, and 401 if the signature is not valid.

Staged Implementation

I think that we have one chance to change the UX here, but we don't necessarily need to implement the back-end changes at the same time.

With the tools in place to manage a large chunk of entropy like the 256-bit key described here, we can hash that secret along with tags to create a password and secret phrase.

The user would still keep the 256-bit secret, but the client would use all of the existing encryption and authentication mechanisms until the new back end is available.

Discussion

Media:wep115-cred-xfer-demo-g8d2b637.tar.gz is a simple python-based demo of a credential exchange, using a simple HTTP server as the backend.

--Brian Warner 21:36, 16 June 2010 (UTC)