Outsourcing of key encryption

Question

I am creating a password manager which uses an SQLite database to store user passwords. I encrypt passwords with AES algorithm, but I do not know where I should save the encryption key generated from the master password.

Answer 1

Important: Hire an expert. Seriously. This stuff is hard. Even the experts get it wrong. But they know what to look out for.

With that said:

So this is a pretty common pattern. There are a few approaches, but they all have a few common patterns.

Key Derivation

The key derivation step happens when you take a secret and derive a key from it. This process uses a KDF (Key Derivation Function).

In this case, you need a PBKDF, which is a Password Based Key Derivation Function. This is a function that is similar to a KDF, but is designed for low entropy secrets. So it adds a layer of protection by making the link from the secret to the key harder to find (and hence make it harder to try brute-forcing).

A common PBKDF function to use is PBKDF2. You could also use scrypt (which is newer, but FAR stronger). I'll use pbkdf2 from here on out, but definitely look into scrypt as well (it has more tuning parameters, but is otherwise the same in terms of usage).

First, you need to generate a salt. This is a random value. This allows for the same password to produce different keys on different systems. The salt is not a secret.

salt := genRandom(16)

This salt would need to be stored somewhere (likely in the database, or somewhere like that).

Then, derive a key from the password. Note that for every derivation with the same settings (and salt), the same password will produce the same key. So we don't store this key. This is computed every time we need it.

key := pbkdf2('sha256', password, salt, count, keyLength)

Note the count parameter. That provides the protection against brute forcing. The higher you make it, the longer the function will take. For online usages (in a web request for example), then values of 10,000 - 20,000 are decent. For offline usages (as yours are), you can tolerate a lot higher (and higher is better).

So now we've derived a key from the password.

Encryption

We could encrypt directly with that key. So that would mean when the user opens the app, they would enter the password, which would derive the key and store it in memory.

This is a double-edged sword. It's simple. But it also means that if anyone can read the key from memory, they could then start to brute force the password.

Another option would be to store a master key. This would be generated on installation, and encrypted using the derived key. So when the user logged in, you'd derive a key, retrieve the master key, and erase the derived key. That provides some protection against brute forcing, and lets the encryption use a far stronger key. It also provides the ability to change passwords without having to re-encrypt everything.

So the flow would look like:

private masterKey;
function login(password) {
    salt = lookupSalt()
    derivedKey = pbkdf2('sha256', password, salt, count, keyLength)
    masterKeyEncrypted = lookupEncryptedMasterKey()
    // NOTE that you **must** authenticate this encryption
    masterKey = decrypt(masterKeyEncrypted, derivedKey)
    derivedKey = null 
}

Then, just encrypt and decrypt using that master key.

Authentication

So I mentioned that you must authenticate the encryption. Basically, that means using Encrypt-Then-Mac.

In pseudo-code

function encrypt(data, key) {
    cipherKey = key[0...256] // first 256 bits
    macKey = key[256...512] // second 256 bits
    iv = key[512...640] // final 128 bits
    cipherText = AES-256-CBC-ENCRYPT(data, cipherKey, iv)
    mac = HMAC('sha256', cipherText | iv, macKey)
    return mac | cipherText
}

Then, when decrypting, you'd do the same:

function decrypt(data, key) {
    cipherKey = key[0...256] // first 256 bits
    macKey = key[256...512] // second 256 bits
    iv = key[512...640] // final 128 bits
    mac = data[0...256] // first 256 bits
    cipherText = data[256...] // rest
    if ( mac != HMAC('sha256', cipherText | iv, macKey)) 
        throw Exception "Invalid Data"
    return AES-256-CBC-DECRYPT(cipherText, cipherKey, iv)
}

Now, the MAC check should be done with a timing safe comparison (to prevent side-channel timing attacks).

Note that since the authentication depends on the password, an invalid password would yield an authentication failure. But also note that you can't tell the difference between an invalid password, and someone tampering with the stored key.

If that is a significant problem, then you could hash the password again (using a different salt), and store it encrypted in the database. Then after decrypting the master key, decrypt the stored password hash and validate that the password satisfies the hash. If you do this, be absolutely sure to encrypt the hash, and to use a different salt (otherwise throw the rest of the work away).