What is the benefit of adding data encrypting key then store it (encrypted) along with data

Question

To protect user's sensitive data, I am considering the following 2 approaches:

1. Create 1 data encrypting key (DEK) for each user, use it to encrypt (using AES CBC mode with a random IV for each encryption operation) all data of the same user. DEK is protected and stored separately from data.
2. Use multiple DEKs, 1 each time a new piece of user data needs to be encrypted (using AES/CBC with IVs like above). The DEK is then ecrypted using a KEK corresponding to that user, and stored side by side (e.g. same row in database) with the data that is ecrypted with it. The KEK is stored securely, separatedly from the data and DEK.

Is there known vulnerabilities in AES/CBC with good random IVs? What is the benefit of the 2nd approach, other than minimizing the amount of data encrypted with the same key, thus reduce the risk of being cryptanalyzed?

Answer 1

I'll give you a concrete example of when / why it makes sense to store the (encrypted) key alongside the data (I happen to have the tab open from answering another question, so why not?):

Android Full Disk Encryption.

In a nutshell: When you turn Android Disk Encryption on, it generates an AES-128 key which it uses to encrypt the drive (called the master key). It then takes your Pattern / PIN / Password and uses that to derive a second AES-128 key which it uses to encrypt and store the master key on disk. You know how the first thing Android does during boot-up is ask for your PIN / Password? That's because it needs it to decrypt the master key so that it can decrypt and mount the main filesystem. The reason for having two AES-128 keys is that if you change your Pattern / PIN / Password, it just has to re-encrypt the master key file, not the whole disk.

Another good use-case is data in transit, for example S/MIME or PGP:

Encrypting large amounts of text / attachment data with an asymmetric cipher (like RSA) is really slow, so what we do is encrypt the bulk data with AES using a random key and IV, then encrypt these with the recipient's RSA public key and attach the encrypted AES key and IV to the massage.

In reference to your point 2.: the exact reason for this choice probably depends on the specific use-case, but one advantage that comes to mind is that you can reveal the key for one row to somebody - for example an auditor - without compromising any other rows in the table. You can also send the data to someone without needing to do the work of decrypting / re-encrypting it (a big saving if the data is large, or you have real-time requirements).

Answer 2

The biggest difference, (I won't call it a benefit) is that if you use a different random key for each piece of data, you can use a static IV and not have to store an IV with each piece of data.

This would not however, give you additional security over option 1, using the same DEK and a strong random IV for each piece of data.

The one potential benefit (and it's a bit of a stretch) is that if the data is accessed independently, the exposure of a data encryption key (but not the master KEK) only exposes the single piece of data that is encrypted with that DEK, and no other data. If this is a real threat scenario for you, then option 2 is definitely the way to go. If not, or if you may need to access many pieces of data simultaneously or in rapid succession, then option 1 has clear benefits.

Answer 3

Have you considered an encrypted filesystem? It works very similar to your second proposal.

Examples are eCryptfs in Unix and modes of NTFS in Windows. Secondly, there are no feasible ways to break AES other than a brute force attack; Serpent-256 cipher is slower but there is no known way to breach more than a few numbers.

As for why you would pick one over two, it's because of a thing called the cold boot attack: If a hacker gains access to a hibernating computer with an encrypted drive, he can take another computer with the same memory standard, remove the memory from the first computer after chilling it and place it in the second machine then booting it up before it degrades. Thus he can recover the keys for any files you were using, so if you only have one it is easy to decrypt the hard drive, while the using an individual file encryption system will only allow the hacker to decrypt what was open and running.

In sum, both will work unless you are worried about physical access attacks.