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

[Joel Alwen <[e-mail]>]

>  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, <[e-mail]> wrote:

>
> On Mon, Nov 4, 2019 at 6:53 PM Richard Barnes <[e-mail]> wrote:
>
>> 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.
>>
>
> 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.
>
>
>
>> 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: <[e-mail]>
>> 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 <[e-mail]>, Joël Alwen <[e-mail]>,
>> Sandro Corretti <[e-mail]>
>>
>>
>>
>> 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
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> --
> "Man is born free, but everywhere he is in chains".
> --Rousseau.
>