Re: [Cfrg] (how to shoehorn clamped private keys) Re: Curve25519 lacks private/public homomorphism?

Richard Barnes <rlb@ipv.sx> Tue, 05 February 2019 14:15 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 20DCB1310C5 for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 06:15:36 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.04
X-Spam-Level:
X-Spam-Status: No, score=-2.04 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.142, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id d1CK8mn6G5EQ for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 06:15:33 -0800 (PST)
Received: from mail-ot1-x332.google.com (mail-ot1-x332.google.com [IPv6:2607:f8b0:4864:20::332]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B1C33124BF6 for <cfrg@irtf.org>; Tue, 5 Feb 2019 06:15:33 -0800 (PST)
Received: by mail-ot1-x332.google.com with SMTP id a11so5810050otr.10 for <cfrg@irtf.org>; Tue, 05 Feb 2019 06:15:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=P5gw6absoR+tWsSEzLCY/YkitwByQVsXNzTn8AqKKIg=; b=wf9/yv3cBXHUNYRZh3ryxkT0J5YXL9UbVAS0GWksO6kUT65aNmFo/u1z+gGK3RJzlL nzFB6Ju2lG85Nsg7ay5Qj72+15WP0MW1SJvey6ZeVPso+EGRWTtNKaXtRS3N7p3Mnvr3 /gJIZKBslsPDmH4KFEEJ1oOMEC5XX6qmSPj0F//6hfqS5e/eh6/I6Fn6QFnruargqoXL iAM6wzZHisgBAqK25vI41DuhWj2yG2b9H/v8/IkEVeV+j4YDnC1aKDb+KyIrRAOEeYHU SfZ3+nfwFD3ByvWwkQ4r0I7ZQc8N8bkWJhnNmOnM0AbpuBDqPI7dke2bZrxLVh/cj+Sl +z6g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=P5gw6absoR+tWsSEzLCY/YkitwByQVsXNzTn8AqKKIg=; b=q3wFnAtcFMWHiUTRhMkhN6AeXEOAljxWZoDF5SZkWESdwqMVzTRm2/abMkd9wFvMnX 1JUvWTtkmKqTHt0Q58r2ITyM9EwA3eXhjbwwc4Jr/59ZtuY7E4lgGdzdIY2e4bTvIrWf MZRr549oytBSiNtQ5g/OhqZ9/3+pQ6hYR4R53xxTeo4HQmgEe3NaqYhRkSigMSmwmexR Reg3cRIzQqFpv69ecLew/3rw8cl5XSQw7o8q4KtYshmCvZjBflW/C9kkrUXeuQMb9y5r phRdBxZkO7ax4LIRSF6DN+v3YK+sIChfXk+ff00ZlWWOICbphTZnKrxlNjbDXA36BC87 PlcA==
X-Gm-Message-State: AHQUAuaDv2Z/j3duOhy+mrPJi/9IiuWA30nsb5OpyA/Ua1kD3eZI2Py7 3GzoeLuHLc3bek8YD9uNVfzPX/W6+KTMSUzTvsEPEzC5
X-Google-Smtp-Source: AHgI3IYXHnT9FNAsWEBXN1dOuFbED/c7uUrS/BVoP5RLILI8vKzW7Bmyw6VKGj3vOsIubJ7pSMQoTmgYG1sKOXMd+3A=
X-Received: by 2002:a9d:3f34:: with SMTP id m49mr2598385otc.23.1549376132768; Tue, 05 Feb 2019 06:15:32 -0800 (PST)
MIME-Version: 1.0
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com> <CAMfhd9Vf1e9ZD_j9h8HNNwc+xF-5qFETu=+YKwcsQ+q8LjwKYQ@mail.gmail.com> <805940ea-47de-22b5-5522-417e042b1fd4@gmail.com>
In-Reply-To: <805940ea-47de-22b5-5522-417e042b1fd4@gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Tue, 5 Feb 2019 09:15:14 -0500
Message-ID: <CAL02cgT55FwG5pPybM9oXb1ftKPF0ZhDuPYXBEtEY_dGWzWcjw@mail.gmail.com>
To: Rene Struik <rstruik.ext@gmail.com>
Cc: Adam Langley <agl@imperialviolet.org>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="0000000000000485770581263eed"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/4QsRwkJh-w_ZnoFdLicNeqvElOc>
Subject: Re: [Cfrg] (how to shoehorn clamped private keys) Re: Curve25519 lacks private/public homomorphism?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 05 Feb 2019 14:15:36 -0000

Hi Rene,

Interesting idea.  It might run into one protocol constraint I may not have
stated clearly, but there may be some utility here.

The constraint I'm worried about is that we need the delta-generating party
to be able to inform the public- and private-key holders of their
respective updates in one message, without the need for a follow-up message
from the private key holders.  (This is because MLS is designed to handle
highly asynchronous messaging.)

That said, it seems like you could run a scheme like the following:

0) Given a key pair (a, a*G) that we are updating...
1) Delta generator generates a random d in [1, n-1]
2) Delta generator encrypts `d` to the holder of `a` (e.g., with ECIES) and
sends it
3) Delta generator sends everyone else *both* d*a*G and (n-d)*a*G
4) Private key holders use whichever of d or (n-d) has its high-order bit
set
5) Public key holders use both public keys when encrypting to the private
key holders

That is, the private key holders can see which of d or (n-d) works, so they
can choose.  But the public-key holders can't see that, so they have to
enable either of the two values to be used.

With that mechanism in hand, it seems like the question for the WG is
whether the prefer to, on the one hand, make a pretty significant special
affordance for Curve25519, or on the other hand, use some newer, less
widely vetted / widely available elliptic curve math (either Ristretto or a
revised Curve25519).

Thanks,
--Richard





On Mon, Feb 4, 2019 at 8:53 PM Rene Struik <rstruik.ext@gmail.com> wrote:

> Dear colleagues:
>
> For any public-private key pair (k,Q:=k*G) for a curve with order n*h,
> where n is prime and h is a small co-factor, and where k is a random
> integer in the interval [1,n-1], (n-k, -Q) is another public-private key
> pair.
>
> If n is close to a power of two (i.e., n ~ 2^m), then either k>=2^{m-1} or
> n-k >= 2^{m-1}, except for cases that are highly unlikely to occur if k is
> truly uniform in [1,n-1] (prob ~ prob of guessing DLP in one try).
>
> So, if n is close to a power of two and h is a power of two, one can
> generate k as follows and shoehorn this into the ugly clamping form
> specified in RFC 7748:
> 1) Generate k in [1,n-1] uniformly at random;
> 2) Replace k by n-k if highest bit zero;
> 3) Set public-private key pair to (h*k, Q:=(h*k)*G).
> Note: since DH keys only depend on the x-coordinate of the shared key,
> this works. For signatures, one should obviously not use this, since it
> would pick k from a "half space" (in that case, one could pick k in Z_{2*n}
> and modify the trick above if one cares).
>
> So, if one cares about clamping, one can use the above approach with
> Curve25519 and Curve448 and any k. Alternatively, simply ignore clamping
> (since nobody would else should find out whether one used clamping or not).
>
> This also works for MLS, since the procedure above is described for any k
> in [1,n-1].
>
> This being said, clamping remains a poor hack.
>
> Best regards, Rene
>
> On 2/4/2019 7:25 PM, Adam Langley wrote:
>
> On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <rlb@ipv.sx> <rlb@ipv.sx>
> wrote:
>
>> When you try to do this with Curve25519 (or Curve448), however, you run
>> into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2]
>> ensures that the second-most-significant bit of a scalar private key is
>> always set, but this bit is not necessarily set in the product of two such
>> scalars.  In other words, there are scalars `ab` such that you can arrive
>> at `abG` as the result of a DH computation, but never abG will never be a
>> public key (since `X25519(ab, 9) != abG`).  The mapping from private keys
>> to public keys is not a homomorphism with regard to addition or
>> multiplication.
>>
>> This means we're out of luck with regard to our delta scheme.  If the
>> delta happens to result in a new private key with its penultimate bit
>> unset, then it can't actually be used as a private key -- and there's no
>> way for the delta-generating party to know this.
>>
>
> Setting the 255th bit is just done to avoid having to worry about infinity
> in the Montgomery ladder, I believe. But if you handle infinity explicitly,
> doesn't that solve the problem?
>
> (p.s. I'm imagining that an answer would either be a) "no, we thought
> about that and it doesn't work because ..." or b) "no idea, what does
> 'handle infinity explicitly' mean?". If (b), then I can see about knocking
> up an example tomorrow.)
>
>
> Cheers
>
> AGL
>
> --
> Adam Langley agl@imperialviolet.org https://www.imperialviolet.org
>
> _______________________________________________
> Cfrg mailing listCfrg@irtf.orghttps://www.irtf.org/mailman/listinfo/cfrg
>
>
> --
> email: rstruik.ext@gmail.com | Skype: rstruik
> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
>
>