1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Copyright 2025 Google LLC 4 */ 5 #include <crypto/poly1305.h> 6 #include "poly1305-testvecs.h" 7 8 /* 9 * A fixed key used when presenting Poly1305 as an unkeyed hash function in 10 * order to reuse hash-test-template.h. At the beginning of the test suite, 11 * this is initialized to bytes generated from a fixed seed. 12 */ 13 static u8 test_key[POLY1305_KEY_SIZE]; 14 15 /* This probably should be in the actual API, but just define it here for now */ 16 static void poly1305(const u8 key[POLY1305_KEY_SIZE], const u8 *data, 17 size_t len, u8 out[POLY1305_DIGEST_SIZE]) 18 { 19 struct poly1305_desc_ctx ctx; 20 21 poly1305_init(&ctx, key); 22 poly1305_update(&ctx, data, len); 23 poly1305_final(&ctx, out); 24 } 25 26 static void poly1305_init_withtestkey(struct poly1305_desc_ctx *ctx) 27 { 28 poly1305_init(ctx, test_key); 29 } 30 31 static void poly1305_withtestkey(const u8 *data, size_t len, 32 u8 out[POLY1305_DIGEST_SIZE]) 33 { 34 poly1305(test_key, data, len, out); 35 } 36 37 /* Generate the HASH_KUNIT_CASES using hash-test-template.h. */ 38 #define HASH poly1305_withtestkey 39 #define HASH_CTX poly1305_desc_ctx 40 #define HASH_SIZE POLY1305_DIGEST_SIZE 41 #define HASH_INIT poly1305_init_withtestkey 42 #define HASH_UPDATE poly1305_update 43 #define HASH_FINAL poly1305_final 44 #include "hash-test-template.h" 45 46 static int poly1305_suite_init(struct kunit_suite *suite) 47 { 48 rand_bytes_seeded_from_len(test_key, POLY1305_KEY_SIZE); 49 return 0; 50 } 51 52 /* 53 * Poly1305 test case which uses a key and message consisting only of one bits: 54 * 55 * - Using an all-one-bits r_key tests the key clamping. 56 * - Using an all-one-bits s_key tests carries in implementations of the 57 * addition mod 2**128 during finalization. 58 * - Using all-one-bits message and r_key results in large values for the 59 * internal products of r_key by (accumulator + message block). This 60 * increases the chance of detecting bugs that occur only in rare cases where 61 * the sum of these internal products is very large, for example the bug fixed 62 * by commit 678cce4019d7 ("crypto: x86/poly1305 - fix overflow during partial 63 * reduction"). 64 * 65 * Bugs with the handling of large internal product sums may be specific to 66 * particular update lengths (in blocks) and/or require that the accumulator 67 * also have a large value. Note that the accumulator starts at 0. Thus, a 68 * single all-one-bits test vector may be insufficient. 69 * 70 * Considering that, do the following test: continuously update a single 71 * Poly1305 context with all-one-bits data of varying lengths (0, 16, 32, ..., 72 * 4096 bytes). After each update, generate the MAC from the current context, 73 * and feed that MAC into a separate Poly1305 context. Repeat that entire 74 * sequence of updates 32 times without re-initializing either context, 75 * resulting in a total of 8224 MAC computations from a long-running, cumulative 76 * context. Finally, generate and verify the MAC of all the MACs. 77 */ 78 static void test_poly1305_allones_keys_and_message(struct kunit *test) 79 { 80 const size_t max_len = 4096; 81 u8 *data = alloc_buf(test, max_len); 82 struct poly1305_desc_ctx mac_ctx, macofmacs_ctx; 83 u8 mac[POLY1305_DIGEST_SIZE]; 84 85 memset(data, 0xff, max_len); 86 87 poly1305_init(&mac_ctx, data); 88 poly1305_init(&macofmacs_ctx, data); 89 for (int i = 0; i < 32; i++) { 90 for (size_t len = 0; len <= max_len; len += 16) { 91 struct poly1305_desc_ctx tmp_ctx; 92 93 poly1305_update(&mac_ctx, data, len); 94 tmp_ctx = mac_ctx; 95 poly1305_final(&tmp_ctx, mac); 96 poly1305_update(&macofmacs_ctx, mac, 97 POLY1305_DIGEST_SIZE); 98 } 99 } 100 poly1305_final(&macofmacs_ctx, mac); 101 KUNIT_ASSERT_MEMEQ(test, mac, poly1305_allones_macofmacs, 102 POLY1305_DIGEST_SIZE); 103 } 104 105 /* 106 * Poly1305 test case which uses r_key=1, s_key=0, and a 48-byte message 107 * consisting of three blocks with integer values [2**128 - i, 0, 0]. In this 108 * case, the result of the polynomial evaluation is 2**130 - i. For small 109 * values of i, this is very close to the modulus 2**130 - 5, which helps catch 110 * edge case bugs in the modular reduction logic. 111 */ 112 static void test_poly1305_reduction_edge_cases(struct kunit *test) 113 { 114 static const u8 key[POLY1305_KEY_SIZE] = { 1 }; /* r_key=1, s_key=0 */ 115 u8 data[3 * POLY1305_BLOCK_SIZE] = {}; 116 u8 expected_mac[POLY1305_DIGEST_SIZE]; 117 u8 actual_mac[POLY1305_DIGEST_SIZE]; 118 119 for (int i = 1; i <= 10; i++) { 120 /* Set the first data block to 2**128 - i. */ 121 data[0] = -i; 122 memset(&data[1], 0xff, POLY1305_BLOCK_SIZE - 1); 123 124 /* 125 * Assuming s_key=0, the expected MAC as an integer is 126 * (2**130 - i mod 2**130 - 5) + 0 mod 2**128. If 1 <= i <= 5, 127 * that's 5 - i. If 6 <= i <= 10, that's 2**128 - i. 128 */ 129 if (i <= 5) { 130 expected_mac[0] = 5 - i; 131 memset(&expected_mac[1], 0, POLY1305_DIGEST_SIZE - 1); 132 } else { 133 expected_mac[0] = -i; 134 memset(&expected_mac[1], 0xff, 135 POLY1305_DIGEST_SIZE - 1); 136 } 137 138 /* Compute and verify the MAC. */ 139 poly1305(key, data, sizeof(data), actual_mac); 140 KUNIT_ASSERT_MEMEQ(test, actual_mac, expected_mac, 141 POLY1305_DIGEST_SIZE); 142 } 143 } 144 145 /* 146 * Test that Poly1305 MACs are computed correctly when r_key=1, s_key=0, and the 147 * message consists of all-ones blocks. 148 * 149 * With r_key=1 and s_key=0, Poly1305 degrades to the sum of the padded blocks 150 * mod 2**130 - 5, then reduced mod 2**128. A padded all-ones block maps to 151 * 2**128 + (2**128 - 1) = 2**129 - 1. Two such blocks sum to 2**130 - 2, which 152 * is congruent to 3 mod 2**130 - 5. Thus, the expected MAC is just 3 * 153 * floor(nblocks / 2), minus 1 if nblocks is odd, then reduced mod 2**128. If 154 * nblocks == 1 this is 2**128 - 1, otherwise it's just a small integer. 155 * 156 * Inside the Poly1305 implementation in this case, the multiplication does 157 * nothing and each block just adds 2**129 - 1 to the accumulator. Without the 158 * multiplication to mix things up, this results in some interesting values 159 * being reached where the limbs are at or near their maximum values, even after 160 * (lazy) reduction. This can reproduce bugs that happen only in such cases. 161 * 162 * For example, this test case reproduces the bug fixed by commit 24f07e8c07a0 163 * ("lib/crypto: arm64: Fix lost Poly1305 carry when resuming NEON state"). 164 * 165 * However, reaching that bug required two consecutive updates: one with >= 8 166 * blocks to cause NEON code to be used and leave the accumulator in base 2**26 167 * with its limbs in a certain pattern, then one with an odd number of blocks >= 168 * 9 to cause NEON to be used again, but first processing one block using scalar 169 * code as a special case, triggering a conversion to base 2**64 where the carry 170 * into the 2**128 bit was lost. To cover this and other similar edge cases 171 * that may exist in other Poly1305 implementations, just test all possible 172 * block-aligned splits between three poly1305_update() calls. 173 */ 174 static void test_poly1305_split_update_carry(struct kunit *test) 175 { 176 static const u8 key[POLY1305_KEY_SIZE] = { 1 }; /* r_key=1, s_key=0 */ 177 /* 178 * Use max_nblocks=66 so that it's a bit more than twice the AVX-512 179 * threshold of 32 blocks. 180 */ 181 const int max_nblocks = 66; 182 u8 *data = alloc_buf(test, max_nblocks * POLY1305_BLOCK_SIZE); 183 u8 expected_mac[POLY1305_DIGEST_SIZE]; 184 u8 actual_mac[POLY1305_DIGEST_SIZE]; 185 struct poly1305_desc_ctx ctx; 186 187 KUNIT_ASSERT_LE(test, 3 * (max_nblocks / 2), U8_MAX); 188 189 memset(data, 0xff, max_nblocks * POLY1305_BLOCK_SIZE); 190 191 for (int nblocks = 0; nblocks <= max_nblocks; nblocks++) { 192 size_t len = nblocks * POLY1305_BLOCK_SIZE; 193 194 expected_mac[0] = 3 * (nblocks / 2) - (nblocks % 2); 195 memset(&expected_mac[1], nblocks == 1 ? 0xff : 0, 196 POLY1305_DIGEST_SIZE - 1); 197 for (size_t part1_len = 0; part1_len <= len; 198 part1_len += POLY1305_BLOCK_SIZE) { 199 for (size_t part2_len = 0; part2_len <= len - part1_len; 200 part2_len += POLY1305_BLOCK_SIZE) { 201 size_t part3_len = len - part1_len - part2_len; 202 203 poly1305_init(&ctx, key); 204 poly1305_update(&ctx, data, part1_len); 205 poly1305_update(&ctx, &data[part1_len], 206 part2_len); 207 poly1305_update(&ctx, 208 &data[part1_len + part2_len], 209 part3_len); 210 poly1305_final(&ctx, actual_mac); 211 KUNIT_ASSERT_MEMEQ_MSG( 212 test, actual_mac, expected_mac, 213 POLY1305_DIGEST_SIZE, 214 "Failed with nblocks=%d, part1_len=%zu, part2_len=%zu, part3_len=%zu", 215 nblocks, part1_len, part2_len, 216 part3_len); 217 } 218 } 219 } 220 } 221 222 static struct kunit_case poly1305_test_cases[] = { 223 HASH_KUNIT_CASES, 224 KUNIT_CASE(test_poly1305_allones_keys_and_message), 225 KUNIT_CASE(test_poly1305_reduction_edge_cases), 226 KUNIT_CASE(test_poly1305_split_update_carry), 227 KUNIT_CASE(benchmark_hash), 228 {}, 229 }; 230 231 static struct kunit_suite poly1305_test_suite = { 232 .name = "poly1305", 233 .test_cases = poly1305_test_cases, 234 .suite_init = poly1305_suite_init, 235 }; 236 kunit_test_suite(poly1305_test_suite); 237 238 MODULE_DESCRIPTION("KUnit tests and benchmark for Poly1305"); 239 MODULE_LICENSE("GPL"); 240