+1
Answered

How exactly does this work, technically?

This username already exists 4 years ago in iOS • updated by Maarten Billemont 4 years ago 2
Is it recreating passwords from saved cryptographic hashes? In other words, if it isn't saving the actual passwords, how can it accurately recreate them? Please be technical in your response. Thank you.
Operation
So your guess is pretty close.  Indeed, the idea behind Master Password is to have zero reliance on storage.  This gives us some very interesting benefits compared to traditional password solutions.  Most notably, you don't need to store a vault, back it up, keep it in sync, send its data over the wire, worry about losing the vault file, worry about the vault falling in the wrong hands, etc.

So the goal was to create a solution where all your password needs can be met using only data that you can come up with yourself, with no outside help.  Relying solely on your memory, your identity, factors you control and cannot be robbed of.

First, let me be clear about "all your password needs".  I don't like being vague in these areas as this is not a marketing pamphlet.  What do you need from passwords?  You need security.  Security is an extremely vague term, so when you hear somebody mention it, you should always be vigilant until they make clear what they actually mean.  In our case, we actually WANT a LOT of things:

  1. Security against people trying to gain access to your identity.
  2. Security against losing access to your own identity.
  3. Security against your own laziness.
The first point is pretty obvious, we want to keep people out.  People that want to get into your accounts are extremely creative, so to achieve this goal we need passwords that are strong against brute-force attacks, we need a solution that is strong against gaining access to all passwords it provides, and we need a solution that minimizes the amount of trust you need to put in third parties.  Master Password solves the password brute-forcing by generating passwords with extremely high entropy.  It solves the problem of brute-forcing the solution by using key derivation (more about all this later).  It solves the problem of minimizing trust by being an OPEN algorithm (feel free to not trust this app and write one yourself) and by relying on NO THIRD PARTIES to give you ubiquitous access to your identity.

The second point is just as important, though.  The password solution with ultimate security for point 1 is by using your system's secure random number generator and generating 256 bits of random data and using that as your password.  But now you have an even bigger problem; how do you log in the second time around?  How do you make sure you can keep logging in, in the face of hardware failures, house fires, or your stuff getting confiscated?  If you lose your data, you lose your identity.  That isn't right.  Master Password is a solution that is hardened against losing access to your own identity.

And the third point is just as much a point of failure for most password solutions.  Even if we have a solution that's perfect in security against intruders and against loss, if it's too much trouble to use it, we just skip it.  Especially for "trivial" sites.  But the truth is, there are no trivial sites.  Again, attackers are extremely creative.  In the face of password re-use, all it takes for an attacker is to gain access to one site, and slowly climb their way up the ladder of your identity.  They could use your profile on one site to fool your friends into giving them more information about you, or fool you into giving them access to other sites.  Every time you get lazy, that's a foot in the door for them.  Master Password aims to be easy to use by making generated passwords legible and memorable.  The apps focus on getting the right password quickly and copying the password to the clipboard so you can paste it elsewhere.  We're constantly thinking of more ways to improve the usability, too.

Enough about what the goal is, your question is how did we get there.  A more technical write-up can be found on the website: http://masterpasswordapp.com/algorithm.html - I will summarize here:

The inputs are things that you either know or need to remember.  We try to minimize the things you need to remember with defaults.  So what are the inputs?

  1. Your name.
  2. Your master password.
  3. The name of your site.  Use its bare domain name, then you don't need to remember a special name.
  4. The password counter for the site.  This counter starts at 1 and doesn't go up unless you need a new password for the site.
The fact that we need a master password is obvious, why do we need a name?  The name is a key element to the security of the algorithm: It is a seed to the key derivation that happens on your master password.  Without this seed (or if everybody had the same name), the key derivation could be weakened by the generation of a rainbow table.
The name of the site is also an obvious requirement, it ensures each site has a unique password.  What's the counter about?  Well, if a site's password was the result of solely your name, your master password, and the site's name, what would you do if somebody saw your password?  Or if the site told you its password database was compromised and you need to set a new password?  The solution is the password counter.  Increase the counter, get a new password.  If you forget the counter, don't worry too much.  Just start at one and bump it until you get a password that logs you into the site.

On to the more technical; the password generation goes like this:

  1. We perform a scrypt key-derivation on your master password using your name as a key.  The result is what we call your "master key".  This key is huge compared to your master password and makes the subsequent operations more against brute forcing.  More about why we need key derivation later.
  2. We perform a HMAC (Hashed Message Authentication Code) operation on the site name and counter using the master key to obtain what we call the password seed.  This operation gets us a sort of personal "hash" for the site.  These bytes are unique to you and to the website.
  3. The password seed would work pretty well as a passcode for the website, but it's not extremely friendly in use as a password.  It's just a string of 256 bit.  The final phase is to encode these bits into a readable and friendly password.  For this, Master Password employs password templates.  Each template encodes a different kind of password, some strong, some weaker.  We have different templates for different use cases, mostly to dodge horrible password policies in place on certain sites, such as "your password MUST contain a number, it MUST start with a letter, and it MUST NOT be longer than 6 characters.  Oh yeah, and it MUST NOT contain quotes or anything fancy because we strip that since we don't know how else do sanitize data against SQL injection while we store your passwords in plain text".  The result of the template is a fancy looking password ready for use.
Why do we have a "key derivation" step?

Since this solution relies on zero storage, nothing is stopping an attacker from trying to generate a password for your name and, say, apple.com, until something works.  That's why we need maximum protection against brute-force attacks.  We need two kinds of protection.  We need to protect against an attacker figuring out your master password using your name, and we need protection against an attacker figuring out your master key by setting up a phising/hoax website, getting you to sign up, and in doing so, getting your name and your password for their own website.

Protection against figuring out your master key through a hoax is done by generating an extremely long master key from your master password.  As a result, it is now computationally impossible to guess your master key using brute-force HMAC operations (there are just too many permutations of a 256-bit key, specifically, there are 115792089237316195423570985008687907853269984665640564039457584007913129639936 master keys to try from).

Protection against figuring our your master password by trying a bunch of random passwords is in theory easier, because passwords aren't 256-bits long.  Your master password will be tiny in size and entropy compared to your huge 256-bit master key.  To protect against brute-forcing, we therefore employ an extremely resource intensive key derivation operation, called "scrypt".  The idea is to perform a huge amount of "pointless" math.  I say pointless, because we don't really gain anything from it.  All we want to do is waste a lot of time, more specifically, force the attacker to also waste a lot of time.  "scrypt" specifically improves on standard key derivation techniques by not only wasting a lot of CPU time, but also wasting huge amounts of RAM.  The theory is, the longer it takes for an attacker to try out one guess of your master password, the longer it'll take him to find the right one.  We pull this theory into the extreme so that guessing a 6-character alphanumeric password takes 19477911.1969 years, instead of 0.3214 years without key derivation, in each case on a system with 10 GPUs working simultaneously non-stop.  The CPU + RAM expense is also important because it means that the more computers you make work simultaneously, the more your $ cost goes up.  CPU and RAM are expensive, and forcing the derivation to use a lot instead of minuscule amounts causes the $ cost of a brute-force attack to become phenomenal.

I think I've covered everything I wanted to explain.  See the algorithm page on the website for more details or to read the actual algorithm.  And of course, if you have any questions at all, just reply or email me at <masterpassword@lyndir.com>.

Cheers,
Maarten.
See http://masterpasswordapp.com/security.html