Subject: Re: [Cfrg] comments on draft-irtf-cfrg-spake2-02.txt

From: Greg Hudson <[email-masked]>
Date: Thu, 22 Oct 2015 16:57:33 -0400

Dan Harkins wrote:
> You might think about publishing the code you're using to generate M
> and N as an appendix.

I was able to reproduce the P-256 and P-521 M and N values with the
following Python code (which is unnecessarily quadratic, but it reads
more clearly this way):

  def iterated_hash(seed, n):
      h = seed
      for i in xrange(n):
          h = SHA256.new(h).digest()
      return h

  def bighash(seed, start, sz):
      n = -(-sz // 32)
      hashes = [iterated_hash(seed, i) for i in xrange(start, start + n)]
      return ''.join(hashes)[:sz]

  def gen_point(seed, ec, order):
      for i in xrange(1, 1000):
          pointstr = ec.canon_pointstr(bighash(seed, i, ec.nbytes_point()))
          try:
              p = ec.decode_point(pointstr)
              if ec.mul(p, order) == ec.identity():
                  return pointstr, i
          except Exception:
              pass

combined with a home-grown Weierstrass curve implementation using SEC 1
compressed points.  The canon_pointstr() method in that implementation
is:

    def canon_pointstr(self, s):
        return chr(ord(s[0]) & 1 | 2) + s[1:]

The check for point order isn't really needed for P-256 and P-521 as
they have cofactor 1, but it would be needed for other curves such as
the ones used in ed25519 and ed448.  The successful iterations were 5
and 3 for P-256 M and N, and 368 and 343 for P-521 M and N.  For P-521,
most trials are invalid because the high-order byte of a valid x
coordinate can only have values 00 or 01, but the algorithm is too dumb
to know that.

I believe the points were originally generated using the Java code in:
http://www.ietf.org/mail-archive/web/cfrg/current/msg06117.html

Salient differences between the code and the current draft text (which
I believe Watson Ladd is planning to rewrite):

* Each trial string begins at the beginning of a hash block.

* Trial strings use overlapping ranges of hash blocks.  For P-521 where
  we need three hash blocks per trial string, the first trial is
  H1|H2|H3 truncated, the second is H2|H3|H4 truncated, etc..

* The first byte of each trial string is set to 0x02 or 0x03, depending
  on its original low-order bit.

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 22 Oct 2015 17:10:27 -0400

>   on its original low-order bit.

Thanks for your independent verification! I had drafted an email today
about the cofactor issue. Thanks for bringing it up.

In short, the method used for generating constants should ignore valid
points which, when used as generators, have a subgroup order that is
different than the group-default generator. Failing to do this could
lead to a compromise.

Nathaniel

---

From: Watson Ladd <[email-masked]>
Date: Thu, 22 Oct 2015 18:24:59 -0400

I'm using quotients, not subgroups. This is not obvious, but I think
the issue you are referring to cannot happen.

My apologies for not pushing a new version out in a reasonable
timeframe: I've been a bit busy. Thanks to everyone for submitting
comments.

On Thu, Oct 22, 2015 at 5:10 PM, Nathaniel McCallum
<[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 22 Oct 2015 18:29:52 -0400

The issue arises implicitly in the multiplication wM or wN. If
multiplication with M or N produces a different (i.e. smaller) number
of values than multiplication against G, then the strength of the
authentication (though not the key exchange) is weakened.

On Thu, 2015-10-22 at 18:24 -0400, Watson Ladd wrote:
> > > > You might think about publishing the code you're using to
> > > > generate
> > > > M
> > > > and N as an appendix.
> > > 
> > >       hashes = [iterated_hash(seed, i) for i in xrange(start,
> > > start +
> > > n)]
> > > combined with a home-grown Weierstrass curve implementation using
> > > SEC
> > > 1
> > > and 3 for P-256 M and N, and 368 and 343 for P-521 M and N.  For
> > > P-
> > > 521,
> > > coordinate can only have values 00 or 01, but the algorithm is
> > > too
> > > dumb
> > > to know that.
> > > 
> > > I believe the points were originally generated using the Java
> > > code
> > > in:

---

From: Michael Hamburg <[email-masked]>
Date: Sat, 24 Oct 2015 17:30:46 -0700

I would expect to see a problem if M and N are not multiples of the generator G; or if the x in xG is not chosen uniformly in [0,ord G); or if ord M and/or ord M were small.  In the first case, wM mod (G) would leak.  The second case might be quite difficult to exploit, but the security proof wouldn’t hold.  The third case would result in weak authentication.

If M and N don’t generate the whole group but do generate at least the p-torsion, the loss in authentication should be negligible.  In fact, according to the document specified, it’s probably zero since w is specified to be reduced modulo p.

— Mike

> On Oct 22, 2015, at 3:29 PM, Nathaniel McCallum <[email-masked]> wrote:
>