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

[Michael Hamburg <[e-mail]>]

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 <[e-mail]> wrote:
> 
> 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:
>> 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
>> <[e-mail]> wrote:
>>> On Thu, 2015-10-22 at 16:57 -0400, Greg Hudson wrote:
>>>> 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.
>>> 
>>> 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
>>> 
>>> _______________________________________________
>>> Cfrg mailing list
>>> [e-mail]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>> 
>> 
>> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg