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

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

2019-07-25 02:46 GMT+02:00 Riad S. Wahby <[e-mail]>:
> Hi Jack,
> 
> Thanks very much for the answers. Can you please help me understand
> a bit more what's going on?
> 
> (At the risk of protesting too much, I want to be clear that the
> concerns below are sincere: I really cannot square the claims in
> this thread with the content of the document or my understanding of
> Decaf/Ristretto. As background, I've read the Decaf paper carefully
> and implemented it fully. So I don't think it is much of a stretch
> to suppose that if I can't parse what's going on in this document,
> there are plenty of others out there who won't be able to, either.)
> 
> Jack Grigg <[e-mail]> 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.
> 
> Sorry, I don't understand. Per the rest of your email, DECODE as
> specified in Section 3 is exactly such a mapping. So how am I to
> interpret what you've said above?
> 
> Concretely: let's say I want to output the sum of two ristretto255
> points, P1 and P2. To do that, I think I need to do something like this
> (all functions as specified in Section 3):
> 
>     P1_decoded = DECODE(P1)
>     P2_decoded = DECODE(P2)
>     Q_decoded = P1_decoded (+) P2_decoded
>     Q = ENCODE(Q_decoded)
> 
> The problem is, the document as currently written does not tell me
> how to implement the (+) operator on the third line above. It implies
> that such an operator exists (in Section 3.3), but as far as I can
> tell it does not tell me what it is.
> 
> Is it edwards25519 point addition? If so, then I just don't see how
> it can be true that the "internal representation" in Section 3 is
> not an edwards25519 point. (Sure, equality testing is different.
> What else is different? What is the same?)
> 
> > Put another way: if a mapping from ristretto255 elements to edwards25519
> > points existed, any higher-level protocol that leveraged this mapping would
> > only work with ristretto255 implementations specifically constructed over
> > edwards25519, breaking interoperability across ristretto255 implementations.
> 
> It's not obvious (to me!) from the draft, the Decaf paper, etc.
> why this should be true. So I think it will be important to spell it
> out somewhere (or maybe I just need to read Decaf more carefully---in
> which case, apologies).
> 
> Here's something I might stupidly decide to do:
> 
>     P_decoded = DECODE(P)
>     P_montgomery = Edwards_To_Montgomery(P_decoded)
>     Q_montgomery = my_scalar (*) P_montgomery
>     Q_decoded = Montgomery_To_Edwards(Q_montgomery)
>     Q = ENCODE(Q_decoded)
> 
> Here, P_montgomery and Q_montgomery are points on curve25519,
> Edwards_To_Montgomery and Montgomery_To_Edwards correspond to
> the birational map of RFC7748, Section 4.1, and (*) is scalar
> multiplication on the Montgomery curve.
> 
> Meanwhile, a better implementor might instead do
> 
>     P_decoded = DECODE(P)
>     R_decoded = my_scalar (*) P_decoded
>     R = ENCODE(R_decoded)
> 
> Here, (*) is scalar multiplication on edwards25519.
> 
> So, finally, the question: is the claim that R != Q? I don't see
> how that can be true given the birational equivalence of curve25519
> and edwards25519.
> 
> Alternatively, if R == Q, then what's the problem with converting
> back and forth between Edwards and Montgomery points, and why am
> I not correct in thinking of P_decoded as an edwards25519 point?
> Is it just that certain operations (equality checking, ...???)
> don't work the same as a "real" edwards25519 point?
> 
> > It is an explicit design decision to define the Ristretto API solely in
> > terms of the four provided operations:
> 
> OK, but this can't actually be true, because there are other operations
> alluded to (but not defined) in the document, and without those
> operations (point addition, point inversion, scalar multiplication)
> ristretto255 doesn't actually let me do anything.

The critical section here is Section 3.3 of -01, which reads

> 3.3.  Operations on internal representations
>
>   Group addition, subtraction and (multi-)scalar multiplication are
>   performed without modification using the internal representations.
>
>   Implementations MUST NOT perform any other operation on internal
>   representations.

and explicitly allows addition and scalar multiplication. Maybe we
should also call out inversion, but I would want to hear from the other
authors before confirming that.

To get to the rest of your comments in aggregate: ristretto255 is, at
its core, an abstraction. To downstream users (specs and implementors)
it intentionally provides a specific closed set of operations on an
abstract prime-order group.

The main challenge that we'd appreciate wording help with is that
of defining the behavior of the group normatively through the example
of its edwards25519 implementation, while making it clear that the
edwards25519 internal representatives are an implementation choice,
and must not be directly generated nor accessed, in order to make
alternative implementations possible.

The other authors would be able to present the details and advantages of
the alternative implementations better than me, but with my API designer
hat on, I want to mention that there is inherent value in clearly
defining the public API surface of a cryptographic primitive: it can be
fully assessed in its security and fitness for the job, leaving no room
for misuse. We're here after all because Curve25519 was designed for
authenticated Diffie-Hellman key exchanges, but did not enforce that in
its API, and was used where it's not safe.

We believe sections 3.2 and 3.3 provide all operations necessary to
implement the "prime order group" interface (and if not, we should
specify the missing ones). Given that, we want to disallow abstraction
breaches that might or might not compromise its security.

(Notwithstanding the fact that someone who read the Decaf paper like
you might indeed make safe abstraction breaches—modulo alternative
implementation compatibility. The point is that we are designing a
primitive that aims to be misuse resistant because it neither requires
nor allows such attempts.)

> > I agree! This is what the current draft aims to do, by allowing
> > implementors to use whatever internal representation they choose.
> > Specifically, the document intends to specify the normative behavior of the
> > group and the API, while providing informationally the details of one
> > possible implementation, the one based on edwards25519. If there are ways
> > we can make this more clear, please do send suggestions.
> 
> I'm hoping to get to the point where I can make such suggestions,
> but first I have to actually understand what's going on!
> 
> Here's my current best guess:
> 
> ENCODE and DECODE convert ristretto255 points into some internal
> representation. For the algorithms in Section 3, that internal
> representation is edwards25519, except that equality testing is
> different (specifically, it must use EQUALS) and maybe some other
> things are different (but I don't know what).
> 
> Operations are the same as for edwards25519, but the only ones that
> are allowed are addition, inversion, and multiplication.
> 
> Implementors can maybe use a different internal representation. There
> is no obvious way to do this given the information in the document.
> In particular, there is no group isomorphic to Curve25519 with order l,
> because Curve25519 has order 8 * l.
> 
> > > If my interpretation is correct, then I suggest the authors provide
> > > a mapping that implementations MAY use, as a way of assisting
> > > implementors in getting things right. This is probably as simple as
> > > citing the birational map between edwards25519 and curve25519 from
> > > Section 4.1 of RFC7748, and explaining how to use this map in concert
> > > with the Ristretto functions.
> > 
> > Per above, the way to ensure implementors get things right is to prohibit
> > such a mapping (which would necessarily be breaking the API provided by the
> > Ristretto functions, rather than being a mapping operating behind them).
> 
> Does the document prohibit such a mapping? Is this the intent
> of Section 3.3? What would go wrong if I did this, assuming that
> after mapping (say) an edwards25519 point to a curve25519 point, I
> continued to observe the restriction that only addition, inversion,
> and multiplication are allowed?
> 
> (I think this is the same as my question about Q and R, above.)
> 
> > This is a salient point. We in fact mean edwards25519 throughout the text,
> > but almost every implementation of edwards25519 that isn't built into an
> > Ed25519 implementation is provided in a Curve25519 library, and I figure
> > the latter is more familiar to readers (even RFC7748 only contains a single
> > occurrence of "edwards25519"). I personally would be happy to replace all
> > occurrences of "Curve25519" with "edwards25519", but I would like to hear
> > from the other authors on this point.
> 
> On the other hand, RFC7748 contains 12 occurrences of "curve25519"
> (17 if you turn off case sensitivity) and every one of those refers
> to the Montgomery curve, not the Edwards curve. So as far as I can
> tell there is no way for a reader to understand this document as
> currently written other than to guess that when you say "Curve25519"
> you actually mean "edwards25519", not "curve25519".
> 
> > If all occurrences of "Curve25519" were replaced with "edwards25519", would
> > this be clearer? For this particular example, the intention is that DECODE
> > takes a 32-byte string and returns either an error, or a ristretto255
> > element that is internally represented as a point (X : Y : Z : T) on
> > edwards25519.
> 
> Sure, that would help. But then it's impossible to understand the
> claim from two emails ago that there's no mapping from ristretto255
> to edwards25519, because ENCODE and DECODE appear to be exactly
> such mappings!
> 
> Sure, it's non-normative, I get that, no worries. But how is it
> possible for me to understand the claim that mapping to edwards25519
> would break compatibility when the document demonstrates exactly such a
> mapping and claims that all other mappings must be compatible with it?
> 
> Thank you preemptively for putting up with my confusion,
> 
> -=rsw
>