3
$\begingroup$

Let's assume we're in some scenario requiring transfer of large amounts of data. This means we can only use AES-GCM chunk-for-chunk as its maximal size is restricted to a few GiBs. This means we have to define a new nonce (a counter?) for each new chunk.

However each chunk needs to have its authentication tag appended to verify decryption. So I had the idea to use this available ressource for the next decryption to completely avoid those counters.
A bonus of this is that re-ordering attacks are completely impossible as the nonce is authenticated as AD for GCM and hence the previous tag will be used for the next tag, "chaining" the chunks together.

Note: One can also replace the word "chunk" by message and apply the same principle to something like TLS. Note further: The "0"th authentication tag is a random value prepended to the chunk.

So my question:
Is it actually safe to use the authentication tag of the last message as the nonce for the next one in AES-GCM mode?

For me it looks like it should be safe as the first chunk is standard GCM and every following one is indirectly based on the exact same nonce.

If needed: The first nonce is assumed to be of size 16 bytes and every tag is also assumed to be of size 16 bytes.

What was the inspiration for this question?
An AE scheme (AERO) that actually verifies based on nonces and state. In this case we don't even need state (except for the bytes we just had available i.e. the latest tag). And this would also reduce the possibility of errors based on wrong nonce states (incremented the counter in the wrong way).

$\endgroup$
  • $\begingroup$ @otus, if you need to assume any tag length 128 bit should be assumed (as it's the standard case I guess) and I've added some more info on why not to use the counter: TL;DR: It's mostly a theoretically interesting question and the non-use of a counter may also strongen the link between the message parts. (And it feels better in terms of combination) $\endgroup$ – SEJPM Aug 28 '15 at 18:37
2
$\begingroup$

The authentication tag in GCM is generated by XORing a block cipher output with the Galois field hash (and truncating it for shorter lengths). It is thus assumed to look PRF. So it is effectively just a random nonce that should not collide until a birthday bound of $2^{t/2}$.

With a tag length of 96 or more bits, it should be secure. Shorter random IV lengths are prohibited in SP 800-38D. However, that standard also limits you to using the key no more than $2^{32}$ times, when using a random IV.

(Even though the nonce is "controllable" by an attacker with a chosen plaintext attack, that does not allow generating a collision except randomly. Otherwise it would lead to a forgery attack.)

I would still prefer a counter.

For me it looks like it should be safe as the first chunk is standard GCM and every following one is indirectly based on the exact same nonce.

Note that this dependence means two things:

  1. You need the tag from the previous chunk to decrypt the next one, so parallelization is slightly more difficult. (E.g. both processors would need to read the same memory location.)
  2. If some chunk does not authenticate, you cannot trust that it's the only one that has changed. An attacker who changed chunk $i$ could also remove any number of chunks after it without that fact being visible. (With counters you can detect a localized change and still authenticate the rest as being in the correct place.)
$\endgroup$
  • $\begingroup$ Yeah, I think I may indeed rather use a counter (maybe indexing the chunks) to get that full $2^{96}$ blocks... $\endgroup$ – SEJPM Aug 28 '15 at 21:08
  • $\begingroup$ ... After some thought: This would still allow me to encrypt $\approx 2^{70}$ bits ($=2^{67}$ bytes) which is about 128 Exabytes (more than most file system accept as single file) of data. As I'm using per-file keys I doubt those files will reach 128 Exabytes in size while AES-GCM is still in use and CAESAR hasn't finished (~2018) and improved the situation so I'm fine with it :) $\endgroup$ – SEJPM Aug 29 '15 at 16:28
  • $\begingroup$ @SEJPM, seems reasonable. I expanded the answer with a couple of points, but they probably don't matter in practice. $\endgroup$ – otus Aug 29 '15 at 17:49

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.