Security of master password in a derived password manager

Question

I am aware of other questions asking similar things as this one, but I believe this design addresses many of the issues raised in those questions. I'm also not concerned with making sure there's no database to store, only that the database doesn't store any secrets.

Using some key derivation function KDF
With master password provided from elsewhere
Password requirements are the rules of what are allowed by the site,
    i.e. length, allowed character classes, required classes

# To register with a new site
With username provided from elsewhere
With password requirements provided from elswhere
Create a salt
Store site,password requirements,username,salt
Create key by KDF(salt, master password)
Convert key to generated password to fit password requirements
Give username and generated password to site
Register

# To login to a site
Retrieve password requirements,username,salt by site
Create key by KDF(salt, master password)
Convert key to generated password to fit password requirements
Give username and generated password to site
Login

Let's say an attacker acquires both the store and the plaintext generated passwords.

1. Does this design make it any easier for the attacker to find the master password than by a brute force attack?
2. Is a brute force attack on this design easier than a brute force attack on an encrypted password store?
3. Is this in any other way easier to attack than encrypted password managers that derive the encryption key from a master password?

Of course the list of sites and usernames itself is important information. I'm only wondering about the security of the master password.

Answer 1

Rather than do all the math, take a top down look at the proposed system. The proposed system doesn't provide any benefits over an ordinary password manager. And it turns out that the proposed system weakens your security when compared to an ordinary password manager.

How? By adding needless coupling to the master password. Let's say you're waiting in an airport. You take out your phone, open up your password manager, and enter your master password. You then realize that a guy in a hoodie is behind you and looking in your direction, and definitely watched you enter your password. Now you're uncomfortable; you really want to change your master password, but if you do, all your site-specific password generation mechanisms won't work with the new password.

Ordinary password managers work by having a cryptographically strong pseudorandom number generator at their core. A strong PRNG is required to generate each random number so that it is completely unrelated to every other random number it's generated. That guarantee of "unrelated" is what makes the PRNG vital for security.

When you initialize a typical password manager, it starts by generating a random Master Key Encrypting Key (MKEK). You then choose a master password. Your master password is run through a Key Derivation Function (KDF) that turns your password into a cryptographic key. Your password-based-key is then used to encrypt the MKEK, which is stored in your database. Every time you open your password manager, your password is used to decrypt the MKEK, which is then available for all the work for that session. When you end the session or lock your password manager, the decrypted MKEK is wiped from memory, and you'll have to enter your password again.

Every time you add a new site, the PRNG is used to generate a random password for it. You choose whether to use the random password or pick your own. Whichever you choose, when you save the password it is encrypted with the MKEK and then stored in the database. Later, when you retrieve the password, it is decrypted with the MKEK.

When you change your master password, the MKEK is decrypted with the old password and reencrypted with your new password. The MKEK doesn't even have to be changed. The individual site records don't need to be changed either, because the MKEK didn't change. And when you want to rotate the MKEK, you can - click a button and the password manager generates a new MKEK, then decrypts each site's password with the old MKEK and re-encrypts it with the new MKEK. The site passwords don't change.

Everything needs to be decoupled, or it becomes "brittle". When something's brittle, it's harder to change it in a timely fashion. And in the case of security, it's sometimes required to change things urgently.

Answer 2

(1) Does this design make it any easier for the attacker to find the master password than by a brute force attack?

No. Not that I see.

(2) Is a brute force attack on this design easier than a brute force attack on an encrypted password store?

Yes. There is more ways for an attacker to obtain the data that they need for a brute force attack. At least that is the case if we take your notion that there are no secrets in your database.

Suppose I set up a server for, say, MyCuteKittyPictures.net, and I store passwords on that server in plaintext. There are plenty of plaintext offenders out there anyway. An evil site operator or anyone who compromises a plaintext offender, is able to learn your password for that site.

This gives them everything that they need to launch a brute force attack except the salt, but you have said that the database file is not a secret, and therefore I should assume that the attacker has access to the salt.

In my example, I talked about a single plaintext offender (and a malicious one), but data from any plaintext offender puts the attacker in a position to launch a brute force attack. And so there is more opportunity to an attacker obtain enough data to launch such attacks

(3) Is this in any other way easier to attack than encrypted password managers that derive the encryption key from a master password?

This is going to depend on some fine details. But on the whole encrypted password managers will generate passwords that are truly independent of each other.

Also what you are calling encrypted password managers will have the ability to encrypt the site, and username, and other data which a user may wish to keep private. I may not want to world to know whether I have a login for ToenailChewersAnon.org or that I am user fluffybuns on some other site.

So you really aren't gaining anything by pursuing yet another attempt at a derived password manager. And you are losing other desirable processes.

Answer 3

The weakest point appears to be your "stored information", which contains the possible rules for your passwords. So, for example, if the attacker knew that your password for example.com must be generated as a case insensitive 12-char string, this information will be useful to set up a more efficient bruteforce attack on example.com. The security of your master password won't be affected in any way though.

For the master password, there's the KDF to consider. If your KDF is secure enough (not known to have weaknesses and taking enough time or memory to be computed), then an attacker cannot get the master password without bruteforcing it, even if they knew the salt or any other information about how you create the final password. But if your KDF is not secure enough (maybe you just use plain SHA for your custom KDF, for example), then bruteforcing your master password might be much easier than bruteforcing the master password of a good password manager (good password managers rely on functions and algorithms that are known to be secure).