[curves] SPAKE2 and SPAKE2 Elligator Edition

[Michael Scott]

Just to be clear, I am talking about this Abdalla paper

http://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf

And I am referring to the last paragraph in the introduction on page 1
(also see figure 1)

They say "this protocol can be easily broken by an active adversary
performing a man-in-the-middle attack."

That's what I'm having difficulties with. I don't see that its at all
"easy".


Mike


On Thu, Feb 19, 2015 at 10:23 AM, Michael Scott <mike.scott at certivox.com>
wrote:

> That's very nice. But there is a lot of hashing going on...
>
> The importance of introducing hashing was motivated in the Abdalla paper.
> The authors point out that an attacker who can launch a man-in-the-middle
> attack, and who learns the value of the two session keys, can carry out an
> off-line dictionary attack and hence determine the password.
> But wait a minute. I see how a man in the middle can insert and modify
> transmitted values, but he can also learn the value of session keys (as
> calculated by Alice and Bob, but not by himself)? How is that to be done
> exactly? And in the presence of an attacker who can grab session keys out
> of process memory, then there is no security anyway. And if this attacker
> can grab session keys, then how does hashing them help - surely the same
> attacker with only a little more effort can grab the keys out of memory
> before they are hashed?
>
>
> Maybe I am missing something..
>
>
> Mike
>
>
>
>
>
> On Thu, Feb 12, 2015 at 9:53 AM, Mike Hamburg <mike at shiftleft.org> wrote:
>
>> Hello curves,
>>
>> It's been suggested that I explain Elligator and SPAKE2-EE in more
>> detail.  Get ready for a wall of text.
>>
>> TL;DR: SPAKE2-EE is probably slightly better overall than SPAKE2. It's
>> slightly faster, has better security assumptions, and makes one or two
>> cases that can arise in SPAKE2 slightly easier.  It's also more complicated
>> to spec and implement, since you need Elligator. SPAKE2-vanilla needs more
>> complicated optimizations to achieve its top speed, but at least you don't
>> have to spec them.
>>
>>
>> Elligator 2:
>>
>> Elligator 2 is a map from the base field F to any elliptic curve E (over
>> a large characteristic field) with a point of order 2. There's also an
>> Elligator 1 but it's more complicated and has more restrictions, so let's
>> stick with Elligator 2.  If the curve doesn't have a point of order 2 (eg,
>> the NIST curves), then the Shallue-Woestijne-Ulas (SWU) algorithm has very
>> similar characteristics, and is only slightly more complicated.
>>
>> Any curve with a point of order 2 is isomorphic to one of the form y^2 =
>> f(x) = x (x^2 + Ax + B), i.e. Weierstrass form with the point of order 2 at
>> (0,0).  From there, the idea is to come up with two values x1 and x2 where
>> one of them has a y on the curve and the other does not.  To do this, it
>> suffices that:
>>
>> x1^2 + Ax1 + B = x2^2 + Ax2 + B, and
>> x1 / x2 is not square in F
>>
>> The first condition is equivalent to x1 + x2 = -A.  The second condition
>> is equivalent to x1 = ur^2 x2, where r is arbitrary and u is a fixed
>> nonsquare value, eg -1 if p==3 mod 4.  (If r=0 then actually x1/x2 = 0 will
>> be square, but that's good enough because (0,0) is on the curve.)  Solving
>> these two equations gives x2 = -A/(1+ur^2), and x1 = ur^2 * that.  Notice
>> that if you plug 1/ur into the equation for x1 you get x2 and vice-versa.
>>
>> So Elligator is conceptually pretty simple:
>>
>> * Map your input value to a field element r.
>> * Compute whether f(-A/(1+ur^2)) is square.  If so, compute its square
>> root.
>> * If not, compute the square root of f(-Aur^2/(1+ur^2)) = ur^2
>> f(-A/(1+ur^2)).
>>
>> There are two important optimizations here.  The first is that you can
>> compute f(-A/(1+ur^2)) projectively, so you don't have to divide.  If it
>> ends up as C/D, then you can compute s = sqrt(CD) and then have y = s/D,
>> again projectively; or if you use the isqrt trick you can compute the
>> actual value of y.  This latter technique is better, because you can easily
>> enforce the spec that y is "positive" if you chose x1 and "negative" if you
>> chose x2, for your favorite definition of those terms (even, Legendre
>> symbol, whatever).
>>
>> The other important optimization is to compute both square roots in one
>> step.  For example, if p == 3 mod 4, then u=-1 and x^((p+1)/4) =
>> sqrt(+-x).  So compute f(...)^((p+1)/4).  If it comes out as sqrt(f(...)),
>> good.  If not, it's sqrt(-f(...)) but you want sqrt(-r^2f(...)).  So
>> multiply it by r and you're good.  In 5-mod-8 world, sqrt(-1) takes the
>> place of -1 here.
>>
>> But you didn't want to hash to a Weierstrass curve.  You wanted to hash
>> to an Edwards curve.  No problem.  Just hash to the isomorphic Montgomery
>> curve, and apply the isomorphism, all in projective coordinates.  Or, in
>> cases like SPAKE2, you'll need to multiply by 4 so that you get something
>> in the main subgroup.  You can hash to Edwards and multiply by 4, or you
>> can hash to the isogenous Montgomery curve instead of the isomorphic one,
>> and apply the isogeny.  Your pick.
>>
>> All in all, this means you can compute Elligator 2 in projective
>> coordinates with maybe one isqrt, a dozen muls, 35 lines of code, a couple
>> cond-selects (or multiplies by values you know in advance to be +-1), and
>> some careful testing.
>>
>> Elligator 2 is implemented in C as one of the many available point ops in:
>>
>> http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/
>> tree/src/ec_point.c
>>
>> This is an unnecessarily nasty implementation, because it maps to affine
>> (using the inverse square root trick) instead of to projective.  Not worth
>> it.  The Decaf version is simpler.
>>
>> In the case of Decaf, the main spec is in terms of a Jacobi quartic,
>> rather than a Weierstrass or Edwards curve, but all the actual math takes
>> place in twisted Edwards.  The Jacobi quartic is isomorphic to L_d : y^2 =
>> x(x-1)(x-d).  So you can do Elligator to that curve -- remember that
>> Elligator 2 doesn't require a Montgomery curve -- and then use the
>> 2-isogeny from there to the twisted Edwards curve where it does all its
>> math.  Same deal as with the Montgomery/Edwards combination, slightly
>> different formulas.
>>
>> This is implemented in C as decaf_point_from_hash_nonuniform in
>>
>> http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/src/decaf.c
>>
>> There's also a function decaf_point_from_hash_uniform which calls
>> Elligator twice and adds the results.  This is indifferentiable from a
>> random oracle, but twice as slow.  It's not necessary in most protocols,
>> because they really only need an argument that looks like "for all you
>> know, the hashed point on the curve could secretly have an embedded CDH
>> challenge" and that doesn't require uniformity, only almost-uniformity and
>> almost-invertibility.
>>
>> For an RFC-style spec, you'd probably want to turn one of these C
>> functions into a few lines of Python and specify that exact computation.
>>
>>
>>
>> OK, now on to PAKE.
>>
>> Elligator is 1:1 on [0,(p-1)/2], and it's easy to invert the map for
>> those points in E where it has an inverse.  This matters for EKE, though,
>> and we're talking about SPAKE2.  Remember that SPAKE2 works like so:
>>
>> Let g, M and N be random generators of G, with no known relationship in
>> the group.  Let "password" be a suitably stretched salted hash of the
>> actual password.  Either the client has to retrieve the salt, or it's equal
>> to her username and the server's name.
>>
>> Alice -> Bob: A := g^x M^password, ID_Alice
>> Bob -> Alice: B := g^y N^password, ID_Bob
>>
>> This can be optimized by a double-exp, possibly with fixed bases if you
>> precomputed a table for M and one for N.  Also, the server can just store
>> M,N^password in the database.
>>
>> Both sides can now compute g^xy = (A/M^password)^y = (B/N^password)^x.
>> They can implement the division as written, or they can use a double-exp,
>> i.e. A^y M^(-password*y).
>>
>> Then both sides compute validators and session key vA,vB,sk =
>> H(A,B,ID_Alice,ID_Bob,g^xy,password).  The session messages are included
>> to prevent tampering.  The password is included as an artifact of the
>> security proof, and is probably technically unnecessary.  For augmented
>> versions of SPAKE2, a hash of password is also a good enough artifact.
>> Anyway, the two sides exchange validators and then start using the session
>> key.
>>
>> The two DH flows and the two validation flows can each happen
>> simultaneously, or more likely Bob's two flows will be merged but Alice's
>> will remain separate.
>>
>>
>> SPAKE2-EE
>>
>> SPAKE2-EE ("Elligator Edition") is a simple variant of this protocol, in
>> which M^password is replaced by h*Elligator(H("M",password)) where h is the
>> cofactor, and likewise for N.  It's very important to clear the cofactor
>> here, or to use a g which generates the entire group and not just the main
>> subgroup; otherwise the cofactor components of the password hash will leak.
>> Decaf's Elligator variant clears the cofactor for you; Goldilocks' does not.
>>
>> Putting Elligator in clearly doesn't hurt the security of the protocol in
>> the ROM, because for all the attacker knows h*Elligator(H("M",password)) is
>> actually equal to, or at least morally equivalent to, M^password.  The
>> rigorous proof proceeds almost exactly the same as SPAKE2 proof, but with
>> an extra invocation of the random oracle model.
>>
>> As far as I see it, SPAKE2-EE's advantage is that it's slightly tidier
>> than SPAKE2 proper, because it removes the static-DH assumption.  In
>> SPAKE2, you have to convince people that you generated M and N with no
>> relationship to g, because an adversary knowing the discrete log of M base
>> g can mount a dictionary attack against everyone.  (I believe that the same
>> is only true for N if the flow ordering allows Alice to authenticate
>> first.)  It shouldn't be hard to generate such an M,N, but it's even better
>> if you don't have to.
>>
>> SPAKE2-EE has a small performance advantage over SPAKE2 proper, at least
>> when Elligator is implemented as described above.  That implementation
>> takes under 1M/bit since the expensive part is the square root, but even if
>> you precompute tables for M,N, it will cost at least 1.8M/bit to compute
>> M^password and again 1.8M/bit for N.
>>
>> The cost is that you have to spec and implement Elligator, which is
>> annoying but not terrible.  At the same time, there won't be any temptation
>> to implement double-fixed-base-comb-exp routines to improve performance.
>>
>>
>>
>> More-symmetric and less-symmetric PAKE:
>>
>> It's not very important that M != N.  I'm pretty sure the proof Trevor
>> cited of this is wrong, but I'm also pretty sure that a proof exists under
>> slightly worse assumptions than the original.
>>
>> Alternatively, N^password can be dropped, so long as Bob sends his
>> validator first.  (If Alice sends hers first without N^password, then a
>> fake Bob clearly has a dictionary attack because his first password-related
>> computation is to check the validator.)  This doesn't harm the proof IIRC,
>> it just adds the ordering restriction.
>>
>> These are both provable under some CDH variant (eg, GapDH if you like
>> shorter proofs with unrealistic assumptions, otherwise straight CDH with
>> tightness loss) in the random oracle model.
>>
>> SPAKE2-EE has the same properties as SPAKE2 with respect to these two
>> options.  It also has another option, which is that Alice and Bob use
>> either temporary identities (IP address, etc) or even just random nonces,
>> and replace M with h*Elligator(H(nonce_M,password)) and likewise for N.
>>
>>
>>
>> Augmentation:
>>
>> SPAKE2 can be augmented, where the server's credentials (i.e. Bob's
>> credentials) are not sufficient to log in.  This is accomplished by storing
>> g^password2, where (password,password2) is the output of the key
>> strengthening function.  Alice can compute g^(y*password2) from Bob's flow
>> because she knows password2 and g^y.  Bob can compute it because he knows y
>> and g^password2.  So they can throw g^(y*password2) into the hash function
>> when they compute the session key.  Dan and Victor's book calls this PAKE2+
>> and contains a security proof, but then again that book isn't published.
>>
>> I suspect that many PAKEs can be augmented in a similar way, but they
>> usually aren't specified with augmentation.
>>
>> SPAKE2 can even be doubly augmented, where Alice does the same thing, but
>> I'm not sure if there's any application to that.
>>
>> Anyway, because SPAKE2EE only affects M^password and N^password, it
>> doesn't interfere with this augmentation scheme.
>>
>> Questions?  Comments?  Corrections?
>>
>> Cheers,
>> -- Mike
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves
>>
>
>
>
> --
> Michael Scott
> Chief Cryptographer
> CertiVox Ltd
> Tel (353) 86 3888746
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150219/c91c18b5/attachment.html>