[curves] XEdDSA specification

[Trevor Perrin]

On Sat, Oct 29, 2016 at 11:39 PM, Brian Smith <brian at briansmith.org> wrote:
> On Fri, Oct 28, 2016 at 6:47 AM, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> I'll clarify that, you're right that "fault" is the more generic term.
>
>
> Simply, I was unsure whether "glitch" was being used colloquially, to
> indicate some unspecified problem, or whether it was referring to glitch
> attacks in general, or a specific type of glitch attack, or fault attacks in
> general, or faults in general (accidental or induced).

I'll add a little more text about faults.  For example, mention that
flipping a single bit in a randomized discrete-log signature
calculation is typically insufficient to leak the private key.  Also,
add a citation for Jivsov [1].


>> 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).
>
>
> The thing that is reduced mod q is the SHA-512 digest, not Z, right? I don't
> see how the FIPS-186-suggested technique applies.

We're reducing a 512-bit hash output, so adding 512 bits of entropy to
the input hopefully means the output gets a full 512 bits of entropy.

Which is overkill but it's easy and simple, and means Z doesn't need
to change sizes depending on curve (e.g. larger Z for 448).  It also
might help if your RNG is slightly weak, so I still like |Z|=512.


> In your justification for why it is fixed at 64 bits, you imply that it is
> kinda-sorta a function of |q|. Notice that 64 bytes = 512 bits = 448 + 64.
> Using the above reasoning, would a 448-bit curve be the maximum supported by
> this scheme? Or, for a 512-bit curve, would we require a Z that is at least
> 512 + 64 = 576 bits = 72 bytes?

Depends, if the 512-bit prime is close to 2^512 maybe you can convince
yourself a 512-bit hash is good enough.  Or maybe you want to follow
NIST's generic advice and add 64 bits, or follow the DJB/EdDSA generic
advice and go to 1024 bits.

So I would dodge that question, but I might add that a 512-bit hash
(and 512-bit Z) is sufficient for curves up to 448 bits in size (or
|q| <= 448 to be exact), following FIPS 186-4's advice on 64 "Extra
Random Bits".

For a larger curve you'd have to think more, and you might need
large-output constructions (e.g. HKDF, XOF, FIPS 186-4 Appendix B,
EdDSA's SHA512/832 or SHA512/912 [2], etc).  Since other curves are
less useful (IMO) and different people might prefer different
large-output constructions, it seems best to leave that out of scope.


>> 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.
>
>
> Understood. But, the questions that entered my mind when reading the
> document were more along these lines:
>
> 1. Is using XEdDSA with a deterministic nonce equally, less, or more safe
> than using EdDSA (with a deterministic nonce)?
>
> 2. Ditto, for VXEdDSA.

About the same, in my opinion.

In terms of provable security in the Random Oracle Model, it's the same.

Because "a" is used in the first hash (XEdDSA), instead of an
independent secret key (EdDSA), a deterministic XEdDSA might have a
slightly increased side-channel risk of leaking "a",  but I think
randomization would help both algorithms reduce side-channel risk.


> 3. Is using XEdDSA with an actively malicious (attacker-controlled) RNG
> equally, less, or more safe than using EdDSA (with a deterministic nonce)?
>
> 4. Ditto for VXEdDSA.

DJB has discussed a malicious RNG that can read (but not write)
memory, and has no other way to exfiltrate secrets except choosing RNG
output.  Such an RNG could bias the discrete-log signature nonce, to
make the private key extractable [3].

I think that's less likely than fault and physical sidechannel
attacks, but it's true that the RNG adds this tradeoff.

Trevor

[1] https://www.ietf.org/mail-archive/web/cfrg/current/msg06759.html
[2] https://ed25519.cr.yp.to/eddsa-20150704.pdf
[3] https://blog.cr.yp.to/20140205-entropy.html