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

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!)

• Also, "block level" encryption is often 16KiB because that is the size of the FLASH pages in most ICs. Nov 10 '20 at 17:12
• I know no standard solution. I also do not know that CKM_AES_GCM supports Associated Data as the question suggests. Is the length (or even the number of blocks) known when the encryption starts?
– fgrieu
Nov 10 '20 at 18:03
• @fgrieu At the very least, AWS CloudHSM's CKM_AES_GCM does: github.com/aws-samples/aws-cloudhsm-pkcs11-examples/blob/master/…. Edit: seems to be standard, CK_GCM_PARAMS in pkcs11t.h. Nov 14 '20 at 13:11

I have a solution that may satisfy you

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

Assume that you divide the file into $$n$$ parts each around 16KB ( need adjustments). Encrypt each of them 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
#Third parameter is the Associated Data
(C_i, tag_i) = AES-GCM(key, i:n || tag_i-1 || P_i, borderFlag)
else
(C_i, tag_i) = AES-GCM(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.

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 from the replay attack.
• @fgrieu thanks. Now i've checked, at least Thales not mentions. Moved the associated data into an appendix to plaintext. Nov 10 '20 at 17:59
• I like the idea of the borderFlag - I hadn't thought of that - nice. Nov 14 '20 at 13:15