Subject: [Cfrg] An attack violating the UMAC security claims

From: David Wagner <[email-masked]>
Date: Wed, 5 Oct 2005 10:49:47 -0700 (PDT)

David McGrew writes:
>your point is that the security claims in draft 05 don't take into  
>account simple key-guessing attacks.

No, that's not his point.  He is making a much broader point.  His point
is that (a) there are no precise security claims; (b) what security
claims can be found are actually *wrong* for the whole scheme (they
are accurate for the 2-univ hash, but not for the complete scheme); (c)
there are no proofs of the claims-that-aren't.  The key-guessing attack
is just a way of illustrating this point.  I think it would be a mistake
to focus in on his note as expressing concern about key-guessing attacks;
I see his note as focusing on insufficient theorems and proofs.

>But it is easy enough to change the claims so  
>that they are correct:

No doubt.  As I wrote in my note, I expect it to be straightforward
to fix DJB's criticisms and write down complete security theorems along
with complete proofs.  But I think DJB's point is that proposers of new
schemes ought to do this before they claim provable security -- it's
not reasonable to put the burden on the reviewers to come up with and
then evaluate security claims and proofs.

As I said before, DJB's points seem accurate to me, though I don't find
them serious enough to delay standardization of UMAC.  But I think at a
minimum we should try to understand what valid points DJB does have.

>    Another result [2],
>    when combined with [3, 6], shows that UMAC is secure under  
>reasonable
>    assumptions about AES, whenever no more than about 2^64 messages are
>    authenticated.

Let me try to channel DJB here.  I suspect he will say that this is not
a precise security claim, because it does not quantify the security level
achieved.  And I agree.

>Of course, what I've done with my edits above is merely gloss over  
>the details in the claims (please let me know if you think the claims  
>above are in error).  This would be completely unacceptable in a  
>scientific publication, but we're discussing a draft spec.  Let me  
>know what you think.

It's a definite improvement, no doubt about it, but I don't think it
fully addresses DJB's complaints: precise security claims and proofs
for the whole scheme are not to be found in either the spec or the
academic paper, so DJB's complaints can't be dismissed just by saying
that claims and proofs are inappropriate in a spec.  (Also, I can imagine
that precise security claims might be ok to put in a spec, because they
provide the implementor guidance on what kind of security can be expected.
Obviously, proofs belong elsewhere.)

Of course, as I said before, I don't view DJB's complaints as a barrier
to standardization, so I think it would be fine to advance this draft
even without addressing DJB's comments.  But, we should do so in full
knowledge of we have done so.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Wed, 5 Oct 2005 15:38:34 -0600

>  knowledge of we have done so.

I cannot see how the draft could be advanced with its current,
confusing claims of security.  Perhaps "we" would understand what "we"
had wrought, but how could we expect anyone else (say, the IESG) to
understand?

Hilarie

---

From: David McGrew <[email-masked]>
Date: Tue, 11 Oct 2005 10:05:27 -0700

David,

thanks for your comments, more inline:

On Oct 5, 2005, at 10:49 AM, David Wagner wrote:

> there are no proofs of the claims-that-aren't.

AFAIC Dan made those points already.

> The key-guessing attack
> schemes ought to do this before they claim provable security

Yes, I think that most would agree.

> -- it's
> that claims and proofs are inappropriate in a spec.

Fair enough.

> (Also, I can imagine

It is a funny thing: provable security was supposed to make  
cryptography *easier*  ;-)

David