[curves] XEdDSA specification

[Trevor Perrin]

On Fri, Oct 28, 2016 at 2:40 AM, Brian Smith <brian at briansmith.org> wrote:
> On Thu, Oct 27, 2016 at 7:44 AM, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> Sure, what do you think needs to be clarified, exactly?  The math
>> seems clear, I'm guessing you think "glitch" attacks need to be
>> defined?
>
>
> It wasn't clear to me that "glitch" referred to glitch/fault attacks.

I'll clarify that, you're right that "fault" is the more generic term.


>> > It seems like it would be better to incorporate the randomness into the
>> > state of the hash function as early as possible to reduce risk of some
>> > (non-timing) differential side-channel attacks on the hashing step.
[...]
> Consider this "best of both worlds" scheme:
>
>      r = hash1(a || [first half of Z] || M || [second half of Z])

Huh, interesting.  I've thought more about leakage of nonce bits,
which is dangerous because even a leak of a few bits can be
accumulated across many nonces into an attack (e.g. [2]).

But it's also possible that hashing a secret key with attacker-chosen
messages could leak that key through "differential" analysis of power
or electromagnetic side-channels.

That leakage is probably small, so a system that has to worry about
hardware attacks like this probably has a lot of other things to worry
about.  But if we can cheaply make the design more robust, that's not
a bad thing.

In your construction, the "first half" keeps the secret "a" from being
directly mixed with the message.  That could help against differential
power/EM analysis, if the randomness is good.

The "second half" would randomize the nonce even if earlier collisions.

I don't see anything wrong with that.  It's still simple, but perhaps
more robust against an exotic threat (power/EM sidechannel leakage in
hash, plus attacker-chosen messages).

Other opinions on this? (or other ideas)?


>> > Why is Z fixed at 64 bytes? That is, why is its length not a function of
>> > the
>> > size of the key and/or the digest function output length
[...]
> OK. I think one might argue that it is overkill to use a Z larger the |p|
> and typically Z-like values are the same size as |p| so it would be more
> consistent with existing practice and more intuitive to use a |p|-sized Z.

For discrete-log signatures you need to make sure the nonce is
unbiased, so one technique is to reduce a value much larger than the
subgroup order by the subgroup order (e.g. FIPS-186 recommends
choosing a value that's 64 bits larger).

So it's traditional to use larger values here.

But I agree there should be a Rationale section that explains things like this.


> TNotice in the email I'm replying to now, you seem to be
> intending that the scheme should be usable even with a compromised RNG to
> some extent, which makes me wonder whether a good RNG is a requirement or
> just nice-to-have.

It's intended to be secure even with a weak RNG, but with more
assumptions about the hash, and private scalar, and exotic attacks
(per above) that randomization helps with.  So I'd rather not give
people the idea the RNG is optional, or could be skimped on.


>> So I think "p" and "q" are good choices, considering?
>
>
> It is not a big deal but IMO the more consistency between this and the EdDSA
> specification, the better. I don't know why the EdDSA specification uses "L"
> but I don't see any harm in using "L" here, and I do see a benefit in making
> it easier to understand this specification relative to the EdDSA
> specification.

The Ed25519 and EdDSA specs from DJB et al use "l", but I think that's
a problem typographically.

The CFRG work-in-progress draft uses "L", but nothing else does, and
that's inconsistent with the XEdDSA convention of using lower-case for
integers (scalars, coordinates) and upper-case for other things
(points, raw byte sequences).  I think that convention helps
readability, so I'm still pretty happy with (p, q).


>> > Section 2.5 says "since the first |p| bits encode an integer greater
>> > than
>> > p." I think it would be useful to add a clarification such as "(This is
>> > why
>> > it is required 2**|p| - 1 - i > p.)" or otherwise clarify the motivation
>> > for
>> > that precondition.
>>
>> OK, I was hoping that was clear, but will try to clarify.
>
>
> I think it actually was pretty clear.
>
> Since only small values of |i| are actualy used in the spec, the main
> takeaway the reader should make is that this scheme can't work for any p
> which is a Mersenne prime, AFAICT. That doesn't seem significant given the
> curves that people are presently using, but it might be useful to make
> crystal clear for anybody trying to use it with different curves in the
> future.

OK, good point.


>> [1] https://moderncrypto.org/mail-archive/curves/2014/0002

oops, [1] https://moderncrypto.org/mail-archive/curves/2014/000227.html

[2]  https://eprint.iacr.org/2013/346.pdf

Trevor