# A question about "attacks on MAC key space"

At page 336 in "Handbook of Applied Cryptography - Menezes", I see the sentence

For $$n$$-bit MAC with $$t$$-bit key space this requires $$2^t$$ MAC operations, after which one expects $$1+2^{(t-n)}$$ candidate keys remain".

I do not understand why is $$1+2^{(t-n)}$$. According to me, it must be $$2^{(t-n)}-1$$.

For example, in exhaustive-key search, we luckily discovered one key, so there must remain $$2^{(t-n)} - 1$$ candidate keys.

I read carefully this chapter but I still cannot understand this idea. I do not know if I misunderstood the authors. Could you explain for me.

I read carefully this chapter but I still cannot understand this idea.

Well, we assume that there is 1 correct key and $$2^t - 1$$ incorrect keys. When we test a key, the correct key will verify. We model that MAC as a random function, that is, that an incorrect key will generate an essentially random MAC, and so would verify will probability $$2^{-n}$$ (as that is the probability that a random $$n$$ bit value being a prespecified value).

Adding these two together to get the expected mean, we get:

$$1 \cdot 1 + (2^t - 1) \cdot 2^{-n} = 1 + 2^{t-n} - 2^{-n} \approx 1 + 2^{t-n}$$

If $$t \ggg n$$, then this is essentially $$2^{t-n}$$ (and so the +1 can be ignored). On the other hand, if (say) $$t=n$$, this indicates that we can expect (on average) 2 results, the correct one and a 'false hit' (and we might not get a false hit, or we might get several; the 'one' is just an average). And, if $$t \lll n$$, then this expected mean is almost exactly one, that is, we find the correct key and with low probability, we might get a false hit.

According to me, it must be $$2^{(t−n)}−1$$

That doesn't work; if we consider the $$t \lll n$$ case, that would suggest that we have a probability of getting a negative number of keys that work - obviously an absurd result. .

• Thank you Poncho. In this question I do not care about "t < n". The reason why I think 2^(t-n) - 1 is in my example. But now I can guess the author's intention. Thanks again Sep 23 at 18:58

Firstly I thank to Poncho for your kind reply. But now I have a guess like this (maybe it is not author's intention):

1. At first I think a number of keys corresponding to a number of outputs is the same. For example, if |K| = 2^3 = 8 and |Output| = 2^2 = 4 then each output will receive 2 keys. I think it is not right (of course it is not wrong). Actually, one output can receive 3 keys and another only receives 1 key. It is ok.
2. In this author's paragraph, the CONTEXT may be that another attacker precomputes all 2^t MAC operations (of course using all 2^t keys). So, each MAC-result has (1/2^t + 1/2^n) probability of success. We have 2^t MAC-results, then multiply 2^t by (1/2^t + 1/2^n) and have 1 + 2^(t - n) EXPECTED candidate-key.
3. Now, applying formular with an example t = 3 and n = 2. So, after computing all 2^3 MAC operations, attacker surely has 1 secret-key (also call target-key) and 2 candidate-key. So in this case, given x and y, we have MAC(secret-key, x) = MAC(candidate-key-1, x) = MAC(candidate-key-2, x) = y. It means that output y corresponds to 3 keys.

That is my guess about author's intention. If anyone has different opinions, please share it to clarify the problem.

• ponchos' answer is the correct one. When we talk about non-specific mac we need to model them as random function to analyze. This is the way in cryptography. Random function, random permutation, pseudo-random permutation (PRF), pseudo-random function (PRP), etc.. Sep 23 at 10:16
• Yes, I know this. But I feel his explanation is not what I want. This is my opinion. If there is no other opinions, maybe I will follow my newest understanding and write it into my book Sep 23 at 12:22
• 1. argument is not correct. It is probabilstic. You can't say each have 2 key, you can save each has 2 keys with probability $p$. Sep 23 at 14:13
• 2. precompute of what? do you include all possible hashed message space? Sep 23 at 14:16
• No kelalaka: 1) I means my initial assumption is not good, although it is not wrong. Each output corresponds to 2 keys, so we have 4 outputs corresponding to 8 keys. 2) precompute all 2^t MAC (using 2^t possible keys) and hope to have expected candidate keys (Value t being large or small is not important in this context). Sep 23 at 14:42