12

Considering AES-256 encryption, what is the maximum amount of data should be encrypted with one key? Does Block cipher modes/IV/counters also governs the limit?

If say the maximum amount is 50GB, does it mean the one file of 50GB has limit or 5 files of 10GB?

Ali Ahmad
  • 4,814
  • 8
  • 35
  • 61
Deepesh M
  • 415
  • 1
  • 5
  • 10

2 Answers2

12

A block cipher is a Pseudorandom permutation: the key selects the function seemingly at random in the set of possible permutations of the space of block values (that space has size 2128 for the AES, since it has 128-bit blocks). Most usages of a PRP are fine as long as it looks like a Pseudorandom function. The difference between a PRP and a PRF is that the PRP will never give you two identical outputs for two distinct inputs, whereas the PRF may do so. However, a randomly selected function will give you such a collision only out of random, and it will require a lot of invocations: on average, 2N/2 invocations if processing blocks of size N.

Translation: when you encrypt more than 264 blocks with AES (i.e. 268 bytes, since an AES block is 16 bytes), AES begins to look more like a PRP than a PRF, and that's the point where you should stop. That's more than 250 millions of terabytes, which is quite a substantial amount.

It does not matter whether the said amount of data was processed as one, ten or 42 billions of whatever you may elect to call a "file". The AES processes blocks of 16 bytes and knows nothing else. On the other hand, it does not matter at all, since you will not practically reach that 268 bytes limit: AES was defined with 128-bit blocks precisely so that we could encrypt terabytes of data without worrying about a key running out of juice. When AES was specified, it was meant to replace 3DES, whose 64-bit block size was indeed worrying (232 blocks of 8 bytes, that's 32 gigabytes, which can be reached quite easily on today's machines).

Key size has nothing to do whatsoever with that matter. It is all about block size, and that's 128 bits for AES (regardless of key size).

Tom Leek
  • 170,038
  • 29
  • 342
  • 480
  • Aren't the practical problems more about IV/nonce collisions and thus reuse and less about detecting the difference between PRP and PPF? – CodesInChaos Feb 02 '13 at 20:10
  • @CodesInChaos well, that also depends on block mode, but lets guess it's one where a sequentially increasing iv (say CTR mode), all we need do is use a >=64bit long IV, and we'll also be at 2^64 blocks before that repeats. – ewanm89 Feb 03 '13 at 00:40
  • @ewanm89 A 64 bit IV only allows around 2^32 messages unless you keep state between messages, which is often problematic. Works fine for encrypting a single connection, but it's quite risky for long term secrets. – CodesInChaos Feb 03 '13 at 11:58
  • A followup question - why then some of business process press on rotating keys after 90 days? – Deepesh M Feb 03 '13 at 14:52
  • @DeepeshM: it is [Cargo Cult](http://en.wikipedia.org/wiki/Cargo_cult). They do that out of some imagined but not clearly defined security benefit. In most places password renewal is enforced because it is _supported_ by the system, and they consider that whatever is supported MUST be "good" in some way or another. See [this question](http://security.stackexchange.com/questions/4704/how-does-changing-your-password-every-90-days-increase-security) for longer discussions on the subject. – Tom Leek Feb 03 '13 at 15:01
  • @DeepeshM it's mostly out of a misguided notion that if it is compromised, it is only compromised for a maximum of 90 days when the keys are all changed. Therefore limiting the breach to that period. Of course, unless the initial breach is fixed, all the attacker has to do is repeat every 90 days to compromise the new keys. If he didn't add a backdoor in the first time. – ewanm89 Feb 03 '13 at 17:16
  • @DeepeshM Often it comes from a frustrating experience such as a compromise due to a password disclosure years ago which wasn't actually found and exploited until months or years later, and which persisted for perhaps years after that. Such a problem clearly is resolved/prevented through password expiry, but expiring passwords creates its own problems too. – tylerl Feb 03 '13 at 21:08
  • Is it true that 3DES [requires a key change at less than 0.5 MB?](http://crypto.stackexchange.com/q/8427/371) – makerofthings7 May 21 '13 at 16:04
  • It is not true when said that way. 3DES does not "require" a key change that often -- it is just that _if_ you change the key that often _and_ you believe 3DES to be an ideal 64-bit cipher _then_ you benefit from a rather strong proof of security. If you use your key beyond these 2^16 blocks then your system won't be immediately broken, but you cease to be protected by the big umbrella proof of security. Since the proof is itself based on rather questionable assumption, that's no big deal. – Tom Leek Jun 26 '13 at 22:34
6

Thomas Pornin (the other bear) posted an excellent explanation of how encryption modes affect this aspect of your cipher. The short answer is that if you use the output of the previous block to set the state for the next block, then you run the risk of repeating yourself.

And in OFB mode in particular, you get into a loop when the pattern repeats itself. This could be a very tight loop, or there's a chance that the loop won't repeat at all until all possible values are explored. The average loop size is at N/2 bits. Specifically, with 2N total possible states, on the average, you'll run through 2N/2 of those states before repeating. Since your state counter is typically the same size as your block, then with a block size of 128 bits, on the average you'll cycle through 264 blocks (not bits, not bytes) before repeating.

Conversely, "counter mode" ("CTR") operation uses a simple counter as the cipher state. This means you're guaranteed to cycle through the entire possible space before repeating. So if your state is 128 bits, then you'll cycle through all 2128 states before repeating.

It's worth pointing out that a space that size is effectively infinite. That's about 5,000,000,000,000,000,000,000,000,000,000,000,000,000 bytes before you have to change keys. And that's with a 128-bit block; with a 256-bit block, you double the number of zeroes.

CBC mode (probably the most common) uses the output of a given cipher block to set the state for the next block, which means that state is heavily affected by the content of the previous block encrypted. This means that the presence and size of cycles (if any) would be partly determined by the plaintext being encrypted. This makes the math a little less exact, but you should expest no worse performance than with OFB mode.

TL;DR: Use CTR mode and don't bother switching keys.

tylerl
  • 82,665
  • 26
  • 149
  • 230
  • saying "average loop size is at N/2 bits" is a bit confusing. I'd rather say the "average loop size is 2^{N/2} using N bit blocks" – CodesInChaos Feb 03 '13 at 11:56
  • You assume that the encrypting program can keep the counter state between messages, which is often problematic. So personally I'd create a new large (128+ bit random IV) for each file and produce a per-file key by hashing it together with the master key. – CodesInChaos Feb 03 '13 at 12:02
  • related: [What's the probability of OFB mode repeating itself](http://crypto.stackexchange.com/q/3123/371) – makerofthings7 Jul 11 '13 at 20:15