Re: [MLS] Re-randomized TreeKEM

[Richard Barnes <[e-mail]>]

FWIW: I did a quick PoC implementing the update primitive on top of
OpenSSL, within the crypto framework of mlspp.  It wasn't trivial, but it
wasn't too painful.  It is almost certainly not constant-time.

https://github.com/cisco/mlspp/pull/59/files#diff-8c57ca8ea136d0bb8c846c77ae5b9e78R665

On Thu, Oct 24, 2019 at 4:19 PM Joel Alwen <[e-mail]> wrote:

> On 24/10/2019 12:09, Raphael Robert wrote:
> > This means that vendors/implementors have to implement something at a
> new layer that is somewhere in between the crypto library and the protocol
> layer.
>
> Yeah, thats a good point. To me, proposing a reasonable way to build UPKE
> on top of, say, libsodium is one of the main
> things I want to figure out right now (along with better understanding of
> how Mult() for X25519 can fail). Basically,
> this means implementing Mult() from, say, libsodium as going from Mult()
> -> multiplicative UPKE should be very
> straightforward using what I'd expect even the most basic interface for
> any X25519 implementation to provide. I guess
> the challenge here is going to be that both clamp() and the composite
> order are neither exported nor directly accessible
> in libsodium?
>
> In any case, if Mult() needs implementing from scratch then some of the
> risks I see here are:
> - Side-Channels: Mult() operates on secret keys so really it should be
> implemented with side-channel free code (e.g.
> constant time, memory access, etc.). We could mitigate this by proposing a
> specific implementation similar to whats done
> in RFC 7748.
> - Memory management: Secret keys being exported out of an X25519 library
> need to be handled safely in memory (e.g. 0-ed
> out before free, don't swap to disk, etc.) Libsodium does provide some
> memory-management functions for this very purpose.
> - Good Entropy: The re-randomizer d' needs to be sampled uniformly and
> independently. (Again I think most crypto
> libraries provide functions to do this.)
>
> Probably a naïve attempt at such a list of risks & mitigations. But making
> this stuff explicit seems useful for later on
> if we put this into the MLS RFCs (not to mention for a separate addendum
> RFC for 7748 describing the key-rerandomization
> technique on its own). So any input on the expected risks (and possible
> mitigations) would be very appreciated!
>
>
> On 24/10/2019 12:09, Raphael Robert wrote:
> > Finally I also understand that because of the clamping the actual
> security level of DH operations with curve 25519 is
> > not as clearly understood as it is the case with X25519 now.
>
> Not sure I follow what you mean here. One the one hand the UPKE
> construction is built on top of the X25519 (or X448)
> group not just Curve25519. In particular, Mult() uses the same point
> representation, clamping of scalars and scalar
> multiplication as specified in RFC 7748.
>
> On the other hand, if anything, I'd have thought questions about exact bit
> security are the other way round. It's X25519
> that does the clamping so that's where the question about exact bit
> security would arise no? Clamping isn't inherent to
> Curve25519 though; rather its just one way to do scalar multiplication
> mapping into a prime order sub-group based on the
> composite order Curve25519 group. But, as shown by Ristretto, other
> methods are possible that completely avoid clamping
> (and also happen to be both additively and multiplicatively homomorphic).
> In particular, I believe CDH, DDH and all the
> other usual crypto hardness assumptions are equivalent for Curve25519's
> prime order subgroup and for the Ristretto
> group. Not sure thats true for X25519 though.
>
> In any case, I'm no expert on this stuff so feel free to correct me if I'm
> wrong. :-)
>
> - Joël
>