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, 5 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