blob: ec831a5594d8fe46266d00de594fbbf66ea058f6
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * NHPoly1305 - ε-almost-∆-universal hash function for Adiantum |
4 | * |
5 | * Copyright 2018 Google LLC |
6 | */ |
7 | |
8 | /* |
9 | * "NHPoly1305" is the main component of Adiantum hashing. |
10 | * Specifically, it is the calculation |
11 | * |
12 | * H_L ← Poly1305_{K_L}(NH_{K_N}(pad_{128}(L))) |
13 | * |
14 | * from the procedure in section 6.4 of the Adiantum paper [1]. It is an |
15 | * ε-almost-∆-universal (ε-∆U) hash function for equal-length inputs over |
16 | * Z/(2^{128}Z), where the "∆" operation is addition. It hashes 1024-byte |
17 | * chunks of the input with the NH hash function [2], reducing the input length |
18 | * by 32x. The resulting NH digests are evaluated as a polynomial in |
19 | * GF(2^{130}-5), like in the Poly1305 MAC [3]. Note that the polynomial |
20 | * evaluation by itself would suffice to achieve the ε-∆U property; NH is used |
21 | * for performance since it's over twice as fast as Poly1305. |
22 | * |
23 | * This is *not* a cryptographic hash function; do not use it as such! |
24 | * |
25 | * [1] Adiantum: length-preserving encryption for entry-level processors |
26 | * (https://eprint.iacr.org/2018/720.pdf) |
27 | * [2] UMAC: Fast and Secure Message Authentication |
28 | * (https://fastcrypto.org/umac/umac_proc.pdf) |
29 | * [3] The Poly1305-AES message-authentication code |
30 | * (https://cr.yp.to/mac/poly1305-20050329.pdf) |
31 | */ |
32 | |
33 | #include <asm/unaligned.h> |
34 | #include <crypto/algapi.h> |
35 | #include <crypto/internal/hash.h> |
36 | #include <crypto/nhpoly1305.h> |
37 | #include <linux/crypto.h> |
38 | #include <linux/kernel.h> |
39 | #include <linux/module.h> |
40 | |
41 | static void nh_generic(const u32 *key, const u8 *message, size_t message_len, |
42 | __le64 hash[NH_NUM_PASSES]) |
43 | { |
44 | u64 sums[4] = { 0, 0, 0, 0 }; |
45 | |
46 | BUILD_BUG_ON(NH_PAIR_STRIDE != 2); |
47 | BUILD_BUG_ON(NH_NUM_PASSES != 4); |
48 | |
49 | while (message_len) { |
50 | u32 m0 = get_unaligned_le32(message + 0); |
51 | u32 m1 = get_unaligned_le32(message + 4); |
52 | u32 m2 = get_unaligned_le32(message + 8); |
53 | u32 m3 = get_unaligned_le32(message + 12); |
54 | |
55 | sums[0] += (u64)(u32)(m0 + key[ 0]) * (u32)(m2 + key[ 2]); |
56 | sums[1] += (u64)(u32)(m0 + key[ 4]) * (u32)(m2 + key[ 6]); |
57 | sums[2] += (u64)(u32)(m0 + key[ 8]) * (u32)(m2 + key[10]); |
58 | sums[3] += (u64)(u32)(m0 + key[12]) * (u32)(m2 + key[14]); |
59 | sums[0] += (u64)(u32)(m1 + key[ 1]) * (u32)(m3 + key[ 3]); |
60 | sums[1] += (u64)(u32)(m1 + key[ 5]) * (u32)(m3 + key[ 7]); |
61 | sums[2] += (u64)(u32)(m1 + key[ 9]) * (u32)(m3 + key[11]); |
62 | sums[3] += (u64)(u32)(m1 + key[13]) * (u32)(m3 + key[15]); |
63 | key += NH_MESSAGE_UNIT / sizeof(key[0]); |
64 | message += NH_MESSAGE_UNIT; |
65 | message_len -= NH_MESSAGE_UNIT; |
66 | } |
67 | |
68 | hash[0] = cpu_to_le64(sums[0]); |
69 | hash[1] = cpu_to_le64(sums[1]); |
70 | hash[2] = cpu_to_le64(sums[2]); |
71 | hash[3] = cpu_to_le64(sums[3]); |
72 | } |
73 | |
74 | /* Pass the next NH hash value through Poly1305 */ |
75 | static void process_nh_hash_value(struct nhpoly1305_state *state, |
76 | const struct nhpoly1305_key *key) |
77 | { |
78 | BUILD_BUG_ON(NH_HASH_BYTES % POLY1305_BLOCK_SIZE != 0); |
79 | |
80 | poly1305_core_blocks(&state->poly_state, &key->poly_key, state->nh_hash, |
81 | NH_HASH_BYTES / POLY1305_BLOCK_SIZE); |
82 | } |
83 | |
84 | /* |
85 | * Feed the next portion of the source data, as a whole number of 16-byte |
86 | * "NH message units", through NH and Poly1305. Each NH hash is taken over |
87 | * 1024 bytes, except possibly the final one which is taken over a multiple of |
88 | * 16 bytes up to 1024. Also, in the case where data is passed in misaligned |
89 | * chunks, we combine partial hashes; the end result is the same either way. |
90 | */ |
91 | static void nhpoly1305_units(struct nhpoly1305_state *state, |
92 | const struct nhpoly1305_key *key, |
93 | const u8 *src, unsigned int srclen, nh_t nh_fn) |
94 | { |
95 | do { |
96 | unsigned int bytes; |
97 | |
98 | if (state->nh_remaining == 0) { |
99 | /* Starting a new NH message */ |
100 | bytes = min_t(unsigned int, srclen, NH_MESSAGE_BYTES); |
101 | nh_fn(key->nh_key, src, bytes, state->nh_hash); |
102 | state->nh_remaining = NH_MESSAGE_BYTES - bytes; |
103 | } else { |
104 | /* Continuing a previous NH message */ |
105 | __le64 tmp_hash[NH_NUM_PASSES]; |
106 | unsigned int pos; |
107 | int i; |
108 | |
109 | pos = NH_MESSAGE_BYTES - state->nh_remaining; |
110 | bytes = min(srclen, state->nh_remaining); |
111 | nh_fn(&key->nh_key[pos / 4], src, bytes, tmp_hash); |
112 | for (i = 0; i < NH_NUM_PASSES; i++) |
113 | le64_add_cpu(&state->nh_hash[i], |
114 | le64_to_cpu(tmp_hash[i])); |
115 | state->nh_remaining -= bytes; |
116 | } |
117 | if (state->nh_remaining == 0) |
118 | process_nh_hash_value(state, key); |
119 | src += bytes; |
120 | srclen -= bytes; |
121 | } while (srclen); |
122 | } |
123 | |
124 | int crypto_nhpoly1305_setkey(struct crypto_shash *tfm, |
125 | const u8 *key, unsigned int keylen) |
126 | { |
127 | struct nhpoly1305_key *ctx = crypto_shash_ctx(tfm); |
128 | int i; |
129 | |
130 | if (keylen != NHPOLY1305_KEY_SIZE) |
131 | return -EINVAL; |
132 | |
133 | poly1305_core_setkey(&ctx->poly_key, key); |
134 | key += POLY1305_BLOCK_SIZE; |
135 | |
136 | for (i = 0; i < NH_KEY_WORDS; i++) |
137 | ctx->nh_key[i] = get_unaligned_le32(key + i * sizeof(u32)); |
138 | |
139 | return 0; |
140 | } |
141 | EXPORT_SYMBOL(crypto_nhpoly1305_setkey); |
142 | |
143 | int crypto_nhpoly1305_init(struct shash_desc *desc) |
144 | { |
145 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |
146 | |
147 | poly1305_core_init(&state->poly_state); |
148 | state->buflen = 0; |
149 | state->nh_remaining = 0; |
150 | return 0; |
151 | } |
152 | EXPORT_SYMBOL(crypto_nhpoly1305_init); |
153 | |
154 | int crypto_nhpoly1305_update_helper(struct shash_desc *desc, |
155 | const u8 *src, unsigned int srclen, |
156 | nh_t nh_fn) |
157 | { |
158 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |
159 | const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm); |
160 | unsigned int bytes; |
161 | |
162 | if (state->buflen) { |
163 | bytes = min(srclen, (int)NH_MESSAGE_UNIT - state->buflen); |
164 | memcpy(&state->buffer[state->buflen], src, bytes); |
165 | state->buflen += bytes; |
166 | if (state->buflen < NH_MESSAGE_UNIT) |
167 | return 0; |
168 | nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT, |
169 | nh_fn); |
170 | state->buflen = 0; |
171 | src += bytes; |
172 | srclen -= bytes; |
173 | } |
174 | |
175 | if (srclen >= NH_MESSAGE_UNIT) { |
176 | bytes = round_down(srclen, NH_MESSAGE_UNIT); |
177 | nhpoly1305_units(state, key, src, bytes, nh_fn); |
178 | src += bytes; |
179 | srclen -= bytes; |
180 | } |
181 | |
182 | if (srclen) { |
183 | memcpy(state->buffer, src, srclen); |
184 | state->buflen = srclen; |
185 | } |
186 | return 0; |
187 | } |
188 | EXPORT_SYMBOL(crypto_nhpoly1305_update_helper); |
189 | |
190 | int crypto_nhpoly1305_update(struct shash_desc *desc, |
191 | const u8 *src, unsigned int srclen) |
192 | { |
193 | return crypto_nhpoly1305_update_helper(desc, src, srclen, nh_generic); |
194 | } |
195 | EXPORT_SYMBOL(crypto_nhpoly1305_update); |
196 | |
197 | int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn) |
198 | { |
199 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |
200 | const struct nhpoly1305_key *key = crypto_shash_ctx(desc->tfm); |
201 | |
202 | if (state->buflen) { |
203 | memset(&state->buffer[state->buflen], 0, |
204 | NH_MESSAGE_UNIT - state->buflen); |
205 | nhpoly1305_units(state, key, state->buffer, NH_MESSAGE_UNIT, |
206 | nh_fn); |
207 | } |
208 | |
209 | if (state->nh_remaining) |
210 | process_nh_hash_value(state, key); |
211 | |
212 | poly1305_core_emit(&state->poly_state, dst); |
213 | return 0; |
214 | } |
215 | EXPORT_SYMBOL(crypto_nhpoly1305_final_helper); |
216 | |
217 | int crypto_nhpoly1305_final(struct shash_desc *desc, u8 *dst) |
218 | { |
219 | return crypto_nhpoly1305_final_helper(desc, dst, nh_generic); |
220 | } |
221 | EXPORT_SYMBOL(crypto_nhpoly1305_final); |
222 | |
223 | static struct shash_alg nhpoly1305_alg = { |
224 | .base.cra_name = "nhpoly1305", |
225 | .base.cra_driver_name = "nhpoly1305-generic", |
226 | .base.cra_priority = 100, |
227 | .base.cra_ctxsize = sizeof(struct nhpoly1305_key), |
228 | .base.cra_module = THIS_MODULE, |
229 | .digestsize = POLY1305_DIGEST_SIZE, |
230 | .init = crypto_nhpoly1305_init, |
231 | .update = crypto_nhpoly1305_update, |
232 | .final = crypto_nhpoly1305_final, |
233 | .setkey = crypto_nhpoly1305_setkey, |
234 | .descsize = sizeof(struct nhpoly1305_state), |
235 | }; |
236 | |
237 | static int __init nhpoly1305_mod_init(void) |
238 | { |
239 | return crypto_register_shash(&nhpoly1305_alg); |
240 | } |
241 | |
242 | static void __exit nhpoly1305_mod_exit(void) |
243 | { |
244 | crypto_unregister_shash(&nhpoly1305_alg); |
245 | } |
246 | |
247 | module_init(nhpoly1305_mod_init); |
248 | module_exit(nhpoly1305_mod_exit); |
249 | |
250 | MODULE_DESCRIPTION("NHPoly1305 ε-almost-∆-universal hash function"); |
251 | MODULE_LICENSE("GPL v2"); |
252 | MODULE_AUTHOR("Eric Biggers <ebiggers@google.com>"); |
253 | MODULE_ALIAS_CRYPTO("nhpoly1305"); |
254 | MODULE_ALIAS_CRYPTO("nhpoly1305-generic"); |
255 |