tag:help.masterpassword.app,2014-09-03:/help/discussions/questions/190-security-questionMaster Password: Discussion 2016-08-25T10:05:43Ztag:help.masterpassword.app,2014-09-03:Comment/405987552016-08-24T21:47:46Z2016-08-24T21:47:48ZSecurity question<div><p>The least thing we could expect is that - when quoting - you
indicate the source and the context of your quote. Without that it
will be just gossip.</p></div>Paultag:help.masterpassword.app,2014-09-03:Comment/405987552016-08-24T22:18:25Z2016-08-24T22:18:25ZSecurity question<div><p>Apologies I have been using the app for a while now but became
alarmed when I read this quote from Hacker News:</p>
<p><a href="https://news.ycombinator.com/item?id=9788597">https://news.ycombinator.com/item?id=9788597</a></p>
<p>I guess my question is could the master password be brute forced
if one of the sites used with this software suffered a password
leak?</p></div>Tomtag:help.masterpassword.app,2014-09-03:Comment/405987552016-08-25T00:28:11Z2016-08-25T00:37:41ZSecurity question<div><p>Hey Tom,</p>
<p>Where did you read this comment, if I might ask?</p>
<p>It is very easy for people to have an opinion on security
related topics. It is also not so hard to sound like you know what
you're talking about while you express that opinion.</p>
<p>Now, let me address the concerns this individual
highlighted.</p>
<p>Firstly, this person was very much correct in a lot of ways: the
nature of this solution is such that <em>if</em> somebody were able
to brute-force the master password of a user, he <em>would</em>
gain access to all of that user's passwords everywhere. This is a
property of the algorithm, not a flaw. The algorithm was designed
specifically such that the only requirement for generating "all
passwords" is a single secure element, being the master
password.</p>
<p>What would be rightly termed "a flaw", however, would be, if
there were a feasible method of performing said brute-force attack
on a user. Master Password was designed specifically with this case
in mind and has naturally been highly strengthened against this
type of attack. It is easy to express theoretical "flaws" in a
comment somewhere, but once you involve mathematics to back that
claim with evidence, it doesn't look so appealing anymore.<br>
So, how does Master Password keep you safe in the event described
above (it is indeed fairly trivial to obtain a hash of a password
on one of the sites you have an account of, or hoax you into
signing up to a fake website)?<br>
Givens (the attacker already possesses):<br>
1. a hash of a password on one of your sites<br>
2. your full name<br>
3. the site properties you used for the password on this website
(ie. site name, password type, etc.)<br>
Wanted (the attacker is trying to obtain):<br>
1a. your master password<br>
1b. your master key<br>
(either of these will do to fully compromise your security)</p>
<p>What is necessary to obtain 1a or 1b?<br>
Let's start with "1b. your master key". The master key is a 64-byte
key that was derived from your master password and is used to
generate every secret Master Password can compute for you, from
passwords to answers to security questions, and so on. It is
effectively your "digital identity", your "passport". Whomever owns
it, is effectively you.</p>
<p>What is necessary to compute your 64-byte master key? Well,
since we have all the input parameters to the Master Password
algorithm (short of the master password/master key) and we have the
expected output, all that is required is to perform the algorithm
with a random master key, over and over again, until the output
matches the desired output, you would think.<br>
Two problems:<br>
1. The operation needed to check a randomly generated master key
against the desired output is effectively a HMAC-SHA-256 and some
trivial extras. A dedicated computational rig based on a powerful
GTX Titan X can compute about 403 million HMAC-SHA-256 operations
per second. That allows it to make quite a few guesses in a short
time. The search space of a 64-byte key, is 8^64, which is too
large a number for me to copy-paste into sensibly this post, but I
suggest you use your favourite calculator to figure it out. If we
search this space using our Titan X, we'll be computing master keys
for about 506396133325000005952029456474178349694976 years if we
don't get lucky.<br>
2. You may say, "but we don't need to search the entire space of 64
bytes, we just calculate until we get a lucky match", that is
true.. except – the odds of finding a match in even a tenth
of that time are only 10%, which is a pretty bad odd and the number
is still astronomical. In addition, it is also false –
finding a match for your random master key against the desired
password hash is by no means a guarantee that you have found the
master key of the user! The Master Password algorithm trims the
HMAC-SHA-256 output and only uses a small subset of the output
bytes, in addition to the fact that a hash is only a small
computational representation of the input, that effectively means
that even if you find a master key that works for this one site, it
by no means is a guarantee that you have found your user's key. It
would be a good candidate key to try against some other sites, but
there's a good chance you'll have to keep looking for a while
longer.</p>
<p>I think this pretty much proves that brute-forcing the master
key is beyond insane and infeasible. Let's move on to brute-forcing
the master password instead (option 1a). This will be easier, since
its entropy is much smaller than that of a 64-byte master key.</p>
<p>What do we need to brute-force the user's master password?<br>
Our given includes that we already know the user's full name, so
all we need to do is try random master passwords against the entire
Master Password algorithm to try and find the right one.</p>
<p>Since the master password is much smaller, there was a need for
an extra measure of protection. Without this, a user could employ a
master password of, say, 8 alpha-numerical characters, which has a
search space of 62^8. Searching this space with our GPU is much
more feasible: it would take only about 6 days to crack your master
password:<br></p>
<pre>
<code>TIMING
Time to search the entire space using 1 GPUs of type GTX Titan X (HMAC-SHA-256) (rate=403,000,000.0/s)
Seconds to crack : 541787 (in one second we can search 0% of the space)
Hours to crack : 150.50 (in one hour we can search 1% of the space)
Days to crack : 6.271 (in one day we can search 16% of the space)
Months to crack : 0.2090 (in one month we can search 478% of the space)
Years to crack : 0.0176 (in one year we can search 5677% of the space)</code>
</pre>
<p>Naturally, this is unacceptable. Enter scrypt. SCrypt is an
algorithm that we term "key derivation", it works very similar to a
cryptographic hash (and technically, it is one) but is used not to
create a short "uniquish" identifier for a large blob, it is used
for the reverse: to generate a large blob out of a short
identifier. More importantly, they are designed specifically such
that their operation takes a long time to perform. This is a
powerful mechanism to protect against fast GPUs which can be used,
like the GTX Titan X, to calculate millions of hashes per second.
SCrypt, in particular, though, is a key derivation algorithm that,
in addition to making the operation slower, also RAM-bounds it. To
perform the hash, you now don't just need a powerful GPU, you also
need a very large amount of RAM. And it is far more expensive,
financially, to parallelize many simultaneous hash operations when
you need to keep vast amounts of data in RAM for each one of
them.</p>
<p>Let's turn this theory into practice. How much of a boost does
Master Password's use of SCrypt give us? For this purpose, I
created the <code>mpw-bench</code> tool:<br></p>
<pre>
<code>mpw: iteration 99 / 100 (99%).. done. 100 mpw iterations in 13s -> 7.46/s
hmac-sha-256: iteration 5445000 / 5500000 (99%).. done. 5500000 hmac-sha-256 iterations in 20s -> 284529.81/s
bcrypt (cost 9): iteration 990 / 1000 (99%).. done. 1000 bcrypt9 iterations in 28s -> 35.40/s<br><br>
<br>== SUMMARY ==
On this machine,
- mpw is 38134.853785 times slower than hmac-sha-256.
- mpw is 4.744541 times slower than bcrypt (cost 9).</code>
</pre>
From this summary, we can see that on my machine, performing a
single pass through the entire Master Password algorithm is many
times more expensive than a pass with just HMAC-SHA-256. While I
was able to calculate HMAC-SHA-256 hashes at a rate of around
284k/s, I was only able to perform a full Master Password run at a
rate of around 7.46/s. In addition, if I wanted to try more than 7
master passwords per second, I would need to invest not only in a
more powerful GPU, but I'll also need to start multiplying the
amount of physical RAM installed in my computer, because each
simultaneous computation requires a large amount space allocated in
physical RAM.
<p>On this machine, the introduction of scrypt has slowed the
attack down by a factor of 38000. That means, what took only 6 days
previously, now takes 6*38000 days. To brute-force a master
password at this rate:<br></p>
<pre>
<code>TIMING
Time to search the entire space using 1 GPUs of type 2.3 GHz i7, 8GB (MPW) (rate=7.5/s)
Seconds to crack : 29268110668200 (in one second we can search 0% of the space)
Hours to crack : 8130030741.17 (in one hour we can search 0% of the space)
Days to crack : 338751280.882 (in one day we can search 0% of the space)
Months to crack : 11291709.3627 (in one month we can search 0% of the space)
Years to crack : 951548.5418 (in one year we can search 0% of the space)</code>
</pre>
<p>Now, we can start multiplying our hardware and parallelizing
calculations to speed things up, but doubling up on hardware only
halves the estimate. To make a brute-force attack against a master
password realistic, you would have to do some seriously expensive
doubling-up of your hardware (say, 100.000 computers similar to my
dedicated server running non-stop for 9.5 years). That gets pretty
expensive, not only in hardware but also in running and operating
costs.</p>
<p>On a final note, this assumes, of course, that your password is
an 8-character alphanumeric, evenly random, identifier. Your actual
master password probably isn't. I personally recommend people use a
short pass phrase over a typical password for their master
password. A master password akin to: "Banana coloured rubber ducky"
actually makes a really powerful password and is far more
convenient in use than a uniform-random 8-character identifier. But
that's another discussion entirely.</p>
<p>Feel free to follow-up with any questions you might have.</p></div>Maarten Billemonttag:help.masterpassword.app,2014-09-03:Comment/405987552016-08-25T00:29:25Z2016-08-25T00:29:25ZSecurity question<div><p>(disregard my question about the origin of your comment –
I started writing this post when you first posted your question and
only finished it after you replied to Paul)</p></div>Maarten Billemonttag:help.masterpassword.app,2014-09-03:Comment/405987552016-08-25T10:05:40Z2016-08-25T10:05:43ZSecurity question<div><p>Hi Maarten,</p>
<p>Thank you very much for the answer and detailed explanation,
that has certainly put my mind at ease. Don't get me wrong, I was
by no means questioning the integrity of your software as I am no
encryption expert myself. As I said I have been using the app for
quite a while now and think it's an absolutely brilliant concept
which has been the ideal choice for me in managing passwords.</p>
<p>Big thanks and respect to you for offering this solution as free
software. All the best and hope you are able to keep up the good
work :)</p></div>Tom