2
$\begingroup$

Say we have a computationally secure Message Authentication Code scheme (Gen, Tag, Ver).

Let $Tag'_k(m):=$ first half bits of $Tag_k(m)$. Let's assume the range of tags is $n$bits.

Is (Gen, Tag', Ver) secure?

An efficient adversary that breaks (Gen, Tag, Ver) can't be constructed using an effecient adversary that breaks (Gen, Tag', Ver) because the former still would have to guess the last $\frac{n}{2}$ bits. So I want to say it's not secure.

Yet I want to say it is secure because I can't think of an algorithm that can efficiently break (Gen, Tag', Ver).

$\endgroup$
  • $\begingroup$ For the usual MAC algorithms the result is $\frac{n}2$ less secure. But it may be possible to construct a MAC where the first and second parts of the authentication tag are related in such a way that it is less secure. Security isn't a boolean though; there is no secure / not secure, only more secure or less secure. And even that may be subjective. $\endgroup$ – Maarten Bodewes Nov 25 '15 at 21:30
3
$\begingroup$

It is not secure in general, but not insecure in general either.

For example, you can get a MAC algorithm for which it would be secure by concatenating constant data to a secure MAC. $Tag_k(m) = M_k(m)||0^n$ is a secure MAC if $M$ is. And clearly taking the first half of that is a secure MAC if $n = |M_k(m)|$.

On the other hand, reverse the order of the constant and non-constant part above and you get a MAC scheme for which taking the first half is very insecure.

If your secure MAC algorithm is based on a PRF, you can take the first half and have a MAC that is secure, but easier to guess randomly. (Because a secure PRF is a secure MAC and a truncated PRF is still a PRF.) Many MAC algorithms like HMAC and CMAC, for example, can be truncated for this reason.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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