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 negligibly 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?
$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). $\endgroup$