How to securely encrypt/decrypt data with a maximum chunk size?

Question

I am aware of the different modes so that a "raw" block cipher such as AES (ECB) can be used to encrypt more than a single block of data (CBC, OFB, CTR, etc) and modes such as AES-GCM which provide a full AEAD implementation.

When looking at the known limitations for Amazon AWS CloudHSM, there is a maximum data size restriction for AES-GCM (https://docs.aws.amazon.com/cloudhsm/latest/userguide/ki-pkcs11-sdk.html#ki-pkcs11-8):

Issue: Buffers for the C_Encrypt and C_Decrypt API operations cannot exceed 16 KB when using the CKM_AES_GCM mechanism

You cannot use the CKM_AES_GCM mechanism to encrypt data larger than 16 KB

You can use an alternative mechanism such as CKM_AES_CBC or you can divide your data into pieces and encrypt each piece individually. You must manage the division of your data and subsequent encryption. AWS CloudHSM does not perform multipart AES-GCM encryption for you. Note that FIPS requires that the initialization vector (IV) for AES-GCM be generated on the HSM. Therefore, the IV for each piece of your AES-GCM encrypted data will be different.

This question is about how to securely "manage the division of your data and subsequent encryption".

Are there any well-known, documented standards for working with such "big blocks", creating an AEAD mode from a "unit" of AES-GCM which can only encrypt/decrypt 16KB at a time? It would obviously need to protect against truncation of data (if ciphertext was N "big blocks" and only the first M blocks given to decrypt operation, this should fail) and substitution of blocks from a different ciphertext encrypted with the same key should fail too. And are there other potential concerns?

It "feels like" the same class of problem going from ECB → CBC/OFB, but obviously, we want authenticated encryption.

Tweakable block ciphers are used for disk encryption, but the substitution of blocks (same block number/rollback) isn't really protected against there.

Clearly appending the last 128 bits of the ciphertext of the first "big block" to the associated data going into the encryption of the second "big block" would prevent substitution of blocks from another ciphertext, but how to prevent truncation attacks? Would it be sufficient to append the overall data length to the associated data for the first "big block"?

I'd ideally rather not switch to CBC + HMAC (especially as the CloudHSM hash of > 16KB data ends up being done locally!)

But: is this already a solved problem? (Ideally with an IND-CCA2 proof!)

Answer 1

I have a solution that may satisfy you

Splitting the file into parts (chunk) and chaining them is a solution for you. To prevent the truncation we will use the associated data, which is the same for the first and last parts.

Assume that you divide the file into $n$ parts where each is around 16KB ( need adjustments). Encrypt each of pars with $\operatorname{AES-GCM}$ with the following additions. Prefix each part before encryption as follows;

tag_0 = ''
borderFlag = random
for i from 1 to n
  if i == 1 or i == n
     #Fourth parameter is the Associated Data
     (C_i, tag_i) = AES-GCM(IVx, key, i:n || tag_i-1 || P_i, borderFlag)
  else
     (C_i, tag_i) = AES-GCM(IVx, key, i:n || tag_i-1 || P_i)

• prefix each part with the part number as i:n

• prefix each part except the first one with the authentication tag of the previous part.

• What is $\text{IVx}$?

  • It has a total size of 12-byte so that there is no additional GHASH calculation.
  • It must be either random per encryption, or,
  • Use counter-based approach, give the next $\text{IVx}$ as the +1 of the last previous counter.
  • This is important so that we don't have the forbidden attack on the CTR mode that is using $(key,IV)$-pair again.

With these, you have now a chain that can be controlled after decryption. You can detect, additions, deletions, and in the final part the truncation. The order is under your control, you can send even without the order. However, you need to check the prefix.

You can also

• add the part size, and
• add the time of encryption, too if you fear the replay attack. This is general advice and requires system knowledge to be specified.