Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-08.txt

[Greg Hudson <[e-mail]>]

I did some additional digging, and want to make sure I've laid out my
argument clearly.  Apologies for the length.

The -08 draft made two changes to the non-augmented SPAKE2 description
which I believe are misguided:

* The private x and y coefficients were in "[0, p*h) divisible by h" but
  are now in "[0,p)".  In other words, x and y were changed from scaled
  coefficients (divisible by h) to unscaled coefficients.

* A verification step was added: "Upon receipt of T, B computes T*h and
  aborts if the result is equal to I" with clarification "A and B
  multiply protocol messages from each peer by h so as to avoid small
  subgroup attacks, but the result of the multiplication is not used for
  operations other than the comparison against I and the non-multiplied
  value is used in subsequent calculations."

I want to address the verification step first.  To do so, I want to
consider the simpler scenario of a Diffie-Hellman key exchange over a
curve with cofactor 1.  In this algorithm, each party picks a private
coefficient from [0,p) and sends xP or yP, and each party computes K=xyP
by multiplying its private coefficient by the other party's public
point.

Should each party check whether the other party's public point is I (or
equivalently, if K=I), and throw it out?  The cases for throwing out K=I
are that everyone will know the shared point, and that the party in a
position to do the verification doesn't contribute anything to the
result (xI=I for all values of x).  Note that this verification step
causes legitimate executions of the algorithm to break in the unlikely
case that either party happens to pick x=0 or y=0; this can be fixed by
selecting the private coefficients from (0,p) instead of [0,p).

K being non-secret isn't an interesting attack; an attacker can achieve
the same result by executing the algorithm correctly and then revealing
K to the world.  The non-contributory behavior (the ability to force a
specific channel key) does pose a problem if channel-binding is used by
an authentication protocol on top of the unauthenticated DH channel.
Checking for K=I foils this attack, but an implementor might leave this
step out while still interoperating.  A better way to foil this attack
at the protocol level is to hash the shared point together with the
public keys to derive the channel key; this measure is more robust
because if an implementor leaves out that step, they won't interoperate.
(See [1] for a related example of this robustness argument.)  Note that
RFC 7748 section 6.1 specifies "a key-derivation function that includes
K, K_A, and K_B".

The question of contributory behavior is discussed in the context of
Bernstein description of X25519 [2].  (X25519 is more complicated
because the cofactor is 8, and it uses Montgomery coordinates which
admits points on the twist, but the question still holds for cofactor 1
and more traditional coordinates).  The issue is also discussed in RFC
7748 section 6 and 7; the RFC notes that "Protocol designers using
Diffie-Hellman over the curves defined in this document must not assume
'contributory behaviour'" and permits an optional verification check
that K!=I, but notes that many implementations don't do it.

If the curve has cofactor h>1, there are two additional considerations
for malicious public points (see also [3]):

1. There are additional points of small order.  For instance, if h=8,
there is one point of order 2, two points of order 4, and four points of
order 8.  Sending any of these low-order points results in a small
number of possible values for the shared key, similarly to sending I.

2. There are additional points of order p times divisors of h.  For
instance, if h=8, there are p-1 points of order 2p, 2p-2 points of order
4p, and 4p-4 points of order 8p.  Sending any of these points results in
a large number of possible values for the shared key--but if the
attacker can find out what the shared key is, they can test its order
and extract a few low-order bits of the other party's private
coefficient.

A simple way of eliminating these extra concerns is to pick private
coefficients which are scaled by h, i.e. from [0,hp) divisible by h.
This change introduces two extra multiplications by h into the
algorithm, one during public point generation and the other during the
computation of K.  Multiplying a point within the p-order subgroup by h
produces another point within the subgroup, with the same range of
possible values (since h is relatively prime to p).  Multiplying a curve
point outside of the p-order subgroup by h results in a point within the
subgroup (e.g. a point of order 8p, multiplied by 8, has order p; a
point of order 4, multiplied by 8, has order 1).  This technique is
sometimes called "clearing the cofactor".  X25519 (RFC 7748 section 5)
does this when massaging random bytes to a scalar value; note that in
this massaging, the three lowest-order bits are set to 0, forcing
divisibility by 8.

Let's return to SPAKE2.  In SPAKE2, the public points are masked by
adding wM or wN: T=xP+wM and S=yP+wN.  The computation of the shared
point unmasks the other party's public point by subtracting wM or wN:
K=x(S-wN) or K=y(T-wM).  The final step is still to multiply by your own
private coefficient, just as in Diffie-Hellman.

Is a verification step necessary in SPAKE2?  I think it is unnecessary
and undesirable, for the following reasons:

* If S or T is a point of small order such that hT=I, the shared point K
  still has a contribution from the legitimate party, -xwN or -ywM, with
  the full range of the prime-order subgroup as possible results.  Even
  if the attacker can learn K, they cannot use it to launch an offline
  attack against w, because they do not know x or y.

* SPAKE2 key derivation folds in the public points, again forcing
  contributory behavior, and foiling an MITM attack by an attacker who
  knows w.  (In this attack the attacker sends T=wM to one party and
  S=wN to the other, forcing K=0 for both parties, in an attempt to get
  both parties to use the same key in order to foil channel binding.)

* Verifying S and T breaks the unlikely case where x=0 or y=0.
  Verifying K breaks the unlikely case where xP=-wM (e.g. if x and w
  both happen to be 0, but also in other cases).

* The Abdalla-Pointcheval paper [4] does not describe any verification
  step.  Although I don't believe they considered groups with stray
  elements outside the prime-order subgroup, they must have considered
  the identity element.

Clearing the cofactor is of value in SPAKE2, as it is in Diffie-Hellman.
For example, if an attacker sends a point T of order 8p, T-wM will also
have order 8p, and the order of K=y(T-wM) will reveal a few low-order
bits of y.  Choosing y from [0,hp) divisible by h means those low-order
bits are always 0, so no information is revealed.

Therefore:

* We should used scaled (divisible by h) coefficients in SPAKE2, as the
  -07 draft did, in order to clear the cofactor

* We should not add a verification step.

* SPAKE2+ should use a scaled (divisible by h) w1 value, to clear the
  cofactor when computing Z and V.  This would be a change from -07.

[1] https://mailarchive.ietf.org/arch/msg/cfrg/3co2iEaaeKRDixtML3OKo9aV9cU
[2] http://cr.yp.to/ecdh.html#validate
[3] https://safecurves.cr.yp.to/twist.html
[4] https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf