Re: Authentication of a messages using a counter and a MAC

"Mike Amling" <spamonly@xxxxxxxxxxx> wrote in message
news:epd68l$f2h@xxxxxxxxxxxxxxxxxxxxxxxxxx
Joseph Ashwood wrote:
To attack a single MAC value that is correct, or actually to attack a
sufficiently small number of MAC values that is correct, but it breaks
down at the birthday point, so if you send out 5 MAC values of the 32-bit
MAC, the adversary only has to exert 2^31/5 work, as you approach the
birthday point the transition is difficult to compute because previously
ignorable epsilons begin to dominate the equation.

Sorry, I'm not following this. If I send 1024 messages with 32-bit MACs,
what does an attacker do 2**21 times that makes her probability of having
come up with a forgery more than about 0.001?

You're forgetting the multiple by the messages. If I am trying to collide
with 1 message I generally have to do half the work to collide with one of 2
messages, extending to I have to perform 1/K times the work to collide with
one of K messages. This leads immediately to the 2^31/5 I gave above.

Whether or not this actually leads to an attack on OMAC is questionable, and
the counter included in the original design provides some resilience, but
the proof itself breaks down at the birthday point. I consider this
breakdown at the birthday point to be a critical point to stop using the
key.



With that said I believe the biggest risk to the system is actually slightly
different from the algorithm I posed before


for(int datumNumber = 0; datumNumber < data in series; datumNumber++)
for(int attemptedMAC = 0; attemptedMAC < 16777216; attemptedMAC++)
send(datumNumber, attemptedMAC, data[datumNumber]);

Instead datumNumber should be fixed at one less than the maximum counter
value, this will eliminate the usefulness of the system, making the entire
construct useless. The reason for the one less is to avoid a bordercase
where due to counter wrapping the adversary accidently wraps the counter
around, voiding the counter, unless there is a specific check for this the
adversary has simply reset the counter, not locked up the system.
Joe


.

Relevant Pages

  • Re: Authentication of a messages using a counter and a MAC
    ... My argument comes from the birthday paradox. ... blindly forging a valid MAC for a particular message. ... Note that adversaries cannot determine offline if a forgery ...
    (sci.crypt)
  • a small technical point
    ... a very small technical question, for those of you who use Mac OS X, ... my beloved but ancient psion pda is dying, and ... birthday feature in the address book. ...
    (soc.motss)
  • Re: Authentication of a messages using a counter and a MAC
    ... Joseph Ashwood wrote: ... sufficiently small number of MAC values that is correct, but it breaks down at the birthday point, so if you send out 5 MAC values of the 32-bit MAC, the adversary only has to exert 2^31/5 work, as you approach the birthday point the transition is difficult to compute because previously ignorable epsilons begin to dominate the equation. ... how would the fact that two messages have the same MAC help the attacker? ...
    (sci.crypt)
  • Re: Teaching an old dog new un-Windows
    ... I sense another semi-senile life form out there. ... Well, if a person qualifies for that status before the 94th birthday, yes. ... I can't even find the power switch on my Mac, have to leave it on all ...
    (comp.sys.mac.misc)
  • Re: cool UIs
    ... >> I wish someone would just buy him a Mac for his birthday, ... >> could all move on and stop lugging this evermore bloated operating ...
    (borland.public.delphi.non-technical)