Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'd like to know how the security of the integrity protection compares between:
Assuming that no side-channel data is leaked and all algorithms are used securely.
For any $k$-bit MAC, an attacker blindly guessing a tag has a one-in-$2^k$ chance of successfully forging a message. Thus, the expected number of attempts needed to forge a message by brute force is $2^{256}$ for a 32-byte tag, $2^{128}$ for a 16-byte tag, and $2^{64}$ for an 8-byte tag.
In practice, attempting $2^{128}$ forgeries is far beyond the reach of any plausible attacker, whereas $2^{64}$ attempts might just barely be feasible in some scenarios.
As far as I know, the best non-brute-force attack on HMAC-SHA-256 is the generic birthday attack on iterated MACs described by Preneel and Oorschot (1999), which allows an attacker to forge a message after finding an internal state collision in the MAC computation. For SHA-256, this would require obtaining MACs for about $2^{128}$ messages, and can thus be safely ignored.
In fact, Bellare (2006) has proven lower bounds on the security of HMAC that are close to the upper bounds given by Preneel and Oorschot, assuming that the hash function used satisfies certain security assumptions (in particular, that its compression function is a PRF, or at least a PP-MAC). Thus, assuming no disastrous new attacks on SHA-256 arise, HMAC-SHA-256 with at least a 16-byte tag should be secure against any feasible attacker.
For GCM / GHASH, there do exist attacks better than brute force. In particular, Ferguson (2005) shows that an attacker can forge an $n$-block message with a $k$-bit tag with probability $n/2^k$. GCM limits the maximum message length to $2^{32}-1$ blocks, so, for a maximum-length message, the forgery probability is about $2^{32}/2^{128} = 1/2^{96}$ for a 16-byte tag, and about $1/2^{32}$ for an 8-byte tag.
While the former is still generally acceptable, the latter may not be, especially as GCM has an unfortunate property, also described by Ferguson, whereby each confirmed successful forgery reveals information about the authentication key, and thus makes successive forgeries much easier. Thus, echoing Ferguson's recommendation, I'd advise against using GCM with a tag length shorter than 16 bytes.
As for CCM, I'm also not aware of any attacks better than brute force. The Preneel and Oorschot attack is not directly applicable to CCM (even though it does apply to CBC-MAC), because the tag is encrypted using CTR mode with a unique nonce, and thus an attacker cannot directly detect internal collisions in the CBC-MAC state. Even if it did apply, the CCM specification limits the total amount of block cipher evaluations made with a single key to at most $2^{61}$, which is less than the expected number of queries needed to find one collision (although not very much less; a more conservative limit would be, say, $2^{40}$ cipher evaluations per key).
Jonsson (2002) has proven a lower bound on the security of CCM mode that is similar to the Preneel and Oorschot bound, in that the success probability of an attacker making $q$ forgery attempts comprising a total of $m$ blocks, and having access of $n$ blocks of valid messages, has a success probability less than $q/2^k + (m+n)^2/2^b$, where $k$ is the bitlength of the tag, and $b$ is the blocksize of the underlying cipher ($b = 128$ for AES).
This bound is rather conservative, and indeed, Jonsson himself has conjectured, but not proven, a bound on the forgery probability that is linear rather than quadratic in the number of encrypted blocks. In fact, Fouque et al. (2008) have managed to prove this, but only for a variant of CCM mode using independent encryption and authentication keys. As far as I know, for regular CCM, this question is still open; of course, as long as the number of blocks processed with a single key remains well below $2^{64}$, it is purely of academic interest.
