Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib, and openssl-master

Andrey Jivsov <crypto@brainhub.org> Fri, 10 October 2014 02:54 UTC

Return-Path: <andrey@brainhub.org>
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 5E3EA1A0089 for <cfrg@ietfa.amsl.com>; Thu, 9 Oct 2014 19:54:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.978
X-Spam-Level:
X-Spam-Status: No, score=-1.978 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, 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 sXrMATLPz-Y4 for <cfrg@ietfa.amsl.com>; Thu, 9 Oct 2014 19:54:21 -0700 (PDT)
Received: from mail-la0-f50.google.com (mail-la0-f50.google.com [209.85.215.50]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EB5961A0081 for <cfrg@irtf.org>; Thu, 9 Oct 2014 19:54:20 -0700 (PDT)
Received: by mail-la0-f50.google.com with SMTP id s18so2383701lam.37 for <cfrg@irtf.org>; Thu, 09 Oct 2014 19:54:19 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=zD2bVgB2rmLRreOS4oTpqGIcO2Wzs6aOYnA23heGPzg=; b=JHi5JlPZFeWYZq4Kq16SsgGHygEiMeqUASQaFkyET1SF1OsMWmVqAlqvKlIEcPYmAl NliFUcEnd82KIwKCjAQ5KblF1XMYyA/20E8kczIRnccY3U25JZWTXmmhDRkuCiquzSXt rSCBg/bwWIV24CE6ACs45WzhGMXWMWYlDvMnSqX71ksuT1lwaqcWXztX6kGpVJxtLs+A wNvijm6eZz8VZQYKYCqTi1hxdbIOKZFxCEzGoCN/CgUSbBNxbn43MiTb8LbEIjuDvCNk XGKVOb12kIGoMo1exTne7V7UG0oMihK5ldAGI7ccnabTUoAdaO6jO0XFPsvGhPKrCmoR Eegw==
X-Gm-Message-State: ALoCoQm3CAi55JWKO/EBPdb+mWm1fC7BNK+LVY0yfWiAoHQD1H4bWeC526KFFHaWLE2cCPFkBX1s
MIME-Version: 1.0
X-Received: by 10.152.43.50 with SMTP id t18mr175115lal.91.1412909658865; Thu, 09 Oct 2014 19:54:18 -0700 (PDT)
Sender: andrey@brainhub.org
Received: by 10.25.205.131 with HTTP; Thu, 9 Oct 2014 19:54:18 -0700 (PDT)
X-Originating-IP: [108.65.79.249]
Received: by 10.25.205.131 with HTTP; Thu, 9 Oct 2014 19:54:18 -0700 (PDT)
In-Reply-To: <543630A2.5060904@shiftleft.org>
References: <53F0010B.6080101@brainhub.org> <CD159876-F061-4EB8-B1DC-FAB8E4798E26@shiftleft.org> <53F108CF.4040704@brainhub.org> <53F18607.3000005@brainhub.org> <5406C23E.80205@brainhub.org> <5407C176.3000109@brainhub.org> <5435DE66.7080803@brainhub.org> <29E067B7-C1F3-427C-8E4A-14F2096A71E4@shiftleft.org> <543616FF.4010503@brainhub.org> <CACsn0cnDKbiHjjOAAC_xb8bseCLHoS8bKExutMC5DKk8utYVjQ@mail.gmail.com> <54362162.8070506@brainhub.org> <543630A2.5060904@shiftleft.org>
Date: Thu, 9 Oct 2014 19:54:18 -0700
X-Google-Sender-Auth: zOFCYIh2UzjVtFMtpTkF0UUNjE4
Message-ID: <CAKUk3buKnTcZ4a40n7ccJbNHMY5xp7jfwetYEfW7zaQg344pMg@mail.gmail.com>
From: Andrey Jivsov <crypto@brainhub.org>
To: Mike Hamburg <mike@shiftleft.org>
Content-Type: multipart/alternative; boundary=001a11c239d0511922050508aa1c
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/uYYSnKMqxOb4L6pxPXmgKucgcos
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib, and openssl-master
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: Fri, 10 Oct 2014 02:54:23 -0000

On Oct 8, 2014 11:52 PM, "Mike Hamburg" <mike@shiftleft.org> wrote:
>
>
> On 10/8/2014 10:47 PM, Andrey Jivsov wrote:
>>
>>
>> Montgomery curve has fewer underlying filed operations. The performance
benefit will be lower than due to prime reduction/hardware/instruction
assistance. However, given that the numbers are fairly close now, we can
expect change in leadership depending on the mix of features. For example,
a hypothetical mix of the P-256 underlying field operations found in the
code that I timed and a Montgomery curve on top would probably move such an
implementation into the lead in the tests I performed.
>
> Yeah, or getting Shay and Vlad to hand-tune an x25519 implementation :-)

BTW, I may be wrong on this one, but the latest performance boost I
reported yesterday is due to OpenSSL team, I believe.

>
>> P-256 has an advantage that it's in standards, widely deployed, can do
point additions (without penalty of coordinate conversion), and you can get
X.509 certs with it. It would have been easier to argue on its
disadvantages if it had worse performance than it appears to have. I am
aware of other disadvantages of P-256.
>>
>> In your other e-mail, Watson, regarding AVX2/vector operations + X25519,
it's an interesting question. The issues here are:
>> * will this hide some benefits of the 2^n-1 prime?
>
> Possibly.  You probably won't be able to use Langley and Bernstein's
carry handling techniques, but fewer coefficients is always good.
>>
>> * increase code complexity?
>
> Compared to a version without handwritten asm?  The field arithmetic will
definitely be more complex.

... and the combined code not so neat ...

>
>> * it seems that this is of no use to mobile devices (in the near future
anyway)
>
> Curve25519 performs quite well on ARM NEON.

My list is regarding vector operations. I was alluding that one of the
driving forces for new ECC is its excellent performance on mobile devices
but many of them don't have vector athithetic. Therefore, there is no
immediate ownership apparent of such vectorized code (until it is in
OpenSSL :-)).

>
>> * but servers will benefit from this.
>
>
> Cheers,
> -- Mike