Security critism

toger5

A comment on the qMasterPassword app in the fedora software repo:

Not a secure implementation. If one of these generated passwords is compromised, an adversary can attempt to brute force your master password. If/when they succeed, ALL passwords are compromised.

It is much safer to have a database that can be protected. Generated passwords are given to websites and other services... can you really trust them?

What are opinions on this?
The way I understand the implementation it is not really feasible to brute force the user secret based on a password (there are numerus possible user secrets to generate the same password. Especially when the user name is not entirely known, but even than) Of course it is still possible to find one possible user secret the same that it is possible to brute force an encrypted file.

It would be nice to hear a better researched opinion on this than mine.

lhunath

It's a common opinion, especially from amateur security enthusiasts.

I'm planning on writing a blog post to detail the security specifics of the Spectre algorithm in particular, and the concerns that it aims to address. I can update you once it's live.

In the general sense, it is a valid criticism. This is why it is important to develop the actual algorithm thoughtfully. For instance, my naive initial solution back in 2010 was to use a seeded SHA256 hash of the domain name as the password. Such an approach would definitely be vulnerable to this issue. Most "similar" solutions such as SuperGenPass and even LessPass are particularly vulnerable to determined attempts at reversing the algorithm; so it is important to be wary of this.

As for Spectre, I've designed the algorithm deliberately to maximally protect against this using a multi-layered approach. The key relevant components are the choice of HMAC and Scrypt functions. The way the algorithm protects against reversal is to make it slow enough that it takes too long to be realistic. Whenever you hear somebody say "brute-force", your immediate next question should be, "how quickly?", since speed is the only way in which a brute-force attack can ever be successful.

We want to know how long it would take for a hash breaking machine to find your personal secret. This will depend on:

The amount of guesses it can make per second.
The entropy of your chosen personal secret.

From some calculations (I'll go into detail in the blog post), a top of the line commercially available hashing GPU nowadays (the Nvidia GTX 1080 Ti) might net us ~168 Spectre guesses per second. This is an extrapolation of my own tests on a GTX 1060.

Now we need to know the entropy of your personal secret. You can use a 4-digit PIN as your personal secret and reversal should be pretty easy, but what did you expect? We recommend using a short nonsense sentence. Let's assume you put some random words together, like wild berry yelling fire, freshly exhasperated kitten dance. The average 8-year old knows about 10,000 words (crazy!). The average adult knows about 20,000 words.

A 3-word personal secret space based on an 8-year old's vocabulary would take about 193 years of constant hashing to search. An adult's vocabulary 1550 years. Make it four words, 30 million years.

FYI, a rough estimate of that adult's personal secret against LessPass' algorithm might drop your 1550 years down to 4 months. SuperGenPass, about half an hour. I'm not going to dive into the many specifics there.

Take away:

The KDF function is very important. Spectre uses scrypt which is very slow, even on expensive GPUs, and is difficult to scale up because it's costly in all of GPU, CPU and RAM.
The entropy of your personal secret is very important too. This is where you can control your own security.

Use a high entropy personal secret and you have nothing to worry about.

You can link this post to users who are concerned, I'm open to any questions.

toger5

lhunath Thanks for taking position on that subject.
I am looking forward to the blog post.

JohnMolotov

lhunath I have a few questions of this topic.

Firstly, you put a lot of emphasis on scrypt being slow to bruteforce. I've read through the explanation of the algorithm here and my impression is that scrypt is only used to generate the master key, while the per site keys are generated using HMAC. Given that the master key is what is used to generate the site keys would it be correct to say that, assuming the goal is to compromise a user's site keys, one could bruteforce the master key instead of the master password? I'm guessing this is probably not a problem due to the master key length chosen, however I'd be interested to know the computational difficulty of bruteforcing the master key.

Secondly, while I understand that for any reasonably complex master password it is unlikely to be bruteforceable in a reasonable amount of time, I'm interested in the security model from a theoretical standpoint. Does stateless offer any inherent security advantage over storing state encrypted (and backed up) with an encryption method that would take an equivalent time to bruteforce as the hash algorithm? Presumably the only difference would be that in that case those with access to the state would be able to attempt to bruteforce it, whereas with Spectre anyone who knows one of the users passwords and that the password was generated with Spectre can. If that's the case, does Spectre provide any security or convenience advantage over say, syncing a keypass database using cloud storage?

lhunath

JohnMolotov

Does stateless offer any inherent security advantage over storing state encrypted (and backed up) with an encryption method that would take an equivalent time to bruteforce as the hash algorithm?

Encryption is effectively unbreakable if done correctly, so there is no need to improve on its security parameters. You wouldn't choose Spectre to have "stronger bruteforce protection". Hopefully the above has clarified that Spectre's bruteforce protection is however more than adequate.

The reason one would select Spectre as a method over encrypting a database lies elsewhere: Spectre allows you to have no state dependency. Why is this a useful property? It turns out that going from stateful to stateless has all sorts of beneficial side-effects. This list is not exhaustive:

You don't need reliable backups.
You don't need to synchronize devices.
You don't need a secure channel for the above.
You can never lose your identity.
Your identity cannot be ransomed by bad actors.
Your identity cannot be confiscated, legally or otherwise.
Mandatory key disclosure laws do not affect you.
You can create business continuity strategies or pass on your secret in a will.
Etc.

lhunath

Hi John,

I'd be happy to expand on the theoretical background for you.

As you mentioned, there are two key components to the Spectre algorithm. They each have a role to play. Let us begin with the site-key, which is the secret we are primarily interested in, since we use it to derive a password for the site:

MAC( user-key, site-salt ) = site-key

We need two inputs: a user-scoped secret user-key, and a site-scoped identifier site-salt whose purpose is to convert the user-scoped key into a site-scoped key.

To evaluate the relevant security properties, let's consider what's required for it to fail:

Since the site-salt is not a secret identifier (Spectre uses the site's domain name), this component's strength rests solely on the user-key's ability to remain uncompromised.
An attacker who can identify both the MAC algorithm and a target site-salt could pre-compute a large table which randomly maps user-keys to site-keys for a given site-salt. This table by itself is not very useful, but:
If the site's passwords get leaked, this table could be used to aid in a reverse lookup, to identify the user-key for any leaked passwords that match a site-key in the precomputed table.
As a result, a single site passwords leak might result in identifying user-keys.

How realistic is this scenario? As it turns out, whether computing such a table is feasibly useful depends a lot on the size of the user-key and site-key. Let's explore how:

If the site-key is small, it would be possible to build a complete table exhaustively mapping all site-keys to user-keys. If site-key is large, this becomes a computationally impossible task, to the point where you could be building terabytes of mapping data and still not come close to creating a single useful reverse mapping. Spectre's site-key is 32 bytes, ie. 256 bits. The amount of different site-keys that can exist is 2^256 (where ^ indicates power-of, feel free to put this into your calculator). If we need to store a mapping from each of these to a user-key, that is at least 32 bytes + user-key bytes for each of those keys (feel free to put (32+64)^(2^256) in your calculator). We find that exhaustively computing the site-keys is not realistic. As a homework assignment for the curious, try to find the largest size table one could reasonably compute in a year and how useful that table would be. It's not great. Moving on!

If the user-key is small, it would be possible to build a complete table mapping all user-keys to site-keys. If user-key is large, this again becomes computationally impossible. However, here we hit a snag: at face value it would appear that we cannot employ the same solution as the site-key: we want our user secret to be memorable by the user, so they do not depend upon state and can recover their passwords after losing all state. A typical user password is not that high in entropy. We might consider a sentence of four random English words (assuming any of the top 20,000 words) a very strong password, but its entropy is only about 57 bits-worth: far smaller than our site-key at 256. Consequently, we need to introduce an additional step in order to reinforce this side of the equation.

To do this, Spectre introduces a step called key-derivation. As you mentioned, we use a special memory-hard algorithm called Scrypt. Here is where we need to introduce the other step in the algorithm:

KDF( user-secret, user-salt ) = user-key

Spectre derives a 64-byte user-key through this method. As a result, just like we had an impossible to exhaust site-key, we now have an impossible to exhaust user-key. This concludes the analysis of the MAC portion, with the conclusion that its security comes from the fact that its search space is too large to exhaust. But this is only true if this KDF step is sufficiently strong! So let's see what's required for this component to stand up to attack.

Compared to a typical efficient MAC such as HMAC-256, the KDF takes a long time to compute a single user-key from a short user-secret combined with a user-salt. How is this any better than passing the user-secret directly into the first step above? It is better in the sense that deriving the user-key from the user-secret is extremely expensive (in time, as constrained by both computation and memory). Your phone can do it quickly for a single attempt, but to do it exhaustively for all of our "small" 57-bit sample set of possible English sentences would take an impossibly long time. We have traded space size for time size. As a result, it now becomes impossible to exhaustively make a table of all site-keys from all possible user-secrets, even though the user-secret is a small secret (empirical details below).

Can this KDF step fail at its goal? Yes, it can, and to understand how, we need to repeat the analysis we did above in step 1, but for this step. Can we make an exhaustive table of user-keys to user-secrets? No, we cannot, the user-key is 64-bytes, which makes it too large to search exhaustively as established before. But the user-secret is only ₅₇ bit, so it's not that large.
As we said before, the KDF is extremely expensive, so exhaustively searching a 57-bit space would still be very hard. You could imagine a massive compute cluster trying to build a table for this. It would be insane to do so for hacking a single user key, but building a table that can be sold and used for breaking any Spectre user's secrets, this might be lucrative.

Here is where we need to introduce the user-salt: its purpose is to make building the table user-secret -> user-key infeasible. How does it do this? Not by being secret!
The user-salt is allowed to be public knowledge: its only purpose is to require the attacker to build multiple user-secret -> user-key tables. One for every unique user-salt, to be specific. With the introduction of the user-salt, an attacker cannot build a table to attack any Spectre user, they need to build a table for each individual Spectre user.

Building a 57bit -[scrypt]-> 64byte table for a single individual is such an expensive operation it is simply not ever going to be worth it.

How expensive? A GTX 1080 Ti could perhaps be optimized to compute about 150 table entries per second (numbers based on scrypt hashcat performance). If you'd like to find out how long it would take to compute the table for a single Spectre user using a Spectre secret of up-to 57-bit, put this into your calculator:

seconds to populate your table = (2^57 permutations) / 150 entries per second

Divide by 356 * 24 * 3600 to find the amount in years.

Second homework assignment, how large a compute cluster to complete the job in a single year? And what's the bill on this operation? (Never mind where you'll source the silicon)

Let me know if anything remains unclear!

JohnMolotov

lhunath Thanks for the thorough response. Definitely put my mind at ease with regards to the MAC side of things. Given I typically use 128 character alphanumeric passwords for important things like this, I'd still see the user key as a potential reduction in entropy, not to mention HMAC being faster to calculate than scrypt, though I cannot see the user key being brute-forced in any practical setting so I suppose it's fine.

Another minor question on that topic however; given it is going to be difficult to change the algorithm as that wouldn't preserve a user's existing passwords, do you see future increases in computation power or other factors that could reduce the computation time of the hashes used as a potential issue? Over time it has been quite often seen that hash algorithms get deemed no-longer good enough anymore, is this likely to be the case for the algorithms used in Spectre? I suppose the worst that could happen is the algorithm eventually needs to be changed and everyone needs to update their passwords, but I can still see that being disruptive.

lhunath I was not particularly meaning stronger bruteforce protection, moreso other potential security benefits. I had thought of the fact that it eliminates the need for reliable backup/sync, however some of those other potential benefits are interesting. I can see the mandatory key disclosure laws point being a big upside. Also the convenience of not managing backups is getting more and more appealing the more I think about it.

note: I'm rather tired so if anything I've said doesn't make sense just ignore it

xiccalepu

lhunath This is exactly why I believe this is the best password project on the market. I'm surprised to see such little progress made towards the android application. Why not make it cross platform? You'd have a lot of people willing to help.

lhunath

JohnMolotov To your question regarding the algorithm's future evolution, the answer is yes, the parameters currently used for Spectre's KDF will evolve over time as the need arises. As electronics become more powerful, it will become feasible to upgrade the KDF's parameters to be more expensive while keeping the performance of the algorithm such that an average consumer device can log in quickly enough. You correctly assess that such an upgrade would affect the passwords the algorithm produces. Spectre has a mechanism for this, which we call the "algorithm version". Currently Spectre sits at v3. Any modifications to the algorithm that might affect its output passwords warrants a bump in algorithm version. When this happens, users will receive the option of upgrading their sites at their own leisure while new passwords are typically generated at the latest algorithm version. There is a user interface to assist with site upgrades. Regardless, this is a rare event.

lhunath

@xiccalepu At risk of deviating from the topic of this thread too much, I'll just say that for now Android users do have the option of using https://spectre.pw in the interim.