Re: [Cfrg] Curve25519 lacks private/public homomorphism?

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Tue, 05 February 2019 03:27 UTC

Return-Path: <sfluhrer@cisco.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 BD069130FA9 for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 19:27:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.641
X-Spam-Level:
X-Spam-Status: No, score=-14.641 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.142, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.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 KCRxT9PP9FvN for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 19:27:05 -0800 (PST)
Received: from rcdn-iport-5.cisco.com (rcdn-iport-5.cisco.com [173.37.86.76]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 704281294FA for <cfrg@irtf.org>; Mon, 4 Feb 2019 19:27:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=9322; q=dns/txt; s=iport; t=1549337225; x=1550546825; h=from:to:cc:subject:date:message-id:references: in-reply-to:mime-version; bh=rlTWnhbUYN1gJRfobjZ5CrJ9Zc5RteeuEY8myh3CpEk=; b=Whj3Lu9+MLcYYl9VQVt7zVPLRO+0agKXZ3ZUBjQETYUbrCQz5wyRXUHe z43zo5QFIafmotS5dxoEOHoShF6Z7Q3AjGvKOfFArqGJ+1s1WJYfB6bBq f/gXwfrIEQVS9FFMWdilUv3VqueaFDzHJf6AMq+uY7oTXoGb+lyFzzYxZ c=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BCAADwAVlc/49dJa1lGQEBAQEBAQE?= =?us-ascii?q?BAQEBAQcBAQEBAQGBZYEOTSlngQMnCoN5lhuSIIdqCwEBhGwCF4MJIjgSAQM?= =?us-ascii?q?BAQIBAQJtKIVKAQEBAQMjCkwQAgEIDgMEAQEoAwICAjAUCQgCBAENBQiDG4E?= =?us-ascii?q?dZKtAgS+KOYxBF4FAP4ERgxJZhF6CU4JXAolWIIYakmYJAosRhx8hkkSKJZE?= =?us-ascii?q?3AhEUgSc2IYFWcBWDJ4M/AQ6ND0ExjVuBHwEB?=
X-IronPort-AV: E=Sophos;i="5.56,560,1539648000"; d="scan'208,217";a="294802698"
Received: from rcdn-core-7.cisco.com ([173.37.93.143]) by rcdn-iport-5.cisco.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 05 Feb 2019 03:27:03 +0000
Received: from XCH-RTP-006.cisco.com (xch-rtp-006.cisco.com [64.101.220.146]) by rcdn-core-7.cisco.com (8.15.2/8.15.2) with ESMTPS id x153R3EX026195 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Tue, 5 Feb 2019 03:27:03 GMT
Received: from xch-rtp-006.cisco.com (64.101.220.146) by XCH-RTP-006.cisco.com (64.101.220.146) with Microsoft SMTP Server (TLS) id 15.0.1395.4; Mon, 4 Feb 2019 22:27:03 -0500
Received: from xch-rtp-006.cisco.com ([64.101.220.146]) by XCH-RTP-006.cisco.com ([64.101.220.146]) with mapi id 15.00.1395.000; Mon, 4 Feb 2019 22:27:02 -0500
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Adam Langley <agl@imperialviolet.org>, Richard Barnes <rlb@ipv.sx>
CC: CFRG <cfrg@irtf.org>
Thread-Topic: [Cfrg] Curve25519 lacks private/public homomorphism?
Thread-Index: AQHUvNgNtZc7Pq3KVEGarVna6KzeeKXQrMCA///d/2A=
Date: Tue, 5 Feb 2019 03:27:02 +0000
Message-ID: <a6a12fd3d3204d4cb4fbaca65a484c94@XCH-RTP-006.cisco.com>
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com> <CAMfhd9Vf1e9ZD_j9h8HNNwc+xF-5qFETu=+YKwcsQ+q8LjwKYQ@mail.gmail.com>
In-Reply-To: <CAMfhd9Vf1e9ZD_j9h8HNNwc+xF-5qFETu=+YKwcsQ+q8LjwKYQ@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.98.2.57]
Content-Type: multipart/alternative; boundary="_000_a6a12fd3d3204d4cb4fbaca65a484c94XCHRTP006ciscocom_"
MIME-Version: 1.0
X-Outbound-SMTP-Client: 64.101.220.146, xch-rtp-006.cisco.com
X-Outbound-Node: rcdn-core-7.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/LFi5YEzTUm3YIqJLGTv6VbZi4XY>
Subject: Re: [Cfrg] 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 03:27:08 -0000

From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Adam Langley
Sent: Monday, February 04, 2019 7:26 PM
To: Richard Barnes <rlb@ipv.sx>
Cc: CFRG <cfrg@irtf.org>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <rlb@ipv.sx<mailto: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?

Actually, the ladder code handles infinity just fine.  DJB put the ‘set the high-order bit’ logic there so that too-clever implementors wouldn’t be tempted to optimize the code by skipping initial 0’s (which would of course add a potential time-based side channel)