[curves] Finalizing XEdDSA

[Brian Smith]

Trevor Perrin <trevp at trevp.net> wrote:

> Brian Smith <brian at briansmith.org> wrote:

> hash_0(x) is reserved for other specifications. But, if hash_0(x) is never
>
> used, then it is clear that Curve25519 and Curve448 are fully domain
> > separated, right?
>
> I was thinking about domain separation with respect to the same key.
>
> With respect to separating hash functions for different types of keys,
> I'm not sure that's important, but it's worth mulling over a bit more.
>

I don't think it matters, because for different values of b, signatures
will be different sizes, and for the same value of b, such domain
separation doesn't work. So, forget this idea of mine.


> > In this paper, should we also consider the EdDSA public key to be a
> secret
> > worth protecting?
>
> Where does that make a difference?  You could do const-time
> verification, I suppose?
>

> > 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?
> > (I guess this may depend on whether the EdDSA public key is supposed to
> be
> > secret.)
>
> This can't be randomized, it needs to be deterministic.
>
> There's not a very strong argument for padding, either, since we're
> not trying to make this a PRF based on A (hashing A just prevents the
> possibility of different keys that are equivalent in their VRF
> outputs, which isn't technically a VRF attack, but seems confusing
> enough that it's worth preventing).
>

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.


> > 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.


> > 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)
> >
> > Note that that is equivalent to:
> >
> >     h = hash(P || R || A || M) where P = 2**b - 1 - i || V || Rv
>
> The order doesn't matter.  I see your point about aligning with EdDSA,
> but the current order somewhat matches the "order of appearance" of
> the variables.  Since this is arbitrary, I'm inclined to leave it
> as-is.


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. Also, I think that maximizing
similarity is probably better for maximizing reuse of analysis of EdDSA and
XEdDSA for VXEdDSA. This is also the motivation for my suggestions to use
naming consistent with the EdDSA specification. Note that I'm not
suggesting that you rewrite the paper in this form.

Note in particular how it is more convenient in this factoring to replace
the the hash_i(x) hash family with a prefix_i construct, where prefix_i =
2**b - 1 - i.


# 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

Cheers,
Brian
-- 
https://briansmith.org/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161102/2632e84d/attachment.html>