crypton 2.1.4 → 2.1.5
raw patch · 14 files changed
+747/−259 lines, 14 files
Files
- CHANGELOG.md +34/−0
- README.md +105/−83
- cbits/aes/armv8.c +150/−131
- cbits/aes/armv8_impl.c +49/−38
- cbits/crypton_sha1.c +1/−1
- cbits/sha1_x86.c +1/−1
- cbits/tests/ct/README +14/−0
- cbits/tests/ct/ct_aes_armv8.c +12/−0
- cbits/tests/ct/known.txt +54/−0
- cbits/tests/ct/run.sh +42/−4
- cbits/tests/perf/floors.txt +22/−0
- cbits/tests/perf/run.sh +102/−0
- cbits/tests/perf/throughput.c +156/−0
- crypton.cabal +5/−1
CHANGELOG.md view
@@ -1,5 +1,39 @@ # CHANGELOG for crypton +## 2.1.5++crypton 2.1.3 and 2.1.4 cannot be built with GCC 14 or newer; it was+reported from a Fedora 43 system, which ships GCC 15. This release is that+fix, and two things that came with it.++* fix(x86): the C builds with GCC 14 and newer again.+ `crypton_sha1_x86_do_chunk` was declared taking `const uint32_t buf[16]`+ while every caller passes a `const uint8_t *`, and GCC 14 made+ `-Wincompatible-pointer-types` an error by default where GCC 13 only warns.+ The declaration now says `const uint8_t buf[64]`, which is the block size+ SHA-1 actually takes and what the two sibling functions already said.+ Reported as #282 and fixed in #284, both by @tbidne, who bisected it to+ the commit that introduced the declaration. CI now builds the C with+ gcc-14 as well, so the next one of these is caught before release+* perf(armv8): AES-GCM is about a quarter faster on AArch64, which puts it+ ahead of OpenSSL 4.0.3 rather than behind it -- 1.15 at AES-128 and 1.06+ at AES-256 on an Apple M4, from 0.86. The GHASH no longer keeps H the way+ GCM writes it; it is twisted once at key setup so that GCM's bit+ reflection is already undone, which turns a reduction of some twenty-five+ shifts and XORs into two PMULL and six EOR, and makes Karatsuba worth+ taking -- three multiplications a block rather than four. Against the+ previous code over 16 KiB messages: 1.34 at AES-128 and 1.23 at AES-256 on+ an M4, and 1.25 across the three key sizes on a Neoverse N2. The scheme+ is ARM's, from the BSD-3-Clause part of+ https://github.com/ARM-software/AArch64cryptolib+* test(armv8): the constant-time harness runs on AArch64, where it never had.+ It was pinned to one x86-64 job, so the AArch64 AES and GHASH had never+ been put to it; they are now, and they let no secret decide a branch or an+ address. Running it somewhere new also found a fault in the harness+ itself: it counted the frame `--track-origins` prints to say where a value+ came from as a place that branched on a secret, which invented a finding+ rather than hiding one+ ## 2.1.4 2.1.3 could not be built from Hackage at all in the default configuration,
README.md view
@@ -64,15 +64,15 @@ The RSA rows in the tables below are the unblinded path. A blinder costs one more exponentiation, by the public exponent, which is the cheap direction:-measured on the M4, signing goes from about 601 to about 620 microseconds,-three per cent.+measured on the M4, signing goes from about 460 to about 476 microseconds,+under four per cent. Performance ----------- -The algorithms a TLS connection uses, measured against the two releases-behind this one and against OpenSSL on the same machine. Throughput is over-16 KiB messages; the public key operations are one operation each; every+The algorithms a TLS connection uses, measured against the last release+before the rewrite and against OpenSSL on the same machine. Throughput is+over 16 KiB messages; the public key operations are one operation each; every figure is the best of several runs, and crypton and OpenSSL are run alternately so that neither gets the quieter machine. @@ -81,92 +81,97 @@ through crypton's Haskell API, since that is where ECDSA and RSA live and it is what a program actually calls; the Haskell layer adds well under a microsecond, which the X25519 and ECDH P-256 rows confirm by agreeing with a-C-level measurement to within a percent. All three releases of crypton are-built the same way -- `-optc-O3`, which is what each asks for -- and by+C-level measurement to within a percent. Both releases of crypton are built+the same way -- `-optc-O3`, which is what each asks for -- and by `cabal build`, since a copy of the sources compiled by hand does not measure-what a program linking the library gets. Each column of a table comes from-one run on the machine named above it.+what a program linking the library gets, and leaves out whole implementations+without saying so. Each column of a table comes from one run on the machine+named above it. ### x86-64 An AMD EPYC 7763, which has AES-NI, PCLMULQDQ, AVX2, ADX, VAES, VPCLMULQDQ-and the SHA extensions, against OpenSSL 3.0.13.+and the SHA extensions, against OpenSSL 4.0.3. Throughput in MB/s, **higher is better**: -| | crypton 1.1.5 | crypton 2.0.1 | crypton 2.1.2 | OpenSSL | 2.1.2 / OpenSSL |-| --- | ---: | ---: | ---: | ---: | ---: |-| AES-128-GCM | 1335 | 4243 | **6041** | 4287 | 1.41 |-| AES-256-GCM | 1093 | 3932 | **5463** | 3954 | 1.38 |-| ChaCha20-Poly1305 | 399 | 2196 | 2195 | 2192 | 1.00 |-| SHA-1 | 729 | 1662 | 1680 | 1681 | 1.00 |-| SHA-256 | 289 | 1586 | 1586 | 1570 | 1.01 |-| SHA-512 | 449 | 770 | 770 | 748 | 1.03 |-| SHA3-256 | 109 | 422 | 421 | 427 | 0.99 |+| | crypton 1.1.5 | crypton 2.1.4 | OpenSSL | 2.1.4 / OpenSSL |+| --- | ---: | ---: | ---: | ---: |+| AES-128-GCM | 1335 | **6038** | 4070 | 1.48 |+| AES-256-GCM | 1093 | **5461** | 3774 | 1.45 |+| ChaCha20-Poly1305 | 399 | 2195 | 2213 | 0.99 |+| SHA-1 | 729 | 1679 | 1682 | 1.00 |+| SHA-256 | 290 | 1585 | 1571 | 1.01 |+| SHA-512 | 449 | 770 | 750 | 1.03 |+| SHA3-256 | 109 | 422 | 425 | 0.99 | Time per operation in microseconds, **lower is better**: -| | crypton 1.1.5 | crypton 2.0.1 | crypton 2.1.2 | OpenSSL | OpenSSL / 2.1.2 |-| --- | ---: | ---: | ---: | ---: | ---: |-| X25519 | 44.40 | 44.15 | **28.35** | 36.50 | 1.29 |-| ECDH P-256 | 164.2 | 164.1 | **50.49** | 51.84 | 1.03 |-| ECDH P-384 | 2220 | 1116 | **164.5** | 855.8 | 5.20 |-| Ed25519 sign | 28.99 | 28.51 | 28.66 | 43.72 | 1.53 |-| Ed25519 verify | 48.14 | 47.81 | 47.54 | 117.2 | 2.47 |-| ECDSA P-256 sign | 81.43 | 80.79 | **18.62** | 22.45 | 1.21 |-| ECDSA P-256 verify | 231.8 | 230.7 | **79.67** | 67.73 | 0.85 |-| ECDSA P-384 sign | 2241 | 397.6 | **330.8** | 899.7 | 2.72 |-| ECDSA P-384 verify | 2655 | 1519 | **500.5** | 734.5 | 1.47 |-| RSA-2048 sign/decrypt | 758.3 | 1327 | **773.2** | 659.0 | 0.85 |-| RSA-2048 verify/encrypt | 33.28 | 30.05 | 29.80 | 18.62 | 0.62 |+| | crypton 1.1.5 | crypton 2.1.4 | OpenSSL | OpenSSL / 2.1.4 |+| --- | ---: | ---: | ---: | ---: |+| X25519 | 43.89 | 28.47 | 36.61 | 1.29 |+| ECDH P-256 | 164.7 | 50.34 | 51.66 | 1.03 |+| ECDH P-384 | 2237 | **163.4** | 835.4 | 5.11 |+| Ed25519 sign | 28.90 | 18.69 | 33.68 | 1.80 |+| Ed25519 verify | 47.81 | 47.77 | 111.2 | 2.33 |+| ECDSA P-256 sign | 81.05 | 18.73 | 21.88 | 1.17 |+| ECDSA P-256 verify | 232.6 | 70.27 | 67.51 | 0.96 |+| ECDSA P-384 sign | 2260 | **302.9** | 879.1 | 2.90 |+| ECDSA P-384 verify | 2668 | **467.8** | 725.2 | 1.55 |+| RSA-2048 sign/decrypt | 758.5 | 611.2 | 659.0 | 1.08 |+| RSA-2048 verify/encrypt | 32.79 | 30.01 | 18.85 | 0.63 | ### AArch64 An Apple M4, which has the AES, PMULL, SHA-1, SHA-2, SHA-512 and SHA-3-instructions, against OpenSSL 3.6.4.+instructions, against OpenSSL 4.0.3. Throughput in MB/s, **higher is better**: -| | crypton 1.1.5 | crypton 2.0.1 | crypton 2.1.2 | OpenSSL | 2.1.2 / OpenSSL |-| --- | ---: | ---: | ---: | ---: | ---: |-| AES-128-GCM | 127 | 8926 | 8731 | 10763 | 0.81 |-| AES-256-GCM | 98 | 7601 | 7712 | 9155 | 0.84 |-| ChaCha20-Poly1305 | 758 | 2247 | 2239 | 2248 | 1.00 |-| SHA-1 | 1201 | 3307 | 3314 | 3296 | 1.01 |-| SHA-256 | 472 | 3299 | 3245 | 3210 | 1.01 |-| SHA-512 | 726 | 1766 | 1798 | 1794 | 1.00 |-| SHA3-256 | 550 | 1076 | 1076 | 1054 | 1.02 |+| | crypton 1.1.5 | crypton 2.1.4 | OpenSSL | 2.1.4 / OpenSSL |+| --- | ---: | ---: | ---: | ---: |+| AES-128-GCM | 131 | 9487 | 11111 | 0.85 |+| AES-256-GCM | 98 | 8149 | 9371 | 0.87 |+| ChaCha20-Poly1305 | 786 | 2321 | 2304 | 1.01 |+| SHA-1 | 1255 | 3382 | 3366 | 1.00 |+| SHA-256 | 483 | 3396 | 3366 | 1.01 |+| SHA-512 | 735 | 1878 | 1888 | 0.99 |+| SHA3-256 | 557 | 1105 | 1100 | 1.00 | Time per operation in microseconds, **lower is better**: -| | crypton 1.1.5 | crypton 2.0.1 | crypton 2.1.2 | OpenSSL | OpenSSL / 2.1.2 |-| --- | ---: | ---: | ---: | ---: | ---: |-| X25519 | 18.25 | 18.27 | **12.05** | 18.27 | 1.52 |-| ECDH P-256 | 69.07 | 56.23 | **20.70** | 24.62 | 1.19 |-| ECDH P-384 | 3333 | 512.3 | **73.33** | 370.9 | 5.06 |-| Ed25519 sign | 13.63 | 13.05 | 13.03 | 15.72 | 1.21 |-| Ed25519 verify | 18.28 | 18.18 | 18.15 | 39.02 | 2.15 |-| ECDSA P-256 sign | 32.35 | 27.80 | **6.98** | 11.02 | 1.58 |-| ECDSA P-256 verify | 95.77 | 79.48 | **31.93** | 32.66 | 1.02 |-| ECDSA P-384 sign | 3232 | 170.5 | **140.4** | 392.6 | 2.80 |-| ECDSA P-384 verify | 3905 | 686.4 | **219.0** | 328.1 | 1.50 |-| RSA-2048 sign/decrypt | 449.3 | 601.8 | 600.2 | 322.8 | 0.54 |-| RSA-2048 verify/encrypt | 18.22 | 15.17 | 15.17 | 8.45 | 0.56 |+| | crypton 1.1.5 | crypton 2.1.4 | OpenSSL | OpenSSL / 2.1.4 |+| --- | ---: | ---: | ---: | ---: |+| X25519 | 17.45 | **11.12** | 15.35 | 1.38 |+| ECDH P-256 | 67.18 | **19.58** | 24.53 | 1.25 |+| ECDH P-384 | 3192 | **72.35** | 373.5 | 5.16 |+| Ed25519 sign | 13.13 | **7.60** | 13.26 | 1.75 |+| Ed25519 verify | 18.02 | 17.93 | 34.97 | 1.95 |+| ECDSA P-256 sign | 32.08 | **6.88** | 11.02 | 1.60 |+| ECDSA P-256 verify | 96.07 | **27.42** | 32.77 | 1.20 |+| ECDSA P-384 sign | 3253 | **124.2** | 396.8 | 3.19 |+| ECDSA P-384 verify | 3912 | **203.7** | 333.3 | 1.64 |+| RSA-2048 sign/decrypt | 452.0 | 465.3 | 321.3 | 0.69 |+| RSA-2048 verify/encrypt | 18.23 | 15.27 | 8.44 | 0.55 | ### What the numbers say -There are two changes in these tables, not one. 1.1.5 to 2.0.1 was a-rewrite: the bulk algorithms moved into C, the curves other than P-256 moved-out of Haskell `Integer` arithmetic, and everything that touches a secret was-made to take the same time whatever the secret is. 1.1.5 had no AArch64 code-of its own at all, which is why AES-GCM there is seventy times what it was,-and on x86-64 it had AES-NI and nothing else.+There are two changes behind the 1.1.5 column and the 2.1.4 one, not a+single steady improvement. -2.0.1 to 2.1.2 is assembly, for the operations where C cannot reach. The two-columns beside each other say which change did what: ECDSA P-384 signing, for-instance, got its nineteenfold from the first and a further fifth from the-second, while X25519 waited for the second entirely.+The first, in 2.0.0, was a rewrite: the bulk algorithms moved into C, the+curves other than P-256 moved out of Haskell `Integer` arithmetic, and+everything that touches a secret was made to take the same time whatever the+secret is. 1.1.5 had no AArch64 code of its own at all, which is why AES-GCM+there is seventy times what it was, and on x86-64 it had AES-NI and nothing+else. +The second, from 2.1.0 onwards, is assembly, for the operations where C+cannot reach. Which of the two a row owes its gain to is not the same+everywhere: ECDSA P-384 signing took nineteenfold from the rewrite and a+further fifth from the assembly, while X25519 waited for the assembly+entirely and ECDH P-384 is almost all of it.+ Most of that assembly is not crypton's. The prime curves, the inverse modulo a group order, X25519, and RSA's Montgomery multiplication on x86-64 go through [s2n-bignum](https://github.com/awslabs/s2n-bignum), vendored in@@ -179,17 +184,22 @@ it is Apache-2.0 only, and Intel and CloudFlare hold copyright in it besides OpenSSL, so nobody is in a position to relicense it. -Where crypton is still behind, it is behind for two reasons.+Where crypton is behind, which is now one row on one architecture and the+AES-GCM rows on the other, it is behind for two reasons. *RSA.* 2.0.0 made signing slower than 1.1.5 on purpose: its modular exponentiation stopped indexing a table with the bits of the exponent, and hiding the exponent is what the difference bought. On x86-64 that cost is-now repaid -- s2n-bignum's Montgomery multiplication is twice the C's,+more than repaid -- s2n-bignum's Montgomery multiplication is twice the C's, because the C cannot form the two carry chains `ADCX` and `ADOX` give, and-2.1.2 signs in about what 1.1.5 took while keeping what 2.0.0 gained. On-AArch64 the C measures faster than that assembly, so none is used and the gap-stays. Verification does not move either way: its exponent is 65537,-seventeen bits, and there is no exponentiation to speak of.+2.1.4 signs in less than 1.1.5 took while keeping what 2.0.0 gained. On+AArch64 there is nothing to use: s2n-bignum has no generic routine for it,+and the same five that help on x86-64 measure level with the C there, so the+C stays and the gap with it. No portable C closes that gap either -- the+measurements are in+[#275](https://github.com/kazu-yamamoto/crypton/issues/275). Verification+does not move much either way: its exponent is 65537, seventeen bits, and+there is no exponentiation to speak of. *The wide AES instructions.* `VAES` and `VPCLMULQDQ` do two blocks where `AES-NI` and `PCLMULQDQ` do one, and four in their 512-bit form. crypton uses@@ -199,23 +209,35 @@ BoringSSL and AWS-LC is Apache-2.0 and s2n-bignum has no GCM, so both files are crypton's own. -The 512-bit path arrived after 2.1.2, and neither machine in the tables above-has AVX-512, so it is in neither column. On the runners that do, measured-over 16 KiB in MB/s: an EPYC 9V45 (Zen 5) goes from-9616 to 14268 with it, a Xeon 6973P-C from 8095 to 9848, a Xeon 8573C from 6983-to 8447. OpenSSL on those machines is ahead still -- 25760 on the first of-them -- because it interleaves the GHASH with the AES where crypton does them-in turn. Zen 4 keeps the 256-bit path: its 512-bit instructions are two passes-through a 256-bit datapath, so the wider encoding buys nothing there and costs-a little.+Having the 256-bit one is where the 1.48 in the x86-64 table comes from, and+it is narrower than it sounds. The EPYC 7763 is Zen 3: VAES and VPCLMULQDQ,+no AVX-512. OpenSSL's x86-64 AES-GCM is `aesni-gcm-x86_64.pl`, which is+128-bit -- its `vaesenc`s are the VEX encoding of `AESENC` on `xmm`, and+there is not one `ymm` in the file -- or `aes-gcm-avx512.pl`, which wants+`AVX512VAES`. There is no rung between them, so on this processor OpenSSL+takes a block at a time where crypton takes two. The same idea as theirs,+one step further down the feature ladder; not a better one. -AArch64 has no counterpart to any of these, which is where the 0.8 on its-AES-GCM rows comes from.+The 512-bit path arrived after 2.1.2, so it is in the 2.1.4 column -- but+neither machine in the tables above has AVX-512, so neither column shows it.+On the runners that do, measured over 16 KiB in MB/s: an EPYC 9V45 (Zen 5)+goes from 9616 to 14268 with it, a Xeon 6973P-C from 8095 to 9848, a Xeon+8573C from 6983 to 8447. OpenSSL on those machines is ahead still -- 25760+on the first of them -- because it interleaves the GHASH with the AES where+crypton does them in turn. Zen 4 keeps the 256-bit path: its 512-bit+instructions are two passes through a 256-bit datapath, so the wider encoding+buys nothing there and costs a little. +AArch64 has no counterpart to any of these, which is where the 0.85 on its+AES-GCM rows comes from -- and, the other way about, why the x86-64 rows are+at 1.48 and 1.45.+ One row wants a word of its own: crypton's `Ed25519.sign` derives the public key from the secret key every time it signs, so that a caller who passes a public key that does not match cannot be made to leak the private one. That-costs a second scalar multiplication, which OpenSSL's signing does not pay.+costs a second scalar multiplication, which OpenSSL's signing does not pay --+and the row is still 1.75 on AArch64 and 1.80 on x86-64, so the safety is had+for nothing here rather than paid for. SHA-1 is in the tables because a number of protocols and file formats still ask for it, not because it is a good choice for anything new. The algorithms
cbits/aes/armv8.c view
@@ -143,171 +143,182 @@ /* * GHASH using PMULL, the AArch64 counterpart to PCLMULQDQ. *- * This is a transliteration of gfmul_pclmuldq in x86ni.c rather than a fresh- * formulation: that code is already pinned by the GCM known-answer tests, and- * every operation it uses has a direct NEON equivalent, so translating it is- * easier to check than reasoning about a new reduction from scratch.+ * Not the transliteration of gfmul_pclmuldq in x86ni.c this used to be. The+ * x86 formulation keeps H in the order GCM writes it and pays, at the end of+ * every batch, a reduction that first has to undo GCM's bit reflection: some+ * twenty-five shifts and XORs, and a batch of eight costs it once. *- * _mm_shuffle_epi8 with a reversing mask -> vrev64q_u8 then vextq_u8- * _mm_clmulepi64_si128 -> vmull_p64 / vmull_high_p64- * _mm_slli_si128 / _mm_srli_si128 -> vextq_u8 against zero- * _mm_slli_epi32 / _mm_srli_epi32 -> vshlq_n_u32 / vshrq_n_u32+ * Instead H is twisted once, at key setup, so that the reflection is already+ * undone and a reversed-polynomial multiply lands in the right place. Two+ * things follow. The reduction becomes two PMULL against 0xC2000..0 and six+ * EOR, a third of what it was. And because nothing has to be byte-reversed+ * back and forth, Karatsuba pays: three PMULL a block rather than four, with+ * the middle terms accumulated in a third register and tidied up once per+ * batch.+ *+ * crypton tried Karatsuba in the old representation and measured it 1.6 per+ * cent slower -- the saved PMULL did not cover the extra EOR when the+ * reduction stayed as expensive as it was. It is the pair that pays.+ * Measured over 16 KiB messages, this against the old code:+ *+ * Apple M4 Neoverse N2+ * AES-128-GCM 1.30 1.25+ * AES-192-GCM 1.22 1.25+ * AES-256-GCM 1.19 1.24+ *+ * The scheme is ARM's, from the 'big' AES-GCM kernel of+ * https://github.com/ARM-software/AArch64cryptolib, which is BSD-3-Clause,+ * (c) 2018-2019 ARM Limited. Their kernels under AArch64cryptolib_opt_bigger+ * are faster again and are NOT under that licence, whatever the repository's+ * LICENSE.md says; nothing here comes from those files.+ *+ * The table holds the twisted powers H^1 .. H^8 at htable[0 .. 7] and the+ * Karatsuba half of each -- its high 64 bits XOR its low -- in the first+ * eight bytes of htable[8 .. 15]. The running tag is kept the way GCM+ * writes it at every boundary, and swapped into the internal form on the way+ * in and out, which is two instructions. */ -/* reverse all 16 bytes */-CRYPTON_TARGET_ARMV8_CRYPTO-static inline uint8x16_t bswap128(uint8x16_t v)-{- return vextq_u8(vrev64q_u8(v), vrev64q_u8(v), 8);-}--/* shift the whole register left by n bytes, as _mm_slli_si128 does */-#define SHIFT_LEFT_BYTES(v, n) vextq_u8(vdupq_n_u8(0), (v), 16 - (n))-/* and right, as _mm_srli_si128 does */-#define SHIFT_RIGHT_BYTES(v, n) vextq_u8((v), vdupq_n_u8(0), (n))--#define SHL32(v, n) vreinterpretq_u8_u32(vshlq_n_u32(vreinterpretq_u32_u8(v), (n)))-#define SHR32(v, n) vreinterpretq_u8_u32(vshrq_n_u32(vreinterpretq_u32_u8(v), (n)))--CRYPTON_TARGET_ARMV8_CRYPTO-static inline uint8x16_t clmul_ll(uint8x16_t a, uint8x16_t b)-{- return vreinterpretq_u8_p128(vmull_p64(- (poly64_t) vgetq_lane_u64(vreinterpretq_u64_u8(a), 0),- (poly64_t) vgetq_lane_u64(vreinterpretq_u64_u8(b), 0)));-}+#define GHASH_MODC ((poly64_t) 0xC200000000000000ul) +/* the internal accumulator form, and back again: its own inverse */ CRYPTON_TARGET_ARMV8_CRYPTO-static inline uint8x16_t clmul_lh(uint8x16_t a, uint8x16_t b)+static inline uint8x16_t ghash_swap(uint8x16_t t) {- return vreinterpretq_u8_p128(vmull_p64(- (poly64_t) vgetq_lane_u64(vreinterpretq_u64_u8(a), 0),- (poly64_t) vgetq_lane_u64(vreinterpretq_u64_u8(b), 1)));+ t = vrev64q_u8(t);+ return vextq_u8(t, t, 8); } +/* the high and low halves XORed together, which is what Karatsuba wants */ CRYPTON_TARGET_ARMV8_CRYPTO-static inline uint8x16_t clmul_hl(uint8x16_t a, uint8x16_t b)+static inline poly64_t ghash_karat(poly64x2_t v) {- return vreinterpretq_u8_p128(vmull_p64(- (poly64_t) vgetq_lane_u64(vreinterpretq_u64_u8(a), 1),- (poly64_t) vgetq_lane_u64(vreinterpretq_u64_u8(b), 0)));+ return (poly64_t) veor_u64(vget_high_u64(vreinterpretq_u64_p64(v)),+ vget_low_u64(vreinterpretq_u64_p64(v))); } -CRYPTON_TARGET_ARMV8_CRYPTO-static inline uint8x16_t clmul_hh(uint8x16_t a, uint8x16_t b)-{- return vreinterpretq_u8_p128(vmull_high_p64(- vreinterpretq_p64_u8(a), vreinterpretq_p64_u8(b)));-}+/* the twisted power H^(i+1) */+#define GHASH_POW(ht, i) \+ vreinterpretq_p64_u8(vld1q_u8((const uint8_t *) &(ht)[i]))+/* and its Karatsuba half */+#define GHASH_KARAT(ht, i) \+ ((poly64_t) vgetq_lane_u64( \+ vreinterpretq_u64_u8(vld1q_u8((const uint8_t *) &(ht)[8 + (i)])), 0)) /*- * The 256-bit carry-less product of a (normal byte order) and b (already- * reversed, as it sits in the table), before the reflection fixup and the- * reduction. Split out from the reduction because both of those are linear- * over XOR: several products can be added together and fixed up just once,- * which is what gf_mul4 below does.+ * One block's three partial products, XORed into the accumulators. b is+ * already in the internal form; hp and hk are the power it is to meet. */-CRYPTON_TARGET_ARMV8_CRYPTO-static inline void clmul_pmull(uint8x16_t a, uint8x16_t b,- uint8x16_t *lo, uint8x16_t *hi)-{- uint8x16_t t3, t4, t5, t6;-- a = bswap128(a);-- t3 = clmul_ll(a, b);- t4 = clmul_lh(a, b);- t5 = clmul_hl(a, b);- t6 = clmul_hh(a, b);-- t4 = veorq_u8(t4, t5);- t5 = SHIFT_LEFT_BYTES(t4, 8);- t4 = SHIFT_RIGHT_BYTES(t4, 8);-- *lo = veorq_u8(t3, t5);- *hi = veorq_u8(t6, t4);-}+#define GHASH_MUL(b, hp, hk, H, M, L) \+ do { \+ poly64x2_t b__ = (b); \+ poly64x2_t hp__ = (hp); \+ (H) = veorq_u64((H), vreinterpretq_u64_p128( \+ vmull_high_p64(b__, hp__))); \+ (L) = veorq_u64((L), vreinterpretq_u64_p128(vmull_p64( \+ (poly64_t) vgetq_lane_u64(vreinterpretq_u64_p64(b__), 0), \+ (poly64_t) vgetq_lane_u64(vreinterpretq_u64_p64(hp__), 0)))); \+ (M) = veorq_u64((M), vreinterpretq_u64_p128( \+ vmull_p64(ghash_karat(b__), (hk)))); \+ } while (0) -/* Shift the 256-bit product left by one to undo GCM's bit reflection, then- * reduce modulo the GCM polynomial. This is the expensive half. */+/*+ * Finish the Karatsuba -- the middle accumulator still holds only the+ * (ah^al)(bh^bl) terms and wants the other two taken out of it -- and reduce+ * the 256 bits modulo the GCM polynomial. The result is in internal form.+ */ CRYPTON_TARGET_ARMV8_CRYPTO-static inline uint8x16_t gfred_pmull(uint8x16_t t3, uint8x16_t t6)+static inline uint64x2_t ghash_reduce(uint64x2_t H, uint64x2_t M, uint64x2_t L) {- uint8x16_t t2, t4, t5, t7, t8, t9;-- t7 = SHR32(t3, 31);- t8 = SHR32(t6, 31);- t3 = SHL32(t3, 1);- t6 = SHL32(t6, 1);-- t9 = SHIFT_RIGHT_BYTES(t7, 12);- t8 = SHIFT_LEFT_BYTES(t8, 4);- t7 = SHIFT_LEFT_BYTES(t7, 4);- t3 = vorrq_u8(t3, t7);- t6 = vorrq_u8(t6, t8);- t6 = vorrq_u8(t6, t9);-- t7 = SHL32(t3, 31);- t8 = SHL32(t3, 30);- t9 = SHL32(t3, 25);+ uint64x2_t t; - t7 = veorq_u8(t7, t8);- t7 = veorq_u8(t7, t9);- t8 = SHIFT_RIGHT_BYTES(t7, 4);- t7 = SHIFT_LEFT_BYTES(t7, 12);- t3 = veorq_u8(t3, t7);+ M = veorq_u64(M, H);+ M = veorq_u64(M, L); - t2 = SHR32(t3, 1);- t4 = SHR32(t3, 2);- t5 = SHR32(t3, 7);- t2 = veorq_u8(t2, t4);- t2 = veorq_u8(t2, t5);- t2 = veorq_u8(t2, t8);- t3 = veorq_u8(t3, t2);- t6 = veorq_u8(t6, t3);+ t = vreinterpretq_u64_p128(vmull_p64(+ (poly64_t) vgetq_lane_u64(H, 0), GHASH_MODC));+ H = vreinterpretq_u64_u8(vextq_u8(vreinterpretq_u8_u64(H),+ vreinterpretq_u8_u64(H), 8));+ M = veorq_u64(M, t);+ M = veorq_u64(M, H); - return bswap128(t6);+ t = vreinterpretq_u64_p128(vmull_p64(+ (poly64_t) vgetq_lane_u64(M, 0), GHASH_MODC));+ M = vreinterpretq_u64_u8(vextq_u8(vreinterpretq_u8_u64(M),+ vreinterpretq_u8_u64(M), 8));+ L = veorq_u64(L, t);+ return veorq_u64(L, M); } +/* a single block against H^1, accumulator in internal form */ CRYPTON_TARGET_ARMV8_CRYPTO-static uint8x16_t gfmul_pmull(uint8x16_t a, const uint8_t *htable)+static inline uint64x2_t ghash_one(uint64x2_t acc, uint8x16_t blk,+ const block128 *ht) {- uint8x16_t lo, hi;+ uint64x2_t H = vdupq_n_u64(0), M = H, L = H;+ poly64x2_t b; - clmul_pmull(a, vld1q_u8(htable), &lo, &hi);- return gfred_pmull(lo, hi);+ acc = vreinterpretq_u64_u8(vextq_u8(vreinterpretq_u8_u64(acc),+ vreinterpretq_u8_u64(acc), 8));+ b = vreinterpretq_p64_u64(veorq_u64(+ vreinterpretq_u64_u8(vrev64q_u8(blk)), acc));+ GHASH_MUL(b, GHASH_POW(ht, 0), GHASH_KARAT(ht, 0), H, M, L);+ return ghash_reduce(H, M, L); } /*- * With PMULL there is no 4-bit table to fill: H goes in at index 0, byte- * reversed, so that gfmul_pmull does not have to swap it every time. This- * mirrors crypton_aesni_hinit_pclmul.+ * Twist H and raise it to the powers a batch needs. *- * Indices 1..7 get H^2 .. H^8, which is what lets a group of blocks fold- * into one reduction: gf_mul4 uses the first four, the GCM loop all eight.- * The table has sixteen slots, so they are free.+ * The twist is a shift left by one with 0xC2000..01 folded back in when a+ * bit falls off the top -- the same correction the old reduction applied to+ * every product, done once here instead. Each further power is one multiply+ * in the twisted domain; the result comes out of ghash_reduce with its+ * halves swapped, which a batch undoes on the way in, so a stored power has+ * to be swapped back. */ CRYPTON_TARGET_ARMV8_CRYPTO void crypton_aes_armv8_hinit_pmull(block128 *htable, const block128 *h) {- uint8x16_t p;+ uint8x16_t hk = vrev64q_u8(vld1q_u8((const uint8_t *) h));+ uint64x2_t shl = vshlq_n_u64(vreinterpretq_u64_u8(hk), 1);+ uint64x2_t shr = vreinterpretq_u64_s64(+ vshrq_n_s64(vreinterpretq_s64_u8(hk), 63));+ uint8x16_t mask = vextq_u8(vreinterpretq_u8_u64(shr),+ vreinterpretq_u8_u64(shr), 12);+ uint64x2_t tc = vdupq_n_u64(0);+ poly64x2_t base, p; int i; - htable[0].q[0] = bitfn_swap64(h->q[1]);- htable[0].q[1] = bitfn_swap64(h->q[0]);+ tc = vsetq_lane_u64(0xC200000000000001ul, tc, 0);+ tc = vsetq_lane_u64(1, tc, 1);+ tc = vandq_u64(vreinterpretq_u64_u8(mask), tc);+ base = vreinterpretq_p64_u64(veorq_u64(tc, shl)); - p = vld1q_u8((const uint8_t *) h);- for (i = 1; i < 8; i++) {- p = gfmul_pmull(p, (const uint8_t *) &htable[0]);- vst1q_u8((uint8_t *) &htable[i], bswap128(p));+ p = base;+ for (i = 0; i < 8; i++) {+ uint64x2_t H = vdupq_n_u64(0), M = H, L = H, r;++ vst1q_u8((uint8_t *) &htable[i],+ vreinterpretq_u8_p64(p));+ vst1q_u8((uint8_t *) &htable[8 + i],+ vreinterpretq_u8_u64(+ vdupq_n_u64((uint64_t) ghash_karat(p))));++ GHASH_MUL(p, base, ghash_karat(base), H, M, L);+ r = ghash_reduce(H, M, L);+ p = vreinterpretq_p64_u8(vextq_u8(vreinterpretq_u8_u64(r),+ vreinterpretq_u8_u64(r), 8)); } } CRYPTON_TARGET_ARMV8_CRYPTO void crypton_aes_armv8_gf_mul_pmull(block128 *a, const block128 *htable) {- vst1q_u8((uint8_t *) a,- gfmul_pmull(vld1q_u8((const uint8_t *) a), (const uint8_t *) htable));+ uint64x2_t acc = vreinterpretq_u64_u8(+ ghash_swap(vld1q_u8((const uint8_t *) a)));++ acc = ghash_one(acc, vdupq_n_u8(0), htable);+ vst1q_u8((uint8_t *) a, ghash_swap(vreinterpretq_u8_u64(acc))); } /*@@ -320,22 +331,30 @@ void crypton_aes_armv8_gf_mul4_pmull(block128 *a, const block128 *blocks, const block128 *htable) {- uint8x16_t lo, hi, l, h;+ uint64x2_t acc = vreinterpretq_u64_u8(+ ghash_swap(vld1q_u8((const uint8_t *) a)));+ uint64x2_t H = vdupq_n_u64(0), M = H, L = H;+ poly64x2_t b; int i; - clmul_pmull(veorq_u8(vld1q_u8((const uint8_t *) a),- vld1q_u8((const uint8_t *) &blocks[0])),- vld1q_u8((const uint8_t *) &htable[3]), &lo, &hi);+ acc = vreinterpretq_u64_u8(vextq_u8(vreinterpretq_u8_u64(acc),+ vreinterpretq_u8_u64(acc), 8));+ b = vreinterpretq_p64_u64(veorq_u64(+ vreinterpretq_u64_u8(vrev64q_u8(+ vld1q_u8((const uint8_t *) &blocks[0]))), acc));+ GHASH_MUL(b, GHASH_POW(htable, 3), GHASH_KARAT(htable, 3), H, M, L); for (i = 1; i < 4; i++) {- clmul_pmull(vld1q_u8((const uint8_t *) &blocks[i]),- vld1q_u8((const uint8_t *) &htable[3 - i]), &l, &h);- lo = veorq_u8(lo, l);- hi = veorq_u8(hi, h);+ b = vreinterpretq_p64_u8(vrev64q_u8(+ vld1q_u8((const uint8_t *) &blocks[i])));+ GHASH_MUL(b, GHASH_POW(htable, 3 - i),+ GHASH_KARAT(htable, 3 - i), H, M, L); } - vst1q_u8((uint8_t *) a, gfred_pmull(lo, hi));+ acc = ghash_reduce(H, M, L);+ vst1q_u8((uint8_t *) a, ghash_swap(vreinterpretq_u8_u64(acc))); }+ int crypton_aes_armv8_pmull_available(void) {
cbits/aes/armv8_impl.c view
@@ -25,8 +25,6 @@ #define EACH1(m) m(0) #define EACH8(m) m(0) m(1) m(2) m(3) m(4) m(5) m(6) m(7)-/* the blocks after the first; GHASH folds block 0 in with the tag */-#define EACH7(m) m(1) m(2) m(3) m(4) m(5) m(6) m(7) #define LOAD_IN(i) s[i] = vld1q_u8((const uint8_t *) (input + (i))); #define STORE_OUT(i) vst1q_u8((uint8_t *) (output + (i)), s[i]);@@ -294,11 +292,15 @@ * runs the two together, and holding a group back only adds copies. The * rest fail for one reason -- none of them makes the loop shorter. * Karatsuba buys a PMULL for two EOR and an EXT, and the folded table turns- * sixteen `dup` into sixteen `ld1r` and sixteen more address adds. A count- * that does come down wants the data laid out differently, which is what- * OpenSSL's aes-gcm-armv8_64.pl is; it is Apache-2.0 and in OpenSSL's tree- * only, and CRYPTOGAMS, which cbits/asm vendors from, publishes AES and- * GHASH separately and nothing that stitches them.+ * sixteen `dup` into sixteen `ld1r` and sixteen more address adds.+ *+ * That last sentence used to end by saying a count which does come down+ * wants the data laid out differently. It does, and since the GHASH was+ * rewritten against a twisted H -- see cbits/aes/armv8.c -- it is laid out+ * differently, so the figures above are what the *previous* GHASH gave.+ * Karatsuba pays now that the reduction it has to carry is a third of what+ * it was; the other three are untried in the new representation and the+ * first of them has no more reason to work than it had. */ #define GCM_CTR(i) s[i] = vreinterpretq_u8_u32(vsetq_lane_u32(cpu_to_be32(c + 1 + (i)), base, 3)); #define GCM_ENC(i) { const uint8x16_t m_ = vld1q_u8(input + 16 * (i)); \@@ -307,27 +309,33 @@ #define GCM_DEC(i) { const uint8x16_t m_ = vld1q_u8(input + 16 * (i)); \ vst1q_u8(output + 16 * (i), veorq_u8(s[i], m_)); \ s[i] = m_; }-#define GCM_GHASH(i) { uint8x16_t l_, h_; \- clmul_pmull(s[i], vld1q_u8((const uint8_t *) &ht[WAY - 1 - (i)]), \- &l_, &h_); \- glo = veorq_u8(glo, l_); ghi = veorq_u8(ghi, h_); }+#define GCM_GHASH(i) \+ { \+ poly64x2_t b_ = vreinterpretq_p64_u8(vrev64q_u8(s[i])); \+ if ((i) == 0) \+ b_ = vreinterpretq_p64_u64(veorq_u64( \+ vreinterpretq_u64_p64(b_), acc)); \+ GHASH_MUL(b_, GHASH_POW(ht, WAY - 1 - (i)), \+ GHASH_KARAT(ht, WAY - 1 - (i)), gH, gM, gL); \+ } /* the eight blocks now in s[] are the ciphertext; fold them into the tag */ #define GCM_FOLD() \ do { \- uint8x16_t glo, ghi; \- clmul_pmull(veorq_u8(tag, s[0]), \- vld1q_u8((const uint8_t *) &ht[WAY - 1]), \- &glo, &ghi); \- EACH7(GCM_GHASH) \- tag = gfred_pmull(glo, ghi); \+ uint64x2_t gH = vdupq_n_u64(0), gM = gH, gL = gH; \+ acc = vreinterpretq_u64_u8( \+ vextq_u8(vreinterpretq_u8_u64(acc), \+ vreinterpretq_u8_u64(acc), 8)); \+ EACH8(GCM_GHASH) \+ acc = ghash_reduce(gH, gM, gL); \ } while (0) #define GCM_PROLOGUE \ const uint8_t *rk = FWD(key); \ const block128 *ht = gcm->htable; \ uint8x16_t s[WAY]; \- uint8x16_t tag = vld1q_u8((const uint8_t *) &gcm->tag); \+ uint64x2_t acc = vreinterpretq_u64_u8( \+ ghash_swap(vld1q_u8((const uint8_t *) &gcm->tag))); \ uint32_t c = be32_to_cpu(gcm->civ.d[3]); \ uint32x4_t base = vreinterpretq_u32_u8(vld1q_u8((const uint8_t *) &gcm->civ)) @@ -340,13 +348,14 @@ ENC_ROUNDS(EACH1); \ s[0] = veorq_u8(s[0], m_); \ (store_c); \- tag = gfmul_pmull(veorq_u8(tag, (ghash_of)), (const uint8_t *) ht); \+ acc = ghash_one(acc, (ghash_of), ht); \ } while (0) #define GCM_EPILOGUE \ do { \ gcm->civ.d[3] = cpu_to_be32(c); \- vst1q_u8((uint8_t *) &gcm->tag, tag); \+ vst1q_u8((uint8_t *) &gcm->tag, \+ ghash_swap(vreinterpretq_u8_u64(acc))); \ } while (0) CRYPTON_TARGET_ARMV8_CRYPTO@@ -380,8 +389,7 @@ block128_zero(&m); for (i = 0; i < length; i++) output[i] = m.b[i] = o.b[i];- tag = gfmul_pmull(veorq_u8(tag, vld1q_u8((const uint8_t *) &m)),- (const uint8_t *) ht);+ acc = ghash_one(acc, vld1q_u8((const uint8_t *) &m), ht); } GCM_EPILOGUE; }@@ -418,8 +426,7 @@ vst1q_u8((uint8_t *) &o, s[0]); for (i = 0; i < length; i++) output[i] = o.b[i];- tag = gfmul_pmull(veorq_u8(tag, vld1q_u8((const uint8_t *) &m)),- (const uint8_t *) ht);+ acc = ghash_one(acc, vld1q_u8((const uint8_t *) &m), ht); } GCM_EPILOGUE; }@@ -581,20 +588,23 @@ /* start a batch, or continue one; blen is how many blocks this batch holds */ #define FG_ABSORB(blk) \ do { \- uint8x16_t b_ = (blk), l_, h_; \+ poly64x2_t b_ = vreinterpretq_p64_u8(vrev64q_u8(blk)); \ if (bn == 0) { \ uint32_t left_ = gtotal - gidx; \ blen = left_ < WAY ? left_ : WAY; \- b_ = veorq_u8(b_, tag); \- glo = vdupq_n_u8(0); \- ghi = vdupq_n_u8(0); \+ acc = vreinterpretq_u64_u8( \+ vextq_u8(vreinterpretq_u8_u64(acc), \+ vreinterpretq_u8_u64(acc), 8)); \+ b_ = vreinterpretq_p64_u64(veorq_u64( \+ vreinterpretq_u64_p64(b_), acc)); \+ gH = vdupq_n_u64(0); \+ gM = gH; \+ gL = gH; \ } \- clmul_pmull(b_, vld1q_u8((const uint8_t *) &ht[blen - bn - 1]), \- &l_, &h_); \- glo = veorq_u8(glo, l_); \- ghi = veorq_u8(ghi, h_); \+ GHASH_MUL(b_, GHASH_POW(ht, blen - bn - 1), \+ GHASH_KARAT(ht, blen - bn - 1), gH, gM, gL); \ gidx++; bn++; \- if (bn == blen) { tag = gfred_pmull(glo, ghi); bn = 0; } \+ if (bn == blen) { acc = ghash_reduce(gH, gM, gL); bn = 0; } \ } while (0) /* a block that is short, zero padded, as GHASH wants it */@@ -612,7 +622,8 @@ { const uint8_t *rk = FWD(key); uint8x16_t s[WAY];- uint8x16_t tag = vdupq_n_u8(0), glo = tag, ghi = tag, ek0;+ uint8x16_t ek0;+ uint64x2_t acc = vdupq_n_u64(0), gH = acc, gM = acc, gL = acc; uint32x4_t base; uint32_t c = 1, bn = 0, blen = 0, gidx = 0; uint32_t gtotal = (aadlen + 15) / 16 + (inlen + 15) / 16 + 1;@@ -677,7 +688,7 @@ { uint8_t tbuf[16];- vst1q_u8(tbuf, veorq_u8(tag, ek0));+ vst1q_u8(tbuf, veorq_u8(ghash_swap(vreinterpretq_u8_u64(acc)), ek0)); memcpy(out + inlen, tbuf, taglen); } @@ -706,7 +717,8 @@ { const uint8_t *rk = FWD(key); uint8x16_t s[WAY];- uint8x16_t tag = vdupq_n_u8(0), glo = tag, ghi = tag, ek0;+ uint8x16_t ek0;+ uint64x2_t acc = vdupq_n_u64(0), gH = acc, gM = acc, gL = acc; uint32x4_t base; uint32_t c = 1, bn = 0, blen = 0, gidx = 0; uint32_t gtotal = (aadlen + 15) / 16 + (inlen + 15) / 16 + 1;@@ -770,7 +782,7 @@ for (i = 0; i < 8; i++) lenb[8 + i] = (uint8_t) (lc >> (56 - 8 * i)); FG_ABSORB(vld1q_u8(lenb)); - vst1q_u8(want, veorq_u8(tag, ek0));+ vst1q_u8(want, veorq_u8(ghash_swap(vreinterpretq_u8_u64(acc)), ek0)); if (outtag) { /* The caller holds the expected tag and will compare it itself. */ memcpy(outtag, want, taglen);@@ -786,7 +798,6 @@ #undef WAY #undef EACH1-#undef EACH7 #undef EACH8 #undef LOAD_IN #undef STORE_OUT
cbits/crypton_sha1.c view
@@ -211,7 +211,7 @@ * They arrived long after the x86-64 baseline, so ask before using them. * Two threads racing to answer here both write the same value. */-extern void crypton_sha1_x86_do_chunk(uint32_t state[5], const uint32_t buf[16]);+extern void crypton_sha1_x86_do_chunk(uint32_t state[5], const uint8_t buf[64]); extern void crypton_sha1_x86_do_chunks(uint32_t state[5], const uint8_t *data, uint32_t blocks);
cbits/sha1_x86.c view
@@ -168,7 +168,7 @@ } /* the one-block form, for the partial block a message ends with */-void crypton_sha1_x86_do_chunk(uint32_t state[5], const uint32_t buf[16])+void crypton_sha1_x86_do_chunk(uint32_t state[5], const uint8_t buf[64]) { crypton_sha1_x86_do_chunks(state, (const uint8_t *) buf, 1); }
cbits/tests/ct/README view
@@ -25,6 +25,7 @@ decaf Ed448 signing and X448, both private scalars chapoly the ChaCha20 key, the plaintext, and the Poly1305 key aes the AES key and the plaintext, through ECB and GCM+ aes_armv8 the same driver again, on AArch64, against the instructions The aes driver is built against cbits/aes/generic.c and cbits/aes/gf.c on purpose, rather than whatever the machine offers. AES-NI and the ARMv8@@ -35,6 +36,19 @@ therefore expected and is a property of those implementations, not a defect found in them; it is here so that the size of it is written down rather than assumed. Everything else is expected to be silent.++On AArch64 the same driver is then built a second time, as aes_armv8, against+cbits/aes/armv8.c with the crypto extension turned on. AESE, AESMC and PMULL+look nothing up and branch on nothing, so that run must report nothing at all+-- not "nothing outside known.txt", nothing; a table site appearing there+would mean the dispatch had not picked the instructions. The two runs keep+each other honest: the table-driven one has to report and the instruction one+has to be silent, and either going the wrong way says the run is not+measuring what it claims to.++Until that was added the harness ran only on x86-64, so crypton's AArch64 AES+and GHASH had never been put to it -- which was noticed when the GHASH was+rewritten. What round eight found ----------------------
+ cbits/tests/ct/ct_aes_armv8.c view
@@ -0,0 +1,12 @@+/* The same driver as ct_aes.c, built against the AArch64 implementation+ * instead of the table-driven C.+ *+ * AESE, AESMC and PMULL look nothing up and branch on nothing, so this one+ * must report nothing at all -- not "nothing unknown", nothing. The+ * table-driven run of the same driver is what keeps that honest: if the+ * marking stopped reaching the code, that run would fall silent and fail,+ * and a silence here would mean no more than a silence there.+ *+ * Until this existed the constant-time harness ran only on x86-64, so+ * crypton's AArch64 AES and GHASH had never been put to it. */+#include "ct_aes.c"
+ cbits/tests/ct/known.txt view
@@ -0,0 +1,54 @@+# Places where a secret reaches a branch that are known, understood and not+# defects. A driver reporting only these passes; anything else fails.+#+# Every entry is "file:line what it is". Keep it short: a long one means+# something has been accepted that should have been fixed.++# assert() on a value derived from the secret. The asserted condition holds+# on every input -- these check an internal invariant of the reduction, not+# anything about the data -- so the branch goes the same way every time and+# no timing follows from it. They are reported because crypton's C is built+# without NDEBUG, so assert() is live in a released library. See the round+# eight notes in cbits/tests/ct/README.+p256.c:200 assert(top <= 1) in crypton_p256_modmul+p256.c:204 assert(top == 0) in crypton_p256_modmul+f_generic.c:94 assert on the borrow in crypton_gf_448_strong_reduce+f_generic.c:106 assert on the carry in crypton_gf_448_strong_reduce++# The same thing for a different reason. crypton_gf_invert asserts that what+# it inverted had an inverse, and the two callers that ask for the assertion+# are inverting a projective z, which is never zero for a point on the curve.+# So this one holds because of what the callers pass rather than because of+# arithmetic, and it too goes the same way on every valid input.+decaf.c:136 assert(ret) in crypton_gf_invert++# The table-driven AES and the table-driven GHASH index with a byte of the+# state, which is what makes them fast and what makes them variable-time.+# That is a property of those implementations rather than a defect in them;+# a machine with AES-NI or the ARMv8 instructions runs neither.+generic.c the AES tables, in key expansion and in the rounds+gf.c the GHASH table+crypton_aes.c the same tables, attributed to the code that inlines them+block128.h likewise++# AArch64 only. gcc keeps a carry in the flags and takes it out with `cset`+# or `cinc`, where on x86-64 it uses `adc` and the carry never leaves the+# data path. memcheck calls `cset` a conditional move and reports it, and+# it attributes the report to the branch that ends the block rather than to+# the `cset` itself -- so the site it names is a loop back-edge, not the+# instruction that touched the secret.+#+# Checked by disassembling the address memcheck named, in a -no-pie build so+# that its addresses and objdump's agree. At every one of these the branch+# reads flags from a `cmp` against a loop counter or a pointer bound, both+# public; the only instructions consuming the secret's flags are `cset` and+# `cinc`, which do not branch and take the same time either way. In decaf's+# lookup the secret only reaches a `dup` and a NEON `and`/`orr`.+#+# 400f60 cmp x3, #0x20 <- public: four digits of 8 bytes+# 400f64 b.ne 400f3c <- what memcheck names+# 404c6c cmp x3, x6 <- public: j against n_table+# 404c70 b.ne 404c30 <- what memcheck names+p256.c:147 addM's loop; the carry is taken with cset and cinc+p256.c:149 the same+constant_time.h:150 decaf's constant-time lookup, over j < n_table
cbits/tests/ct/run.sh view
@@ -32,6 +32,12 @@ # table-driven code every other machine runs. aes_src="cbits/crypton_aes.c cbits/aes/generic.c cbits/aes/gf.c" +# And, on AArch64, the same driver again against the instructions. That one+# has to be silent; this one has to report. Either going the wrong way says+# the run is not measuring what it claims to.+armv8_src="$aes_src cbits/aes/armv8.c cbits/crypton_cpu.c"+armv8_inc="-DWITH_ARMV8_CRYPTO -march=armv8-a+crypto -Icbits/aes"+ status=0 have_valgrind=no ct_define=@@ -56,11 +62,19 @@ --log-file="$out/$name.log" "$out/$name" > /dev/null 2>&1 || true n=$(grep -c "^==[0-9]*== \(Conditional jump\|Use of uninitialised\)" "$out/$name.log" || true) # Which places did it name? Only the frame the report is against -- the- # "at" line -- is the place; the "by" lines below it are how the code got- # there and are not themselves branching on anything. A site is+ # first "at" line under the complaint -- is the place; the "by" lines+ # below it are how the code got there and are not themselves branching+ # on anything. Nor is the "at" line under "Uninitialised value was+ # created by", which --track-origins prints to say where the value came+ # from: that frame is a stack allocation, not a branch, and taking it+ # for one put a function's opening brace on the list. A site is # "file:line", and the ones listed in known.txt are understood.- sites=$(sed -n 's/^==[0-9]*== at 0x[0-9A-Fa-f]*: [A-Za-z_0-9]* (\([^)]*\))$/\1/p' \- "$out/$name.log" | grep -v '^ct_' | sort -u)+ sites=$(awk '+ /^==[0-9]*== (Conditional jump|Use of uninitialised)/ { want = 1; next }+ want && /^==[0-9]*== at 0x/ { print; want = 0 }+ ' "$out/$name.log" |+ sed -n 's/^==[0-9]*== at 0x[0-9A-Fa-f]*: [A-Za-z_0-9]* (\([^)]*\))$/\1/p' |+ grep -v '^ct_' | sort -u) unknown= for site in $sites; do file=${site%%:*}@@ -94,6 +108,22 @@ echo "note aes: $n report(s), from $(echo "$sites" | tr '\n' ' ')" fi ;;+ aes_armv8)+ # The opposite demand, and known.txt does not apply: the entries in+ # it are for the tables, and this build is not supposed to reach+ # them. Anything at all here is a finding, including a table site,+ # which would mean the dispatch did not pick the instructions.+ if [ "$n" -eq 0 ]; then+ echo "ok aes_armv8: the instructions decided nothing"+ else+ echo "FAIL aes_armv8: $n report(s) from the AArch64 AES or GHASH,"+ echo " which look nothing up and should branch on nothing:"+ for site in $sites; do echo " $site"; done+ sed -n '/Conditional jump\|Use of uninitialised/,/^==[0-9]*== $/p' \+ "$out/$name.log" | head -30 | sed 's/^/ /'+ status=1+ fi+ ;; *) if [ "$n" -eq 0 ]; then echo "ok $name: the secret decided nothing"@@ -121,6 +151,14 @@ run_one decaf "$decaf_src" "$decaf_inc" run_one chapoly "cbits/crypton_chacha.c cbits/crypton_poly1305.c" "" run_one aes "$aes_src" ""++# Only where the instructions exist. Elsewhere there is nothing to measure+# and the build would not even compile.+case $(uname -m) in+aarch64 | arm64)+ run_one aes_armv8 "$armv8_src" "$armv8_inc"+ ;;+esac if [ "$have_valgrind" = no ]; then echo "skip no valgrind here, so none of the above was checked"
+ cbits/tests/perf/floors.txt view
@@ -0,0 +1,22 @@+# A primitive that falls off its accelerated path does not get a little+# slower, it falls off a cliff: #274 took SHA-256 from 3396 MB/s to 644 on an+# Apple M4, a factor of five, and no test noticed because the answers stayed+# right.+#+# Absolute numbers cannot be checked here. ubuntu-latest is not one machine+# -- EPYC 7763, EPYC 9V74, Xeon 8370C and Xeon 6973P-C have all turned up, and+# the ones with AVX-512 differ from the ones without by more than twofold on+# AES-GCM. So each line is a ratio between two primitives measured in the+# same run on the same machine, with a floor generous enough that only a cliff+# reaches it.+#+# faster slower floor what it would catch+#+# Measured for the floors: an M4 gives 1.00, 0.56, 4.04 and 0.58 for the four+# below; an EPYC 7763 gives 0.94, 0.46, 2.75 and 0.55. Every floor is less+# than half of both, and #274 put the first at 0.19.++sha256 sha1 0.40 SHA-256 off the SHA-2 instructions+sha512 sha1 0.20 SHA-512 off its assembly+aes128gcm chachapoly 1.00 AES-GCM off AES-NI or the ARMv8 AES instructions+sha3-256 sha512 0.25 SHA-3 off the SHA-3 instructions
+ cbits/tests/perf/run.sh view
@@ -0,0 +1,102 @@+#!/bin/sh+# Watching for a primitive that has fallen off its accelerated path.+#+# #274 took SHA-256 from 3396 MB/s to 644 on an Apple M4 and shipped, because+# the answers were right and only the speed was wrong. No test can catch+# that; this is what does.+#+# What it checks is ratios between primitives measured in the same run, not+# absolute throughput, because the runner is not the same machine twice --+# see cbits/tests/perf/floors.txt. A ratio is only useful against a cliff;+# this will not notice a few per cent, and is not meant to.+#+# The last thing it does is build the library again with the AES acceleration+# turned off and check that the AES line then fails. Without that, a run+# where the measurement had quietly stopped working would look exactly like a+# run where everything was fast.+#+# Usage: cbits/tests/perf/run.sh [build-dir]+set -eu++root=$(CDPATH= cd -- "$(dirname -- "$0")/../../.." && pwd)+out=${1:-$(mktemp -d)}+cc=${CC:-cc}+mkdir -p "$out"+cd "$root"++# The harness links against the library as cabal built it, so that what is+# measured is the configuration the package actually ships.+build_harness() {+ builddir=$1; bin=$2; shift 2+ cabal build lib:crypton --builddir="$builddir" -v0 "$@" > /dev/null+ archive=$(find "$builddir" -name 'libHScrypton-*.a' | head -1)+ test -n "$archive" || { echo "no library archive under $builddir"; exit 1; }+ $cc -O3 -Icbits -Icbits/include64 -Icbits/include32 \+ -o "$bin" cbits/tests/perf/throughput.c "$archive" 2>/dev/null ||+ $cc -O3 -Icbits -Icbits/include64 \+ -o "$bin" cbits/tests/perf/throughput.c "$archive"+}++measure() {+ best=0+ for _ in 1 2 3; do+ v=$("$1" "$2" 2>/dev/null || echo 0)+ best=$(awk -v a="$best" -v b="$v" 'BEGIN{print (b>a)?b:a}')+ done+ echo "$best"+}++# Every ratio in floors.txt, against the binary named. Prints one line each+# and returns the number that were under the floor.+check() {+ bin=$1; label=$2; quiet=${3:-no}+ bad=0+ while read -r fast slow floor _rest; do+ case "$fast" in ''|\#*) continue ;; esac+ a=$(measure "$bin" "$fast")+ b=$(measure "$bin" "$slow")+ r=$(awk -v a="$a" -v b="$b" 'BEGIN{printf "%.2f", (b>0)?a/b:0}')+ under=$(awk -v r="$r" -v f="$floor" 'BEGIN{print (r<f)?1:0}')+ if [ "$under" = 1 ]; then+ bad=$((bad + 1))+ [ "$quiet" = yes ] ||+ printf 'BELOW %-10s %-11s %s / %s = %s, floor %s\n' \+ "$fast" "$slow" "$a" "$b" "$r" "$floor"+ else+ [ "$quiet" = yes ] ||+ printf 'ok %-10s %-11s %s / %s = %s, floor %s\n' \+ "$fast" "$slow" "$a" "$b" "$r" "$floor"+ fi+ done < cbits/tests/perf/floors.txt+ return $bad+}++build_harness "$out/dist-perf" "$out/throughput"+set +e+check "$out/throughput" "as shipped"+failed=$?+set -e++# The calibration: with the AES acceleration compiled out, the AES line has to+# fail. If it does not, the measurement is not reaching the library and+# nothing above meant anything.+echo "--- with -f-support_aesni, the AES line must fail ---"+build_harness "$out/dist-noaes" "$out/throughput-noaes" -f-support_aesni+set +e+check "$out/throughput-noaes" "no AES" yes+noaes=$?+set -e+if [ "$noaes" -eq 0 ]; then+ echo "FAIL the build without AES acceleration passed every floor, so this"+ echo " job is not measuring the library and its result means nothing"+ exit 1+fi+echo "ok the detector notices a primitive taken off its fast path"++if [ "$failed" -ne 0 ]; then+ echo ""+ echo "$failed ratio(s) under the floor: a primitive has lost its"+ echo "accelerated path, as in #274. The floors are in"+ echo "cbits/tests/perf/floors.txt with what each one is for."+ exit 1+fi
+ cbits/tests/perf/throughput.c view
@@ -0,0 +1,156 @@+/* Throughput of the primitives that have an accelerated implementation, one+ * per process so that a caller can ask for them one at a time.+ *+ * Prints MB/s over 16 KiB. The state is set up once and the same buffer run+ * through it, which is the shape `openssl speed` measures and the shape the+ * README's tables are in.+ *+ * This is here to be compared with itself -- see run.sh -- and not to be+ * quoted. A number from a CI runner is a number from whichever machine the+ * job landed on.+ */+#include <stdio.h>+#include <string.h>+#include <stdlib.h>+#include <stdint.h>+#include <time.h>++#include "crypton_aes.h"+#include "crypton_sha1.h"+#include "crypton_sha256.h"+#include "crypton_sha512.h"+#include "crypton_sha3.h"+#include "crypton_chacha.h"+#include "crypton_poly1305.h"++#define LEN 16384+#define REPS 12++static uint8_t inb[LEN], outb[LEN + 64];+static uint64_t sink;++static double now_us(void)+{+ struct timespec ts;+ clock_gettime(CLOCK_MONOTONIC, &ts);+ return ts.tv_sec * 1e6 + ts.tv_nsec / 1e3;+}++static void bench_gcm(int keybits, int iters)+{+ aes_key key;+ aes_gcm gcm;+ uint8_t kb[32], iv[12], tag[16];+ int i;+ for (i = 0; i < 32; i++) kb[i] = (uint8_t)(i * 7);+ for (i = 0; i < 12; i++) iv[i] = (uint8_t)(i + 3);+ crypton_aes_initkey(&key, kb, keybits / 8);+ crypton_aes_gcm_init(&gcm, &key, iv, 12);+ for (i = 0; i < iters; i++) {+ crypton_aes_gcm_encrypt(outb, &gcm, &key, inb, LEN);+ sink += outb[i & 1023];+ }+ crypton_aes_gcm_finish(tag, &gcm, &key);+ sink += tag[0];+}++static void bench_chachapoly(int iters)+{+ crypton_chacha_context ctx;+ poly1305_ctx pctx;+ poly1305_key pkey;+ poly1305_mac mac;+ uint8_t kb[32], iv[12];+ int i;+ for (i = 0; i < 32; i++) kb[i] = (uint8_t)(i * 5);+ for (i = 0; i < 12; i++) iv[i] = (uint8_t)(i + 1);+ memcpy(&pkey, kb, sizeof(pkey));+ for (i = 0; i < iters; i++) {+ crypton_chacha_init(&ctx, 20, 32, kb, 12, iv);+ crypton_chacha_combine(outb, &ctx, inb, LEN);+ crypton_poly1305_init(&pctx, &pkey);+ crypton_poly1305_update(&pctx, outb, LEN);+ crypton_poly1305_finalize(mac, &pctx);+ sink += mac[0] + outb[i & 1023];+ }+}++static void bench_sha1(int iters)+{+ struct sha1_ctx c;+ uint8_t out[20];+ int i;+ for (i = 0; i < iters; i++) {+ crypton_sha1_init(&c);+ crypton_sha1_update(&c, inb, LEN);+ crypton_sha1_finalize(&c, out);+ sink += out[0];+ }+}++static void bench_sha256(int iters)+{+ struct sha256_ctx c;+ uint8_t out[32];+ int i;+ for (i = 0; i < iters; i++) {+ crypton_sha256_init(&c);+ crypton_sha256_update(&c, inb, LEN);+ crypton_sha256_finalize(&c, out);+ sink += out[0];+ }+}++static void bench_sha512(int iters)+{+ struct sha512_ctx c;+ uint8_t out[64];+ int i;+ for (i = 0; i < iters; i++) {+ crypton_sha512_init(&c);+ crypton_sha512_update(&c, inb, LEN);+ crypton_sha512_finalize(&c, out);+ sink += out[0];+ }+}++static void bench_sha3(int iters)+{+ /* sha3_ctx ends in a flexible array the caller provides room for. */+ uint8_t raw[SHA3_CTX_BUF_MAX_SIZE];+ struct sha3_ctx *c = (struct sha3_ctx *)raw;+ uint8_t out[32];+ int i;+ for (i = 0; i < iters; i++) {+ crypton_sha3_init(c, 256);+ crypton_sha3_update(c, inb, LEN);+ crypton_sha3_finalize(c, 256, out);+ sink += out[0];+ }+}++int main(int argc, char **argv)+{+ const char *algo = argc > 1 ? argv[1] : "sha256";+ int iters = 2000, r, i;+ double best = 1e30;++ for (i = 0; i < LEN; i++) inb[i] = (uint8_t)(i * 17 + 3);++ for (r = 0; r < REPS; r++) {+ double t0 = now_us(), t1;+ if (!strcmp(algo, "aes128gcm")) bench_gcm(128, iters);+ else if (!strcmp(algo, "aes256gcm")) bench_gcm(256, iters);+ else if (!strcmp(algo, "chachapoly")) bench_chachapoly(iters);+ else if (!strcmp(algo, "sha1")) bench_sha1(iters);+ else if (!strcmp(algo, "sha256")) bench_sha256(iters);+ else if (!strcmp(algo, "sha512")) bench_sha512(iters);+ else if (!strcmp(algo, "sha3-256")) bench_sha3(iters);+ else { fprintf(stderr, "unknown algo %s\n", algo); return 2; }+ t1 = now_us();+ if (r > 1 && t1 - t0 < best) best = t1 - t0;+ }+ if (sink == 0) return 3;+ printf("%.1f\n", (double)LEN * iters / best); /* bytes/us == MB/s */+ return 0;+}
crypton.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: crypton-version: 2.1.4+version: 2.1.5 license: BSD-3-Clause license-file: LICENSE copyright: Vincent Hanquez <vincent@snarc.org>@@ -72,6 +72,7 @@ cbits/s2n/x86_att/*.S cbits/tests/ct/*.c cbits/tests/ct/*.h+ cbits/tests/ct/known.txt cbits/tests/ct/README cbits/tests/ct/run.sh cbits/tests/endian/*.c@@ -83,6 +84,9 @@ cbits/tests/fuzz/README cbits/tests/fuzz/corpus/*.bin cbits/tests/fuzz/run.sh+ cbits/tests/perf/*.c+ cbits/tests/perf/floors.txt+ cbits/tests/perf/run.sh cbits/tests/scrub/*.c cbits/tests/scrub/README cbits/tests/scrub/known.txt