Re: [LinkSec] Factoid: MIC size
Hi Marcus,
I am confused... What attacks/threats do you consider when you say
that we need to avoid collisions of MIC values? Moreover, if there
indeed is a problem, I don't see that the countermeasures you
suggest solves the problem.
First, a good MIC is supposed to behave like a PRF (pseudo
random function). PRFs *should* have collisions after that
many messages. The point is that an attacker cannot predict
when the collision will happen, except by chance (more below).
Moreover, should he passively observe a collision (after 2^32
messages say), the only way I see to exploit this would be in
a replay attack, but for "reasonable" replay-window sizes, this
will not pass the replay screening anyway.
Secondly, *if* there indeed was a problem, notice that after
square-root messages, this problem/collision will occur
with constant probability (about 1/2) which would be
cryptographically unacceptable anyway.
Thirdly, why does changing the key help? Suppose that
you MIC 2^31 messages with k1 and 2^31 with k2. Heuristically,
the expexted number of collisions among these 2^32
is still about one (1), despite the key change. If these
collisions as such were a problem, it would be quite serious.
I took the liberty of asking (and also cc:ing, I don't think
his on the list) David McGrew (who knows more abot
MICs that I do) just to be sure. I quote:
<quote>
A collision between two MICs is *not* a security
problem. A message authentication code is secure as long as an
adversary cannot
generate a message/MIC pair that will be accepted as valid. This
property is
independent on whether or not two MIC values happen to collide.
Also, the expected number of successful forgeries in a system with an
ideal MAC
is (N / 2^t) when the adversary makes N attempts against a t-bit tag.
There's no birthday paradox here.
The one place where the birthday paradox shows up in message authentication
(AFAIK) is the case in which the same message is MICed many times. Then the
attacker can use a standard key-collision attack. But note that in this
case,
the size of the tag *does not* matter - the collisions are on the keys,
not on
the tags, so the key size is the important thing.
</quote>
Sorry for the rather lengthy reaction, but I think it
is important to be accurate. If you do know of a weakness
caused by normal, accidental collisions, I am most interested
to hear.
Best,
/Mats
Leech, Marcus (EXCHANGE:FITZ:8M86) wrote:
> Under the standard birthday attack collision assumptions, the probability
> of collision becomes significant when the number of messages under a given
> key approachs sqrt(2^size-of-mic).
>
> That means that for a 64-bit MIC, you need to change keys before 2^32 messages
> have been sent under a key. For a 10gbit link, under assumption of average
> 1000-bit messages, that's a key change every 7.15 minutes or so. That impacts
> the efficiency of the key-exchange algorithm, and the decision-point for
> key-change (if you algorithm for key-changing is slow, you want to start trying
> to do a key-change rather early, so that there's NO possibility of exceeding
> the collision limit).
>
> Since we seem to be in the "how many bits can we realistically add to the header"
> phase, I'd vote for more MIC bits than 64.
>