How terribly flawed is this design for key storage?

Question

Dave here, with a plan for storing secrets.

Threat model:

• Database and keyfile may (will?) be stored on un-trusted servers.
• Database contains many valuable secrets (passwords), encrypted by key stored in keyfile.
• Source code is public.
• Keyfile and database SHOULD never be stored on the same server, but will always need to be accessible from the client.

Out-of-scope threats:

keylogger, malware, rubber hose, chocolate

Failure mode:

Attacker obtains a copy of both keyfile and database and derives the encrypted key by attacking the keyfile.

Defenses:

• keyfile is encrypted with a key derived from a password.
• prototype uses bcrypt as the key derivation function.
• The high-entropy master password is selected randomly (diceware).
• the keyfile has no visible signature/structure -- someone who happens upon it will be unable to distinguish it from from random noise. This is not a big deal, but it adds plausible deniability.

Details

What I am most interested in is whether I am botching the keyfile encryption. The prototype (see https://github.com/scholarly/pynacl/blob/master/examples/bcrypt_wrap.py) is written in python using pynacl and py-bcrypt.

workfactor: 1 byte, default: 8  
nonce: 24 random bytes
salt: 32 random bytes
key: 32 random bytes  
magic = 24 bytes of sha1(salt+MAGIC+workfactor) [optional, looks random to casual observer]  
kek = bcrypt.kdf(password,salt,key_bytes=32,rounds=1<<workfactor)  
ciphertext = nacl.secret.SecretBox(kek).encrypt(key,nonce)  
keyfile = magic + salt + ciphertext

Questions

• Is this an appropriate way to use bcrypt.kdf? (which seems to be PBKDF2withBcryptHash. I don't know if this is a standard implementation or only used in py-bcrypt)
• Is there a problem with using SecretBox instead of a specialized key wrapping cipher?

Answer 1

To begin with, I see four potential problems with your key file.

1. The work factor (8) is probably too low. If we presume you pick your pass phrase by selecting $c$ words at random from a list of $2^{13}$ distinct words (e.g. correct horse battery staple) you get a pass phrase with $13c$ bits of entropy. (AFAIK the dictionary used by Diceware only barely contains $2^{13}$ words, but I presume it might be extended.) With a work factor $f$ you get an equivalent security strength $s = 13c+f$. A work factor $f=8$ is an odd choice, since it barely saves you of a single word in your pass phrase, to get an equivalent security strength that is greater or equal to your desired minimum security strength.
2. Presuming your $MAGIC$ parameter is a constant that is hard coded in your public source code, including the $magic$ tag is not consistent with your claim that the key file has no visible signal/structure. SHA-1 is fast enough, to make automatically searching for data that fits your format relatively easy.
3. There is at least one problem with your output lengths. The output length of SHA1 is only 20 bytes, but your pseudo code seems to pull 24 bytes from it. Also, if the bcrypt implementation you use conforms to the original paper (you seem to indicate otherwise), the maximum output length is limited to 192 bits or 24 bytes and not 32 bytes. Also, even if you use some form of PBKFD2 with bcrypt as PRF, the input length of bcrypt is limited to 56 bytes. A Diceware pass phrase with a minimum of $256-8$ bits of entropy is most likely to be longer than that.
4. According to the NaCl documentation, SecretBox performs authenticated encryption. This also adds structure to your key file, in the sense that an attacker will only need the key file, not both the key file and the encrypted database, in order to attack your pass phrase. While you don't specify exactly why you intend to put the encrypted key data in a separate file rather than a header of the encrypted database, or what you mean by "plausible deniability", this doesn't seem like a feature that is consistent with your general design.

---

The purpose of using bcrypt and other slow PBKDFs, is to to slow down attacks on the password, if the attacker should get hold of the cipher text, just enough to give all users an opportunity to change their passwords.

However, from your question it seems as if you intend to store the cipher text on an untrusted server. This means that it is not really a question of if the attacker will get hold of the cipher text. You must assume it has already happened, and that it is only a matter of time before the attacker manages to crack your password.

Presuming you use this scheme, what would be an appropriate usage policy?

• Firstly, you have to change the password you use for encrypting the key file, with an interval that equals the time you expect it would take an attacker to crack your password, should the attacker have managed to get access to your files yesterday.
• Secondly, as if that is not enough, you also have to change both the database encryption key and all passwords that are stored in the database, with the same frequency you change the password you use for the key file. Reason? Because the attacker only needs one generation of the key file and database pair, to be able to get to the contents of the database in that generation.

Consequently, in order to get this to fly, you really need a passphrase for the key file that contains enough entropy, to cause the password replacement interval to be 10 years or more. This means well above 80 bits of entropy in the pass phrase. Arguably, if you got a pass phrase that is that good, the bcrypt component is probably redundant. The extra bits of security strength you get by using bcrypt, are probably less than the confidence interval for your passphrase strength estimation. IOW, using bcrypt probably doesn't hurt, but you will have a hard time proving that it is necessary to get the desired security strength.

Answer 2

The random number generation routine must have supreme randomness, special care should be taken to ensure this. The larger concern is the decryption of the keyfile should in no way reveal the key to even authorized users. The password entropy concerns have been well voiced. Depending on the frequency of key changes, you may require > 112 bits of entropy. Your construction allows change of password without change of key, which I assume was a primary design criteria. Back up that key file! And as Henrick said, if the password is crackable, all secrets are revealed.

Is this an appropriate way to use bcrypt.kdf? (which seems to be PBKDF2withBcryptHash. I don't know if this is a standard implementation or only used in py-bcrypt)

Get rid of the nonce, this type of application does not require it, and using it anyway will not increase security. Get rid of 'magic', once again it will not increase security in a practical way.

I would use scrypt for this scenario, and require 1GB of RAM for the key derivation (assuming you have those resources), preventing parallel cracking on general purpose devices as well as specialized hardware. The workload to crack the password should exceed the entropy of the key.

Is there a problem with using SecretBox instead of a specialized key wrapping cipher?

Possibly, one purpose of key wrapping is to increase the workload of the decryption function, not just the key derivation (you can brute force the key faster). The workload to retrieve the key should exceed the entropy of the key, and AES does not technically meet that requirement. I have a special algorithm for key wrapping which is 512-bit key on 256-bit block, much slower than software AES. 'RollYourOwn' algorithms are generally not recommended, I use it because I am confident in the security level. I would not be confident using a single iteration of any common block cipher.