6
$\begingroup$

We intend to encrypt certain values in a database which holds personal information such as addresses so as to prevent data leakage should the database be compromised.

The intention is that each field is individually encrypted with AES GCM with a 128-bit key and 128-bit randomly generated nonce. Fields will generally be quite short in length so there will be many short values encrypted with the same key.

AES GCM was chosen on the basis that it provides authentication in addition to encryption.

There will be approximately 50 million data items with 30 fields each. The intention is to use different keys for subsets of the fields, so likely 5-10 keys initially.

Would AES GCM be suitable for use in this scenario?

| improve this question | |
$\endgroup$
  • $\begingroup$ If we can assume that there will be less than $n$ fields, then you don't need a random nonce, but you can set it to a 96-bit value from the number $i \cdot n + j$ where $i$ would be the row index and $j$ would be the field index. A problem may be when you overwrite a previous value, but an attacker knows the previous and the current value. How much data are we talking about here and do you want to use the same key for everything? $\endgroup$ – Artjom B. Jan 22 '16 at 17:44
  • $\begingroup$ Initially there will be perhaps 30 different fields (though I expect that to grow over time) and there may be up to 50,000,000 items of data for each field. The intention is to use different keys for subsets of the fields, so likely 5-10 keys initially. The data store is schema-less so unfortunately I don't think a nonce based on row index would be possible. $\endgroup$ – Paul Smith Jan 22 '16 at 18:38
  • $\begingroup$ how small is small when you are talking about the data in the field? what is the largest probable entry in bytes? $\endgroup$ – Richie Frame Jan 23 '16 at 1:11
6
$\begingroup$

The only limitation that you really have to consider is that of nonce collisions. With 128-bit random nonces, you would expect collisions after about $2^{64}$ nonces due to the birthday bound.

Even if you stored all 30 fields of all 50 million rows thousands of times (you need a new nonce if a field is rewritten), you would still have a chance smaller than $2^{-32}$ of a collision. With your plan of using different keys for some fields you should be fine.

There are other limits on how much you can authenticate with GCM, but as long as you use the full-length authentication tag those limits are larger than the one above with short messages like you have. See section 7 of The Galois/Counter Mode of Operation (GCM) (pdf).

NIST SP 800-38D (pdf) says to only use a key for $2^{32}$ messages at most (Section 8.3) unless you are creating deterministic 96-bit nonces. It also gives even smaller limits if you wish to truncate the authentication tag (Appendix C).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ actually with non 96-bit nonces, the probability of a collision is higher, since it is multiplied and truncated to 96-bits internally $\endgroup$ – Richie Frame Jan 23 '16 at 1:10
  • $\begingroup$ @RichieFrame, doesn't GCM just hash the IV into a 128-bit value and increment that? With very short messages like here, the loss of nonce space to hash collisions and counters is just a couple of bits. $\endgroup$ – otus Jan 23 '16 at 5:23
  • 1
    $\begingroup$ Thank-you for the great comments. Having read NIST SP-800-38D it seems the recommendation as per section 8.3 is to limit the number of values encrypted with a given key to 2^32 (this is with a random IV or non-96-bit nonce). In addition Rogaway "Evaluation of Some Blockcipher Modes of Operation" strongly suggests that only 96-bit IVs should be used with GCM. Would I be correct in saying that the best approach therefore would be to use a 96-bit IV and limit the number of encrypted values to 2^32 for an individual key? $\endgroup$ – Paul Smith Jan 24 '16 at 19:17
  • $\begingroup$ @PaulSmith, that would certainly be the safe way to go. I should have mentioned the $2^{32}$ NIST guideline in the answer, but I don't think that following it is strictly speaking necessary in your original setup of 128-bit IV + short messages (unless you need to follow the standard to the letter). With 96-bit nonces you should limit each key to that amount. $\endgroup$ – otus Jan 24 '16 at 19:28
  • $\begingroup$ OK thanks for all the advice, last comment (and please let me know if you think this would be better as a separate question) but I would like to disguise the length of the plaintext, my intention is to apply PKCS7 padding to the plaintext up to a 128-bit boundary, is it safe to apply such padding when using GCM? $\endgroup$ – Paul Smith Jan 25 '16 at 9:40
0
$\begingroup$

No, AES-GCM is not suitable.

First, I am assuming that you will not need to search based on the encrypted fields. Searching on encrypted fields requires deterministic encryption.

Second, it is better to use a nonce-misuse-resistant mode of encryption. Examples include AES-GCM-SIV, which is almost as fast as AES-GCM and much more robust.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.