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

Rene Struik <rstruik.ext@gmail.com> Tue, 05 February 2019 01:53 UTC

Return-Path: <rstruik.ext@gmail.com>
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 B8A31130F2A for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 17:53:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 hk-QsGy5ecNj for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 17:53:09 -0800 (PST)
Received: from mail-it1-x142.google.com (mail-it1-x142.google.com [IPv6:2607:f8b0:4864:20::142]) (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 43ED9130F28 for <cfrg@irtf.org>; Mon, 4 Feb 2019 17:53:09 -0800 (PST)
Received: by mail-it1-x142.google.com with SMTP id z7so4771988iti.0 for <cfrg@irtf.org>; Mon, 04 Feb 2019 17:53:09 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language; bh=zTOhoSkGEVxREH5Wi19lzCS7VI8x65oJP8VFb5jn1YI=; b=UKkFjYaVMlmvTeVO2xN/0Bz73nqZA9+oeTLN9geq4cK8mI0KPY3G/o/E6xZ/NFFxZr qmwotoGgv1f/Lo2Jqo/lb1EZN7DF3YEiK/6JIH0Uu2pOE61K1BSDhrgtuY/QpyqGpOjm t1bRvgh9fIomhwUtQHPMF27HuXEzJpp5zdbJ3U6+v/82DD3VYvtc6GqRNNRZwMl7U70W SBk88HcwRZDP9U7kOUYdiNBhz3v5QZQMYTt1URIIRdyuFL7RmRwcfSdSdYEQACKJvaYn H9PbTjk/yvN+VrvuvIXESDxCpkEQwasOr4RMzbecTmEcdDRInzVv9HLHbWMas8UJlabh hreg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=zTOhoSkGEVxREH5Wi19lzCS7VI8x65oJP8VFb5jn1YI=; b=pLGr32nPPd4tteeZEVurBLHMzWjHEj58SuX0dfg84yLQwb8z0gn/x97wmcyviHVcgs KuliIhsS1JckQFqerTumPKspyDDpcQywXWYIA8hGtVBotzKBv1JrAlCQyz7v5WIgOnFA i0XRqDdTxk7JEiHaBhT0AaCygDE3O63RsKYDjEHSpuyHN1qpwpyUINDiMCe2QnBFbIn4 H+YFjIMuLKBQYhHgWW1HkbFInh7/DdkvJRZQZFWwXfxpnC5WZtX3gShxEzCAq7z+tKpi +VILE6Zu05uQEK2oFMhnMYGBVt7OY13jenOjGyVALAGnnga2jq2alVWuFXfx3vBnFDg4 +sBg==
X-Gm-Message-State: AHQUAuZpav0Gj08NzJuEwnzn7mvkfL/wZDf4dSy8WB6kzxwO3qhlg44p gffM4Ld/owBtcd1MXlpeOIFKUrGC
X-Google-Smtp-Source: AHgI3IacfCddJQq7na6Wpx9EEq75J798XwmZnPH/s8GiKiU2T1dTq2cC2uzywLFXhc+rPmuZVwcUaQ==
X-Received: by 2002:a24:5a8f:: with SMTP id v137mr1294935ita.65.1549331588358; Mon, 04 Feb 2019 17:53:08 -0800 (PST)
Received: from ?IPv6:2607:fea8:69f:f5eb:a0ad:4c9a:2634:9f46? ([2607:fea8:69f:f5eb:a0ad:4c9a:2634:9f46]) by smtp.gmail.com with ESMTPSA id e68sm884961ite.7.2019.02.04.17.53.07 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 04 Feb 2019 17:53:07 -0800 (PST)
To: Adam Langley <agl@imperialviolet.org>, Richard Barnes <rlb@ipv.sx>
Cc: CFRG <cfrg@irtf.org>
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com> <CAMfhd9Vf1e9ZD_j9h8HNNwc+xF-5qFETu=+YKwcsQ+q8LjwKYQ@mail.gmail.com>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <805940ea-47de-22b5-5522-417e042b1fd4@gmail.com>
Date: Mon, 4 Feb 2019 20:53:05 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.5.0
MIME-Version: 1.0
In-Reply-To: <CAMfhd9Vf1e9ZD_j9h8HNNwc+xF-5qFETu=+YKwcsQ+q8LjwKYQ@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------D1C0D559AAA8FB7281B7C71E"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/b1eBNLUpylVhnJt-BjqqXdFlvt8>
Subject: [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 01:53:12 -0000

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> 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 <mailto:agl@imperialviolet.org> 
> https://www.imperialviolet.org
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363