Subject: [Cfrg] 40 bit loop and DragonFly

From: "Igoe, Kevin M." <[email-masked]>
Date: Sun, 5 Jan 2014 01:41:25 +0000

Scott Fluhrer wrote:

I think we agree that what Dan specified in the draft is broken.  However, I believe that's because Dan got it wrong (and I was busy elsewhere, and did not review the draft).

I believe my suggestion is an improvement (but still needs caution; the checking if x^3+ax+b is a QR must be done in constant time, or in random time via blinding; I believe that in this case blinding is easier).

Now, I believe the issue is 'did Kevin endorse my suggestion, or did he endorse Dan's implementation?'
---------------------------------

Actually I had something more like the process outlined below in mind.  

First an elementary (and somewhat obscure)fact:

  For any prime p = 3 mod 4 and any non-zero f in Z/p, let 
            r = f**((p+1)/4).
  If f is a quadratic residue mod p (i.e. has a square root mod p),
  then r**2 = f, otherwise r**2 = -f.

(This is easy to see since 
             r**2 = f**((p+1)/2) mod p
                  = f * f**((p-1)/2) mod p
and f**((p-1)/2) = 1 mod p if f has a square root mod p and is 
-1 otherwise).  

Aside from cases of vanishingly small probability (e.g f = 0, 1 or -1),
the time to do this exponentiation  depends upon two publicly known 
values, the modulus p and the exponent ((p+1)/4), and not upon the secret 
values x and f.  I'd advise using Montgomery arithmetic as this is 
a very efficient and methodical technique for doing mod p arithmetic.

So what had I envisioned is something like this (in pythonese):

Bad = []
Good = []
for t in range(40):
    x  = one_way_update(x)
    f  = x**3 + a*x + b mod p
    r  = f**((p+1)/4)
    f1 = r**2
    if f1 == f:
        Good.append( (x,r) )
    else:
        Bad.append( (x,r) )

if len(Good) == 0:
    raise ValueError
else:
    return Good[0]

Observations:
 - This should be consant in time and memory usage.
 - Prob of hitting the error condition is 2**-40 ~= 10**-12.
 - The 40 could be increased if the RG deems that to be prudent.

Potential IPR issues:
Certicom has granted permission to the IETF to use the NIST curves, 
and at least two of these, P256 and P384, have p = 3 mod 4.  Not 
being a patent lawyer, I have no idea what impact the Certicom patents 
have on the use of newer families of curves, such as Edwards curves.  
RFC 6090 outlines elliptic curve technology which predates the Certicom
patents.

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Sun, 5 Jan 2014 01:48:12 +0000

Make that 40 long loop, not 40 bit loop.

(Proofreading on a Blackberry is a torturous task.  I'm not sure why Pres. Obama is so addicted to these things!)

----- Original Message -----
From: Igoe, Kevin M.
Sent: Saturday, January 04, 2014 08:41 PM Eastern Standard Time
To: [email-masked]' <[email-masked]>
Subject: 40 bit loop and DragonFly

Scott Fluhrer wrote:

Bad = []
Good = []
for t in range(40):
    x  = one_way_update(x)
    f  = x**3 + a*x + b mod p
    r  = f**((p+1)/4)
    f1 = r**2
    if f1 == f:
        Good.append( (x,r) )
    else:
        Bad.append( (x,r) )

if len(Good) == 0:
    raise ValueError
else:
    return Good[0]

Observations:

Potential IPR issues:

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 05 Jan 2014 10:33:42 +0000

Kevin,

On 01/05/2014 01:41 AM, Igoe, Kevin M. wrote:
> and at least two of these, P256 and P384, have p = 3 mod 4.  

I'm not sure what exactly you mean there. From my POV, Certicom
have declared [1] that they consider that some of their IPR is somehow
required in order to implement the most excellent RFC 6090 [2] which
only references things published at least a year before Certicom's
first filing. I also seem to recall that some of their IPR
declarations do include restrictions on things like CAs issuing
certs.

So "granted permission" is not quite so clear. At least not
without either being a lawyer, or having whatever time machine
Certicom's lawyers seem to possess. I doubt we'll clarify the
IPR situation around ECC here, nor around PAKEs unfortunately.

But I think we can conclude that the Dragonfly goal of designing
around existing IPR remains a valid design goal. Whether or not
Dan has succeeded in that is another matter, participants who
care about IPR need to evaluate that for themselves.

S.

[1]
https://datatracker.ietf.org/ipr/search/?option=rfc_search&rfc_search=6090
[2] http://tools.ietf.org/html/rfc6090

> Not

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 5 Jan 2014 08:24:16 -0800

> Certicom has granted permission to the IETF to use the NIST curves, 

This is completely wrong on many different axes.

- Certicom's IPR statements are for implementers, not the IETF.

- Certicom did not "grant permission" to anyone.

- Certicom's IPR statements do not mention "the NIST curves".

Certicom/RIM/Blackberry has spread a great deal of FUD in its IRP claims; it harms the crypto community when people parrot it, and makes it even worse when they parrot it badly.

> have on the use of newer families of curves, such as Edwards curves.  

Just to be clear: you also have no idea what impact the Certicom patents have on any family of curves. None of us do.

> RFC 6090 outlines elliptic curve technology which predates the Certicom

Correct. It would have been *way* better to leave out the rest of that paragraph.

--Paul Hoffman

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Sun, 5 Jan 2014 20:36:14 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Igoe, Kevin M.
> Sent: Saturday, January 04, 2014 8:41 PM
> To: [email-masked]'
> Subject: [Cfrg] 40 bit loop and DragonFly
> 
> Scott Fluhrer wrote:
> 
> I think we agree that what Dan specified in the draft is broken.  However, I
> believe that's because Dan got it wrong (and I was busy elsewhere, and did
> not review the draft).
> 
> I believe my suggestion is an improvement (but still needs caution; the
> checking if x^3+ax+b is a QR must be done in constant time, or in random
> time via blinding; I believe that in this case blinding is easier).
> 

Both your procedure and mine look good.

The only thing (and I think we ought to be explicit about it) is that the various operations need to run in constant time; we need to explicitly state that the modular additions and multiplications need to be run in time independent of the values being added and multiplied.  The only exception in either of our proposals is the Legendre symbol computation, and that's true IF you are using blinding like I suggested; that's safe because the time it takes is not correlated with any value we need to keep secret.

This might be fairly obvious; however I don't know if we want to omit obvious precautions.

>                   = f * f**((p-1)/2) mod p and f**((p-1)/2) = 1 mod p if f has a square
> root mod p and is
> -1 otherwise).
> 
> Aside from cases of vanishingly small probability (e.g f = 0, 1 or -1), the time
> to do this exponentiation  depends upon two publicly known values, the
> modulus p and the exponent ((p+1)/4), and not upon the secret values x and
> f.  I'd advise using Montgomery arithmetic as this is a very efficient and
> methodical technique for doing mod p arithmetic.
> 
> Certicom has granted permission to the IETF to use the NIST curves, and at
> least two of these, P256 and P384, have p = 3 mod 4.  Not being a patent
> lawyer, I have no idea what impact the Certicom patents have on the use of
> newer families of curves, such as Edwards curves.
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 6 Jan 2014 16:46:46 +0000

For the record, some observations:

1) We will often need to try more than one x until we find 
one where f = x**3+a*x*b is a quadratic residue mod p (probability 
(1/2)**k that it takes k tries).  Requiring that we always pass 
through the loop
     { update x; 
       calculate f; 
      check if f is a quadratic residue; } 
a fixed number of times (I suggested 40) masks how many steps 
were actually need to find an x for which f is a QR.

2) Since computing a Jacobi symbol is faster than exponentiation, 
I like your idea of blinded calculation of the Jacobi symbol.  
to see whether or not a given f is a QR. It's nice that the client 
and server can use independent blinding factors and still arrive 
at the same result.

3) When 2^k | p-1 for k>1, some square root calculations are 
faster than others, but taking the square root of the blinded
f should mask that just fine. 

4) That just leaves multiplying sqrt((r**2)*f ) = r*sqrt(f)
by (1/r) => need to calculate 1/r, which can be done either 
by an exponentiation or by the extended Euclidean algorithm.
Since the extended Euclidean algorithm is variable time, it 
might leak information about r, so exponentiating by p-2 is 
the safer alternative.  Fortunately, this only has to be done
once, not "40" times.

------------------------------------------------------------

I believe there aren't any insurmountable issues associated 
with DragonFly, but that doesn't mean Dan and the RG don't 
have some work to do.  

> From: Scott Fluhrer (sfluhrer) [mailto:[email-masked]]
> Sent: Sunday, January 05, 2014 3:36 PM
> To: Igoe, Kevin M.; [email-masked]'
> Subject: RE: 40 bit loop and DragonFly
> 
> 
> 
> > I think we agree that what Dan specified in the draft is broken.
> > However, I believe that's because Dan got it wrong (and I was busy
> > elsewhere, and did not review the draft).
> >
> > I believe my suggestion is an improvement (but still needs caution;
> > the checking if x^3+ax+b is a QR must be done in constant time, or in
> > random time via blinding; I believe that in this case blinding is
> easier).
> >
> The only thing (and I think we ought to be explicit about it) is that
> the various operations need to run in constant time; we need to
> explicitly state that the modular additions and multiplications need to
> be run in time independent of the values being added and multiplied.
> The only exception in either of our proposals is the Legendre symbol
> computation, and that's true IF you are using blinding like I
> suggested; that's safe because the time it takes is not correlated with
> any value we need to keep secret.
> 
> >                   = f * f**((p-1)/2) mod p and f**((p-1)/2) = 1 mod p
> > if f has a square root mod p and is
> > -1 otherwise).
> >
> > Aside from cases of vanishingly small probability (e.g f = 0, 1 or
> > -1), the time to do this exponentiation  depends upon two publicly
> > known values, the modulus p and the exponent ((p+1)/4), and not upon
> > the secret values x and f.  I'd advise using Montgomery arithmetic as
> > this is a very efficient and methodical technique for doing mod p
> arithmetic.
> >
> being
> > a patent lawyer, I have no idea what impact the Certicom patents have
> > on the use of newer families of curves, such as Edwards curves.
> > RFC 6090 outlines elliptic curve technology which predates the
> > Certicom patents.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Jan 2014 09:18:05 -0800

> the safer alternative.  Fortunately, this only has to be done

What about that 2^{-40} failure probability? Why aren't we using
Elligator to fix it?

I still haven't found a formal security claim that is true about Dragonfly.

There also are possible issues over F_{p}^{\times}: in particular
multitarget variations
of index-calculus get an improvement. This needs to be analyzed, and I
really don't feel
like doing it, because we have J-PAKE.

Why are we still trying to fix Dragonfly? We've got alternatives that
don't have the
significant theoretical issues, don't have the implementation issues,
don't have the IPR issues
(pith and marrow makes me think Dragonfly is covered by SPEKE patent),
and have been
vetted far more extensively.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Trevor Perrin <[email-masked]>
Date: Mon, 6 Jan 2014 18:02:02 -0800

>> with DragonFly, but that doesn't mean Dan and the RG don't
[...]
> vetted far more extensively.

I share Watson's incredulity that Kevin expects further work on
Dragonfly.  As Watson states, there are better alternatives (SPAKE2,
J-PAKE, SRP, AugPAKE, and Elligator-based variants).

Dan insists that he wants a balanced EC PAKE without patents, so let's
talk about SPAKE2 and J-PAKE.  Both have been around for years, have
formal security analysis, and are easily implemented without
side-channels.

Kevin and Dan: please explain why you prefer Dragonfly to these protocols.

Trevor

---

From: David Jacobson <[email-masked]>
Date: Mon, 06 Jan 2014 18:59:51 -0800

On 1/6/14 8:46 AM, Igoe, Kevin M. wrote:
> [snip]

Isn't this easy?  Choose a random non-zero b from the same field as r.  
Compute b*(r*sqrt(f)) and b*r.  Compute 1/(b*r).  Since all values of b 
are equally likely and the attacker does not know b, any leakage from 
the inverse that makes some values of b*r more likely gives no 
information at all about r.  Now compute (b*(r*sqrt(f)) * (1/(b*r))  = 
sqrt(f).

      --David

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 7 Jan 2014 00:36:17 -0800 (PST)

Hi Trevor,

  I guess it was just an idle threat then for you to say you would "give
up participating in IETF/IRTF any further" if Kevin was endorsed through
an open process (note: he actually was, and that decision has been
confirmed by the IRTF chair). Oh well….

> Kevin and Dan: please explain why you prefer Dragonfly to these protocols.

  Where did you divine Kevin's preferences from? I have not heard
or read any statements from him that he prefers dragonfly as a PAKE
over any other protocol.

  I think SPAKE2 and j-PAKE are great. But for the uses I'm interested in
right now they are not the best choice. I'm looking for something to
protect an EST exchange where the group used for the PAKE is the same
as the group in which the key-to-be-certified was generated in, and I'm
also looking for something also to allow for small, constrained devices
in a home network setting to be provisioned by people with no security
clue so they can securely connect to a local server-- this means ECC
and it means as simple and idiot-proof a configuration as possible.

  SPAKE2 requires establishment of additional elements in the group that
are assigned to the players. This increases provisioning cost and requires
a certain amount of security clue on the part of the person doing the
provisioning. Dragonfly does not; just configure a simple password on each
end and voila. In addition, SPAKE2 cannot support different groups on the
fly so it won't work with the EST need. SPAKE2 does not work for either of
my two primary uses of Dragonfly.

  J-PAKE does not fit into TLS very well. It has an additional round of
message exchanging. Dragonfly fits in perfectly, key establishment
is done entirely in the client/server key exchange messages and
key confirmation fits into the finished message.

  But even if those were not the case and J-PAKE and/or SPAKE2
were acceptable, it's because there are no alternatives ready RIGHT
NOW. As I have explained numerous times to you, this is already late.
EST was already published and implementations exist. The need for a
certificate-less TLS cipher suite that supports ECC and does not bind
a single group to a password is already several months past due.

  Also, I have stated to you earlier that I think EKE with elligator curves
would be perfect. But such a draft doesn't exist. Even if you had a -00
draft written today we're still looking at 2+ years before it's published
as an RFC. So that doesn't work.

  Of course, you are more than welcome to write a draft specifying
any other kind of PAKE you want. You have previously stated that
you see no need for another PAKE in TLS so doing so would be,
according to you, a pointless endeavor. But, as we have seen, your
statements (e.g. "I will give up participating in IETF/IRTF") seem to
be made primarily for effect. So hopefully your statement against
any other PAKEs in TLS besides SRP was similarly made just for
effect and you will be advancing a PAKE draft really soon now.

  I await your draft of J-PAKE or SPAKE2 or anything else you think
is more appropriate. But, unfortunately, it is not of any use to me
right now.

  Dan.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 7 Jan 2014 05:47:49 -0800

> and it means as simple and idiot-proof a configuration as possible.

Why "the same?". Why not more secure?

128-bits can be represented as 26 elements of a 32 character alphabet.
Divide it into 4 groups of 6, and you have something that a major consumer
product has people type in.

PAKE is likely to be less secure than this: it also will permit a break
in one of the devices to be extended to a break in all of them.

You can also use TOFU, or a distance-bounded initial connection. Some
of these are significantly better from a UI perspective then passwords.

> my two primary uses of Dragonfly.

Why can't M&N be global: one for the client, one for the server?
I agree with you this means picking one group, but M-511 exists.
AGL has this working for Pond.

> key confirmation fits into the finished message.

Why do you care how well it fits? If we can shoehorn it in, it will work.

> as an RFC. So that doesn't work.

I think you are ignoring the fact that the TLS WG will not consider dragonfly
for the foreseeable future. You are also ignoring the fact that the 2+ years
are primarily a function of very avoidable process delays: a last call takes
4 weeks. Try writing up SPAKE2, submit it, and see how long it takes to
get a good standard through.

Dragonfly has unfixable flaws relating to its provable security that will
prevent me from endorsing it for any protocol, ever. I am not alone in
thinking that we should expect more from the protocols we standardize.

Also, is this implemented in OpenSSL or NSS or PolarSSL? Not yet.
So the vaunted readiness is really overstated. Granted, SPAKE2 would
take a while, but we already have an implementation to use living at
https://github.com/agl/panda.

Lastly, if this was needed for EST to work, they should have noticed
this dependency, and tackled it head on. That they punted on
this problem does not mean it is our responsibility to fix it.

> is more appropriate. But, unfortunately, it is not of any use to me

Dan, if this is such a need, why haven't you used TLS-SRP while
waiting for something better?
Even if this is standardized, you still need the browser makers to follow suite.
Besides, you can also turn a paper into a draft: why you didn't do
this instead of come up
with Dragonfly n years ago is beyond me.

Of course, there are drafts for J-PAKE and AugPAKE sitting around, one for TLS.
I still haven't figured out why AugPAKE couldn't be used for the
example use case.

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 7 Jan 2014 09:47:17 -0800 (PST)

On Tue, January 7, 2014 5:47 am, Watson Ladd wrote:
> Try writing up SPAKE2, submit it, and see how long it takes to

  You're the one proposing it, why don't you? In fact, since you have
previously stated it really only takes 30 minutes to write an
interoperable standard why don't you do it during your lunch hour?

> Also, is this implemented in OpenSSL or NSS or PolarSSL? Not yet.

  ZZzzzztt! Wrong. I implemented it in OpenSSL. That's where Appendix
A of draft-ietf-tls-pwd came from. In fact, the sample exchange was
from my EST client talking to my EST server being authenticated with
TLS-pwd.

> this problem does not mean it is our responsibility to fix it.

  You use pronouns very loosely. And you exaggerate a bit too much.
Nobody said it was necessary for EST to work. It's needed for EST to
be deployed properly in many situations where there is no trust
anchor database established before the EST exchange is initiated.
There is a chicken-and-egg problem with needing a certificate to
get a certificate. Understand?

  Dan.

---

From: Feng Hao <[email-masked]>
Date: Tue, 7 Jan 2014 18:01:22 +0000

Hi Dan,

On 07/01/2014 08:36, "Dan Harkins" <[email-masked]> wrote:

>confirmed by the IRTF chair). Oh well..

I am afraid this kind of comment is not helpful; it only creates tension
and animosity. Please, can we limit ourselves to strictly technical
arguments only?

>key confirmation fits into the finished message.

You're correct that J-PAKE needs an extra round. I am not too familiar
with TLS, but I am inclined to think if SRP can be fit into TLS, so can
J-PAKE. From the SRP-6 protocol description, SRP needs 6 passes to
complete the key agreement with explicit key confirmation. For J-PAKE, it
actually only needs 4 passes to do the same. So it looks that fitting
J-PAKE into TLS shouldn't be impossible.

To me, the biggest question is if the TLS community perceives a need for
TLS-JPAKE (or similar).

If not, let us not bother. If yes, I am more than happy to spend time
working it up to an RFC, and I sincerely welcome TLS experts and other
interested parties to contact me (online or offline), so we can write the
document together.

I could see three arguments against TLS-JPAKE: 1) there is already
TLS-SRP; 2) an augmented PAKE should be preferred; 3) TLS-SRP is rarely
used in practice. 

For 1) I don't think the existence of TLS-SRP must exclude other entries.
At the moment, SRP doesn't readily support ECC, which is a practical
limitation. J-PAKE doesn't have this limitation.

For 2) There is one practical advantage with an augmented PAKE (SRP) that
if the server database is compromised, the stolen password verifiers can't
be directly used to allow the thief to authenticate back to the
(compromised) server without first doing an offline password search. (The
scenario is a bit artificial but anyway...) The advantage is actually
limited, as it merely slows down the attack rather than prevents it.
Furthermore, an augmented PAKE is inherently more complex than a balanced
PAKE. One may wonder if the limited advantage justifies the extra
complexity. This is not to argue which one is better, but as you can see,
a balanced and augmented PAKEs present different trade-offs. I think
TLS-SRP and TLS-JPAKE can co-exist, to suit different application
requirements.

For 3), this concerns me most. I can see the benefits of including PAKE
(balanced/augmented) into TLS, but I don't understand why in reality few
people use TLS-SRP. Something is amiss somewhere and it's not clear to me
exactly what and why. This is an important question, as otherwise, we will
be wasting time to work on something no one cares.

In my opinion, a potentially major advantage of TLS-JPAKE is protection
against "phishing attacks", which are currently a big industry problem.
However, that would require a trusted user interface for the user to enter
the password; if the user enters the password in the wrong place, the
security promise of TLS-JPAKE is gone. If the user uses a web browser,
then the log in interface should be tightly built within the web browser
(not the web page), which will be impossible without the active
participation from browser vendors. Not sure if that caused the low-uptake
of TLS-SRP.

Regards,
Feng

---

From: Watson Ladd <[email-masked]>
Date: Tue, 7 Jan 2014 10:02:56 -0800

> interoperable standard why don't you do it during your lunch hour?

Because http://tools.ietf.org/html/draft-shin-tls-augpake-01 exists already.
In fact, AugPAKE is necessary to avoid an attacker breaking into my coffee pot
from changing my alarm clock as well. These are critical systems you are
talking about!

Why don't we move this over to TLS, get augpake through, and be done with it.
It satisfies everyone's needs.