From ffcf6234bccf652a6a35ea18d71997d46f147d4f Mon Sep 17 00:00:00 2001 From: jsing <> Date: Wed, 22 Jul 2026 14:34:38 +0000 Subject: Improve SHA-3 performance. Replace the tiny-sha3 keccakf implementation with an unrolled and interleaved algorithm, that is hidden away in an obsolete reference implementation. This gets us 3.3x speed up on arm64 (Apple M2), a 1.3x speed up on amd64 (Intel i7-1165G7) and 6x speed up on sparc64 (M3000). ok tb@ --- src/lib/libcrypto/sha/sha3.c | 318 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 281 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/lib/libcrypto/sha/sha3.c b/src/lib/libcrypto/sha/sha3.c index fde0da94ff..bfbbe10303 100644 --- a/src/lib/libcrypto/sha/sha3.c +++ b/src/lib/libcrypto/sha/sha3.c @@ -1,4 +1,4 @@ -/* $OpenBSD: sha3.c,v 1.20 2025/04/18 07:36:11 jsing Exp $ */ +/* $OpenBSD: sha3.c,v 1.21 2026/07/22 14:34:38 jsing Exp $ */ /* * The MIT License (MIT) * @@ -41,55 +41,299 @@ static const uint64_t sha3_keccakf_rndc[24] = { 0x000000000000800a, 0x800000008000000a, 0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008 }; -static const int sha3_keccakf_rotc[24] = { - 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14, - 27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44 -}; -static const int sha3_keccakf_piln[24] = { - 10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4, - 15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1 -}; static void sha3_keccakf(uint64_t st[25]) { - uint64_t t0, t1, bc[5]; - int i, j, r; + uint64_t bc0, bc1, bc2, bc3, bc4; + uint64_t d0, d1, d2, d3, d4; + int i, r; for (i = 0; i < 25; i++) st[i] = le64toh(st[i]); - for (r = 0; r < KECCAKF_ROUNDS; r++) { + /* + * Optimized Keccak algorithm from + * KeccakReferenceAndOptimized/Sources/Keccak-inplace.c contained in + * https://keccak.team/obsolete/KeccakReferenceAndOptimized-3.2.zip + */ - /* Theta */ - for (i = 0; i < 5; i++) - bc[i] = st[i] ^ st[i + 5] ^ st[i + 10] ^ st[i + 15] ^ st[i + 20]; + for (r = 0; r < KECCAKF_ROUNDS; r += 4) { + /* + * Round 1 + */ + bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20]; + bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21]; + bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22]; + bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23]; + bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24]; + d0 = bc4 ^ crypto_rol_u64(bc1, 1); + d1 = bc0 ^ crypto_rol_u64(bc2, 1); + d2 = bc1 ^ crypto_rol_u64(bc3, 1); + d3 = bc2 ^ crypto_rol_u64(bc4, 1); + d4 = bc3 ^ crypto_rol_u64(bc0, 1); - for (i = 0; i < 5; i++) { - t0 = bc[(i + 4) % 5] ^ crypto_rol_u64(bc[(i + 1) % 5], 1); - for (j = 0; j < 25; j += 5) - st[j + i] ^= t0; - } + bc0 = st[0] ^ d0; + bc1 = crypto_rol_u64(st[6] ^ d1, 44); + bc2 = crypto_rol_u64(st[12] ^ d2, 43); + bc3 = crypto_rol_u64(st[18] ^ d3, 21); + bc4 = crypto_rol_u64(st[24] ^ d4, 14); + st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 0]; + st[6] = bc1 ^ (~bc2 & bc3); + st[12] = bc2 ^ (~bc3 & bc4); + st[18] = bc3 ^ (~bc4 & bc0); + st[24] = bc4 ^ (~bc0 & bc1); - /* Rho Pi */ - t0 = st[1]; - for (i = 0; i < 24; i++) { - j = sha3_keccakf_piln[i]; - t1 = st[j]; - st[j] = crypto_rol_u64(t0, sha3_keccakf_rotc[i]); - t0 = t1; - } + bc2 = crypto_rol_u64(st[10] ^ d0, 3); + bc3 = crypto_rol_u64(st[16] ^ d1, 45); + bc4 = crypto_rol_u64(st[22] ^ d2, 61); + bc0 = crypto_rol_u64(st[3] ^ d3, 28); + bc1 = crypto_rol_u64(st[9] ^ d4, 20); + st[10] = bc0 ^ (~bc1 & bc2); + st[16] = bc1 ^ (~bc2 & bc3); + st[22] = bc2 ^ (~bc3 & bc4); + st[3] = bc3 ^ (~bc4 & bc0); + st[9] = bc4 ^ (~bc0 & bc1); - /* Chi */ - for (j = 0; j < 25; j += 5) { - for (i = 0; i < 5; i++) - bc[i] = st[j + i]; - for (i = 0; i < 5; i++) - st[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5]; - } + bc4 = crypto_rol_u64(st[20] ^ d0, 18); + bc0 = crypto_rol_u64(st[1] ^ d1, 1); + bc1 = crypto_rol_u64(st[7] ^ d2, 6); + bc2 = crypto_rol_u64(st[13] ^ d3, 25); + bc3 = crypto_rol_u64(st[19] ^ d4, 8); + st[20] = bc0 ^ (~bc1 & bc2); + st[1] = bc1 ^ (~bc2 & bc3); + st[7] = bc2 ^ (~bc3 & bc4); + st[13] = bc3 ^ (~bc4 & bc0); + st[19] = bc4 ^ (~bc0 & bc1); + + bc1 = crypto_rol_u64(st[5] ^ d0, 36); + bc2 = crypto_rol_u64(st[11] ^ d1, 10); + bc3 = crypto_rol_u64(st[17] ^ d2, 15); + bc4 = crypto_rol_u64(st[23] ^ d3, 56); + bc0 = crypto_rol_u64(st[4] ^ d4, 27); + st[5] = bc0 ^ (~bc1 & bc2); + st[11] = bc1 ^ (~bc2 & bc3); + st[17] = bc2 ^ (~bc3 & bc4); + st[23] = bc3 ^ (~bc4 & bc0); + st[4] = bc4 ^ (~bc0 & bc1); + + bc3 = crypto_rol_u64(st[15] ^ d0, 41); + bc4 = crypto_rol_u64(st[21] ^ d1, 2); + bc0 = crypto_rol_u64(st[2] ^ d2, 62); + bc1 = crypto_rol_u64(st[8] ^ d3, 55); + bc2 = crypto_rol_u64(st[14] ^ d4, 39); + st[15] = bc0 ^ (~bc1 & bc2); + st[21] = bc1 ^ (~bc2 & bc3); + st[2] = bc2 ^ (~bc3 & bc4); + st[8] = bc3 ^ (~bc4 & bc0); + st[14] = bc4 ^ (~bc0 & bc1); + + /* + * Round 2 + */ + bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20]; + bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21]; + bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22]; + bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23]; + bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24]; + d0 = bc4 ^ crypto_rol_u64(bc1, 1); + d1 = bc0 ^ crypto_rol_u64(bc2, 1); + d2 = bc1 ^ crypto_rol_u64(bc3, 1); + d3 = bc2 ^ crypto_rol_u64(bc4, 1); + d4 = bc3 ^ crypto_rol_u64(bc0, 1); + + bc0 = st[0] ^ d0; + bc1 = crypto_rol_u64(st[16] ^ d1, 44); + bc2 = crypto_rol_u64(st[7] ^ d2, 43); + bc3 = crypto_rol_u64(st[23] ^ d3, 21); + bc4 = crypto_rol_u64(st[14] ^ d4, 14); + st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 1]; + st[16] = bc1 ^ (~bc2 & bc3); + st[7] = bc2 ^ (~bc3 & bc4); + st[23] = bc3 ^ (~bc4 & bc0); + st[14] = bc4 ^ (~bc0 & bc1); + + bc2 = crypto_rol_u64(st[20] ^ d0, 3); + bc3 = crypto_rol_u64(st[11] ^ d1, 45); + bc4 = crypto_rol_u64(st[2] ^ d2, 61); + bc0 = crypto_rol_u64(st[18] ^ d3, 28); + bc1 = crypto_rol_u64(st[9] ^ d4, 20); + st[20] = bc0 ^ (~bc1 & bc2); + st[11] = bc1 ^ (~bc2 & bc3); + st[2] = bc2 ^ (~bc3 & bc4); + st[18] = bc3 ^ (~bc4 & bc0); + st[9] = bc4 ^ (~bc0 & bc1); + + bc4 = crypto_rol_u64(st[15] ^ d0, 18); + bc0 = crypto_rol_u64(st[6] ^ d1, 1); + bc1 = crypto_rol_u64(st[22] ^ d2, 6); + bc2 = crypto_rol_u64(st[13] ^ d3, 25); + bc3 = crypto_rol_u64(st[4] ^ d4, 8); + st[15] = bc0 ^ (~bc1 & bc2); + st[6] = bc1 ^ (~bc2 & bc3); + st[22] = bc2 ^ (~bc3 & bc4); + st[13] = bc3 ^ (~bc4 & bc0); + st[4] = bc4 ^ (~bc0 & bc1); + + bc1 = crypto_rol_u64(st[10] ^ d0, 36); + bc2 = crypto_rol_u64(st[1] ^ d1, 10); + bc3 = crypto_rol_u64(st[17] ^ d2, 15); + bc4 = crypto_rol_u64(st[8] ^ d3, 56); + bc0 = crypto_rol_u64(st[24] ^ d4, 27); + st[10] = bc0 ^ (~bc1 & bc2); + st[1] = bc1 ^ (~bc2 & bc3); + st[17] = bc2 ^ (~bc3 & bc4); + st[8] = bc3 ^ (~bc4 & bc0); + st[24] = bc4 ^ (~bc0 & bc1); + + bc3 = crypto_rol_u64(st[5] ^ d0, 41); + bc4 = crypto_rol_u64(st[21] ^ d1, 2); + bc0 = crypto_rol_u64(st[12] ^ d2, 62); + bc1 = crypto_rol_u64(st[3] ^ d3, 55); + bc2 = crypto_rol_u64(st[19] ^ d4, 39); + st[5] = bc0 ^ (~bc1 & bc2); + st[21] = bc1 ^ (~bc2 & bc3); + st[12] = bc2 ^ (~bc3 & bc4); + st[3] = bc3 ^ (~bc4 & bc0); + st[19] = bc4 ^ (~bc0 & bc1); + + /* + * Round 3 + */ + bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20]; + bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21]; + bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22]; + bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23]; + bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24]; + d0 = bc4 ^ crypto_rol_u64(bc1, 1); + d1 = bc0 ^ crypto_rol_u64(bc2, 1); + d2 = bc1 ^ crypto_rol_u64(bc3, 1); + d3 = bc2 ^ crypto_rol_u64(bc4, 1); + d4 = bc3 ^ crypto_rol_u64(bc0, 1); + + bc0 = st[0] ^ d0; + bc1 = crypto_rol_u64(st[11] ^ d1, 44); + bc2 = crypto_rol_u64(st[22] ^ d2, 43); + bc3 = crypto_rol_u64(st[8] ^ d3, 21); + bc4 = crypto_rol_u64(st[19] ^ d4, 14); + st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 2]; + st[11] = bc1 ^ (~bc2 & bc3); + st[22] = bc2 ^ (~bc3 & bc4); + st[8] = bc3 ^ (~bc4 & bc0); + st[19] = bc4 ^ (~bc0 & bc1); + + bc2 = crypto_rol_u64(st[15] ^ d0, 3); + bc3 = crypto_rol_u64(st[1] ^ d1, 45); + bc4 = crypto_rol_u64(st[12] ^ d2, 61); + bc0 = crypto_rol_u64(st[23] ^ d3, 28); + bc1 = crypto_rol_u64(st[9] ^ d4, 20); + st[15] = bc0 ^ (~bc1 & bc2); + st[1] = bc1 ^ (~bc2 & bc3); + st[12] = bc2 ^ (~bc3 & bc4); + st[23] = bc3 ^ (~bc4 & bc0); + st[9] = bc4 ^ (~bc0 & bc1); + + bc4 = crypto_rol_u64(st[5] ^ d0, 18); + bc0 = crypto_rol_u64(st[16] ^ d1, 1); + bc1 = crypto_rol_u64(st[2] ^ d2, 6); + bc2 = crypto_rol_u64(st[13] ^ d3, 25); + bc3 = crypto_rol_u64(st[24] ^ d4, 8); + st[5] = bc0 ^ (~bc1 & bc2); + st[16] = bc1 ^ (~bc2 & bc3); + st[2] = bc2 ^ (~bc3 & bc4); + st[13] = bc3 ^ (~bc4 & bc0); + st[24] = bc4 ^ (~bc0 & bc1); + + bc1 = crypto_rol_u64(st[20] ^ d0, 36); + bc2 = crypto_rol_u64(st[6] ^ d1, 10); + bc3 = crypto_rol_u64(st[17] ^ d2, 15); + bc4 = crypto_rol_u64(st[3] ^ d3, 56); + bc0 = crypto_rol_u64(st[14] ^ d4, 27); + st[20] = bc0 ^ (~bc1 & bc2); + st[6] = bc1 ^ (~bc2 & bc3); + st[17] = bc2 ^ (~bc3 & bc4); + st[3] = bc3 ^ (~bc4 & bc0); + st[14] = bc4 ^ (~bc0 & bc1); + + bc3 = crypto_rol_u64(st[10] ^ d0, 41); + bc4 = crypto_rol_u64(st[21] ^ d1, 2); + bc0 = crypto_rol_u64(st[7] ^ d2, 62); + bc1 = crypto_rol_u64(st[18] ^ d3, 55); + bc2 = crypto_rol_u64(st[4] ^ d4, 39); + st[10] = bc0 ^ (~bc1 & bc2); + st[21] = bc1 ^ (~bc2 & bc3); + st[7] = bc2 ^ (~bc3 & bc4); + st[18] = bc3 ^ (~bc4 & bc0); + st[4] = bc4 ^ (~bc0 & bc1); + + /* + * Round 4 + */ + bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20]; + bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21]; + bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22]; + bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23]; + bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24]; + d0 = bc4 ^ crypto_rol_u64(bc1, 1); + d1 = bc0 ^ crypto_rol_u64(bc2, 1); + d2 = bc1 ^ crypto_rol_u64(bc3, 1); + d3 = bc2 ^ crypto_rol_u64(bc4, 1); + d4 = bc3 ^ crypto_rol_u64(bc0, 1); + + bc0 = st[0] ^ d0; + bc1 = crypto_rol_u64(st[1] ^ d1, 44); + bc2 = crypto_rol_u64(st[2] ^ d2, 43); + bc3 = crypto_rol_u64(st[3] ^ d3, 21); + bc4 = crypto_rol_u64(st[4] ^ d4, 14); + st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 3]; + st[1] = bc1 ^ (~bc2 & bc3); + st[2] = bc2 ^ (~bc3 & bc4); + st[3] = bc3 ^ (~bc4 & bc0); + st[4] = bc4 ^ (~bc0 & bc1); + + bc2 = crypto_rol_u64(st[5] ^ d0, 3); + bc3 = crypto_rol_u64(st[6] ^ d1, 45); + bc4 = crypto_rol_u64(st[7] ^ d2, 61); + bc0 = crypto_rol_u64(st[8] ^ d3, 28); + bc1 = crypto_rol_u64(st[9] ^ d4, 20); + st[5] = bc0 ^ (~bc1 & bc2); + st[6] = bc1 ^ (~bc2 & bc3); + st[7] = bc2 ^ (~bc3 & bc4); + st[8] = bc3 ^ (~bc4 & bc0); + st[9] = bc4 ^ (~bc0 & bc1); + + bc4 = crypto_rol_u64(st[10] ^ d0, 18); + bc0 = crypto_rol_u64(st[11] ^ d1, 1); + bc1 = crypto_rol_u64(st[12] ^ d2, 6); + bc2 = crypto_rol_u64(st[13] ^ d3, 25); + bc3 = crypto_rol_u64(st[14] ^ d4, 8); + st[10] = bc0 ^ (~bc1 & bc2); + st[11] = bc1 ^ (~bc2 & bc3); + st[12] = bc2 ^ (~bc3 & bc4); + st[13] = bc3 ^ (~bc4 & bc0); + st[14] = bc4 ^ (~bc0 & bc1); + + bc1 = crypto_rol_u64(st[15] ^ d0, 36); + bc2 = crypto_rol_u64(st[16] ^ d1, 10); + bc3 = crypto_rol_u64(st[17] ^ d2, 15); + bc4 = crypto_rol_u64(st[18] ^ d3, 56); + bc0 = crypto_rol_u64(st[19] ^ d4, 27); + st[15] = bc0 ^ (~bc1 & bc2); + st[16] = bc1 ^ (~bc2 & bc3); + st[17] = bc2 ^ (~bc3 & bc4); + st[18] = bc3 ^ (~bc4 & bc0); + st[19] = bc4 ^ (~bc0 & bc1); - /* Iota */ - st[0] ^= sha3_keccakf_rndc[r]; + bc3 = crypto_rol_u64(st[20] ^ d0, 41); + bc4 = crypto_rol_u64(st[21] ^ d1, 2); + bc0 = crypto_rol_u64(st[22] ^ d2, 62); + bc1 = crypto_rol_u64(st[23] ^ d3, 55); + bc2 = crypto_rol_u64(st[24] ^ d4, 39); + st[20] = bc0 ^ (~bc1 & bc2); + st[21] = bc1 ^ (~bc2 & bc3); + st[22] = bc2 ^ (~bc3 & bc4); + st[23] = bc3 ^ (~bc4 & bc0); + st[24] = bc4 ^ (~bc0 & bc1); } for (i = 0; i < 25; i++) -- cgit v1.2.3-55-g6feb