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

Michael Hamburg <mike@shiftleft.org> Sun, 17 August 2014 17:09 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 7CDE11A0AF8 for <cfrg@ietfa.amsl.com>; Sun, 17 Aug 2014 10:09:48 -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 Kgfg2z-aBqaq for <cfrg@ietfa.amsl.com>; Sun, 17 Aug 2014 10:09:46 -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 74B041A0B03 for <cfrg@irtf.org>; Sun, 17 Aug 2014 10:09:46 -0700 (PDT)
Received: from [192.168.1.146] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 9ABF93AA12; Sun, 17 Aug 2014 10:08:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1408295298; bh=PQqZ8DH0Uidr1tK5c6K4JJ3YhmuLdE6kjQ0H1UPvJ+s=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=dRKTlQVA0OetBY0qiPSh2au463dGrx6gmk2cyHV4BnsNcXA7GTj32WjvP3KRM8y2a MPQY9qQ8PZAbDWSlBswrwXWDv0xl4b+LkQvvbgkEH6q67dWO7sE6eg+nSi8RiI3fvT UGoWj57+gWFv/Q9gKGnnV7HIq5v6/ZFNf9L4IjA4=
Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1971.5\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <53F0010B.6080101@brainhub.org>
Date: Sun, 17 Aug 2014 10:09:44 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <CD159876-F061-4EB8-B1DC-FAB8E4798E26@shiftleft.org>
References: <53F0010B.6080101@brainhub.org>
To: Andrey Jivsov <crypto@brainhub.org>
X-Mailer: Apple Mail (2.1971.5)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/vfB5tqOvsajBnG37LdiSgP0mnao
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: Sun, 17 Aug 2014 17:09:49 -0000

> On Aug 16, 2014, at 6:10 PM, Andrey Jivsov <crypto@brainhub.org>; wrote:
> 
> I timed libsodium, curve25519-donna, MSR ECCLib, and openssl-master.

Thanks for the data!

> In all cases minor tweaks to the source code were added to measure and report the timing. I made sure to time the variable base scalar multiplication. I also timed the fixed base multiplication and precomputation (only needed for MSR ECCLib).
> 
> Operations are reported as operations per second. I used default compile options.
> 
> MSR ECCLib was slightly faster in variable base operations. It uses assembler code.
> 
> Interestingly, MSR ECCLib Weierstrass a=-3 curves are only 10% slower than curve25519-donna. At the same time all pseudo-Mersenne prime curves are ~5 times faster than NIST P-256 (this is better than factor of 2 back-of-envelope difference in modp multiplication performance)
> 
> The factor of 2+ improvement for fixed base calculation in MSR ECCLib is impressive. Note, however, the significant penalty that precalculation step adds. If the pre-calculation is included in timing, we could do ~50% more EDH agreements with NIST P-256.

Precomputation on the curve’s base point shouldn't be included in timing, because it will be hard-coded in a production version.  Handling it will be cheap, unless it’s big enough to cause CPU cache thrashing.

> CPU: Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, no AVX2. Fedora Core 20 64 bit.

Do you know if TurboBoost was on?  That CPU can boost to 3.7 GHz, so the cycle counts could be 12% different one way or another.

> https://github.com/jedisct1/libsodium
> modified tests in libsodium/test/default to take the timing:
> crypto_scalarmult_curve25519_base: 15620.2 op/s
> crypto_scalarmult_curve25519: 15602.8 op/s
> 
> https://github.com/agl/curve25519-donna:
> make ./speed-curve25519-donna-c64 && ./speed-curve25519-donna-c64
> 63 us, 15722.1 op/s
> (also modified to check variable base v.s. generator 9 -- no difference)
> 
> OpenSSL 1.0.1e-fips 11 Feb 2013:
> openssl speed ecdhp256 (ECDH_compute_key)
> 256 bit ecdh (nistp256)   0.0003s   3245.4  op      op/s
> and from git://git.openssl.org/openssl.git:
> 256 bit ecdh (nistp256)   0.0003s   3406.7  op      op/s
> 
> MSR ECCLib http://research.microsoft.com/en-us/downloads/149804d4-b5f5-496f-9a17-a013b242c02d/
> 
> In the function that prints "Crypto operations: Weierstrass a=-3 over GF(2^256-189)":
> with variable base (baseecdh_secret_agreement_Jac256) 14047.9 op/sec
> with fixed base (ecdh_keygen_Jac256) 35370 op/sec
> table precomp (ecdh_generator_table_Jac256) 1284.03 op/sec
> table precomp+keygen+variable base 1056.86 op/sec
> "ECDH(E) runs in [...] 328926 cycles"
> 
> In the function that prints "Crypto operations: twisted Edwards a=-1 over GF(2^256-189)"
> with variable base (ecdh_secret_agreement_Ted256): 17482 op/sec
> with fixed base (ecdh_keygen_Ted256) 35370 op/sec: 45762.9 op/sec
> table precomp (ecdh_generator_table_Ted256) 1346.98 op/sec
> table precomp+keygen+variable base 1195.89 op/sec
> "ECDH(E) runs in [...] 261385 cycles"
> 
> memcpy of the 32 bytes: 595968511 op/sec, see attached code
> ( i.e. memcpy count / crypto_scalarmult_curve25519 count = 38042 )
> <memcpy-timing.c>_______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg