[curves] Finalizing XEdDSA

[Trevor Perrin]

On Wed, Nov 2, 2016 at 3:00 PM, Brian Smith <brian at briansmith.org> wrote:
>> > In VXEdDSA, will the call to hash_to_point change from hash_to_point(A
>> > || M)
>> > to something similar to the proposed change for the first hashing in
>> > XEdDSA?
[...]
>> This can't be randomized, it needs to be deterministic.
[...]
> I understand it can't be randomized. My question was this: If A is secret
> then when we call hash_to_point(A || M), should we do anything to prevent
> any kind of (side channel) attacks on A where the attacker controls M, like
> we reordered the inputs to hash_1(...) for.

That re-ordering was so that random data could be inserted between the
long-term secret (a) and message (M), to prevent the message from
being directly mixed with the secret.

We can't do that here - even if A is a secret, there's no way to
prevent M from being mixed with it (or a deterministic function of
it).

So I'm not seeing any changes worth making.


>> > In VXEdDSA, every use of a hash function is a hash_i(x). But, in XEdDSA,
>> > the
>> > first use of the hash function is hash_1(x) but the second use of the
>> > hash
>> > function is just hash(x). Why isn't it hash_2(x) instead for the second
>> > hashing?
>>
>> Compatibility with EdDSA.
>
> It seems worth expanding on what exactly compatibility and incompatibility
> is intended. It's unclear to me.

XEd25519 signatures are intended to be equivalent to Ed25519
signatures, just with the public keys converted.  So we need to
calculate "h" the exact same way, i.e. h = HASH(R || A || M).

Agreed this should be explained, somewhere.

(XEd448 may not be identical to the CFRG's version of Ed448, because
they're not using the equivalent curve to X448, but that's a separate
issue).


>> > In XEdDSA and EdDSA, near the end we calculate:
>> >
>> >     h = hash(R || A || M).
>> >
>> > But in VXEdDSA we calculate:
>> >
>> >     h = hash_4(A || V || R || Rv || M).
>> >
>> > Why doesn't VXEdDSA use this instead?:
>> >
>> >     h = hash_4(V || Rv || R || A || M)
[...]
> See below where I try to demonstrate how code that implements both XEd25519
> and Ed25519 would be factored. I would like to do similar for VXEdDSA, which
> is why I think consistency is useful.
[...]
> # Uses naming from the XEdDSA specification.
> xed25519_sign(k, M, Z):
>     pad = ""
>     A, a = calculate_key_pair(k)
>     prefix = prefix(1) || a || Z || pad
>     return ed25519_sign'(A, a, prefix, M)
>
> # Uses naming from draft-irtf-cfrg-eddsa-05.
> ed25519_sign(A, seed, M):
>     a, prefix = hash(seed).split_at(32)
>     return ed25519_sign'(A, a, prefix, M)
>
> # Uses naming from draft-irtf-cfrg-eddsa-05.
> ed25519_sign'(A, a, prefix, M):
>     r = hash(prefix || M) (mod L)
>     R = rB
>     k = hash(R || A || M) (mod L)
>     S = r + k * a (mod L)
>     return R || S

Nice - That works well, another reason for moving Z earlier.

So you're thinking of similarly factoring out h and s computation into
a helper function, with V and Rv moved to a prefix?

Hadn't occurred to me, but I guess that could tilt the argument your
direction, let me think more...

Trevor