summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorjsing <>2026-07-22 14:34:38 +0000
committerjsing <>2026-07-22 14:34:38 +0000
commitffcf6234bccf652a6a35ea18d71997d46f147d4f (patch)
treec3ae88fb533a86365c140ed0e320fe27903ee34f /src
parent1cf0a1493f6c88cf1b6b29ab13034d3dcb5f676d (diff)
downloadopenbsd-ffcf6234bccf652a6a35ea18d71997d46f147d4f.tar.gz
openbsd-ffcf6234bccf652a6a35ea18d71997d46f147d4f.tar.bz2
openbsd-ffcf6234bccf652a6a35ea18d71997d46f147d4f.zip
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@
Diffstat (limited to 'src')
-rw-r--r--src/lib/libcrypto/sha/sha3.c318
1 files changed, 281 insertions, 37 deletions
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 @@
1/* $OpenBSD: sha3.c,v 1.20 2025/04/18 07:36:11 jsing Exp $ */ 1/* $OpenBSD: sha3.c,v 1.21 2026/07/22 14:34:38 jsing Exp $ */
2/* 2/*
3 * The MIT License (MIT) 3 * The MIT License (MIT)
4 * 4 *
@@ -41,55 +41,299 @@ static const uint64_t sha3_keccakf_rndc[24] = {
41 0x000000000000800a, 0x800000008000000a, 0x8000000080008081, 41 0x000000000000800a, 0x800000008000000a, 0x8000000080008081,
42 0x8000000000008080, 0x0000000080000001, 0x8000000080008008 42 0x8000000000008080, 0x0000000080000001, 0x8000000080008008
43}; 43};
44static const int sha3_keccakf_rotc[24] = {
45 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14,
46 27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44
47};
48static const int sha3_keccakf_piln[24] = {
49 10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4,
50 15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1
51};
52 44
53static void 45static void
54sha3_keccakf(uint64_t st[25]) 46sha3_keccakf(uint64_t st[25])
55{ 47{
56 uint64_t t0, t1, bc[5]; 48 uint64_t bc0, bc1, bc2, bc3, bc4;
57 int i, j, r; 49 uint64_t d0, d1, d2, d3, d4;
50 int i, r;
58 51
59 for (i = 0; i < 25; i++) 52 for (i = 0; i < 25; i++)
60 st[i] = le64toh(st[i]); 53 st[i] = le64toh(st[i]);
61 54
62 for (r = 0; r < KECCAKF_ROUNDS; r++) { 55 /*
56 * Optimized Keccak algorithm from
57 * KeccakReferenceAndOptimized/Sources/Keccak-inplace.c contained in
58 * https://keccak.team/obsolete/KeccakReferenceAndOptimized-3.2.zip
59 */
63 60
64 /* Theta */ 61 for (r = 0; r < KECCAKF_ROUNDS; r += 4) {
65 for (i = 0; i < 5; i++) 62 /*
66 bc[i] = st[i] ^ st[i + 5] ^ st[i + 10] ^ st[i + 15] ^ st[i + 20]; 63 * Round 1
64 */
65 bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20];
66 bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21];
67 bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22];
68 bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23];
69 bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24];
70 d0 = bc4 ^ crypto_rol_u64(bc1, 1);
71 d1 = bc0 ^ crypto_rol_u64(bc2, 1);
72 d2 = bc1 ^ crypto_rol_u64(bc3, 1);
73 d3 = bc2 ^ crypto_rol_u64(bc4, 1);
74 d4 = bc3 ^ crypto_rol_u64(bc0, 1);
67 75
68 for (i = 0; i < 5; i++) { 76 bc0 = st[0] ^ d0;
69 t0 = bc[(i + 4) % 5] ^ crypto_rol_u64(bc[(i + 1) % 5], 1); 77 bc1 = crypto_rol_u64(st[6] ^ d1, 44);
70 for (j = 0; j < 25; j += 5) 78 bc2 = crypto_rol_u64(st[12] ^ d2, 43);
71 st[j + i] ^= t0; 79 bc3 = crypto_rol_u64(st[18] ^ d3, 21);
72 } 80 bc4 = crypto_rol_u64(st[24] ^ d4, 14);
81 st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 0];
82 st[6] = bc1 ^ (~bc2 & bc3);
83 st[12] = bc2 ^ (~bc3 & bc4);
84 st[18] = bc3 ^ (~bc4 & bc0);
85 st[24] = bc4 ^ (~bc0 & bc1);
73 86
74 /* Rho Pi */ 87 bc2 = crypto_rol_u64(st[10] ^ d0, 3);
75 t0 = st[1]; 88 bc3 = crypto_rol_u64(st[16] ^ d1, 45);
76 for (i = 0; i < 24; i++) { 89 bc4 = crypto_rol_u64(st[22] ^ d2, 61);
77 j = sha3_keccakf_piln[i]; 90 bc0 = crypto_rol_u64(st[3] ^ d3, 28);
78 t1 = st[j]; 91 bc1 = crypto_rol_u64(st[9] ^ d4, 20);
79 st[j] = crypto_rol_u64(t0, sha3_keccakf_rotc[i]); 92 st[10] = bc0 ^ (~bc1 & bc2);
80 t0 = t1; 93 st[16] = bc1 ^ (~bc2 & bc3);
81 } 94 st[22] = bc2 ^ (~bc3 & bc4);
95 st[3] = bc3 ^ (~bc4 & bc0);
96 st[9] = bc4 ^ (~bc0 & bc1);
82 97
83 /* Chi */ 98 bc4 = crypto_rol_u64(st[20] ^ d0, 18);
84 for (j = 0; j < 25; j += 5) { 99 bc0 = crypto_rol_u64(st[1] ^ d1, 1);
85 for (i = 0; i < 5; i++) 100 bc1 = crypto_rol_u64(st[7] ^ d2, 6);
86 bc[i] = st[j + i]; 101 bc2 = crypto_rol_u64(st[13] ^ d3, 25);
87 for (i = 0; i < 5; i++) 102 bc3 = crypto_rol_u64(st[19] ^ d4, 8);
88 st[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5]; 103 st[20] = bc0 ^ (~bc1 & bc2);
89 } 104 st[1] = bc1 ^ (~bc2 & bc3);
105 st[7] = bc2 ^ (~bc3 & bc4);
106 st[13] = bc3 ^ (~bc4 & bc0);
107 st[19] = bc4 ^ (~bc0 & bc1);
108
109 bc1 = crypto_rol_u64(st[5] ^ d0, 36);
110 bc2 = crypto_rol_u64(st[11] ^ d1, 10);
111 bc3 = crypto_rol_u64(st[17] ^ d2, 15);
112 bc4 = crypto_rol_u64(st[23] ^ d3, 56);
113 bc0 = crypto_rol_u64(st[4] ^ d4, 27);
114 st[5] = bc0 ^ (~bc1 & bc2);
115 st[11] = bc1 ^ (~bc2 & bc3);
116 st[17] = bc2 ^ (~bc3 & bc4);
117 st[23] = bc3 ^ (~bc4 & bc0);
118 st[4] = bc4 ^ (~bc0 & bc1);
119
120 bc3 = crypto_rol_u64(st[15] ^ d0, 41);
121 bc4 = crypto_rol_u64(st[21] ^ d1, 2);
122 bc0 = crypto_rol_u64(st[2] ^ d2, 62);
123 bc1 = crypto_rol_u64(st[8] ^ d3, 55);
124 bc2 = crypto_rol_u64(st[14] ^ d4, 39);
125 st[15] = bc0 ^ (~bc1 & bc2);
126 st[21] = bc1 ^ (~bc2 & bc3);
127 st[2] = bc2 ^ (~bc3 & bc4);
128 st[8] = bc3 ^ (~bc4 & bc0);
129 st[14] = bc4 ^ (~bc0 & bc1);
130
131 /*
132 * Round 2
133 */
134 bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20];
135 bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21];
136 bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22];
137 bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23];
138 bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24];
139 d0 = bc4 ^ crypto_rol_u64(bc1, 1);
140 d1 = bc0 ^ crypto_rol_u64(bc2, 1);
141 d2 = bc1 ^ crypto_rol_u64(bc3, 1);
142 d3 = bc2 ^ crypto_rol_u64(bc4, 1);
143 d4 = bc3 ^ crypto_rol_u64(bc0, 1);
144
145 bc0 = st[0] ^ d0;
146 bc1 = crypto_rol_u64(st[16] ^ d1, 44);
147 bc2 = crypto_rol_u64(st[7] ^ d2, 43);
148 bc3 = crypto_rol_u64(st[23] ^ d3, 21);
149 bc4 = crypto_rol_u64(st[14] ^ d4, 14);
150 st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 1];
151 st[16] = bc1 ^ (~bc2 & bc3);
152 st[7] = bc2 ^ (~bc3 & bc4);
153 st[23] = bc3 ^ (~bc4 & bc0);
154 st[14] = bc4 ^ (~bc0 & bc1);
155
156 bc2 = crypto_rol_u64(st[20] ^ d0, 3);
157 bc3 = crypto_rol_u64(st[11] ^ d1, 45);
158 bc4 = crypto_rol_u64(st[2] ^ d2, 61);
159 bc0 = crypto_rol_u64(st[18] ^ d3, 28);
160 bc1 = crypto_rol_u64(st[9] ^ d4, 20);
161 st[20] = bc0 ^ (~bc1 & bc2);
162 st[11] = bc1 ^ (~bc2 & bc3);
163 st[2] = bc2 ^ (~bc3 & bc4);
164 st[18] = bc3 ^ (~bc4 & bc0);
165 st[9] = bc4 ^ (~bc0 & bc1);
166
167 bc4 = crypto_rol_u64(st[15] ^ d0, 18);
168 bc0 = crypto_rol_u64(st[6] ^ d1, 1);
169 bc1 = crypto_rol_u64(st[22] ^ d2, 6);
170 bc2 = crypto_rol_u64(st[13] ^ d3, 25);
171 bc3 = crypto_rol_u64(st[4] ^ d4, 8);
172 st[15] = bc0 ^ (~bc1 & bc2);
173 st[6] = bc1 ^ (~bc2 & bc3);
174 st[22] = bc2 ^ (~bc3 & bc4);
175 st[13] = bc3 ^ (~bc4 & bc0);
176 st[4] = bc4 ^ (~bc0 & bc1);
177
178 bc1 = crypto_rol_u64(st[10] ^ d0, 36);
179 bc2 = crypto_rol_u64(st[1] ^ d1, 10);
180 bc3 = crypto_rol_u64(st[17] ^ d2, 15);
181 bc4 = crypto_rol_u64(st[8] ^ d3, 56);
182 bc0 = crypto_rol_u64(st[24] ^ d4, 27);
183 st[10] = bc0 ^ (~bc1 & bc2);
184 st[1] = bc1 ^ (~bc2 & bc3);
185 st[17] = bc2 ^ (~bc3 & bc4);
186 st[8] = bc3 ^ (~bc4 & bc0);
187 st[24] = bc4 ^ (~bc0 & bc1);
188
189 bc3 = crypto_rol_u64(st[5] ^ d0, 41);
190 bc4 = crypto_rol_u64(st[21] ^ d1, 2);
191 bc0 = crypto_rol_u64(st[12] ^ d2, 62);
192 bc1 = crypto_rol_u64(st[3] ^ d3, 55);
193 bc2 = crypto_rol_u64(st[19] ^ d4, 39);
194 st[5] = bc0 ^ (~bc1 & bc2);
195 st[21] = bc1 ^ (~bc2 & bc3);
196 st[12] = bc2 ^ (~bc3 & bc4);
197 st[3] = bc3 ^ (~bc4 & bc0);
198 st[19] = bc4 ^ (~bc0 & bc1);
199
200 /*
201 * Round 3
202 */
203 bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20];
204 bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21];
205 bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22];
206 bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23];
207 bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24];
208 d0 = bc4 ^ crypto_rol_u64(bc1, 1);
209 d1 = bc0 ^ crypto_rol_u64(bc2, 1);
210 d2 = bc1 ^ crypto_rol_u64(bc3, 1);
211 d3 = bc2 ^ crypto_rol_u64(bc4, 1);
212 d4 = bc3 ^ crypto_rol_u64(bc0, 1);
213
214 bc0 = st[0] ^ d0;
215 bc1 = crypto_rol_u64(st[11] ^ d1, 44);
216 bc2 = crypto_rol_u64(st[22] ^ d2, 43);
217 bc3 = crypto_rol_u64(st[8] ^ d3, 21);
218 bc4 = crypto_rol_u64(st[19] ^ d4, 14);
219 st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 2];
220 st[11] = bc1 ^ (~bc2 & bc3);
221 st[22] = bc2 ^ (~bc3 & bc4);
222 st[8] = bc3 ^ (~bc4 & bc0);
223 st[19] = bc4 ^ (~bc0 & bc1);
224
225 bc2 = crypto_rol_u64(st[15] ^ d0, 3);
226 bc3 = crypto_rol_u64(st[1] ^ d1, 45);
227 bc4 = crypto_rol_u64(st[12] ^ d2, 61);
228 bc0 = crypto_rol_u64(st[23] ^ d3, 28);
229 bc1 = crypto_rol_u64(st[9] ^ d4, 20);
230 st[15] = bc0 ^ (~bc1 & bc2);
231 st[1] = bc1 ^ (~bc2 & bc3);
232 st[12] = bc2 ^ (~bc3 & bc4);
233 st[23] = bc3 ^ (~bc4 & bc0);
234 st[9] = bc4 ^ (~bc0 & bc1);
235
236 bc4 = crypto_rol_u64(st[5] ^ d0, 18);
237 bc0 = crypto_rol_u64(st[16] ^ d1, 1);
238 bc1 = crypto_rol_u64(st[2] ^ d2, 6);
239 bc2 = crypto_rol_u64(st[13] ^ d3, 25);
240 bc3 = crypto_rol_u64(st[24] ^ d4, 8);
241 st[5] = bc0 ^ (~bc1 & bc2);
242 st[16] = bc1 ^ (~bc2 & bc3);
243 st[2] = bc2 ^ (~bc3 & bc4);
244 st[13] = bc3 ^ (~bc4 & bc0);
245 st[24] = bc4 ^ (~bc0 & bc1);
246
247 bc1 = crypto_rol_u64(st[20] ^ d0, 36);
248 bc2 = crypto_rol_u64(st[6] ^ d1, 10);
249 bc3 = crypto_rol_u64(st[17] ^ d2, 15);
250 bc4 = crypto_rol_u64(st[3] ^ d3, 56);
251 bc0 = crypto_rol_u64(st[14] ^ d4, 27);
252 st[20] = bc0 ^ (~bc1 & bc2);
253 st[6] = bc1 ^ (~bc2 & bc3);
254 st[17] = bc2 ^ (~bc3 & bc4);
255 st[3] = bc3 ^ (~bc4 & bc0);
256 st[14] = bc4 ^ (~bc0 & bc1);
257
258 bc3 = crypto_rol_u64(st[10] ^ d0, 41);
259 bc4 = crypto_rol_u64(st[21] ^ d1, 2);
260 bc0 = crypto_rol_u64(st[7] ^ d2, 62);
261 bc1 = crypto_rol_u64(st[18] ^ d3, 55);
262 bc2 = crypto_rol_u64(st[4] ^ d4, 39);
263 st[10] = bc0 ^ (~bc1 & bc2);
264 st[21] = bc1 ^ (~bc2 & bc3);
265 st[7] = bc2 ^ (~bc3 & bc4);
266 st[18] = bc3 ^ (~bc4 & bc0);
267 st[4] = bc4 ^ (~bc0 & bc1);
268
269 /*
270 * Round 4
271 */
272 bc0 = st[0] ^ st[5] ^ st[10] ^ st[15] ^ st[20];
273 bc1 = st[1] ^ st[6] ^ st[11] ^ st[16] ^ st[21];
274 bc2 = st[2] ^ st[7] ^ st[12] ^ st[17] ^ st[22];
275 bc3 = st[3] ^ st[8] ^ st[13] ^ st[18] ^ st[23];
276 bc4 = st[4] ^ st[9] ^ st[14] ^ st[19] ^ st[24];
277 d0 = bc4 ^ crypto_rol_u64(bc1, 1);
278 d1 = bc0 ^ crypto_rol_u64(bc2, 1);
279 d2 = bc1 ^ crypto_rol_u64(bc3, 1);
280 d3 = bc2 ^ crypto_rol_u64(bc4, 1);
281 d4 = bc3 ^ crypto_rol_u64(bc0, 1);
282
283 bc0 = st[0] ^ d0;
284 bc1 = crypto_rol_u64(st[1] ^ d1, 44);
285 bc2 = crypto_rol_u64(st[2] ^ d2, 43);
286 bc3 = crypto_rol_u64(st[3] ^ d3, 21);
287 bc4 = crypto_rol_u64(st[4] ^ d4, 14);
288 st[0] = bc0 ^ (~bc1 & bc2) ^ sha3_keccakf_rndc[r + 3];
289 st[1] = bc1 ^ (~bc2 & bc3);
290 st[2] = bc2 ^ (~bc3 & bc4);
291 st[3] = bc3 ^ (~bc4 & bc0);
292 st[4] = bc4 ^ (~bc0 & bc1);
293
294 bc2 = crypto_rol_u64(st[5] ^ d0, 3);
295 bc3 = crypto_rol_u64(st[6] ^ d1, 45);
296 bc4 = crypto_rol_u64(st[7] ^ d2, 61);
297 bc0 = crypto_rol_u64(st[8] ^ d3, 28);
298 bc1 = crypto_rol_u64(st[9] ^ d4, 20);
299 st[5] = bc0 ^ (~bc1 & bc2);
300 st[6] = bc1 ^ (~bc2 & bc3);
301 st[7] = bc2 ^ (~bc3 & bc4);
302 st[8] = bc3 ^ (~bc4 & bc0);
303 st[9] = bc4 ^ (~bc0 & bc1);
304
305 bc4 = crypto_rol_u64(st[10] ^ d0, 18);
306 bc0 = crypto_rol_u64(st[11] ^ d1, 1);
307 bc1 = crypto_rol_u64(st[12] ^ d2, 6);
308 bc2 = crypto_rol_u64(st[13] ^ d3, 25);
309 bc3 = crypto_rol_u64(st[14] ^ d4, 8);
310 st[10] = bc0 ^ (~bc1 & bc2);
311 st[11] = bc1 ^ (~bc2 & bc3);
312 st[12] = bc2 ^ (~bc3 & bc4);
313 st[13] = bc3 ^ (~bc4 & bc0);
314 st[14] = bc4 ^ (~bc0 & bc1);
315
316 bc1 = crypto_rol_u64(st[15] ^ d0, 36);
317 bc2 = crypto_rol_u64(st[16] ^ d1, 10);
318 bc3 = crypto_rol_u64(st[17] ^ d2, 15);
319 bc4 = crypto_rol_u64(st[18] ^ d3, 56);
320 bc0 = crypto_rol_u64(st[19] ^ d4, 27);
321 st[15] = bc0 ^ (~bc1 & bc2);
322 st[16] = bc1 ^ (~bc2 & bc3);
323 st[17] = bc2 ^ (~bc3 & bc4);
324 st[18] = bc3 ^ (~bc4 & bc0);
325 st[19] = bc4 ^ (~bc0 & bc1);
90 326
91 /* Iota */ 327 bc3 = crypto_rol_u64(st[20] ^ d0, 41);
92 st[0] ^= sha3_keccakf_rndc[r]; 328 bc4 = crypto_rol_u64(st[21] ^ d1, 2);
329 bc0 = crypto_rol_u64(st[22] ^ d2, 62);
330 bc1 = crypto_rol_u64(st[23] ^ d3, 55);
331 bc2 = crypto_rol_u64(st[24] ^ d4, 39);
332 st[20] = bc0 ^ (~bc1 & bc2);
333 st[21] = bc1 ^ (~bc2 & bc3);
334 st[22] = bc2 ^ (~bc3 & bc4);
335 st[23] = bc3 ^ (~bc4 & bc0);
336 st[24] = bc4 ^ (~bc0 & bc1);
93 } 337 }
94 338
95 for (i = 0; i < 25; i++) 339 for (i = 0; i < 25; i++)
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2026-09-03 21:24:18 +0000