[Cfrg] draft-hdevalence-cfrg-ristretto and draft-irtf-cfrg-hash-to-curve

["Filippo Valsorda" <[e-mail]>]

The discussion about draft-hdevalence-cfrg-ristretto so far brought up a
number of areas worth clarifying which we plan to address in -02. Aside
from that, if I'm not mistaken, the only other topic of discussion was
the interaction with draft-irtf-cfrg-hash-to-curve.

I am bringing it into its own thread and adding my remarks at the bottom.

2019-07-26 22:09 GMT+02:00 Henry de Valence <[e-mail]>:
> Riad S. Wahby <[e-mail]> wrote:
> > 7. Make FROM_UNIFORM_BYTES incorporate edwards25519-SHA256-EDELL2-RO
> >    by reference, and specify a DST (domain separation tag, see Section
> >    5.1 and 5.3 of hash-to-curve), e.g., "Ristretto255-Hash".
> >
> > 7.1. Also, rename FROM_UNIFORM_BYTES to either FROM_BYTES or FROM_STRING,
> > and remove the length and distribution requirements on the input.
> > The hash-to-curve document handles the uniformity internally while
> > ensuring that conforming usage meets relevant security requirements.
> > There's no reason to make higher-level protocols reinvent the wheel.
> 
> I don't think this suggestion is a good idea, for a number of reasons:
> 
> 1. edwards25519-SHA256-EDELL2-RO is not compatible with ristretto255, as
> it does not produce valid internal representatives;
> 
> 2. even if it did, ristretto255 implementations are not required to
> use Curve25519 internally, so the hash-to-group method cannot be
> defined in terms of Curve25519;
> 
> 3. ristretto255 already provides a hash-to-group method, which is defined
> so that implementations remain wire-compatible even when changing the
> curve used internally, as noted in the Ristretto website and the Decaf
> paper;
> 
> 4. requiring use of a specific hash function is a layering violation,
> as the definition of an elliptic curve should not depend on use of a
> particular symmetric primitive.
> 
> The FROM_UNIFORM_BYTES function provides a generic hook which handles
> all of the details specific to the ristretto255 group, whose input
> uniformity requirement retains composability with various symmetric
> constructions.  This isn't requiring higher-level protocols to
> reinvent the wheel, but retaining compatibility with them.
> 
> For instance, why should a higher-level protocol that everywhere else
> uses domain-separated SHA3 be forced to use SHA2 for hash-to-group?
> 
> Or, consider a protocol that uses a duplex construction to ensure that
> hash output is not just bound to a single domain separator, but to an
> entire message transcript with arbitrary application domain separation
> messages (e.g., https://merlin.cool).  Why should it be forced to
> launder its domain-separated hash output through a second HKDF
> construction?
> 
> Of course, it would be most preferable to achieve compatibility
> between the ristretto255 draft and the hash-to-curve draft.  But since
> the hash-to-curve draft describes hash-to-curve methods for various
> elliptic curve groups (P-256, secp256k1, Curve25519, etc), while this
> draft is tightly focused on describing a specific group, it seems like
> the cleaner layering would be for the hash-to-curve draft to
> incorporate this draft by reference, and use this draft's
> FROM_UNIFORM_BYTES function to define a
> 
> ristretto255-SHA256-RISTRETTO-RO
> 
> or similar (I'm not 100% confident in my understanding of your naming
> scheme).
> 
> In this way, the hash-to-curve draft defines hash-to-curve methods for
> various elliptic-curve-based groups (P-256, secp256k1, Curve25519, and
> ristretto255), while the ristretto255 draft remains focused on
> definining a single group and retains compatibility with other
> symmetric constructions (e.g., sponge constructions).

I agree with Henry, and I think it helps to think about it in terms of
implementations. As I see it, there are three options.

Option 1: use an existing hash-to-curve method

This is definitely unworkable. A method that hashes to Curve25519 points
is not fit for hashing to ristretto255 because ristretto255 internal
representatives are a different type from Curve25519 points. Internal
representatives are an opaque type that might or might not be a wrapper
around a Curve25519 point, and there's no map between Curve25519 points
and internal representatives.

Option 2: specify FROM_UNIFORM_BYTES in hash-to-curve

This would require putting a method that returns a ristretto255 internal
representative in hash-to-curve. On top of moving a lot of the Ristretto
math to hash-to-curve, that would leak all the complexity of specifying
behavior without mandating the actual curve to the hash-to-curve
specification, and is a major breach of the ristretto255 abstraction.

Think about a ristretto255 implementation,
https://github.com/gtank/ristretto255 for example. The spec requires
it to keep its element type opaque (to preserve the group abstraction,
to guarantee interoperability with other implementations, to prevent
misuse, to allow switching curve, ...), so there is no way for a
hash-to-curve implementation to construct an element from an internal
representative. It's internal after all!

Consequently forcing ristretto255 implementations to also implement
hash-to-curve and making it impossible for generic hash-to-curve
implementations to offer the ristretto255 method sounds wrong.

Option 3: use FROM_UNIFORM_BYTES from hash-to-curve

This is what Henry is suggesting, and it looks like the natural
separation of concerns to me. hash-to-curve is in charge of
parametrizing hashes, defining domain separation, and all the things it
already does. It then generates uniform bytes, and ristretto255 defines
the interoperable map to an opaque group element.

Of course, we'd be happy to contribute such a method to hash-to-curve,
but unlike Option 2 it should be fairly trivial (which in itself
suggests we hit the right level of abstraction).