2
$\begingroup$

When encrypting many short plaintexts with a single key, lets say about 2^64 total plaintexts at under 64 bytes each: (edit note - was 2^70 in the original question)

  • Is there a way to use AES-GCM, as specified by NIST Special Publication 800-38D, safely in this scenario?
  • Is is safe to use when there are no IV collisions, e.g when the IV is a counter?
  • Is it possible to use a larger IV while still adhering to the NIST specs, possibly large enough to collisions even with random IVs?

Does this change if the plaintexts are high-entropy, for example when wrapping keys?

Improve this question
$\endgroup$
3
  • $\begingroup$ The benefit I see is that vetted AES-GCM implementations are easy to find $\endgroup$
    – orip
    May 3, 2018 at 17:25
  • 1
    $\begingroup$ This does not sound safe. You can't get $2^{70}$ plaintexts on a sequential computer in under a millennium even if you churn them out at the nearly unbelievable speed of one per nanosecond, so you will be copying the key to many different computers to work in parallel. Now you have operational security issues to manage that one key. What are you really trying to do? $\endgroup$
    – Squeamish Ossifrage
    May 7, 2018 at 20:25
  • $\begingroup$ @SqueamishOssifrage it's possible under the assumption that these many computers are secure but are distributing the ciphertexts to untrusted channels. $\endgroup$
    – orip
    May 8, 2018 at 8:44

2 Answers 2

Reset to default
4
$\begingroup$

No. You're well above the birthday bound for a 128-bit block cipher. Using AES under a single key for more than about $2^{64}$ blocks of data is asking for trouble.

The largest nonce you can use with standard AES-GCM is 96 bits,* which is safe sequentially, but you're probably not doing this sequentially unless you plan to wait a millennium for your sequential computer to count to $2^{70}$. You could carve up the input space and assign disjoint subsets to an array of computers in parallel, but now you have much larger operational security and scaling issues that you almost certainly need to address first, and most likely the way you address those will be by using more than one key anyway.

Your best bet here is to give more details about what you're actually trying to accomplish, rather than ask how to use AES-GCM far beyond its advertised limits.

* Technically you can use >96-bit nonces with AES-GCM, but that's foolish because it is effectively the same as using random 96-bit nonces, and so it is worse than using sequential 96-bit nonces.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Cool! Would a birthday attack be relevant if different IVs are used? Would a cipher block collision leak data if the plaintext is high entropy and undistinguishable (e.g keys)? Regarding what I'm trying to accomplish, then (a) I'm trying to wrap many keys with a single master key, and (b) I'm trying learn about the limits of AES-GCM - not necessarily to use it for the task, but to understand. $\endgroup$
    – orip
    May 9, 2018 at 11:45
0
$\begingroup$

Nonce-based key derivation, introduced here by Shay Gueron and Yehuda Lindell, solves this issue including passing beyond birthday bounds.

AES-GCM-SIV (S. Gueron, A. Langley, Y. Lindell) is an example of this approach, as far as I can tell, but AWS KMS achieves the same goal - with much lower performance - using standard NIST-approved building blocks by deriving an effective key for each encryption using the source key and 128 bits of random IV fed into a counter-mode KBKDF (SP 800-108) with HMAC-SHA256. This effective key is used with AES-256-GCM with another random 96 bits as nonce. Source - this talk (slides), by Matthew Campagna and Shay Gueron.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ AES-GCM-SIV derives a fresh key for each message, and is not built out of AES-GCM. (Yes, the name is confusing.) Maybe that's acceptable for your unstated purposes, but it does not address the question you asked about AES-GCM. $\endgroup$
    – Squeamish Ossifrage
    Feb 28, 2019 at 16:16
  • $\begingroup$ Fair enough, but AWS's approach does use AES-GCM for this purpose $\endgroup$
    – orip
    Feb 28, 2019 at 20:56
  • 1
    $\begingroup$ If you can change the cryptosystem you're using from AES-GCM to AES-GCM-with-subkey-derivation (as AWS KMS does, according to the talk you cited; for each key AWS KMS limits the number of ciphertexts to $2^{50}$), then yes, that's fine; it just strikes me as a somewhat different question from the one you asked. $\endgroup$
    – Squeamish Ossifrage
    Feb 28, 2019 at 21:12

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.