Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto

[Jeff Burdges <[e-mail]>]

On 25.07.19 01:31, Jack Grigg wrote:
> The ability for ristretto255 implementations to interoperate, despite
> using different internal representations, is contingent on implementors
> following the normative requirement that the internal representations
> are not exposed, or operated on except via the Ristretto APIs. This
> precludes any mapping from ristretto255 elements to edwards25519 points.

This does not explain the problem because an implementation could use
any representation it liked and still expose or not expose any maps it
likes.  We still using GF(2^255-19) after all, so it's just a bit more
work for some than for others.

The real issue is that there are two such mappings, depending upon the
branch of the inverse square root chosen.  These two interoperate
seamlessly, provided the mapping is not exposed.  If however the mapping
is exposed later then they suddenly differ.  The problematic scenario goes:


Joe implements the basic Ristretto using generic math libraries that
expose suitable arithmetic, so Joe does not delve into the arithmetic
further.  Joe's Ristretto passes all test vectors for functionality he
implemented, making it fully compliant with the basic implementation.

Joe later expands his protocol by adding and using the mapping, using
the form of the mapping natural given the arithmetic he inherited.
Again everything works, so now people depend upon Joe's mapping.  Joe
does not however check all newly applicable test vectors from the
standard because everything works fine.

Joe expands his protocol to interoperate with another implementation.
Now suddenly everything breaks because the mappings differ.  Yet both
incompatible forms are deployed.


If almost all uses needed the mapping, then yes you could standardize
it, but most do not, and using the mapping incurs cofactor worries.  So
the mapping would occupy a niche poorly implemented layer of the
standard, and the above scenario sounds likely.

Jeff