Can someone help me understanding the CCM authenticity bound by Phillip Rogaway? i-e Success probability < $q_{\text{dec}}/2^\tau + \sigma/2^b$.

$\tau$ is tag length, where as $b$ is block length. $q_{\text{dec}}$ is the number of forgery attempts, I can not get whats "$\sigma$" is?

Also If i am not looking for forgery attempts but looking for the channel errors that cause invalid message to go through CBC MAC. Then for that case $q_{\text{dec}}=1$. Am I right? And I am attempting to send 500MB of data? So what will be the number of un-authenticated messages that go through CBC MAC because of channel errors.


1 Answer 1


If you mean this paper by Rogaway, "Evaluation of Some Blockcipher Modes of Operation" (PDF, relevant page is 120) then it very clearly documents everything.

  • $q_{\text{dec}}$ is the total amount of decryption queries the adversary asks. If you only accept one decryption query before using different keys, this can be approximated by $1$.
  • $\sigma$ is the total number of block cipher calls the mode would make on the adversary's sequence of queries. So if all adversarial queries (encryption and decryption ones) together require 4 block cipher calls to process, then $\sigma=4$. For 500 MByte of Data (in the single query) this would imply $\sigma\approx 2^{26}$

Also note that the bound stated in the paper (note the additional square on the $\sigma$) is $$\leq \frac{q_{\text{dec}}}{2^\tau}+\frac{\sigma^2}{2^b}$$

Plugging in the above values yields an advantage of $\leq 1/2^\tau+2^{52}/2^b$ which bounds the success probability of any adversary. Now random noise usually isn't exactly a smart adversary so the probability of a (successful) forgery from random noise is even much lower.

So let's clarify on what a "block cipher call" actually is. Modes of operation like CCM are built on block-ciphers which get modelled as functions $C=E_K(P)$ for some plaintext $P$, some key $K$ and the corresponding ciphertext $C$ where $P$ and $C$ are the same, fixed size. One computation of $C$ from $K,P$ or of $P$ from $K,C$ is called one block cipher call (because in the implementation you call the block cipher function for this). Now for CCM mode, which I will skip describing here, you end up with about 2 block cipher calls per data block (one for privacy, one for authenticity), yielding the aforementioned $2^{26}\approx 2\cdot 500\cdot 10^6/16$.

  • $\begingroup$ ThankYou SEJPM, It helps a lot. I am newbie to this world. I wasn't able to get the block cipher calls. Still I a have little bit confusion about single query and block cipher calls (if you can elaborate I will be thankful or refer me to any documentation). From your example it means 500MB = $(500*8*10^6)/128$ (AES block size)= $2^{25}$. So $\sigma$ is basically for a given amount of data how many blocks will be made (Depending upon block size). Thanks in advance $\endgroup$ Aug 3, 2018 at 22:05
  • $\begingroup$ @faheemawan I have added a paragraph to (hopefully) clarify what a block cipher call is. $\endgroup$
    – SEJPM
    Aug 4, 2018 at 8:56
  • $\begingroup$ ThankYou very much It was very helpful. I would just like to ask one last question. Hope you won't mind. If I am using Bluetooth Low energy(4.0) in which the transmitted frame size is 336 bytes. So for a single frame the bound will be $\leq \frac{1}{2^{32}} + (((336)/(16 * 2))^2)/2^{128}$, whereas if I consider an entire data of 500MB, then it will be like the previous case. Am i Right? Also if I only consider channel errors, so it will be quite less than that. Thanks in advance. $\endgroup$ Aug 4, 2018 at 11:34
  • $\begingroup$ @faheemawan yes, if you make the reject / force-key-rotation decision on a per-frame basis, then the bound you gave is indeed the correct one (but you may want to note that $\frac{1}{2^{32}}\gg 2^{52}/2^{128}\gg 1764/2^{128}$ and as such the $\frac{1}{2^{32}}$ will be "your main worry"). $\endgroup$
    – SEJPM
    Aug 4, 2018 at 11:42
  • $\begingroup$ Thanks, as TLS do it on per frame base. If I am not doing it on per frame base so $\frac{1}{2^{32}}$ will be increased further, then instead of one we have the number of attempts. Thanks SEJPM, discussion helps me absorb easily. $\endgroup$ Aug 4, 2018 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.