9
$\begingroup$

I am working on an application where we will be encrypting billions of small (< 2,000 bytes) records. Combined, we are facing many TB of data. Each record will be encrypted independently, using a unique IV/nonce.

We are aware of the restrictions around the reuse of IV/nonce values and the limits on the amount of data which can be encrypted using a key/IV pair (the NIST SP 800-38 series). Given that each record will use a unique IV, this will likely be the primary factor driving the rotation of keys.

Is there a maximum amount of data - regardless of the number of encryption operations using a unique IV/nonce - where the AES key itself should be rotated, or is the retirement driven entirely by the restrictions set by block chaining mode?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Well, there is the birthday bound on the input block, but that has undoubtedly counted towards the IV reusage limits as well. What's more important is that you seem to protect an awful lot of data with the same key. Of course, leaking the key would then have more dire consequences (although that also depends greatly on the type of data that is protected of course, 1 byte worth of information can be more important than e.g. the BluRay encryption of a bad movie). $\endgroup$
    – Maarten Bodewes ♦
    May 17, 2019 at 12:42
  • $\begingroup$ This typically depends on your cipher mode and usage. Most modes does have some defined maximum safe ciphertext lengths per key. XTS mode is on the lower end at some terabyte (no IV), while CTR should reach petabytes per key+IV pair. Of course then there's also the issue with number of usable IV:s per key, which also varies (AES-GCM is on the lower end, as low as 2^32 for some configurations). $\endgroup$
    – Natanael
    May 17, 2019 at 16:28
  • $\begingroup$ For very large amounts of data, it's easier to split the data up and use a KDF to derive unique keys per individual data set. $\endgroup$
    – Natanael
    May 17, 2019 at 16:30
  • $\begingroup$ AES has no known weaknesses that would cause it to be any less secure than an ideal block cipher, so any issues with encrypting a large amount of data are caused by the block mode of operation. It's not like 3DES where large amounts of data can make linear or differential cryptanalysis possible. $\endgroup$
    – forest ♦
    May 17, 2019 at 22:14

2 Answers 2

Reset to default
8
$\begingroup$

You should generally never use a single AES key for more than a few petabytes of data because of the so-called birthday bound: Cryptosystems based on AES like AES-GCM tend to have distinguishing advantages bounded only by $$\frac{q(q - 1)/2}{2^b}$$ after processing $q$ blocks of data, where $b = 128$ is the block size, arising from the birthday paradox.

When $q \approx \sqrt{2^b} = 2^{64}$, the standard theorems provide essentially no security guarantees. See sweet32 for what can go wrong when you reach the birthday bound of a block cipher—of course the birthday bound is much smaller for a 64-bit block cipher like Blowfish, where it is $2^{32}$, but the idea is still relevant to AES.

(Had we standardized a 256-bit block cipher like Rijndael-256 or Threefish, the birthday bound of $2^{128}$ would be completely irrelevant. But we didn't, and while there are 256-bit block ciphers out there, hardly anyone ever uses them.)

Particular cryptosystems using AES may have smaller limits—for example, AES-GCM with a random nonce is unsafe for more than a few billion messages under the same key, because the nonce is only 96 bits long and the security degrades catastrophically in case of collision, which is expected to happen after only about $\sqrt{2^{96}} = 2^{48}$ messages.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Would the downvoter care to explain what you disagreed with in this post? $\endgroup$
    – Squeamish Ossifrage
    May 18, 2019 at 15:12
  • $\begingroup$ AES + GCM is one of the modes we have been considering. If we take this path, the key will be used with random nonces (96 bit) and we'll limit the number of rows encrypted by a key to no more than 4.2 billion (2^32). $\endgroup$
    – Jeff W
    May 19, 2019 at 2:17
  • 1
    $\begingroup$ Why don't you use a sequential nonce, like the row id? Side note: Don't think of it as ‘choosing a block cipher like AES, and then choosing a mode like GCM’. You should pick an authenticated cipher, like AES-GCM as a unit or like crypto_secretbox_xsalsa20poly1305 (which can securely handle much larger volumes of data! but doesn't involve any block cipher) as a unit; ‘block cipher’ and ‘modes of operation’ are confusing implementation details, not something application developers should even be thinking about—focus on the security contract. $\endgroup$
    – Squeamish Ossifrage
    May 19, 2019 at 2:22
2
$\begingroup$

2000 bytes is 125 128-bit blocks of data. It is easy to use a 1 byte counter per message to keep track of blocks, that allows you to encrypt 4KiB per nonce. Since the nonce space is now 15 bytes, you can encrypt a LOT of messages, many TB is not a problem. However as mentioned, you do run into an issue with the birthday bound, but that should not be an issue for you. A 48-bit nonce will allow you to encrypt 281474 trillion messages under 4KB safely, which for your message size is half a billion TB.

Keeping with a standard 32-bit block counter implementation and limiting the nonce space to 48 bits will be more than sufficient to keep up with your data requirements and stay within the safety limit of the birthday bound.

The real problem with that message count will be in the mode of operation, the nonce generation method, and the method of message authentication. GCM has a safety limit for invocations of the authentication method, which can lead to forgery of authentication tags. If GCM was your goal, you will probably need a more computationally expensive method to replace or augment it.

It already sounds like you have a way to guarantee nonce uniqueness, but you should make sure that is also safe against tampering by a determined adversary, as well as technical issues. A 48-bit incrementing nonce combined with a 32-bit block counter means you have 48 bits of block space to play with to mitigate intentional counter reset.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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