2
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

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. .

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – hellobc
    Sep 23 at 18:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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.. $\endgroup$
    – kelalaka
    Sep 23 at 10:16
  • $\begingroup$ 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 $\endgroup$
    – hellobc
    Sep 23 at 12:22
  • $\begingroup$ 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$. $\endgroup$
    – kelalaka
    Sep 23 at 14:13
  • $\begingroup$ 2. precompute of what? do you include all possible hashed message space? $\endgroup$
    – kelalaka
    Sep 23 at 14:16
  • $\begingroup$ 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). $\endgroup$
    – hellobc
    Sep 23 at 14:42

Your Answer

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

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