Birthday attack on AES-CCM with 32-bit Authentication Tag

Question

I would like to use AES-CCM with a very small Authentication Tag length of 32 bits. Thus, I have a question about the vulnerability to birthday attacks.

How vulnerable is CCM to birthday attacks?
Jonsson explains that the adversary does not gain more than neg­ligibly from making multiple forgery attempts if the tag length is considerably larger than $\frac{k_b}{2}$.

Theorem: $\mathcal{Adv} \leq \frac{q_{dec}}{2^{\tau}} + \frac{\sigma^2}{2^n}$, where $q_{dec}$ bounds the total number of decryption queries that the adversary asks and $\sigma$ bounds the total number of blockcipher calls that the mode would make on the adversary’s sequence of queries, both to encrypt all the encryption queries and to decrypt all the decryption ones [explanation from Rogaway].

Since AES is used, $k_b$ should be 128 and the theorem wouldn't hold on a 32-bit authentication tag size. Does that mean that a birthday attack would work after $2^{16}$ attempts? Does this apply to blocks or messages (since blocks are mentioned here)? It would make quite a difference if it's the amount of blocks the function is called or the amount of messages:
$2^{16} \times 128\text{-bit block} = 1\text{MB}$
Thus, there'd be a collision after 1MB of data?

Or do I misunderstand Jonsson's theorem? On the other side, Rogaway applies Jonsson's theorem on 32-bit tags and explains that if a forgery that can perform 10,000 attempts until the key will be retired and the total amount of plaintext or ciphertext that the adversary attempts to encrypt or decrypt corresponds to $2^{50}$ blocks, then the adversary’s probability of forging will be at most $\frac{10000}{2^{32}} + 2^{-28} \approx \frac{10000}{2^{32}} < 0.000003$
Again, he works with $2^{50}$ blocks. Does that mean that the birthday bound describes the amount of messages instead of the blocks?

In short: How many messages can I securely send in CCM with a 32-bit authentication tag and after how many INVALIDs should the key be retired? Is Jonsson's Theorem applicable on 32-bit tags?

Answer 1

Please note: This answer is entirely based on the theorem the OP stated.

Notation:

• $\tau$: length of the tag, in bits, this is 32 in your case
• $\sigma$: the number of encrypted / decrypted blocks
• $n$: the block size of the cipher, in bits, this is 128 for AES
• $q_{dec}$: the allowed number of decryption queries
• $\text{Adv}$: the probability that an attacker wins "the game" and thus breaks the associated security definition

Formula: $$\text{Adv}<\frac{q_{dec}}{2^\tau}+\frac{\sigma^2}{2^n}$$

---

First, for $q_{dec}$: You should really set this value as low as you can tolerate it to be without giving (too many) false positives, ideally this would be $1$.

The next step is to chose the upper probability you're willing to tolerate for an attacker breaking your scheme. Ideally, you'd want to set this as low as possible, for example FIPS 140-2 specifies that no random attempt should have a chance better than $\frac{1}{10^6}$ of succeeding (at wrongly authenticating the user) and it also specifies that an attacker may not have a chance greater than $\frac{1}{10^5}$ of succeeding within one minute when being alone with a cryptographic module. Also note that the chance of an attacker succeeding at least once after $k$ tries with probability $\text{Adv}$ is $1-(1-\text{Adv})^k$, so you may want to do the math and keep the value reasonably low for a given time-period and try-count an adversary has.

Now, after you figured out how much advantage you're willing to give to the attacker and how many decryption queries you're willing to accept, you can finally go ahead and use the above equation to find the maximal number of block cipher calls allowed for the scheme. This should be $$\sigma<2^{48}\cdot\sqrt{2^{32}\cdot\text{Adv} - q_{dec}}$$