Re: [Cfrg] On the differences of Ed25519/448 and how it affects a vote on twoshakes-d

[Gilles Van Assche <[e-mail]>]

Dear all,

On Wed, Dec 09, 2015 at 10:08:26AM +0100, Simon Josefsson wrote:
> If we select twoshakes-d, I believe we should consider separating
> Ed25519(ph) and Ed448 into two documents. While sharing some elements,
> they have become different beasts. Ed25519(ph) is domain separated by
> naming, Ed448 will be domain separated by parameters. The separate
> algorithm Ed448ph no longer makes any sense; whether to prehash or not
> becomes a parameter to the process instead. 

Another point of view could be that Ed448 and Ed448ph are still
distinctly-named algorithms (i.e., symmetrically with Ed25519 and
Ed25519ph), but thanks to the domain separation brought by twoshakes-d
in the internal hash they enjoy the property that a public key can be
certified for one, for the other or for both. As far as I have seen,
twoshakes-d is the only proposal so far that offers that property.

> If the twoshakes-d domain separation is a good domain separation
> algorithm or not is something I don't feel qualified to judge, but I
> don't feel comfortable with it as it is novel.  The algorithms will
> behave different and have different security considerations.

With the point of view above, there is no problem if a public key is
used in either Ed448 or Ed448ph. This follows from that if f(x) is a
sound hash function, then so is f(dom|x) for a fixed prefix "dom".

With a public key used for both Ed448 and Ed448ph, the internal hash can
be viewed as a tree-hash mode on top of SHAKE256, such as:
    without pre-hashing:
        H(x|M)=SHAKE256(dom00|x|M), or
    with pre-hashing:
        H(x|M)=SHAKE256(dom10|x|SHAKE256(dom11|M)),
where "domXY" follows Bryan's coding with X separating between PureEdDSA
and HashEdDSA and Y separating between the internal hash and the
prehash. The security of this domain separation scheme follows from
checking the sufficient conditions defined in [1].

Kind regards,
Gilles

[1] Bertoni et al., Sufficient conditions for sound tree and sequential
hashing modes, IJS 2013