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

Mike Hamburg <mike@shiftleft.org> Thu, 09 October 2014 06:52 UTC

Return-Path: <mike@shiftleft.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 F29E01A910F for <cfrg@ietfa.amsl.com>; Wed, 8 Oct 2014 23:52:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=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 7T4eSqoaZpY9 for <cfrg@ietfa.amsl.com>; Wed, 8 Oct 2014 23:52:19 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4ADFA1A0007 for <cfrg@irtf.org>; Wed, 8 Oct 2014 23:52:19 -0700 (PDT)
Received: from [192.168.1.124] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id B7E60F2208; Wed, 8 Oct 2014 23:50:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1412837452; bh=VjPTOOst2JblbKkLPcKGVA6e3bEWxpPKnPjrvU/EDM4=; h=Date:From:To:CC:Subject:References:In-Reply-To:From; b=NaZ66LhxmCK/s97fYsBJg1LcdR50wqHEknsc7EHx8oFEJLXAFWlOprm7PD1F2kgRR 0a31HwSzGeWfhv9873DC5TQJic68pXUZxd94r5+OpLS1gI28Z15lDEbuLBQeaTtAJa eHeFkU1kJc9b7vQ8Jqr/UizYvMt9PCFAY/uQKdLU=
Message-ID: <543630A2.5060904@shiftleft.org>
Date: Wed, 08 Oct 2014 23:52:18 -0700
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Andrey Jivsov <crypto@brainhub.org>, Watson Ladd <watsonbladd@gmail.com>
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>
In-Reply-To: <54362162.8070506@brainhub.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/tb6ZVMdNdwysG98XhXXbZXp90pE
Cc: "cfrg@irtf.org" <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: Thu, 09 Oct 2014 06:52:20 -0000

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 :-)
> 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.
> * it seems that this is of no use to mobile devices (in the near 
> future anyway)
Curve25519 performs quite well on ARM NEON.
> * but servers will benefit from this. 

Cheers,
-- Mike