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

Adam Langley <agl@imperialviolet.org> Tue, 05 February 2019 00:25 UTC

Return-Path: <alangley@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 0440B129B88 for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 16:25:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.894
X-Spam-Level:
X-Spam-Status: No, score=-1.894 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 bdUSG4mBg1m4 for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 16:25:50 -0800 (PST)
Received: from mail-qt1-f181.google.com (mail-qt1-f181.google.com [209.85.160.181]) (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 BA5FA124408 for <cfrg@irtf.org>; Mon, 4 Feb 2019 16:25:49 -0800 (PST)
Received: by mail-qt1-f181.google.com with SMTP id b8so2071115qtr.9 for <cfrg@irtf.org>; Mon, 04 Feb 2019 16:25:49 -0800 (PST)
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=YWZHw1n7ushjzXRra16Y6YIfpJyc1loRdTR/jK8cYa0=; b=n8hj1EdF1kASVGQBhoLcymIyHI1kJ87IJyYCQN8dWb2V4MNksKW2H2rTApiYcZiPlO 7TL4F3BWAyOh2Zv++MdTR5ErLbKEfDJagGpmfcQ5KD9xGi7lZZ7Q5nAb07OBz1QI+imL IvVn70o2qp4XtPWQFgluaozxSegkH9hqzPrkKzHxM07OUVXyr/UcicnzEW+WDpiJi/TJ kL46hdqkEpoTEwz557PFGWqRsDCwL/gtIHXa8ddaZSr13hGO4f30sf2hVvrCWAlVMQaW HAeXC12EqrzOPZoE0ttM2p3WEwWYLweHAWTfsbqiYVLgrJ1Hmn0VwPm6gElL1GJnZZcu +F5w==
X-Gm-Message-State: AHQUAubhzXY+fJlTMqi9AClu8D6OyxHYDPjX2zPwyfDkF/sexuOm0n7V C3fTHbImciPzJpEeKz+yicH+B99FDuDDdknF2ws=
X-Google-Smtp-Source: AHgI3IYGktiXWPw1sv2KWLG8t1YOdOp2I+Yee1XOs3P6LJqht2AnN+kTuTIMqtd7fE22hRRa7fZzVk5Kef2OF1Sj12g=
X-Received: by 2002:ac8:7201:: with SMTP id a1mr1560452qtp.291.1549326348444; Mon, 04 Feb 2019 16:25:48 -0800 (PST)
MIME-Version: 1.0
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
In-Reply-To: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
Date: Mon, 4 Feb 2019 16:25:35 -0800
Message-ID: <CAMfhd9Vf1e9ZD_j9h8HNNwc+xF-5qFETu=+YKwcsQ+q8LjwKYQ@mail.gmail.com>
To: Richard Barnes <rlb@ipv.sx>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000a3ea9205811aa6b5"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JSUI7TDIa01ygwgXQIbr23Ih3H8>
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 00:25:52 -0000

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 https://www.imperialviolet.org