Skip to content

v5.1: Faster AES-256 & SHA-256 ? 🔑

Choose a tag to compare

View all tags
@ashvardanian ashvardanian released this 05 Aug 15:09
v5.1.0
16eede6

AES-256 and SHA-256 are some of the world's most common workloads implemented in software and hardware to accelerate encryption and hashing. Both have been optimized for decades and on x86 basically converged to more-or-less the same pure Asm snippets reused in most TLS & cryptography libraries. There are however multiple optimization axis still left to explore:

  1. Parallelize across input streams, where you are simultaneously computing checksums of more than one file at a time. To my knowledge, the only other libraries doing that are Intel's ISA-L Crypto and intel-ipsec-mb, and neither is widely used, easy to integrate, or friendly to small inputs. That's one of those areas, where using vanilla Skylake-generation wide AVX-512 intrinsics is more productive than relying on specialized SHA hardware.
  2. Better leverage specialized, wider, and newer hardware where possible, like the 4-way AES computation with VAES and faster GHASH for authentication via VPCLMULQDQ. OpenSSL v3.0.13 runs it 1-way, and Rust's Ring v0.17.14 does only 2-way.

Those points come with their challenges and limitations. More on that and performance guidance numbers below.

Hashing: SHA-256

The first axis is the only one SHA-256 has. One digest is a serial chain of 32 dependent SHA256RNDS2 at four cycles each, so no vector width shortens it, and every single-message implementation lands within a few percent of every other — they all ride the same instructions. Sixteen independent messages have no dependency between them at all, and there plain Skylake AVX-512 arithmetic pulls clear of the dedicated silicon:

Hashing, one core Throughput Hardware
sha2::Sha256 1.54 GB/s 1 message, SHA-NI
ring::SHA256 1.53 GB/s 1 message, SHA-NI
stringzilla::Sha256, single message 1.41 GB/s 1 message, SHA-NI
stringzilla::Sha256s, dataset order 0.90 GB/s 16 lanes, AVX-512
stringzilla::Sha256s, length-sorted 2.83 GB/s 16 lanes, AVX-512 
lanes = sz.Sha256s(16)                         # one hasher per lane
digests = bytearray(len(lanes) * sz.Sha256.digest_length)
lanes.update(batch).digest(out=digests)        # no allocation, GIL released

tags = sz.hmac_sha256(b"secret", messages)     # one tag per message, same kernels

The distance between the last two rows is the one limitation worth knowing. Lanes advance one block per turn, so a group costs as much as its longest member. They retire independently rather than dropping the whole group to scalar when one runs short, but XLSum lines run from 21 bytes to 445 KB, and in dataset order that skew leaves most slots idle. Feeding inputs in length order is the caller's lever, and argsort produces that ordering.

Encryption: AES-256

AES needs no help from the first axis, because counter mode is already parallel inside a single message. Four consecutive counter blocks of one stream encrypt at once, and GHASH follows once the key powers $H^1$ through $H^8$ are precomputed, so the problem reduces to how many blocks an implementation puts in flight per instruction. Profiling makes the ladder obvious, because everyone's hot symbol names its own width: Ring dispatches to aes_gcm_enc_update_vaes_avx2, the OpenSSL that Ubuntu 24.04 ships predates the vaes-avx512 assembly and runs AES-NI one block wide, and we issue _mm512_aesenc_epi128 with _mm512_clmulepi64_epi128.

Encrypting, one core Throughput Width
openssl::aes256gcm 2.92 GB/s 1-way, AES-NI
ring::aes256gcm 4.33 GB/s 2-way, VAES on YMM
stringzilla::aes256gcm 6.41 GB/s 4-way, VAES on ZMM
stringzilla::aes256ctr 9.23 GB/s 4-way, VAES on ZMM

Decryption tracks it. Counter mode pulls further ahead than the ladder alone predicts, because OpenSSL hand-wrote AVX-512 for GCM and the chaining modes but never for CTR.

key = sz.Aes256GcmKey(bytes(32))
ciphertext, tag = key.encrypt(b"hello", bytes(12))
assert key.decrypt(ciphertext, bytes(12), tag) == b"hello"

seekable = sz.Aes256CtrKey(bytes(32))          # unauthenticated, and its own inverse
assert seekable.xor(seekable.xor(b"hello", bytes(12)), bytes(12)) == b"hello"

Counter mode takes an absolute byte offset, so a reader after row group four hundred of a million-row file starts there rather than pushing the preceding gigabyte through the AES units. Galois/counter mode adds a tag and gives up seeking to get it, and streaming splits by type rather than by a flag — Aes256GcmEncryptor seals and Aes256GcmDecryptor opens, so a state pointed the wrong way is a compile error rather than a runtime one. Beyond x86 the backends cover Arm crypto extensions and SVE2-AES, RISC-V Zvkned with Zvkg, Power vcipher with vpmsumd, and a WebAssembly path with no cipher instructions at all, which emulates the round function through a constant-time tower-field substitution — the 256-byte lookup table a serial implementation reaches for is itself the side channel.

Both tables come from the StringWars harness over the same XLSum corpus, on one Intel Sapphire Rapids core, against OpenSSL 3.0.13 and Ring 0.17.14. Per-backend and per-size breakdowns live in include/stringzilla/cipher/README.md and include/stringzilla/hash/README.md.

Minor

  • Add: Batched HMAC-SHA256 for Rust (dcca5eb)
  • Add: Batched SHA256 and HMAC bindings for Rust and Python (9474833)
  • Add: Multi-state SHA-256 for batched hashing (ff12ed3)
  • Add: AES-256 through the C dispatch, Rust and Python (f0abf92)
  • Add: AES-256 counter and Galois/counter modes (c504053)
  • Add: Differential coverage for the byte-sum kernels (64f2dac)

Patch

  • Fix: Keep the Sha256s doctest off third-party imports (6796567)
  • Fix: Transpose the SHA256 message window in place (d6aa02e)
  • Improve: Move SHA256 lane state by shuffle rather than gather (84bc915)
  • Improve: Keep every SHA256 lane vectorized to its own end (e8573df)
  • Fix: Keep the whole Ice Lake SHA256 path clear of wide registers (7382cfe)
  • Fix: Reseed tests without the hashing kernels (3830932)
  • Fix: Spell GHASH carry-less products for MSVC (725300f)
  • Fix: Keep the Ice Lake SHA256 block clear of ZMM (2eca82c)
  • Improve: Register Python types from one table (d2335f3)
  • Fix: Stop punning the SHA256 state through wider types (128e862)
  • Fix: Call platform intrinsics directly for ctz/clz/popcount in ISA kernels (79d9a06)
  • Improve: Spell out the tag compare and the streaming spend path (41584d1)
  • Fix: Scrub the streaming state when a Rust encryptor drops (681559d)
  • Improve: Stop widening the scalar hash and cipher tiers (26691db)
  • Fix: Close the evex512 version window at both ends (c437048)
  • Improve: Reach for the ISA where the cipher fell back to scalar C (5e4a9c3)
  • Improve: Write the AES rounds out instead of looping (96ef67a)
  • Fix: Clamp duration histogram bins to the last slot (a1e33d8)
  • Fix: Select the RISC-V crypto tier at compile time (b35eb90)
  • Improve: Rebalance and retier the C++ test suite (21693ac)
  • Improve: Rebalance the Rust test suite and de-abbreviate its generics (c40b3de)
  • Fix: Resume UTF-8 delimiter scans at the last emitted match (027c042)
  • Improve: Unify runtime asserts on sz_assert_ (d6231a6)
  • Improve: Build the Rust types in const context (2b4b45c)
  • Fix: Keep the Haswell boundary drain inside its index buffer (cb0f513)
  • Fix: Bound the Haswell LUT reads to their tables (712c6cc)
  • Fix: Write Unicode test caches atomically (a9a6343)
Assets 8
Loading