Are tags longer than 128 bit possible for AES-256-CCM and AES-256-GCM?

Question

I have an existing application that uses AES-256-CBC for encrypting data blocks, and HMAC-SHA-256 on the plaintext for eliminating duplicate data blocks.

For performance reasons, I would like to move to AES-256-CCM and using the resulting authentication tag instead of the SHA-256 .

However, this algorithm is designed to generate a 128 bit tag. This is more prone to hash collisions than HMAC-SHA-256. 128 bits doesn't seem to be sufficiently future proof to ensure collision safety for a system potentially storing enormous numbers of blocks.

Is there a way to extend the tags of AES-256-CCM or AES-256-GCM to have 256 bits strength?

Edit: What I'm try to accomplish is to encrypt a set of objects which are eventually stored in Amazon S3 in a content addressed way, that is, the key of the object should be a hash of the plaintext . People with access to my Amazon S3 bucket should not be able to be able to decrypt the data, nor should the scheme allow checking whether a specific known plaintext exists or not in the bucket. That is why the current scheme is HMAC-SHA256 on the plaintext to choose a key for the object, and then encrypting the object using AES-256-CBC with a unique and unpredictable IV.

AES-256-CBC and HMAC-SHA256 are rather slow, and thus I had the idea to use some form of fast authenticated encryption.

Answer 1

No, there is no black-box type way of increasing the security strength of the tags of CCM and GCM. Because in this case you would apply a deterministic function which couldn't bring you any increases in security as a collision on the input would still lead to a collision on the output.

For CCM there is also no non-black box type of way, at least if you want to stick to AES. This is because CCM uses CMAC internally which is close to CBC-MAC which is CBC adapted for authentication. The authentication tag for CMAC is the result of an AES encryption and AES is solely specified for 128-bit blocks (which is the size of the AES in- and output).

GCM is similar in that respect to CCM, in that the output of the polynomial hash function is actually XOR encrypted with the output of an AES block. However if you pick a longer polynomial for GCM (which will instantly break all implementations you may have) and if you maybe make some educated changes to how often the polynomial gets evaluated, you might get a stronger tag as the result. However this would most-likely be a GCM look-a-like, but would needs its own (difficult) security analysis and new implementations.

On a final note, the tags of CCM, GCM and HMAC are MACs. MACs are not neccesarily designed to be good hashes (for a fixed key), because the threat model is different for them. They are designed so that you can't find a tag for a message for which you haven't seen a tag before. They are absolutely allowed to output two different tags for the same message or the same tag for two different messages (because an adversary could maybe have predicted a collision but not for which message pair).

Answer 2

For huge amounts of data it would be better to re-key periodically. You could do something like hash your initial secret with SHA256 every 1GiB of data and re-key AES with new secrets.

If I were designing this from scratch I'd put a large (e.g. 512-bit) random nonce at the start of the large message/stream. Then I'd use part of this nonce to seed a CSPRNG for GCM nonces and then use the rest as a salt when repeatedly hashing AES keys to generate new session keys as you go... or something along those lines.

I wouldn't trust AES-GCM with the same key for more than a few gigs of data personally... and less if you're using smaller auth tags or nonces than the 96-bit/128-bit default. There is a table somewhere of recommended max message sizes for different tag sizes, and nonce size will impact how much data you can safely process with one key.