projects/linux·blob master · refs

511 lines · 16.0 KiB

1/* SPDX-License-Identifier: GPL-2.0-or-later */
2/*
3 * Test cases for hash functions, including a benchmark. This is included by
4 * KUnit test suites that want to use it. See sha512_kunit.c for an example.
5 *
6 * Copyright 2025 Google LLC
7 */
8#include <kunit/run-in-irq-context.h>
9#include <kunit/test.h>
10#include "test-utils.h"
11
12/*
13 * Test the hash function against a list of test vectors.
14 *
15 * Note that it's only necessary to run each test vector in one way (e.g.,
16 * one-shot instead of incremental), since consistency between different ways of
17 * using the APIs is verified by other test cases.
18 */
19static void test_hash_test_vectors(struct kunit *test)
20{
21 const size_t max_len = 16384;
22 u8 *data = alloc_buf(test, max_len);
23
24 for (size_t i = 0; i < ARRAY_SIZE(hash_testvecs); i++) {
25 size_t data_len = hash_testvecs[i].data_len;
26 u8 actual_hash[HASH_SIZE];
27
28 KUNIT_ASSERT_LE(test, data_len, max_len);
29 rand_bytes_seeded_from_len(data, data_len);
30 HASH(data, data_len, actual_hash);
31 KUNIT_ASSERT_MEMEQ_MSG(
32 test, actual_hash, hash_testvecs[i].digest, HASH_SIZE,
33 "Wrong result with test vector %zu; data_len=%zu", i,
34 data_len);
35 }
36}
37
38/*
39 * Test that the hash function produces correct results for *every* length up to
40 * 4096 bytes. To do this, generate seeded random data, then calculate a hash
41 * value for each length 0..4096, then hash the hash values. Verify just the
42 * final hash value, which should match only when all hash values were correct.
43 */
44static void test_hash_all_lens_up_to_4096(struct kunit *test)
45{
46 const size_t max_len = 4096;
47 u8 *data = alloc_buf(test, max_len);
48 struct HASH_CTX ctx;
49 u8 hash[HASH_SIZE];
50
51 rand_bytes_seeded_from_len(data, max_len);
52 HASH_INIT(&ctx);
53 for (size_t len = 0; len <= max_len; len++) {
54 HASH(data, len, hash);
55 HASH_UPDATE(&ctx, hash, HASH_SIZE);
56 }
57 HASH_FINAL(&ctx, hash);
58 KUNIT_ASSERT_MEMEQ(test, hash, hash_testvec_consolidated, HASH_SIZE);
59}
60
61/*
62 * Test that the hash function produces the same result with a one-shot
63 * computation as it does with an incremental computation.
64 */
65static void test_hash_incremental_updates(struct kunit *test)
66{
67 const size_t max_len = 16384;
68 u8 *data = alloc_guarded_buf(test, max_len);
69
70 for (int i = 0; i < 1000; i++) {
71 size_t total_len, offset;
72 struct HASH_CTX ctx;
73 u8 hash1[HASH_SIZE];
74 u8 hash2[HASH_SIZE];
75 size_t num_parts = 0;
76 size_t remaining_len, cur_offset;
77
78 total_len = rand_length(max_len);
79 offset = rand_offset(max_len - total_len);
80 rand_bytes(&data[offset], total_len);
81
82 /* Compute the hash value in one shot. */
83 HASH(&data[offset], total_len, hash1);
84
85 /*
86 * Compute the hash value incrementally, using a randomly
87 * selected sequence of update lengths that sum to total_len.
88 */
89 HASH_INIT(&ctx);
90 remaining_len = total_len;
91 cur_offset = offset;
92 while (rand_bool()) {
93 size_t part_len = rand_length(remaining_len);
94
95 HASH_UPDATE(&ctx, &data[cur_offset], part_len);
96 num_parts++;
97 cur_offset += part_len;
98 remaining_len -= part_len;
99 }
100 if (remaining_len != 0 || rand_bool()) {
101 HASH_UPDATE(&ctx, &data[cur_offset], remaining_len);
102 num_parts++;
103 }
104 HASH_FINAL(&ctx, hash2);
105
106 /* Verify that the two hash values are the same. */
107 KUNIT_ASSERT_MEMEQ_MSG(
108 test, hash1, hash2, HASH_SIZE,
109 "Incremental test failed with total_len=%zu num_parts=%zu offset=%zu",
110 total_len, num_parts, offset);
111 }
112}
113
114/*
115 * Test that the hash function does not overrun any buffers. Uses a guard page
116 * to catch buffer overruns even if they occur in assembly code.
117 */
118static void test_hash_buffer_overruns(struct kunit *test)
119{
120 const size_t buf_len = 16384;
121 u8 *buf = alloc_guarded_buf(test, buf_len);
122 void *const buf_end = &buf[buf_len];
123 const size_t max_tested_len = buf_len - sizeof(struct HASH_CTX);
124 struct HASH_CTX *guarded_ctx = buf_end - sizeof(*guarded_ctx);
125
126 rand_bytes(buf, buf_len);
127
128 for (int i = 0; i < 100; i++) {
129 size_t len = rand_length(max_tested_len);
130 struct HASH_CTX ctx;
131 u8 hash[HASH_SIZE];
132
133 /* Check for overruns of the data buffer. */
134 HASH(buf_end - len, len, hash);
135 HASH_INIT(&ctx);
136 HASH_UPDATE(&ctx, buf_end - len, len);
137 HASH_FINAL(&ctx, hash);
138
139 /* Check for overruns of the hash value buffer. */
140 HASH(buf, len, buf_end - HASH_SIZE);
141 HASH_INIT(&ctx);
142 HASH_UPDATE(&ctx, buf, len);
143 HASH_FINAL(&ctx, buf_end - HASH_SIZE);
144
145 /* Check for overruns of the hash context. */
146 HASH_INIT(guarded_ctx);
147 HASH_UPDATE(guarded_ctx, buf, len);
148 HASH_FINAL(guarded_ctx, hash);
149 }
150}
151
152/*
153 * Test that the caller is permitted to alias the output digest and source data
154 * buffer, and also modify the source data buffer after it has been used.
155 */
156static void test_hash_overlaps(struct kunit *test)
157{
158 const size_t buf_len = 16384;
159 u8 *buf = alloc_guarded_buf(test, buf_len);
160 const size_t max_tested_len = buf_len - HASH_SIZE;
161 struct HASH_CTX ctx;
162 u8 hash[HASH_SIZE];
163
164 rand_bytes(buf, buf_len);
165
166 for (int i = 0; i < 100; i++) {
167 size_t len = rand_length(max_tested_len);
168 size_t offset = HASH_SIZE + rand_offset(max_tested_len - len);
169 bool left_end = rand_bool();
170 u8 *ovl_hash = left_end ? &buf[offset] :
171 &buf[offset + len - HASH_SIZE];
172
173 HASH(&buf[offset], len, hash);
174 HASH(&buf[offset], len, ovl_hash);
175 KUNIT_ASSERT_MEMEQ_MSG(
176 test, hash, ovl_hash, HASH_SIZE,
177 "Overlap test 1 failed with len=%zu offset=%zu left_end=%d",
178 len, offset, left_end);
179
180 /* Repeat the above test, but this time use init+update+final */
181 HASH(&buf[offset], len, hash);
182 HASH_INIT(&ctx);
183 HASH_UPDATE(&ctx, &buf[offset], len);
184 HASH_FINAL(&ctx, ovl_hash);
185 KUNIT_ASSERT_MEMEQ_MSG(
186 test, hash, ovl_hash, HASH_SIZE,
187 "Overlap test 2 failed with len=%zu offset=%zu left_end=%d",
188 len, offset, left_end);
189
190 /* Test modifying the source data after it was used. */
191 HASH(&buf[offset], len, hash);
192 HASH_INIT(&ctx);
193 HASH_UPDATE(&ctx, &buf[offset], len);
194 rand_bytes(&buf[offset], len);
195 HASH_FINAL(&ctx, ovl_hash);
196 KUNIT_ASSERT_MEMEQ_MSG(
197 test, hash, ovl_hash, HASH_SIZE,
198 "Overlap test 3 failed with len=%zu offset=%zu left_end=%d",
199 len, offset, left_end);
200 }
201}
202
203/*
204 * Test that if the same data is hashed at different alignments in memory, the
205 * results are the same.
206 */
207static void test_hash_alignment_consistency(struct kunit *test)
208{
209 const size_t max_len = 16384;
210 u8 *data = alloc_guarded_buf(test, max_len);
211 u8 hash1[128 + HASH_SIZE];
212 u8 hash2[128 + HASH_SIZE];
213
214 for (int i = 0; i < 100; i++) {
215 size_t len = rand_length(max_len);
216 size_t data_offs1 = rand_offset(max_len - len);
217 size_t data_offs2 = rand_offset(max_len - len);
218 size_t hash_offs1 = rand_offset(128);
219 size_t hash_offs2 = rand_offset(128);
220
221 rand_bytes(&data[data_offs1], len);
222 HASH(&data[data_offs1], len, &hash1[hash_offs1]);
223 memmove(&data[data_offs2], &data[data_offs1], len);
224 HASH(&data[data_offs2], len, &hash2[hash_offs2]);
225 KUNIT_ASSERT_MEMEQ_MSG(
226 test, &hash1[hash_offs1], &hash2[hash_offs2], HASH_SIZE,
227 "Alignment consistency test failed with len=%zu data_offs=(%zu,%zu) hash_offs=(%zu,%zu)",
228 len, data_offs1, data_offs2, hash_offs1, hash_offs2);
229 }
230}
231
232/* Test that HASH_FINAL zeroizes the context. */
233static void test_hash_ctx_zeroization(struct kunit *test)
234{
235 static const u8 zeroes[sizeof(struct HASH_CTX)];
236 struct HASH_CTX ctx;
237 const size_t data_len = 128;
238 u8 *data = alloc_buf(test, data_len);
239 u8 hash[HASH_SIZE];
240
241 rand_bytes(data, data_len);
242 HASH_INIT(&ctx);
243 HASH_UPDATE(&ctx, data, data_len);
244 HASH_FINAL(&ctx, hash);
245 KUNIT_ASSERT_MEMEQ_MSG(test, &ctx, zeroes, sizeof(ctx),
246 "Hash context was not zeroized by finalization");
247}
248
249#define IRQ_TEST_DATA_LEN 256
250#define IRQ_TEST_NUM_BUFFERS 3 /* matches max concurrency level */
251
252struct hash_irq_test1_state {
253 u8 *data;
254 u8 expected_hashes[IRQ_TEST_NUM_BUFFERS][HASH_SIZE];
255 atomic_t seqno;
256};
257
258/*
259 * Compute the hash of one of the test messages and verify that it matches the
260 * expected hash from @state->expected_hashes. To increase the chance of
261 * detecting problems, cycle through multiple messages.
262 */
263static bool hash_irq_test1_func(void *state_)
264{
265 struct hash_irq_test1_state *state = state_;
266 u32 i = (u32)atomic_inc_return(&state->seqno) % IRQ_TEST_NUM_BUFFERS;
267 u8 actual_hash[HASH_SIZE];
268
269 HASH(&state->data[i * IRQ_TEST_DATA_LEN], IRQ_TEST_DATA_LEN,
270 actual_hash);
271 return memcmp(actual_hash, state->expected_hashes[i], HASH_SIZE) == 0;
272}
273
274/*
275 * Test that if hashes are computed in task, softirq, and hardirq context
276 * concurrently, then all results are as expected.
277 */
278static void test_hash_interrupt_context_1(struct kunit *test)
279{
280 const size_t total_data_len = IRQ_TEST_NUM_BUFFERS * IRQ_TEST_DATA_LEN;
281 struct hash_irq_test1_state state = {};
282
283 /* Prepare some test messages and compute the expected hash of each. */
284 state.data = alloc_buf(test, total_data_len);
285 rand_bytes(state.data, total_data_len);
286 for (int i = 0; i < IRQ_TEST_NUM_BUFFERS; i++)
287 HASH(&state.data[i * IRQ_TEST_DATA_LEN], IRQ_TEST_DATA_LEN,
288 state.expected_hashes[i]);
289
290 kunit_run_irq_test(test, hash_irq_test1_func, 100000, &state);
291}
292
293struct hash_irq_test2_hash_ctx {
294 struct HASH_CTX hash_ctx;
295 atomic_t in_use;
296 int offset;
297 int step;
298};
299
300struct hash_irq_test2_state {
301 u8 *data;
302 size_t data_len;
303 struct hash_irq_test2_hash_ctx ctxs[IRQ_TEST_NUM_BUFFERS];
304 u8 expected_hash[HASH_SIZE];
305 u16 update_lens[32];
306 int num_steps;
307};
308
309static bool hash_irq_test2_func(void *state_)
310{
311 struct hash_irq_test2_state *state = state_;
312 struct hash_irq_test2_hash_ctx *ctx;
313 bool ret = true;
314
315 for (ctx = &state->ctxs[0]; ctx < &state->ctxs[ARRAY_SIZE(state->ctxs)];
316 ctx++) {
317 if (atomic_cmpxchg(&ctx->in_use, 0, 1) == 0)
318 break;
319 }
320 if (WARN_ON_ONCE(ctx == &state->ctxs[ARRAY_SIZE(state->ctxs)])) {
321 /*
322 * This should never happen, as the number of contexts is equal
323 * to the maximum concurrency level of kunit_run_irq_test().
324 */
325 return false;
326 }
327
328 if (ctx->step == 0) {
329 /* Init step */
330 HASH_INIT(&ctx->hash_ctx);
331 ctx->offset = 0;
332 ctx->step++;
333 } else if (ctx->step < state->num_steps - 1) {
334 /* Update step */
335 HASH_UPDATE(&ctx->hash_ctx, &state->data[ctx->offset],
336 state->update_lens[ctx->step - 1]);
337 ctx->offset += state->update_lens[ctx->step - 1];
338 ctx->step++;
339 } else {
340 /* Final step */
341 u8 actual_hash[HASH_SIZE];
342
343 if (WARN_ON_ONCE(ctx->offset != state->data_len))
344 ret = false;
345 HASH_FINAL(&ctx->hash_ctx, actual_hash);
346 if (memcmp(actual_hash, state->expected_hash, HASH_SIZE) != 0)
347 ret = false;
348 ctx->step = 0;
349 }
350 atomic_set_release(&ctx->in_use, 0);
351 return ret;
352}
353
354/*
355 * Test that if hashes are computed in task, softirq, and hardirq context
356 * concurrently, *including doing different parts of the same incremental
357 * computation in different contexts*, then all results are as expected.
358 * Besides detecting bugs similar to those that test_hash_interrupt_context_1
359 * can detect, this test case can also detect bugs where hash function
360 * implementations don't correctly handle these mixed incremental computations.
361 */
362static void test_hash_interrupt_context_2(struct kunit *test)
363{
364 const size_t data_len = 16384;
365 struct hash_irq_test2_state *state;
366 size_t remaining = data_len;
367
368 state = kunit_kzalloc(test, sizeof(*state), GFP_KERNEL);
369 KUNIT_ASSERT_NOT_NULL(test, state);
370 state->data_len = data_len;
371 state->data = alloc_buf(test, data_len);
372
373 rand_bytes(state->data, data_len);
374 HASH(state->data, data_len, state->expected_hash);
375
376 /*
377 * Generate a list of update lengths to use. Ensure that it contains
378 * multiple entries but is limited to a maximum length.
379 */
380 KUNIT_ASSERT_GT(test, data_len / 4096, 1);
381 for (state->num_steps = 0;
382 state->num_steps < ARRAY_SIZE(state->update_lens) - 1 && remaining;
383 state->num_steps++) {
384 state->update_lens[state->num_steps] =
385 rand_length(min(remaining, 4096));
386 remaining -= state->update_lens[state->num_steps];
387 }
388 if (remaining)
389 state->update_lens[state->num_steps++] = remaining;
390 state->num_steps += 2; /* for init and final */
391
392 kunit_run_irq_test(test, hash_irq_test2_func, 250000, state);
393}
394
395#define UNKEYED_HASH_KUNIT_CASES \
396 KUNIT_CASE(test_hash_test_vectors), \
397 KUNIT_CASE(test_hash_all_lens_up_to_4096), \
398 KUNIT_CASE(test_hash_incremental_updates), \
399 KUNIT_CASE(test_hash_buffer_overruns), \
400 KUNIT_CASE(test_hash_overlaps), \
401 KUNIT_CASE(test_hash_alignment_consistency), \
402 KUNIT_CASE(test_hash_ctx_zeroization), \
403 KUNIT_CASE(test_hash_interrupt_context_1), \
404 KUNIT_CASE(test_hash_interrupt_context_2)
405/* benchmark_hash is omitted so that the suites can put it last. */
406
407#ifdef HMAC
408/*
409 * Test the corresponding HMAC variant.
410 *
411 * This test case is fairly short, since HMAC is just a simple C wrapper around
412 * the underlying unkeyed hash function, which is already well-tested by the
413 * other test cases. It's not useful to test things like data alignment or
414 * interrupt context again for HMAC, nor to have a long list of test vectors.
415 *
416 * Thus, just do a single consolidated test, which covers all data lengths up to
417 * 4096 bytes and all key lengths up to 292 bytes. For each data length, select
418 * a key length, generate the inputs from a seed, and compute the HMAC value.
419 * Concatenate all these HMAC values together, and compute the HMAC of that.
420 * Verify that value. If this fails, then the HMAC implementation is wrong.
421 * This won't show which specific input failed, but that should be fine. Any
422 * failure would likely be non-input-specific or also show in the unkeyed tests.
423 */
424static void test_hmac(struct kunit *test)
425{
426 const size_t max_data_len = 4096;
427 const size_t max_key_len = 293;
428 const size_t outer_key_len = 32;
429 u8 *data = alloc_guarded_buf(test, max_data_len);
430 u8 *raw_key = alloc_guarded_buf(test, max_key_len);
431 static const u8 zeroes[sizeof(struct HMAC_CTX)];
432 struct HMAC_KEY key;
433 struct HMAC_CTX ctx;
434 u8 mac[HASH_SIZE];
435 u8 mac2[HASH_SIZE];
436
437 rand_bytes_seeded_from_len(data, max_data_len);
438 rand_bytes_seeded_from_len(raw_key, outer_key_len);
439
440 HMAC_PREPAREKEY(&key, raw_key, outer_key_len);
441 HMAC_INIT(&ctx, &key);
442 for (size_t data_len = 0; data_len <= max_data_len; data_len++) {
443 /*
444 * Cycle through key lengths as well. Somewhat arbitrarily go
445 * up to 293, which is somewhat larger than the largest hash
446 * block size (which is the size at which the key starts being
447 * hashed down to one block); going higher would not be useful.
448 * To reduce correlation with data_len, use a prime number here.
449 */
450 size_t key_len = data_len % max_key_len;
451
452 HMAC_UPDATE(&ctx, data, data_len);
453
454 rand_bytes_seeded_from_len(raw_key, key_len);
455 HMAC_USINGRAWKEY(raw_key, key_len, data, data_len, mac);
456 HMAC_UPDATE(&ctx, mac, HASH_SIZE);
457
458 /* Verify that HMAC() is consistent with HMAC_USINGRAWKEY(). */
459 HMAC_PREPAREKEY(&key, raw_key, key_len);
460 HMAC(&key, data, data_len, mac2);
461 KUNIT_ASSERT_MEMEQ_MSG(
462 test, mac, mac2, HASH_SIZE,
463 "HMAC gave different results with raw and prepared keys");
464 }
465 HMAC_FINAL(&ctx, mac);
466 KUNIT_EXPECT_MEMEQ_MSG(test, mac, hmac_testvec_consolidated, HASH_SIZE,
467 "HMAC gave wrong result");
468 KUNIT_EXPECT_MEMEQ_MSG(test, &ctx, zeroes, sizeof(ctx),
469 "HMAC context was not zeroized by finalization");
470}
471#define HASH_KUNIT_CASES UNKEYED_HASH_KUNIT_CASES, KUNIT_CASE(test_hmac)
472#else
473#define HASH_KUNIT_CASES UNKEYED_HASH_KUNIT_CASES
474#endif
475
476/* Benchmark the hash function on various data lengths. */
477static void benchmark_hash(struct kunit *test)
478{
479 static const size_t lens_to_test[] = {
480 1, 16, 64, 127, 128, 200, 256,
481 511, 512, 1024, 3173, 4096, 16384,
482 };
483 const size_t max_len = 16384;
484 u8 *data = alloc_buf(test, max_len);
485 u8 hash[HASH_SIZE];
486
487 if (!IS_ENABLED(CONFIG_CRYPTO_LIB_BENCHMARK))
488 kunit_skip(test, "not enabled");
489
490 /* Warm-up */
491 memset(data, 0, max_len);
492 for (size_t i = 0; i < 10000000; i += max_len)
493 HASH(data, max_len, hash);
494
495 for (size_t i = 0; i < ARRAY_SIZE(lens_to_test); i++) {
496 size_t len = lens_to_test[i];
497 /* The '+ 128' tries to account for per-message overhead. */
498 size_t num_iters = 10000000 / (len + 128);
499 u64 t;
500
501 KUNIT_ASSERT_LE(test, len, max_len);
502 preempt_disable();
503 t = ktime_get_ns();
504 for (size_t j = 0; j < num_iters; j++)
505 HASH(data, len, hash);
506 t = ktime_get_ns() - t;
507 preempt_enable();
508 kunit_info(test, "len=%zu: %llu MB/s", len,
509 div64_u64((u64)len * num_iters * 1000, t ?: 1));
510 }
511}