[cryptography] Master Password

Maarten Billemont lhunath at lyndir.com
Thu Jun 28 04:04:11 EDT 2012

On 30 May 2012, at 01:01, Maarten Billemont wrote:
> Dear readers,
> I've written an iOS / Mac application whose goal it is to produce passwords for any purpose.  I was really hoping for the opportunity to receive some critical feedback or review of the algorithm used[1].

I'd like to thank everyone involved for their tremendously useful feedback.

After considering the discussion both on this list and with external parties, an attempt to weigh the careful balance between security, usability, convenience and safety, I've completed a new release of Master Password which embodies the following changes since it was last evaluated:

- Still using scrypt[1] to derive a key from the user's master password, however, I've introduced a "name" concept for its salt.

The name has few constraints and is chosen by the user.  This choice assumes that the user understands that their name is a key part of access to their passwords. I believe that in modern times, where users sign up for websites everywhere using a username - password combination, that we can safely expect this of most users.

The name introduces a salt to the scrypt key derivation.  The salt is not secure-random, so its entropy is understandably fairly low.  I'm convinced, however, that this moderate entropy is sufficient to protect the user against a reasonable attempt at pre-calculating rainbow tables.

- I'm prefixing user data with (1) a fixed identifier "com.lyndir.masterpassword" and (2) the length of the user data.

The identifier (1) should help avoid cases where the algorithm might in the future be inadvertently re-implemented by another party, unexpectedly yielding the same results.
The length (2) should help protect the algorithm if any of the functions in the future are found vulnerable to certain length-based side-effects.

- I've "normalized" the algorithm by using HMAC-SHA256 instead of SHA1 hashing to determine the seed.

There's been some discussion about this, and in the end I believe the original implementation was without known flaws.

However, following certain recommendations I've decided the job is very befitting of a HMAC hash (given that we're hashing data using a key) and this should help avoid awkward questions from future peers.

The algorithm now calculates the seed using hmac-sha256(key, 'com.lyndir.masterpassword' | length(site-name) | site-name | site-counter)

The reason I've opted for SHA256 over SHA1 here (against certain recommendations) is that the function yields me a larger hash.  This is important because:

- I've increased the entropy of the "Long Password" type (1) and added a "Maximum Security Password" type (2).

Assume that you've used Master Password to create a password for a certain website, the site stores a hash of your password but gets compromised and your hash becomes public.

The idea of Master Password is to generate passwords for sites that are strong enough to give you at least a good chance at safety in this event.  Naturally, it depends on the exact conditions under which the hosting site was compromised and whether or not they stored your site password in clear-text, as a result of a salted hash, or a simple hash function.

Master Password can only do its best in this case to protect you, so assuming the site host had taken mild precautions and only a SHA1 or MD5 hash of your password got leaked and became public, it would be nice if Master Password's generated passwords were strong enough to make finding your site password from a leaked hash infeasible.

"Long Password" (1) type passwords were before a 14-character sequence of numbers, upper-and-lowercase letters, and symbols.  Assuming the attacker knows nothing more about the layout of your password, that would take him 1210537694726365245693116416 (86**14) attempts to try all combinations.

Assume furthermore that our attacker is in the posesssion of a machine that can calculate 2 billion MD5/SHA1's per second (eg. 10 8800GT's).

This blind attempt at brute-forcing a "Long" Master Password generated password would take them at most 19678164253 years.

However, because of the template that Master Password uses to make "Long Password"s readable to the user (usability), the true entropy of such passwords was in fact much less than 86**14.  In fact, doing the math, I determined that it would take a mere 964868861250000 permutations.

With the same hardware at his disposal, an attacker that knows your password was generated by Master Password and is a "Long Password" type, he now needs less than 5 days to discover the password for your leaked hash.

This has made me revise the template used to create the "Long Password".  It was important to me that passwords generated by Master Password were easy for a user to transfer manually using a keyboard.  After all, the standard use case is generating a password on your iPhone (with a moderately secure keypad - at least in comparison to that of your desktop) and typing it in on your desktop/terminal.

The template for "Long Password" used to be: CvcvnoCvcvCvcv or CvcvCvcvnoCvcv or CvcvCvcvCvcvno, where C is a capital consonant, c is a lowercase consonant, v is a lower-case vowel, n is a decimal digit and o is an "other" character (symbol from the set "@&%?,=[]_:-+*$#!'^~;()/.").  The result is word-like passwords: MitoLeta5^Pino.  Because of the way our mind works, we can easily copy them in chunks.

The template has now been revised to also permutate the Cvcv word with a Cvcc alternative.  This chance does not significantly impair the ability to word-chunk the password mentally.  That yields us with any of these templates: CvcvnoCvcvCvcv, CvcvCvcvnoCvcv, CvcvCvcvCvcvno, CvccnoCvcvCvcv, CvccCvcvnoCvcv, CvccCvcvCvcvnom CvcvnoCvccCvcv, CvcvCvccnoCvcv, CvcvCvccCvcvno, CvcvnoCvcvCvcc, CvcvCvcvnoCvcc, CvcvCvcvCvccno, CvccnoCvccCvcv, CvccCvccnoCvcv, CvccCvccCvcvno, CvcvnoCvccCvcc, CvcvCvccnoCvcc, CvcvCvccCvccno, CvccnoCvcvCvcc, CvccCvcvnoCvcc, CvccCvcvCvccno.  The result is that the permutations go up to 64183076650350000.

With the same hardware at his disposal, an attacker now needs at most 1 year to discover the password to your leaked hash.

I've decided that this is adequately high a number to discourage most attempts to brute-force a user's password.  Remember that his assumes the attacker knows that the user is using Master Password, so this would already have to be a very targeted attack.

Since 1 year on a small cluster isn't terribly high, I've added a second password type (2) for the more security-aware of Master Password's users.  I've called it "Maximum Security Password".  Essentially, this is a 20 character password that leads with a letter (any case -- this still helps with certain site password policies) either followed by or trailing the password with a symbol and a number, whose body consists of 17 characters (roman letters, decimal digits, certain symbols).  This password type has a terribly high entropy (19218445308363549398955938143178588160 permutations, 312409704477000007680 years for our assumed attacker), albeit very hard to manually copy.  An example password would be: XFN#BUOs0bMZ4lzlNv^2


Master Password is has now passed Apple review and is available on the store.  For the first week, only to those with a "promotional code" to redeem, after that, to the public.  Its code is still GPLv3 licensed and publicly available[2].

I believe that while Master Password remains a stateless solution that does not rely on secure random input or storage of any kind, a fact that may cripple its ability to provide certain levels of security, the end result is a product whose benefits with regards to usability and safety against loss or theft of your device and its data, far outweigh the loss in security that solutions without these constraints could provide.  Security is always a balancing game, and perfect security really doesn't exist.  I believe strongly that if you're facing a government or group with excellent funding that's focussed on getting *your* passwords or identity, then not even a solution with secure random input is going to protect you in the end.  I believe Master Password is a security solution that makes dealing with passwords for 99% of candidate users a nearly perfect approach.

I'd appreciate any final thoughts, be they constructive or critical.

I'd also very much appreciate it if any of you are OK with being quoted.  The end goal is still to sell this solution.  A lot of my time and energy has gone into not only the algorithm but also the end product that implements it in a way that hopefully makes the whole a pleasing experience.  A quote would mean a lot for any users contemplating this solution to improve the security of their daily lives.

To facilitate the latter, I'm closing this mail with a series of "promotional codes" that can be used by anyone with an iTunes account and a compatible device (iOS 5+).  They will give you free access to the pre-release[3] of Master Password.

Thanks a lot for all your interest and involvement!
Remember you can always contact me privately for any information as well.

Maarten Billemont

[1] http://www.tarsnap.com/scrypt.html
[2] https://github.com/Lyndir/MasterPassword
[3] NOTE: The pre-release of Master Password (v1.2.0) currently has a bug that causes keyboard input using a non-English keyboard to fail.  Anyone affected can wait for 1.2.1 to hit the store or switch to a standard US-QWERTY layout.

iTunes promotional codes (Go into iTunes, select the iTunes Store, click the App Store tab and hit "Redeem" on the side):
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4969 bytes
Desc: not available
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20120628/6a34d9ba/attachment.p7s>

More information about the cryptography mailing list