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

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?

• They use binary ($\log:=\log_2$) instead of decimal logarithm. And of course they approximate results.
– SEJPM
Sep 23 '16 at 22:12
• Thank you very much, I've already deleted this part of the question since it was a very stupid faulty reasoning. Thanks for your hint! Sep 23 '16 at 22:15
• So, the theorem states the probability that an adversary wins the game and thus breaks the security guarantees of CCM for the given set of $(q_{dec},\sigma^2,\tau,n)$ parameters. So go ahead and plug-in the values you're going to tolerate and use $n=128$ and $\tau=32$ if I'm understanding the theorem right. For example, if you always kill and re-key a connection after a single invalid decryption tag (which is what TLS would do), then the probability of an attacker winning the game is bound to be $<\frac{1}{2^{32}}+\frac{(q_{enc}+1)^2}{2^{128}}$
– SEJPM
Sep 25 '16 at 20:00
• Yes that's true but what confuses me is Jonsson's statement in the Authenticity section of chapter 3.2: "we want to show that the adversary does not gain more than neg­ligibly from making multiple forgery attempts if the tag length is considerably larger than $k_b/2$". But he actually showed that an adversary cannot gain more than negligibly even when the tag length is smaller than the block size, since here, $k_b=128$ and tag size $\tau=32$. Sep 25 '16 at 20:55
• If TLS encounters a bad MAC (and thus very likely an attack) it immediately triggers a fatal alert and terminates the connection. So if you want to know about how $Protocol behaves, look at the specification of $Protocol and see what happens in the case of a bad MAC. TLS forces attackers to get the MAC right in the first run, thus $q_{dec}=1$. If the decryption fails, a fatal bad_record_mac alert MUST be generated. from RFC 5246 (TLS v1.2).
– SEJPM
Sep 25 '16 at 21:25

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}}$$

• Assuming CCM should be used in a communication protocol and I have calculated the maximal number of block cipher calls allowed for the scheme based on this formula. Do I need to divide the result by 2 since both sender and receiver are making block cipher calls to limit the total maximal number of block cipher calls or are their computations independent from each other? The NIST standard limits block cipher calls to $2^{61}$. Does that also mean that a protocol should allow at most $2^{60}$ blocks since sender and receiver are both processing the blocks? Oct 25 '16 at 22:31