Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
Watson Ladd <watsonbladd@gmail.com> Tue, 06 January 2015 04:28 UTC
Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B33EA1A1A33 for <cfrg@ietfa.amsl.com>; Mon, 5 Jan 2015 20:28:14 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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, LOTS_OF_MONEY=0.001, SPF_PASS=-0.001] autolearn=ham
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 4tHTJ6lYaKBY for <cfrg@ietfa.amsl.com>; Mon, 5 Jan 2015 20:28:12 -0800 (PST)
Received: from mail-yk0-x235.google.com (mail-yk0-x235.google.com [IPv6:2607:f8b0:4002:c07::235]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5830B1A1A2D for <cfrg@irtf.org>; Mon, 5 Jan 2015 20:28:12 -0800 (PST)
Received: by mail-yk0-f181.google.com with SMTP id 142so10843232ykq.26 for <cfrg@irtf.org>; Mon, 05 Jan 2015 20:28:11 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=d0/aER5hVOgwpxaQTyynAL5YVk/2PBMdTb5n+TTz/eE=; b=SWhagHZg1QrPg1mimdAJDlHbQ8GvDJ+vFi+1HG7FxiXHOpOMUWVNKgItlmoH0FZ3Kx 0ej87PKkRupm0eysDHULlTLvlkdP4gaaN3/DWmZ3qYkyOoCVUMF/A+BBxSNTYyBI3Jr5 ClNbS5BXxcmgAp+eQVap7yHisegiXxtdHKJjx16k7kOFGOf/Tgto0tFcKdytMp7w6o5z ICi+j4Prj2rWy+KrNGe3Hbd+9gBm/j2nPLQ9HVqIwPCY8oZqCSj8BdPA+Us9OBDT2PRU 4XplpyhrowQs+wwQ+cHDxOMDmIQxz4L95ncT0r6p9286nl68tKClxCjjQa7OaocX8VJ1 ls3A==
MIME-Version: 1.0
X-Received: by 10.170.89.130 with SMTP id g124mr67836607yka.24.1420518491579; Mon, 05 Jan 2015 20:28:11 -0800 (PST)
Received: by 10.170.207.6 with HTTP; Mon, 5 Jan 2015 20:28:11 -0800 (PST)
In-Reply-To: <54AAEEFC.9060309@brainhub.org>
References: <54AA4AB9.70505@brainhub.org> <54AA5AD3.9020009@shiftleft.org> <54AAEEFC.9060309@brainhub.org>
Date: Mon, 05 Jan 2015 23:28:11 -0500
Message-ID: <CACsn0c=nFHgwmx7aENVAp=xBm8QkqV0CLDSvFnydXSXcRVpG6A@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Andrey Jivsov <crypto@brainhub.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/KOhl25huydkWRHz8VboMO7OKRl8
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 06 Jan 2015 04:28:14 -0000
On Mon, Jan 5, 2015 at 3:07 PM, Andrey Jivsov <crypto@brainhub.org> wrote: > Thank you, Mike, this is helpful. This brings a few thoughts, below. <snip> > > > Unfortunately, the conversion between representations costs ~10% due to F(p) > inverse. Decompression costs about the same. We also know that the > performance difference between Montgomery/Edwards operations is in the > similar range. Therefore, selection of the format on the wire determines the > implementation. If we are sending a Montgomery x, we are committing to > Montgomery ladder implementation. Is this justified? Yes. Despite claims earlier in your email that certification stops the problem, invalid point attacks are a real threat. In RFC 4492, ECDH_ECDSA authentication of servers to clients involves one signed point and one unsigned point, the unsigned point being sent by the client. An attacker can extract the private key relatively quickly from a vulnerable implementation, which do exist: I've found some, and I believe Kenny Patterson has a student or two working on finding more now, as well as attacking other protocols. RFC 6090 doesn't mention the need for point validation, for instance. Point compression doesn't solve this issue: there is a presentation by Adrian Antipa, Dan Brown, Alfred Menezes, Rene Struik, and Scott Vanstone at PKCS 2003 which demonstrates attacks even when point compression is mandatory. DJB has also found a patent on point validation, which may mean we have a problem. (This is why RFC 6090 doesn't mention point validation: the relevant patent is US7215773) That's why NUMS switched to x-coordinate only Montgomery: the security issues associated with invalid point attacks go away. The Montgomery ladder is so simple that adding it to an Edwards form implementation adds very little complexity. The architectural issues being claimed are in my view irrelevant: most protocol implementations are able to integrate RSA and ECC, which are radically different: an x-coordinate only key exchange isn't much harder to integrate, and if it was, people wouldn't be doing it. The consequences of these attacks are losing one's private key, and telling implementors to check inputs isn't stopping them. Sincerely, Watson Ladd > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg -- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
- [Cfrg] On relative performance of Edwards v.s. Mo… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Mike Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Mike Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Peter Dettman
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Michael Hamburg
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Kurt Roeckx
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov
- Re: [Cfrg] On relative performance of Edwards v.s… Watson Ladd
- Re: [Cfrg] On relative performance of Edwards v.s… Andrey Jivsov