Re: [Cfrg] 2^40. I can't exhibit it, but it exists.

[Watson Ladd <[e-mail]>]

On Feb 4, 2014 2:06 PM, "Paul Lambert" <[e-mail]> wrote:
>
>
>
> >From: Cfrg [mailto:[e-mail]] On Behalf Of Watson Ladd
> >Sent: Tuesday, February 04, 2014 12:12 PM
>
>
>
> >This attack is interesting because of the limits it puts on reductions,
which are
> >the main tool for doing cryptography. If dragonfly could be shown to
have no
> >other weaknesses this would be fine, but no such proof is forthcoming.
>
> When you say ‘no other’ you continue to imply that you have identified a
realistic exploitable weakness. The difficulty in ‘reducing’ the Dragonfly
proposal is not a exploitable flaw.  The changes necessary in protocol to
allow a formal proof may in fact weaken the overall security of the
protocol (reference below).

The paper below claims no such thing. I am claiming that there is a
weakness in standard model security for dragonfly,  not that there is an
exploitable flaw.

In fact tight reductions are possible, despite your claim otherwise.
>
>
>
>                         On the Security Loss in Cryptographic Reductions
>
> Proceeding: EUROCRYPT '09 Proceedings of the 28th Annual International
Conference on Advances in Cryptology: the Theory and Applications
Cryptographic Techniques
>
> Pages 72 - 87
>
> Almost all the important cryptographic protocols we have today base their
security on unproven assumptions, which all imply NP $\ne$ P, and thus
having unconditional proofs of their security seems far beyond our reach.
One research effort then is to identify more basic primitives and prove the
security of these protocols by reductions to the security of these
primitives. However, in doing so, one often observes some security loss in
the form that the security of the protocols is measured against weaker
adversaries, e.g., adversaries with a smaller running time. Is such a
security loss avoidable? We study two of the most basic cryptographic
reductions: hardness amplification of one-way functions and constructing
pseudorandom generators from one-way functions. We show that when they are
done in a certain black-box way, such a security loss is in fact
unavoidable.
>
>
>
>
>
> Your adamancy to make up issues with Dragonfly seems to imply you feel
this is a ‘down selection’ between multiple protocols.  It is not.  TLS is
one possible application, but the Dragonfly protocol was written in a
generic manner to specifically allow the analysis independent of the target
application.  Other schemes would be viable for TLS and I would strongly
support publication and review of multiple password protocol  alternatives
for TLS.
>

I am not "making up issues". I simply think that when a protocol goes into
an RFC it gets used. And that means we should be careful with the protocols
we publish.

Which alternative do you think TLS should use?
>
>
> The Dragonfly protocol has been in other standards act ivies for quite a
few years (usually called  SAE).  The review in this forum has improved
side channel security.  Your suggestions for other TLS solutions should not
block the analysis of this protocol if it is secure.  Making sure we have
clarity on the actual security of a fielded solution in critical and we
should be professional and correct in our analysis.  Mesh networking
networks are using SAE (aka Dragonfly).  Other consumer oriented
applications will appear based on the analysis that the protocol has no
exploitable weakness.
>
>

Not our problem. We are the IETF not the consumer electronics board.
Analyse it yourself. Or wait for someone else to do so. Or pay.

>
> Do also note that the  IPR disclosures for AugPAKE that you advocate have
limitations and are constrained to the IETF and TLS.  AugPAKE is completely
unacceptable for any broader application in consumer equipment (IMHO).
There are many engineering criteria to balance in the section of
appropriate algorithms for the industry.  Support of ‘reductions’ for a
formal proof are way down the list in my priorities.  I see that we
disagree on this point, and hope that you would look at the broader set of
industry requirements  and tone down your rhetoric.  If you continue to
have objections, please be clear and correct with the analysis.  You still
owe the group a clarification or a retraction on your claimed  2^40th
attack on Dragonfly.
>

It's a foundations of hashing style attack: utterly impractical but
theoretically important.

Why don't you list the requirements, and we'll come up with a protocol that
meets them?

What about being secure against reflection attacks or being well studied?

Of course I thought we were here to support the IETF. Still, this explains
WEP: marvel does not have a single cryptographer reviewing standards
submissions and expects it to be done by the community.
>
>
> Thanks,
>
>
>
> Paul
>
>
>
>
>
>
>
> From: Cfrg [mailto:[e-mail]] On Behalf Of Watson Ladd
> Sent: Tuesday, February 04, 2014 12:12 PM
> To: rransom. 8774; [e-mail]
> Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-dragonfly-03.txt
>
>
>
>
> On Feb 4, 2014 11:41 AM, "Robert Ransom" <[e-mail]> wrote:
> >
> > On 2/4/14, Dan Harkins <[e-mail]> wrote:
> >
> > >   This is mentioned in section 6.3 of RFC 5931 (dragonfly as an EAP
> > > method), knowledge of r where PE = r * G can enable a dictionary
> > > attack. But knowledge of r requires doing a discrete logarithm. A
discrete
> > > logarithm is assumed to be "computationally infeasible" and you're
talking
> > > about doing 2^40 of them!?!
> >
> > <http://cr.yp.to/papers.html#nonuniform> is relevant here.  It
> > discusses several other ‘attacks’ of this general type, and explains
> > why they should not be taken seriously.
>
> Bernstein actually argues that one should define complexity measures to
exclude such attacks. This is clear in the paper. Unfortunately time memory
product for the weak password variation is only 2^40.
>
> The problem with foundations of hashing usually isn't a real problem: one
can sign r,H (r, m) with r random to bypass it.
>
> This attack is interesting because of the limits it puts on reductions,
which are the main tool for doing cryptography. If dragonfly could be shown
to have no other weaknesses this would be fine, but no such proof is
forthcoming.
>
> Such a proof would be in the ROM, but as the IETF 88 slides show it would
be tricky.
> >
> >
> > Robert Ransom