tree 44909a13068d2fd38a8b90881f478f26bfe1711f
parent 6cc352e216938d78b65fb8ccbeebfc1f7f7486c4
author Andres Erbsen <andreser@google.com> 1508768624 +0000
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1509734411 +0000

curve25519: adhere to preconditions of fe_*.

Previously, the ed25519 and SPAKE implementations called field element
operations in ways that did not satisfy the preconditions about ranges
of limbs. Furthermore, replacing signed field arithmetic with unsigned field
arithmetic with similar specifications caused tests to fail.  This commit
addresses this in three steps:

(1) Split fe into fe and fe_loose, tracking the bounds
(2) Insert carry operations before uses of fe_add/fe_sub/fe_neg whose
input is already within only the loose bounds
(3) Assert that each field element is within the appropriate bounds at
the beginning and end of every field operation.

Throughput diff:

Ed25519 key generation: -2%
Ed25519 signing: -2%
Ed25519 verify: -2%
X25519: roughly unchanged

Detailed benchmarks on Google Cloud's unidentified Intel Xeon with AVX2:
git checkout $VARIANT && ( cd build && rm -rf * && CC=clang CXX=clang++ cmake -GNinja -DCMAKE_TOOLCHAIN_FILE=../util/32-bit-toolchain.cmake -DCMAKE_BUILD_TYPE=Release .. && ninja && ./tool/bssl speed -filter 25519 )

this branch:

Did 11206 Ed25519 key generation operations in 1029462us (10885.3 ops/sec)
Did 11104 Ed25519 signing operations in 1035735us (10720.9 ops/sec)
Did 3278 Ed25519 verify operations in 1087969us (3013.0 ops/sec)
Did 12000 Curve25519 base-point multiplication operations in 1078962us (11121.8 ops/sec)
Did 3610 Curve25519 arbitrary point multiplication operations in 1002767us (3600.0 ops/sec)

Did 11662 Ed25519 key generation operations in 1077690us (10821.3 ops/sec)
Did 10780 Ed25519 signing operations in 1011474us (10657.7 ops/sec)
Did 3289 Ed25519 verify operations in 1083638us (3035.1 ops/sec)
Did 12000 Curve25519 base-point multiplication operations in 1087477us (11034.7 ops/sec)
Did 3610 Curve25519 arbitrary point multiplication operations in 1017023us (3549.6 ops/sec)

Did 11018 Ed25519 key generation operations in 1011606us (10891.6 ops/sec)
Did 11000 Ed25519 signing operations in 1029961us (10680.0 ops/sec)
Did 3124 Ed25519 verify operations in 1045163us (2989.0 ops/sec)
Did 12000 Curve25519 base-point multiplication operations in 1081770us (11092.9 ops/sec)
Did 3610 Curve25519 arbitrary point multiplication operations in 1014503us (3558.4 ops/sec)

master:

Did 11662 Ed25519 key generation operations in 1059449us (11007.6 ops/sec)
Did 10908 Ed25519 signing operations in 1000081us (10907.1 ops/sec)
Did 3333 Ed25519 verify operations in 1078798us (3089.5 ops/sec)
Did 12000 Curve25519 base-point multiplication operations in 1072831us (11185.4 ops/sec)
Did 3850 Curve25519 arbitrary point multiplication operations in 1075821us (3578.7 ops/sec)

Did 11102 Ed25519 key generation operations in 1017540us (10910.6 ops/sec)
Did 11000 Ed25519 signing operations in 1013279us (10855.8 ops/sec)
Did 3311 Ed25519 verify operations in 1066866us (3103.5 ops/sec)
Did 12000 Curve25519 base-point multiplication operations in 1069668us (11218.4 ops/sec)
Did 3905 Curve25519 arbitrary point multiplication operations in 1095501us (3564.6 ops/sec)

Did 11206 Ed25519 key generation operations in 1014127us (11049.9 ops/sec)
Did 10908 Ed25519 signing operations in 1015821us (10738.1 ops/sec)
Did 3344 Ed25519 verify operations in 1100592us (3038.4 ops/sec)
Did 12000 Curve25519 base-point multiplication operations in 1072847us (11185.2 ops/sec)
Did 3570 Curve25519 arbitrary point multiplication operations in 1009373us (3536.8 ops/sec)

Change-Id: Ia014386daf36c913f3ea44c5f9a420b98670e465
Reviewed-on: https://boringssl-review.googlesource.com/22104
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>