Subject: [Cfrg] Fwd: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt

From: Richard Barnes <[email-masked]>
Date: Mon, 4 Nov 2019 18:52:19 -0500

Hi CFRG folks,

This draft is a proposal to address a deficiency in X25519 and X448 that
has been noted a couple of times on this list (e.g., [1]), namely the fact
that multiplication of scalars and point multiplication do not commute.
While looking into applications of updateable public-key encryption in the
context of MLS [2], my co-authors came upon a solution that while not
perfect, works in all but a statistically insignificant number of cases.

The draft describes how to do scalar multiplication in a way that is
compatible with point multiplication in the X25519 and X448 groups,
describes the cases where these algorithms can fail, and provides methods
for detecting failure.  While "move to Ristretto" is also a solution to
this problem, it seemed like a solution for X25519 / X448, even if partial,
might have a slightly faster path to deployment.

As with any -00 draft, feedback is very welcome!  If Go is your preferred
medium, we've also implemented the relevant concepts in the corresponding
GitHub repo [3].

Thanks,
--Richard

[1] https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ
[2] https://eprint.iacr.org/2019/1189
[3] https://github.com/bifurcation/draft-barnes-cfrg-mult-for-7748/

---------- Forwarded message ---------
From: <[email-masked]>
Date: Mon, Nov 4, 2019 at 6:44 PM
Subject: New Version Notification for draft-barnes-cfrg-mult-for-7748-00.txt
To: Richard L. Barnes <[email-masked]>, Joël Alwen <[email-masked]>, Sandro
Corretti <[email-masked]>

A new version of I-D, draft-barnes-cfrg-mult-for-7748-00.txt
has been successfully submitted by Richard L. Barnes and posted to the
IETF repository.

Name:           draft-barnes-cfrg-mult-for-7748
Revision:       00
Title:          Homomorphic Multiplication for X25519 and X448
Document date:  2019-11-04
Group:          Individual Submission
Pages:          10
URL:
https://www.ietf.org/internet-drafts/draft-barnes-cfrg-mult-for-7748-00.txt
Status:
https://datatracker.ietf.org/doc/draft-barnes-cfrg-mult-for-7748/
Htmlized:
https://tools.ietf.org/html/draft-barnes-cfrg-mult-for-7748-00
Htmlized:
https://datatracker.ietf.org/doc/html/draft-barnes-cfrg-mult-for-7748

Abstract:
   In some contexts it is useful for holders of the private and public
   parts of an elliptic curve key pair to be able to independently apply
   an updates to those values, such that the resulting updated public
   key corresponds to the updated private key.  Such updates are
   straightforward for older elliptic curves, but for X25519 and X448,
   the "clamping" prescribed for scalars requires some additional
   processing.  This document defines a multiplication procedure that
   can be used to update X25519 and X448 key pairs.  This algorithm can
   fail to produce a result, but only with negligible probability.
   Failures can be detected by the holder of the private key.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Watson Ladd <[email-masked]>
Date: Mon, 4 Nov 2019 22:07:56 -0500

> perfect, works in all but a statistically insignificant number of cases.

If you have a ladder that doesn't require the high bit to be in any
particular place, then you're fine.  What's the application where you
cannot modify the implementation to compute n*X for any n, not just one of
a particular length? Secondly the calculation assumes d uniformly random:
but if d is say 2, then whether or not the generation fails is entirely
dependent on the second bit of y if we write sk=2^254+8y, as 2*sk is
2^255+8*2*y, which if it's in the fail range proves y<x/2, which is true
for about half the possibly y if I understand the notation correctly. What
I don't know is if you can do this again, and extract another bit, and
another, etc.

>    fail to produce a result, but only with negligible probability..
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Joel Alwen <[email-masked]>
Date: Tue, 5 Nov 2019 16:16:20 +0100

>  What's the application where you cannot modify the implementation to
compute n*X for any n, not just one of a particular length?

The idea is for key updates/re-randomization to be implemented as a (thin)
layer on-top of an arbitrary X25519/X448 implementations. To me, this seems
like a significantly less risky approach than to expect implementers to
correctly modify the (often pretty complex) X25519/X448 implementations. In
particular, if I'm not mistaken, then what you are proposing would require
digging in to the montgomery ladder code. The second concern I'd have with
your suggest is it requires modifying otherwise standard libraries which
means people would have to backport those changes to every new version of
the library (or worse, not update).

>  Secondly the calculation assumes d uniformly random

Yes, that is the intended instantiation here. But depending on the
application it could be relaxed in one of two ways. For key updates as used
in BIP32 style Hierarchical Deterministic Key Derivation [2] and Tor's
Hidden Service Identity Blinding [3] I believe its sufficient that d simply
has negligible probability of hitting the "failure set" F. Thus d's
distribution could be very far from uniform and still be fine. However, for
the Updateable-PKE application as being considered for MLS [1] we also want
an extra forward secrecy type of property. Namely, given the old pk and the
updated key pair it should be infeasible to compute the old sk (more
precisely, the old sk should still have CPA security). Formally, that
probably means d should be (close to) uniform.

Having said this, we actually expect d to be chosen by first sampling some
input(s) to a cryptographic hash function and setting d to be the output.
I.e. choose d' and set d:=truncate(H(d'), |d|). With this approach I
believe it would in fact be secure to have d' chosen adversarially (up to a
large number of updates). After all, modeling H as a RO means the
likelihood any given d' hits F is at most 2^{-125} for X25519 (and much
smaller for X448) so even trying say 2^{45} different d' values still only
has a 2^{-80} probability of finding a single d \in F. (Not to mention that
given only the pk its not at all clear to me if its even feasible to
determine what the corresponding set F looks like.) All three applications
above use some variant of this technique for sampling d.

In any case, to be clear, AFAIK adversarially chosen d is outside the
target adversarial model for MLS.

- Joël

[1] https://mailarchive.ietf.org/arch/msg/mls/y5ikXqQh7VAojXrNSt9odxgNVmE
[2] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[3] https://www-users.cs.umn.edu/~hoppernj/basic-proof.pdf

On Tue, 5 Nov 2019, 04:08 Watson Ladd, <[email-masked]> wrote:

>> [1]
>> https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ
>> To: Richard L. Barnes <[email-masked]>, Joël Alwen <[email-masked]>,
>> Sandro Corretti <[email-masked]>
>>
>>
>>