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

Richard Barnes <rlb@ipv.sx> Tue, 05 February 2019 14:01 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 4A21C1310C1 for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 06:01:49 -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 wjjZfTPhWA7H for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 06:01:46 -0800 (PST)
Received: from mail-ot1-x32e.google.com (mail-ot1-x32e.google.com [IPv6:2607:f8b0:4864:20::32e]) (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 DB9B41294D0 for <cfrg@irtf.org>; Tue, 5 Feb 2019 06:01:45 -0800 (PST)
Received: by mail-ot1-x32e.google.com with SMTP id t5so5852681otk.1 for <cfrg@irtf.org>; Tue, 05 Feb 2019 06:01:45 -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=mw31Umml4+uva0FMk4PWmI58TiSVrL6bVWPBV/ehDbo=; b=anFAruH4/shEV0ALT++nZCx1N6b6iYyj+1A4Ng7tFe7BlpUuQH/EC1ZxmoDwVmZNZQ 8JJrUCOqwpC27/d3zljk9N4ZcGtHGSRql9zPNfiR7k2pHkIawdt9c1be1MPXVjSc4Tpj j6uCJlihg9ZvLcvXh7tj6cHLIdjeHCbYQpVM0CpskgRo/wf97KjaRWN6ye61jZldmewC 1DoMzRUsD1ILkKHFXo52KN21sr42wU4GNwK0NdAtYheoQE6C8Mb51ZCLA0t1JJFrvT0r 97RmHNrTRgcAx3PTkE1huEJDSKPNrw4+bO29POm639Ro3qFg/c/NEfT5x2Bs4EklC9XP 7EgQ==
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=mw31Umml4+uva0FMk4PWmI58TiSVrL6bVWPBV/ehDbo=; b=p326now48lpFv1pOi3r5j34xl2hjHNUt2MHCruwgI08zGY+OQ0FQpgRwGwMLzn5fu7 KRXTro/lq7QWSDDYsuvL5GKBuAaczTi3y5XRdjtkznN/ZGDGJm4eMuuL+hqwlC00ExT9 kb3ziElxIn6gQhHv0lklTuzAmheLQM0Iknp63zMSkLVYhGXG8GcSK05B7XRJqTlV28lf HACMhxxGDO0jt2FKzPfKZJvysgofV+66v51qu2ak5jIO1tUZuBMy5A89/9zgYfR5+X4T 8LgYuW5t7LIwSKzZiT1jHnf8WXrEidnAWkFrap/WTKqgaRhEyM0rGChsZ/68GNJlDPY9 b4XA==
X-Gm-Message-State: AHQUAuZ2bd1P+8WsX11PtOwU89j7cJl8gGhqL3uSArCzVjITutTO+UH6 DSiZ8SudiviN3OxKKz52byHPRYyje+DG296j+vIcXw==
X-Google-Smtp-Source: AHgI3Iarp/k1VS0aVLe7PEv6RdwPoMo9KrSdI7Hpx36SVbqqxQIwfWYu7baTw3x/IQ6lCpwMnMxjRi84Aj8uV3dmS5M=
X-Received: by 2002:aca:f18:: with SMTP id 24mr2494399oip.310.1549375304766; Tue, 05 Feb 2019 06:01:44 -0800 (PST)
MIME-Version: 1.0
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>
From: Richard Barnes <rlb@ipv.sx>
Date: Tue, 5 Feb 2019 09:01:26 -0500
Message-ID: <CAL02cgQAQSG8qrtH-=M5ObtsjUDUZaXO_iWwCACdKE7ja7Gmcg@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000aa32fd0581260c8b"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/2YoNPM5XAE9r5hrqhSuOgKsTZWE>
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 14:01:49 -0000

On Mon, Feb 4, 2019 at 7:25 PM Adam Langley <agl@imperialviolet.org> 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.)
>

I'm more in the (b) camp, in the sense that it's not clear to me what you
mean by that phrase.  As Scott says, it seems to me that the Montgomery
ladder works fine with infinities [0] as intermediate values.  It also
seems like setting the top bit doesn't guarantee that you don't get
infinity as output, since RFC 7748 still has you do an explicit check for
that.

In any case, I'm not sure it's worth spending a lot of time on this.  The
question underlying my question was whether it was possible to use
off-the-shelf Curve25519 libraries to implement a delta scheme, and it's
becoming pretty clear that the answer to that is "no".

--Richard

[0] I'm assuming that by "infinity" you mean the point at infinity, i.e.,
the identity of the curve group



>
> Cheers
>
> AGL
>
> --
> Adam Langley agl@imperialviolet.org https://www.imperialviolet.org
>