19
$\begingroup$

Based on NIST SP 800-38D section 5.2.1.1, it seems that the maximum length of plaintext is 2^39-256 bits ~ 64 GB.

Screenshot of the spec

We've got 100+GB files in genomics that need to be GCM encrypted so are concerned about hitting this.

So two questions:

  • What's the source of this rather low limitation?
  • What happens (mathematically, not implementation wise) if you do cross this limit?
$\endgroup$
  • 2
    $\begingroup$ "What's the source of this rather low limitation? " - The security proofs. You loose (high) security reductions beyond the limit. But this is only from what I remember (and I can't find any good source right now -> no answer). Any reason why you can't chunk the data, i.e. encrypt everything in small (10GB) chunks? $\endgroup$ – SEJPM Jan 8 '16 at 19:58
  • 1
    $\begingroup$ The problem is with the authentication tag, not the enciphering of the data, so the data will still be secure. I assume you will be using a unique key for each file? $\endgroup$ – Richie Frame Jan 8 '16 at 21:07
  • 3
    $\begingroup$ @RichieFrame Wait up there. In GCM's use of CTR the 128-96=32 bits that aren't from the GCM IV are the part of the input block that contains the counter. If an implementation overflows the 32 bit space for the count I expect either 1. The cipher stream of the next IV will match this 64GB+ cipher stream or 2. The 64GB+ and 0 to 64GB cipher streams will match. Either way, the XOR of plaintext is revealed (unless there is no "next IV" as was hinted at). It's hard to talk mathematically and not implementation wise since the mathematics is intentionally undefined here. $\endgroup$ – Thomas M. DuBuisson Jan 8 '16 at 23:24
  • 1
    $\begingroup$ @ThomasM.DuBuisson you are right, I forgot about the fixed 32-bit block counter, even if you use 64-bit IVs. An overflow will NOT increment the IV, rather it should throw an error. Poly1305 seems a much better choice for a large data set given that fact. $\endgroup$ – Richie Frame Jan 9 '16 at 1:19
  • 1
    $\begingroup$ Use ChaCha20-Poly1305 instead. libsodium can do this in a mode that uses a 64-bit internal counter and is thus secure for much larger messages (I am not sure of the actual limit). If you must use AES, use a different authentication mechanism, such as HMAC-SHA2, Blake2, Poly1305-AES, or SHA3. $\endgroup$ – Demi Jan 27 '16 at 7:51
9
$\begingroup$

The source of the limitation lies in the fact that GCM has a fixed block counter using a 32-bit integer. Since the block size is $2^7$ bits, the total amount that can be encrypted with the CTR component is $2^{39}$ bits.

The first limit reducing this by 128-bits is the fact that the block counter starts at 1 and not 0, at least with a 96-bit nonce. Nonce sizes other than 96-bits are know to have reduced security. The second limit reducing this by 128-bits is because the CTR component is also used to encrypt the final GHASH prior to tag output.

Implementation wise, you should not be allowed to cross this limit. In theory, the security breaks down. There are different security limits for the amount of data encrypted, and for the amount of tags generated. With a long message, an $n$-bit tag provides $n-k$ bits of authentication security for a $2^k$ block message, in your case this brings it down to around $2^{63}$ with a file between 100 and 128 GB when used with a 96-bit tag, much lower than the $2^{128}$ one may expect. The worst case scenario is recovery of the hash subkey $H$, allowing forgery of tags with the same key.

Encrypting a full size 128-bit tag with a separate key in ECB mode should eliminate that problem, as the bits will no longer be malleable. That can be done as a wrapper around a GCM implementation with minimal modification and almost 0 overhead. The implementation would need to be modified to use a larger block counter, and the nonces would need to be shorter. You would no longer be able to call it GCM, but would be able to make use of all the features and code that make GCM implementations fast and timing attack resistant. A 32-bit nonce and a 40-bit block counter (with no additional GHASH) would allow almost 16TB per nonce, without the restriction of changing keys for every message if you encrypt the tag with a second key. If you even consider something like this, a professional consult on both the modifications and the code to do it would be highly recommended, new security proofs would need to be developed.

Other solutions to the problem including not using GCM, but a different mode like Poly1305-AES. OCB mode also has a suggested limit of 64GB per key, CWC mode has the same limit as GCM.

$\endgroup$
  • $\begingroup$ @DeepSpace101 I am aware you may have significant limitations on what you can do. If you are required to use GCM on a 100+GB file without chunking, you will not be able to meet that requirement $\endgroup$ – Richie Frame Jan 9 '16 at 2:18
  • $\begingroup$ Actually, I think the bounds are lower than you presented. If I understand the paper "Breaking and Repairing GCM Security Proofs" (2012) by Iwata, Ohashi and Minematsu correctly, the the security against forgery is at most $n-2k$ (see theorem 2) and if you mess with the nonce sizes things seem to get even weirder... $\endgroup$ – SEJPM Jan 9 '16 at 11:23
  • $\begingroup$ @SEJPM if you use a non 96-bit nonce, GCM requires an iteration of GHASH prior to incrementation, which creates counter collisions. In the case of removing that GHASH, the attacker advantage is the same as with the 96-bit nonce, which is approx $0.5(2^{33})^2/2^{n}$ + $2^{33}/2^{96}$ = $2^{-63}$ + $2^{-63}$ = $2^{-62}$ for a max 128GB data set and 96-bit tag, and $2^{-63}$ with a 128-bit tag, assuming unique keys per message... I think that is what I get from that paper $\endgroup$ – Richie Frame Jan 10 '16 at 4:29
3
$\begingroup$

I do not agree with the other answers and comments given here. The use of the 96-bit nonce gives the best bounds, but it is certainly not the only way to use GCM. Also, the degradation is gradual. It is not the case that anything else is insecure. Having said this, it is completely insecure to encrypt beyond $2^{32}$ blocks using a 96-bit counter since the same counter will repeat, and this is a complete disaster.

The easiest solution to this is to use an 88-bit nonce. You can then encrypt up to $2^{47}$ bits which is enough.

$\endgroup$
  • 5
    $\begingroup$ To use this better solution, you will probably need to deviate from the standard. If you just use an 88 bit nonce with a random implementation, it will hash that nonce into a 96 bit nonce and still use a 32-bit counter, which does not solve the problem. $\endgroup$ – K.G. Jan 10 '16 at 9:15
  • $\begingroup$ Also the degradation is gradual with respect to input data length, as well as the amount of messages encrypted and decrypted with the same key. The data length the op is looking for drops the security bound significantly, even with only a single message per key $\endgroup$ – Richie Frame Jan 10 '16 at 9:17
  • $\begingroup$ an 88-bit nonce with standard GCM still only allows $2^{32}-2$ blocks, but reduces privacy from $2^{65}$ for a single full size message, to $2^{64}$ after only 256 messages. That is the PRIVACY bound, not the authentication bound, and that is bad. 96-bit tags take 1.77 billion messages for the same reduction, and that message count reduces the non-96-bit nonce version to less than $2^{45.6}$ $\endgroup$ – Richie Frame Jan 12 '16 at 7:31
0
$\begingroup$

If there are machines that really are worth over 200 million dollars involved, you presumably have a secure physical environment. That means there is another option: Do all cryptography OUTSIDE of the expensive, inflexible machines, and transfer the data to/from the machines in plaintext, using physically secure networks, air-gapped from the outside world. Transferring data over a network in plaintext is not a vulnerability if the attacker cannot gain access to the network to tamper with it (because it is in a locked room witb an armed guard).

$\endgroup$
  • $\begingroup$ The machines are 'just' 200,000 or 200k ... typo on my part by also putting in the 'k'. I can't edit that old comment now but sorry for the excitement :) $\endgroup$ – DeepSpace101 Feb 19 '16 at 4:58

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.