BATCH BINARY WEIERSTRASSECC 2019, Bochum, Germany
02 December 2019

Billy Bob Brumley
Kide Vuojärvi

Sohaib ul Hassan

Network and Information Security Group (NISEC)
Tampere University, Tampere, FINLAND

Alex Shaindlin

Nicola Tuveri

dBitslicing: extreme SIMD
SSE2 SIMD
You could do 32-bit ops in 4-way parallel (w = 128).
lane:

32
10+------+------+------+------+|7F..60|5F..40|3F..20|1F..00|+------+------+------+------+

Bitslicing
You could do 1-bit ops in w-way parallel.
lane:

7F 7E .. 02 01 00+--+--+--+--+--+--+|7F|7E|..|02|01|00|+--+--+--+--+--+--+
2 / 20d3-bit ripple carry adder: addition modulo 8

3 / 20dParallel bitsliced implementation (1)

i0
12.
.
w-1

a[0]
a[1]
a[2]+----+ +----+ +----+
|
| |
| |
|
|
| |
| |
|
|
| |
| |
|
.
. .
. .
.
.
. .
. .
.
|
| |
| |
|
+----+ +----+ +----+

b[0]
b[1]
b[2]+----+ +----+ +----+|| || |||| || |
|
|
| |
| |
|
.
. .
. .
.
.
. .
. .
.
|
| |
| |
|
+----+ +----+ +----+s[0]
s[1]
s[2]
+----+ +----+ +----+
|
| |
| |
|
|
| |
| |
|
|
| |
| |
|
.
. .
. .
.
.
. .
. .
.
|
| |
| |
|
+----+ +----+ +----+

4 / 20dParallel bitsliced implementation (2)void add(reg_t *s, const reg_t *a, const reg_t *b) {reg_t t0, cc, s0, s1, s2,
a0 = a[0], a1 = a[1], a2 = a[2],b0 = b[0], b1 = b[1], b2 = b[2];s0 = XOR(a0, b0);
cc = AND(a0, b0);t0 = XOR(a1, b1);s1 = XOR(cc, t0);
cc = AND(cc, t0);
t0 = AND(a1, b1);
cc = OR(cc, t0);
t0 = XOR(a2, b2);s2 = XOR(cc, t0);s[0] = s0; s[1] = s1; s[2] = s2;}This computes (in w-way parallel) 3-bit integer additions: s[0],s[1],s[2] holds
the 3-bit results, result for instance i aligned at position i in s.
5 / 20dBitslicing in the wild
Bitsliced symmetric crypto
I Primitive designs (Serpent, SHA3, Ascon, . . . )I OpenSSL (AES, Käsper & Schwabe CHES 2009)
I JohnTheRipper (DES)

Bitsliced PKC

Figure: https://commons.wikimedia.org/wiki/File:PlantaRodadora.jpg
6 / 20d

PKC bitslicing: binary Edwards curves
CRYPTO 2009
Batch Binary Edwards
Daniel J. BernsteinDepartment of Computer Science (MC 152)
The University of Illinois at Chicago
Chicago, IL 60607–7053
djb@cr.yp.toAbstract. This paper sets new software speed records for high-security
Diﬃe-Hellman computations, speciﬁcally 251-bit elliptic-curve variablebase-point scalar multiplication. In one second of computation on a $200
Core 2 Quad Q6600 CPU, this paper’s software performs 30000 251-bit
scalar multiplications on the binary Edwards curve d(x + x2 + y + y 2 ) =(x + x2 )(y + y 2 ) over the ﬁeld F2 [t]/(t251 + t7 + t4 + t2 + 1) whered = t57 + t54 + t44 + 1. The paper’s ﬁeld-arithmetic techniques can beapplied in much more generality but have a particularly eﬃcient interaction with the completeness of addition formulas for binary Edwardscurves.
Keywords: Scalar multiplication, Diﬃe–Hellman, batch throughput,
vectorization, Karatsuba, Toom, elliptic curves, binary Edwards curves,

Good gate counts! Butdiﬀerential
straightline
isn’taddition
alwayspractical when bitslicing. Why?
addition, completeformulas.
1

Introduction

7 / 20

dGF layer: splitting strategies/* original BBE251 split *//* (32K251, 31K85, 30K84, 32K83, 42K30, 41K29, 40K28, 43K27, G8, G7, G6) */WAY43(27, gf2_mul_6, gf2_mul_7) /* 9M */WAY40(28, gf2_mul_7)
WAY41(29, gf2_mul_7)
WAY42(30, gf2_mul_7, gf2_mul_8)
WAY32(83, karatmult27, karatmult28, karatmult29)
WAY30(84, karatmult28, karatmult30) /* 5M 2E 1I */WAY31(85, karatmult27, karatmult29, karatmult30)
WAY32(251, karatmult83, karatmult84, karatmult85)/* another possible split -- better or worse? *//* (43K251, 43K63, 42K62, G16, G15) */WAY42(62, gf2_mul_15, gf2_mul_16)
WAY43(63, gf2_mul_15, gf2_mul_16)
WAY43(251, karatmult62, karatmult63)
8 / 20d

GF layer: overview

Automated tool description
I Started as just m = 251. Then exploded.
I Supports (potentially) any ﬁeld size and/or ﬁeld polynomial.
I Enumerate possible ﬁeld conﬁgurations. Benchmark them.
I Sometimes there’s a lot. Apply a few (sane) heuristics.
I Supports several architectures: NEON, w = 128; AVX2, w = 256; AVX-512,w = 512

9 / 20d

GF layer: benchmarks
AVX2-AMD450

Scaled CPU cycles

400
350
300
250

AVX2200
150
AVX-51210050150m
AVX-512
AVX2
AVX2-AMDNEON

113
132437228

131
1630
47290

163
22
4367
425

191
30
5483
523

200

193
3155
89
534

250

300

233
4484
114
708

350
400
Field size

450

239
44
77
116
724

283
59
121
153
928

251
51
91
132
805

500

550

359
82
166
224
1340

409
99
216
274
1659

431
104
214
300
1819

571
170
351
459
2953

10 / 20

dEC layer: overview

E (F2m ) : y 2 + xy = x3 + ax2 + b

I Targets key generation, i.e. kG. Allows relaxing several implementation details.
I Covered use cases: keygen, ECDSA sign, half of ECDH
I Stock ladder, stock ladder step formulae

11 / 20

dEC layer: why keygen?

I The code potentially works for any point. Why restrict to G?
I At the app layer, “scatter / gather” is hard
I Security: controlling scalars and points is sometimes important
I Some minor sliced representation savings

12 / 20

dEC layer: why legacy?
Curve forms
I Legacy: E (F2m ) : y 2 + xy = x3 + ax2 + b
I Binary Edwards: d1 (x + y ) + d2 (x2 + y 2 ) = (x + x2 )(y + y 2 )I Binary Huff: aX (Y 2 + fYZ + Z 2 ) = bY (X 2 + fXZ + Z 2 )I Maps to legacy usually exist (birational equivalence)

Challenges
I Started with potential changes to OpenSSL’s EC module (binary)
I Use a modern form internally, then map it when exporting
I Almost worked. But y-recovery is hard
I All the forms end up with roughly same ladder cost
I PSA: BBE251 6= curve2251
13 / 20

dEC layer: linear maps
The good
I Some are easy: e.g. c 7→ c2
I curve2251 has nice sparse coeﬃcients (a = 0, b = 0x2387)
I Since curve2251 is not standardized, we can tweak x(G)The badI In general, curve coeﬃcient b not guaranteed to have special form
I In general, to remain standards compliant we cannot tweak x(G)I We tried tooling, but the code size exploded

14 / 20

dEC layer: benchmarks
Curve
sect113r1
sect131r1
sect131r2
sect163r1
c2pnb163v1
c2tnb191v1
sect193r1
sect233r1
c2tnb239v1

curve2251
sect283r1
c2tnb359v1
sect409r1
c2tnb431r1
sect571r1

AVX-512
9547
13684
13639
22849
23005
36094
37899
65491
67144
57756
105304
186680260619283319627668

AVX2
18074
26821
26856
45231
45017
66799
67325
1258041194901063912181303626655466905676081303759

AVX2-AMD
27470
40478
40466
70046
74888
102005109376167761
175914146031272544504219697021
780886
1629335

NEON
1539442277652281684272744356516329076392701013458
1079930
8703761595423296185742297414812995
10676160

15 / 20

dOpenSSL layer: architecture
3rd party binaries
3rd partylibraries

OpenSSL binaries

OpenSSL libcrypto
KDF

EVP
PKEY

OpenSSL libsslcontainers,encodings

CONF

PKCS#12 PKCS#7 CMS PEM

STORE

EVP

3rd party
ENGINEs

TS OCSP CT X509

EVP
CIPHEREVPMDOBJECTS table

ENGINE API&built-in
ENGINEs

UI
low-level crypto

RSA

DH

EC

DSA

ECX

...

ASN1

BIO

(I/O abstraction:network sockets,memory buffers,ﬁles, ﬁlters, etc.)

ERR

low-level generic modules

RAND(randomnumber gen.)BN(arbitraryprec. int)

CRYPTO(memory,threads, ...)

BUFFER(in-mem bytebuffers)

ASYNC(async. jobs)

COMP(zlib,compression)

OS / System libraries
HWFigure: Start your ENGINES: dynamically loadable contemporary crypto (IEEE SecDev 2019,
N. Tuveri, B. B. Brumley)
16 / 20

dOpenSSL layer: engine concept

Figure: Start your ENGINES: dynamically loadable contemporary crypto (IEEE SecDev 2019,17 / 20
N. Tuveri, B. B. Brumley)

dOpenSSL layer: engine implementation

I Hijack the entire EC module. Yes.
I All legacy named curves by OID; curve2251 by explicit parameters.
I Compute w key generations in parallel.
I Serve them up as needed; reﬁll when empty.
I ECDSA: Montgomery’s trick for simultaneous inversion.

18 / 20

dOpenSSL layer: AVX2 benchmarksAverage CPU cycles per operation
Curve

sect113r1
sect113r2
sect131r1
sect131r2
c2pnb163v1
c2pnb163v2
c2pnb163v3
sect163r1
sect163r2
c2tnb191v1
c2tnb191v2
c2tnb191v3
sect193r1
sect193r2
sect233r1
c2tnb239v1
c2tnb239v2
c2tnb239v3

curve2251
ED25519
secp256r1
sect283r1
c2tnb359v1
sect409r1
c2tnb431r1
ED448
sect571r1

Key generation
default

libbecc

309998309892515314519635699094690930700345690258697992673839668479669240762628758937940852966659960048961976113943913029535805
1631437
2016295
2731705
2968140960595628309826758 (11.6x)
26810 (11.6x)
37617 (13.7x)37293 (13.9x)
54717 (12.8x)54603 (12.7x)
54432 (12.9x)
53996 (12.8x)54875 (12.7x)
74407 ( 9.1x)74308 ( 9.0x)73836 ( 9.1x)77378 ( 9.9x)77109 ( 9.8x)133436 ( 7.1x)
127149 ( 7.6x)
126222 ( 7.6x)
125478 ( 7.7x)118368 ( 9.6x)130254 ( 1.0x)
36741 ( 1.0x)
226075 ( 7.2x)
377226 ( 5.3x)552476 ( 4.9x)
587026 ( 5.1x)
957772 ( 1.0x)
1359731 ( 4.6x)Signature generation
default
323163323586533484540221
718671
710865722117719847725706694368695895697687803603800200985741
1008116
10049131008270
1198634
13117469228
1700907
2126677
288019031252459698256624862

libbecc

25049 (12.9x)25043 (12.9x)
35950 (14.8x)
35711 (15.1x)52785 (13.6x)52653 (13.5x)
52709 (13.7x)52548 (13.7x)52635 (13.8x)72989 ( 9.5x)
72811 ( 9.6x)
73037 ( 9.6x)76853 (10.5x)76908 (10.4x)
133941 ( 7.4x)
126843 ( 7.9x)126053 ( 8.0x)125681 ( 8.0x)
118661 (10.1x)129597 ( 1.0x)
68921 ( 1.0x)
225973 ( 7.5x)374781 ( 5.7x)551485 ( 5.2x)
579913 ( 5.4x)
969300 ( 1.0x)
1311432 ( 5.1x)

19 / 20

dConclusion
I Over time, bitslicing is scaling well with register size
I Solid baseline for serial implementations to target
I Parallel PKC can be practical
I Who uses binary curves?

Future work
I OpenSSL engine: traditional SIMD (P-256, . . . )I GitLab URLs for the libraries will be live soon (really . . . )Marketing
I Help us help you get your stuff into OpenSSL
20 / 20