# Database row level encryption scheme

I am wanting to secure some highly sensitive data in a database. This would mean that the data needs to be encrypted and remain secure for 100 years if it were to fall into adversary hands. I also want to limit the amount of data that is vulnerable in plaintext at a time in RAM. This is so there is less chance of plaintext data being paged to disk. Also the database may be quite large so it needs to be more efficient than decrypting the whole database at a time just to access it. Therefore I am thinking about encrypting the sensitive data on a database row level. This would mean a unique index which references the record is unencrypted, so each record can still be found/retrieved, however the sensitive data itself is encrypted.

My solution would be to have the data per database row:

index | IV | sensitive encrypted data | MAC

• A 256 bit database key will be used to encrypt the sensitive data which will be generated using /dev/random.
• The IV for each row will be 256 bits from /dev/urandom (faster than /dev/random).
• The encryption algorithm will be Twofish.
• The MAC of each record will be HMAC-SHA3 of the index, IV & sensitive data using the key.

The system is single user. The user will create a strong alphanumeric passphrase (minimum 14 characters).

A password based key derivation function will be run on the passphrase to create a derived encryption key which will then be used to separately encrypt the database key with Twofish. This is so the user can change their password without having to re-encrypt the entire database - they can just create a new password and re-encrypt the database key instead.

• To derive the key from the passphrase, PBKDF2 will be used with 10,000 iterations using HMAC-SHA3 with a 256 bit output and a salt of 256 bits obtained from /dev/urandom.
• What I am trying to do is balance the number of password characters required to make the data secure versus making it reasonably fast for users on a mobile device which have slow processors and limited memory. I don't expect the user to wait more than 5 seconds for the PBKDF to complete.
• A MAC is created using HMAC-SHA3-256(derived encryption key, salt | encrypted database key) and stored next to the salt and encrypted database key on disk. This can be verified when logging in to make sure they entered the correct password.

When the program loads, the user enters the passphrase. The KDF runs, which generates the key to decrypt the database encryption key. The real encryption key is then the only thing kept in RAM while the program is running and used to verify and decrypt individual database records when required.

1. What's the optimal length for the row level IV? Is 256 bits fine?
2. Is the minimum password strength of 14 characters and 10,000 iterations of PBKDF2 strong enough to protect the 256 bit database key? If not, what parameters would work?
3. Is PBKDF2 still a good algorithm still to use here? If not, what Scrypt parameters?
4. Any further changes or recommendations to make the system secure?
• If you want actual security for a long period, get rid of that "14 character password" part. Unless you pick a uniform random key from the entire keyspace, this is not gonna be the highest security you can get. Other than that, none of those questions seem to be about cryptography but rather the application (which is off-topic most of the time). – tylo Oct 14 '14 at 11:45
• @tylo, Then how does the user access the database? Manually enter the 256 bit database key? Seems like a hassle, especially if it's to be used on a mobile device. – aobocod Oct 14 '14 at 18:41
• @tylo, The tour/FAQ says "Get answers to practical, detailed questions", "Cryptography Stack Exchange is a question and answer site for software developers", and "Ask about... Cryptographic protocols". So seems to be on topic to me. Mainly I'm asking if the whole protocol will be secure. Or do you think it's a better fit on security.stackexchange? – aobocod Oct 14 '14 at 18:44
• If your password is completely random printable ASCII characters, then it needs to be at least $\frac{\log{2}}{\log{97}}\cdot 256 \approx 39$ characters long. Maybe better off storing it on a removable USB stick or, depending on your network setup, logging in with an asymmetric keypair. – Travis Mayberry Oct 15 '14 at 0:51
• @Travis, does your calculation factor in the PBKDF iterations? Do you really need 256 bits of security if it takes 10,000 iterations just to test one password by brute force? Could you go with maybe 128 bits, which is approximately 19 characters long using your formula? I think the security needs to rest in the strength of the passphrase, as any sort of secondary token could be compromised at the same time as the phone. I am thinking the phone & token could be confiscated for arbitrary reasons when going through airport security so it would be no use. – aobocod Oct 15 '14 at 9:46

The way the iterations work is that it roughly increases your security (in bits) by $\log_2(iterations)$. So you would still need $\frac{\log{2}}{\log{97}}\cdot (256 - \log_2(10000)) \approx 37$ characters in your password to have 256-bits of security. Think of it this way, if you have $2^{256}$ possible keys, that is an astronomically large number. Much more than the number of elementary particles in the universe. In comparison, 10,000 is basically nothing. Increasing the keyspace gives you exponential security, while adding iterations to your key derivation function gives you only linear security. It's nice, but at the end of the day it doesn't help as much as you think it does.

Having said that, you probably don't need 256-bits of security anyway. As I said before, that is a ridiculous amount of security. No increase in computational power will ever let anyone brute force a 256-bit key. There are physical limits to computation, and it would take something like the entire energy of a dozen stars to be able to do that. The reason we have things like AES-256 is that we anticipate in the future people will find more efficient attacks against AES which do not require brute forcing. But, with a longer key we hopefully delay these attacks. So, if someone discovers an attack which works in time $2^{n/2}$, AES-128 will be effectively broken. But, with AES-256 we still have 128-bits of security, which should suffice for a while longer.

For 100 years, the number of bits of security you really need is closer to 120-150. The outside limit of what anyone can brute force today is probably 70-80 bits, and remember adding bits gives you exponentially more security. So, you would really only need a password that was 17-20 characters long.

• Great answer thankyou. Makes a lot more sense now. Any opinion on the rest of the scheme? – aobocod Oct 15 '14 at 10:16
• What is the number of particles in the universe – curious Oct 15 '14 at 10:49
• Looks good to me. – Travis Mayberry Oct 15 '14 at 10:50

• Why HMAC-SHA3? HMAC and its security proofs have been devised for Merkle-Damgård hashes, and SHA3 is not one. HMAC-SHA256 would be fine (Updated per comment: the Keccak submission does endorse its use with HMAC, using a block size parameters of 576 (resp. 832, 1088, 1152) bits for the hash with output of 512 (resp 384, 256, 224) bits; but NIST's current draft specification of SHA-3 does not mention HMAC, or a block size; on NIST's website I only located this slide that does).
• Why Twofish? It did not win the AES competition, and is (thus) less widely available, especially in hardware.
• Twofish alone does not define an encryption algorithm, for it is a block cipher. You need to specify an operating mode.
• On 1.: Since Twofish is a 128-bit block cipher (as AES is), we do not even know what to do with a 256-bit IV (in common operating modes). 128-bit is fine for all common mode.
• On 2.: As explained in a fine other answer, a 14 characters key/pass-phrase can't give 256-bit security. If 14 characters are drawn uniformly randomly among 64 characters, and with 10000 iterations of PKKDF2, one gets $14\cdot\log_2(64)+\log_2(10000)\approx 97$ bits of security; that is, odds of success of an hypothetical effort involving $2^{90}$ hashes (which may be feasible in a 5 years effort, starting from now, for a well funded governmental organization) are less than $1/150$. That's likely enough for any practical use (though there might exist regulations interpretable as requiring even more).
• On 2. and 3.: However if a human needs to memorize a 14 characters key/pass-phrase, or worse generates it, security can be tremendously lower. How much lower is hard to quantify (and the key will often end written on a badly hidden note anyway). I advise
• at least allowing long and diverse pass-phrases;
• education of users on how to chose a good pass-phrase if they care for security;
• not hoping for strong security if they do not, no matter how clever the criteria to filter weak passwords is, and the entropy-stretching function used;
• rather than PBKDF2, using scrypt with highest parameters (memory, iteration, CPUs) practical in all envisioned runtime environments and circumstances (in particular, scrypt's increase of the memory requirement dramatically lowers the efficiency of brute-force attack for a given cost; if for some reason the use of HMAC-SHA256 in scrypt was seen as an issue, it is easy to use any trusted MAC, including HMAC-SHA3-256); whatever the method for stretching of pass-phrase to key(s), I suggest that it requires heavy use of significant memory, which is a simple and effective deterrent for ASIC/FPGA-based brute force crackers;
• using a random per-instance salt (where instance is e.g. the passphrase, or database),
• trying to keep that salt secret inasmuch as feasible, which can only help.
• It is un-academic to use the same key for encryption and integrity, which seems to be the case here; however since the algorithms proposed for these two functions are so different, the main practical issue is that if one key leaks (e.g. thru DPA), the other does.
• Why not AES-GCM, which is standard and kills the confidentiality and integrity birds with the same stone/key?
• It is not discussed how the passphrase, key, and deciphered data, are going to be protected from disclosure (e.g. by shoulder-surfing, keyboard logger, RAM dump..); that's a hard practical issue. Smart Cards may help, but that turns the whole proposition around.
• Why HMAC-SHA3? Well the authors of Keccak claim that it can be used with HMAC. You asked a question here and it seems HMAC-SHA3 is viable. Even if you don't want HMAC-SHA3, you could just do Keccak(K | M) which is fine too. I rate Keccak as more secure than SHA-2 which was designed by the NSA. – aobocod Oct 17 '14 at 9:27
• Why Twofish? Well although it did not win the AES competition, it was a finalist and it does have a higher security margin than that of AES. It also runs faster in software which is what I will be implementing it in. If your adversary ran an "open" competition, where they had final say over the "winning" algorithm, would you really trust their decision? Keen developers who possess an understanding of game theory might choose an algorithm by an author like Schneier who is very vocal about the dangers of mass surveillance and the NSA. – aobocod Oct 17 '14 at 9:34
• You need to specify an operating mode. Correct, I was thinking of counter mode. – aobocod Oct 17 '14 at 9:35
• Since Twofish is a 128-bit block cipher (as AES is), we do not even know what to do with a 256-bit IV (in common operating modes) Correct, I should have checked which IV length it requires. – aobocod Oct 17 '14 at 9:36
• @tylo I believe so. Generally I do make use of well reviewed crypto libraries to save time. It depends on what constitutes a "professional developer of encryption algorithms". 10 years industry experience? 5 libraries written? Some industry certification? What actually is needed is a clear understanding of the pitfalls: memory management, buffer overflows, side channel attacks etc. Your mantra is scare tactics to discourage people from developing secure crypto. I am sure NSA would love everyone using a small number of subtly backdoored libraries that they have covert operatives working on... – aobocod Oct 18 '14 at 3:27