RndPhrase

RndPhrase is now closing in on v1.0 - the first stable release. This is yet another attempt at creating an add-on that will help users securing their many personal accounts on the Internet. The idea is simple: Given your normal password, the add-on will generate a new secure password to use instead. For a long time, I have wanted to use such a tool, however I've run in to some common problems:

• They rely on 3rd party servers, that store your password.
• They rely on storing your passwords locally, and only work on this machine.
• They only work on one platform (e.g. Mozilla Firefox or Google Chrome).

This post is about where, how and why RndPhrase differ.

Auto-generated secure passwords

The main goal of any password generator is to help the user improve his or hers online security. More specifically: How do I minimize the risk of someone hacking my accounts and the personal cost if it happens anyway.
I originally had three ideas to realize this:

1. To generate 64-bit passwords.
2. To generate a unique password for each domain.
3. To work transparantly and be available as a service to the user.

Number one is about minimizing the risk of your account being hacked in the first place. We basically make brute-force hard. Very hard. So hard, at no-one will try this approach. However, there are other ways of hacking an account. An attacker could exploit a security vulnerability on the website and gain access that way instead. An attacker might even retrieve the password in clear text. This makes it clear: We don't trust the individual website.

This leads us to idea number two. By generating a unique password for each domain, we lower the cost of intrusion. If an attacker manages to retrieve the password for facebook.com, this is all he or she gets. The password isn't valid anywhere else. And the user doesn't have to change passwords anywhere else.

You probably remember the story of rockyou.com? If not, take a quick look at:
http://techcrunch.com/2009/12/14/rockyou-hacked/

This is exactly why we want unique passwords.

The third point seems trivial, but is an important one. Most people doesn't like to break their habits. Therefore, RndPhrase should make the transition as easy as possible. The add-on should be usable to anyone.

Currently, RndPhrase works in the background, automatically transforming all passwords starting with '@'. Whether this is a good idea or not will show with user feedback.

Regarding availability, RndPhrase will be available in several versions:

1. Mozilla Firefox add-on
2. Google Chrome add-on
3. Online version, works in any browser
4. Conkeror page-mode

Download and more

For more information on RndPhrase, stop by the GitHub wiki page at:
http://wiki.github.com/brinchj/RndPhrase/

Technical Details

This section is mainly for those interested in the technical inner-working of RndPhrase.

Per domain passwords

RndPhrase will generate per domain passwords using a predefined seed, the hostname and the chosen password. The seed is constant over all domains, but unique for the current user. The password can differ from site to site (or if several accounts are used at the same host).

RndPhrase uses a hash to generate a 256-bit pseudo-random number. This number is then used to pick the password for the site. The pseudo-random number is computed as such:

N = H(password + H(seed + H(password + '$' + host)))

Where H is the hash function. This layout is inspired by the HMAC function, however expands this with the use of a seed. The function has the following goals:

1. To annoy brute-forcing as much as possible: the first variable used is the secret.
2. To break rainbow-tables: the seed is unique for each user.

The hash function used is CubeHash8/1. Why? Because it's simple to implement in Javascript and because I believe it to be secure. The three hash function invocations yield a minimum of 3*80 = 240 rounds, due to CubeHash's aggressive finalization. Furthermore, the output of H is 64 hexadecimal digits. CubeHash8/1 runs 8 rounds per byte. This yields a stronger lower bound of 240 + 64*8*2 = 1264 rounds. Even though this does not reject a brute-force attack it certainly does slow it down. However, this isn't comparable to scrypt or other aggressive key derivation functions. If someone comes up with an idea suitable for Javascript, let me know.

UPDATE: Feb 26, 11:42 GMT
I don't know why I didn't think of this at first, but this definition of N has one problem: It allows reuse of intermediate values as it hashes the same prefix's several times. To avoid this, one could instead use:

N = H(H(H(password + '$' + host) + seed) + password)

This definition forces all computations to be executed as no prefixes are repeated.

Alphabets and the modulus operator

RndPhrase uses an alphabet of letters to construct the passwords.
The default alphabet is:

"abcdefghijklmnopqrstuvwxyz0123456789"

This alphabet has a few nice properties:

1. If letters are chosen with equal probability we get 5.169 bits of entropy per char. This yields 82.704 bits of entropy (>64 bit) for a 16 character password.
2. The passwords only belong to two digit-groups, lowercase letters and numbers. Hopefully, they will pass the restrictions of most sites.

However, this alphabet also comes with a problem. It consists of 36 letters. Hence, in order to pick a letter we need a number in the range [0,36]. But what we have is a random 256-bit number.

This is what we do:

1. Split the 256-bit number into 16-bit numbers.
2. Use each 16-bit number modulo 36 to pick a letter.

This yields a password of 16 characters. However, the letters are not equally likely to be picked. In particular, when choosing a letter each of the first 16 (a-p) letters has a probability of 1821/65536 of being chosen while the rest (q-9) has a probability of 1820/65536. This is a small bias. But it affects the entropy of the password slightly.

Let's estimate the entropy contain in each letter. In the unbiased case, this would be:

H(p) = p * log_2(p)
E = -1 * 36 * H(1/36) ~= 5.1699250

Now, we introduce the bias (H is the same):

E = -1 * (16 * H(1821/65536) + 20 * H(1820/65536)) ~= 5.1699249

The loss in entropy per letter is very small. Had we used 8-bit numbers (and not 16-bit numbers) to determine each letter, the entropy value per letter would have been 5.1686; somewhat smaller, but still not much. RndPhrase generates passwords of length 16, each of these containing about 82 bits of entropy.