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/internal/poly1305.h> |
37 | #include <crypto/nhpoly1305.h> |
38 | #include <linux/crypto.h> |
39 | #include <linux/kernel.h> |
40 | #include <linux/module.h> |
41 | |
42 | static void nh_generic(const u32 *key, const u8 *message, size_t message_len, |
43 | __le64 hash[NH_NUM_PASSES]) |
44 | { |
45 | u64 sums[4] = { 0, 0, 0, 0 }; |
46 | |
47 | BUILD_BUG_ON(NH_PAIR_STRIDE != 2); |
48 | BUILD_BUG_ON(NH_NUM_PASSES != 4); |
49 | |
50 | while (message_len) { |
51 | u32 m0 = get_unaligned_le32(p: message + 0); |
52 | u32 m1 = get_unaligned_le32(p: message + 4); |
53 | u32 m2 = get_unaligned_le32(p: message + 8); |
54 | u32 m3 = get_unaligned_le32(p: message + 12); |
55 | |
56 | sums[0] += (u64)(u32)(m0 + key[ 0]) * (u32)(m2 + key[ 2]); |
57 | sums[1] += (u64)(u32)(m0 + key[ 4]) * (u32)(m2 + key[ 6]); |
58 | sums[2] += (u64)(u32)(m0 + key[ 8]) * (u32)(m2 + key[10]); |
59 | sums[3] += (u64)(u32)(m0 + key[12]) * (u32)(m2 + key[14]); |
60 | sums[0] += (u64)(u32)(m1 + key[ 1]) * (u32)(m3 + key[ 3]); |
61 | sums[1] += (u64)(u32)(m1 + key[ 5]) * (u32)(m3 + key[ 7]); |
62 | sums[2] += (u64)(u32)(m1 + key[ 9]) * (u32)(m3 + key[11]); |
63 | sums[3] += (u64)(u32)(m1 + key[13]) * (u32)(m3 + key[15]); |
64 | key += NH_MESSAGE_UNIT / sizeof(key[0]); |
65 | message += NH_MESSAGE_UNIT; |
66 | message_len -= NH_MESSAGE_UNIT; |
67 | } |
68 | |
69 | hash[0] = cpu_to_le64(sums[0]); |
70 | hash[1] = cpu_to_le64(sums[1]); |
71 | hash[2] = cpu_to_le64(sums[2]); |
72 | hash[3] = cpu_to_le64(sums[3]); |
73 | } |
74 | |
75 | /* Pass the next NH hash value through Poly1305 */ |
76 | static void process_nh_hash_value(struct nhpoly1305_state *state, |
77 | const struct nhpoly1305_key *key) |
78 | { |
79 | BUILD_BUG_ON(NH_HASH_BYTES % POLY1305_BLOCK_SIZE != 0); |
80 | |
81 | poly1305_core_blocks(state: &state->poly_state, key: &key->poly_key, src: state->nh_hash, |
82 | NH_HASH_BYTES / POLY1305_BLOCK_SIZE, hibit: 1); |
83 | } |
84 | |
85 | /* |
86 | * Feed the next portion of the source data, as a whole number of 16-byte |
87 | * "NH message units", through NH and Poly1305. Each NH hash is taken over |
88 | * 1024 bytes, except possibly the final one which is taken over a multiple of |
89 | * 16 bytes up to 1024. Also, in the case where data is passed in misaligned |
90 | * chunks, we combine partial hashes; the end result is the same either way. |
91 | */ |
92 | static void nhpoly1305_units(struct nhpoly1305_state *state, |
93 | const struct nhpoly1305_key *key, |
94 | const u8 *src, unsigned int srclen, nh_t nh_fn) |
95 | { |
96 | do { |
97 | unsigned int bytes; |
98 | |
99 | if (state->nh_remaining == 0) { |
100 | /* Starting a new NH message */ |
101 | bytes = min_t(unsigned int, srclen, NH_MESSAGE_BYTES); |
102 | nh_fn(key->nh_key, src, bytes, state->nh_hash); |
103 | state->nh_remaining = NH_MESSAGE_BYTES - bytes; |
104 | } else { |
105 | /* Continuing a previous NH message */ |
106 | __le64 tmp_hash[NH_NUM_PASSES]; |
107 | unsigned int pos; |
108 | int i; |
109 | |
110 | pos = NH_MESSAGE_BYTES - state->nh_remaining; |
111 | bytes = min(srclen, state->nh_remaining); |
112 | nh_fn(&key->nh_key[pos / 4], src, bytes, tmp_hash); |
113 | for (i = 0; i < NH_NUM_PASSES; i++) |
114 | le64_add_cpu(var: &state->nh_hash[i], |
115 | le64_to_cpu(tmp_hash[i])); |
116 | state->nh_remaining -= bytes; |
117 | } |
118 | if (state->nh_remaining == 0) |
119 | process_nh_hash_value(state, key); |
120 | src += bytes; |
121 | srclen -= bytes; |
122 | } while (srclen); |
123 | } |
124 | |
125 | int crypto_nhpoly1305_setkey(struct crypto_shash *tfm, |
126 | const u8 *key, unsigned int keylen) |
127 | { |
128 | struct nhpoly1305_key *ctx = crypto_shash_ctx(tfm); |
129 | int i; |
130 | |
131 | if (keylen != NHPOLY1305_KEY_SIZE) |
132 | return -EINVAL; |
133 | |
134 | poly1305_core_setkey(key: &ctx->poly_key, raw_key: key); |
135 | key += POLY1305_BLOCK_SIZE; |
136 | |
137 | for (i = 0; i < NH_KEY_WORDS; i++) |
138 | ctx->nh_key[i] = get_unaligned_le32(p: key + i * sizeof(u32)); |
139 | |
140 | return 0; |
141 | } |
142 | EXPORT_SYMBOL(crypto_nhpoly1305_setkey); |
143 | |
144 | int crypto_nhpoly1305_init(struct shash_desc *desc) |
145 | { |
146 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |
147 | |
148 | poly1305_core_init(state: &state->poly_state); |
149 | state->buflen = 0; |
150 | state->nh_remaining = 0; |
151 | return 0; |
152 | } |
153 | EXPORT_SYMBOL(crypto_nhpoly1305_init); |
154 | |
155 | int crypto_nhpoly1305_update_helper(struct shash_desc *desc, |
156 | const u8 *src, unsigned int srclen, |
157 | nh_t nh_fn) |
158 | { |
159 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |
160 | const struct nhpoly1305_key *key = crypto_shash_ctx(tfm: desc->tfm); |
161 | unsigned int bytes; |
162 | |
163 | if (state->buflen) { |
164 | bytes = min(srclen, (int)NH_MESSAGE_UNIT - state->buflen); |
165 | memcpy(&state->buffer[state->buflen], src, bytes); |
166 | state->buflen += bytes; |
167 | if (state->buflen < NH_MESSAGE_UNIT) |
168 | return 0; |
169 | nhpoly1305_units(state, key, src: state->buffer, NH_MESSAGE_UNIT, |
170 | nh_fn); |
171 | state->buflen = 0; |
172 | src += bytes; |
173 | srclen -= bytes; |
174 | } |
175 | |
176 | if (srclen >= NH_MESSAGE_UNIT) { |
177 | bytes = round_down(srclen, NH_MESSAGE_UNIT); |
178 | nhpoly1305_units(state, key, src, srclen: bytes, nh_fn); |
179 | src += bytes; |
180 | srclen -= bytes; |
181 | } |
182 | |
183 | if (srclen) { |
184 | memcpy(state->buffer, src, srclen); |
185 | state->buflen = srclen; |
186 | } |
187 | return 0; |
188 | } |
189 | EXPORT_SYMBOL(crypto_nhpoly1305_update_helper); |
190 | |
191 | int crypto_nhpoly1305_update(struct shash_desc *desc, |
192 | const u8 *src, unsigned int srclen) |
193 | { |
194 | return crypto_nhpoly1305_update_helper(desc, src, srclen, nh_generic); |
195 | } |
196 | EXPORT_SYMBOL(crypto_nhpoly1305_update); |
197 | |
198 | int crypto_nhpoly1305_final_helper(struct shash_desc *desc, u8 *dst, nh_t nh_fn) |
199 | { |
200 | struct nhpoly1305_state *state = shash_desc_ctx(desc); |
201 | const struct nhpoly1305_key *key = crypto_shash_ctx(tfm: desc->tfm); |
202 | |
203 | if (state->buflen) { |
204 | memset(&state->buffer[state->buflen], 0, |
205 | NH_MESSAGE_UNIT - state->buflen); |
206 | nhpoly1305_units(state, key, src: state->buffer, NH_MESSAGE_UNIT, |
207 | nh_fn); |
208 | } |
209 | |
210 | if (state->nh_remaining) |
211 | process_nh_hash_value(state, key); |
212 | |
213 | poly1305_core_emit(state: &state->poly_state, NULL, dst); |
214 | return 0; |
215 | } |
216 | EXPORT_SYMBOL(crypto_nhpoly1305_final_helper); |
217 | |
218 | int crypto_nhpoly1305_final(struct shash_desc *desc, u8 *dst) |
219 | { |
220 | return crypto_nhpoly1305_final_helper(desc, dst, nh_generic); |
221 | } |
222 | EXPORT_SYMBOL(crypto_nhpoly1305_final); |
223 | |
224 | static struct shash_alg nhpoly1305_alg = { |
225 | .base.cra_name = "nhpoly1305" , |
226 | .base.cra_driver_name = "nhpoly1305-generic" , |
227 | .base.cra_priority = 100, |
228 | .base.cra_ctxsize = sizeof(struct nhpoly1305_key), |
229 | .base.cra_module = THIS_MODULE, |
230 | .digestsize = POLY1305_DIGEST_SIZE, |
231 | .init = crypto_nhpoly1305_init, |
232 | .update = crypto_nhpoly1305_update, |
233 | .final = crypto_nhpoly1305_final, |
234 | .setkey = crypto_nhpoly1305_setkey, |
235 | .descsize = sizeof(struct nhpoly1305_state), |
236 | }; |
237 | |
238 | static int __init nhpoly1305_mod_init(void) |
239 | { |
240 | return crypto_register_shash(alg: &nhpoly1305_alg); |
241 | } |
242 | |
243 | static void __exit nhpoly1305_mod_exit(void) |
244 | { |
245 | crypto_unregister_shash(alg: &nhpoly1305_alg); |
246 | } |
247 | |
248 | subsys_initcall(nhpoly1305_mod_init); |
249 | module_exit(nhpoly1305_mod_exit); |
250 | |
251 | MODULE_DESCRIPTION("NHPoly1305 ε-almost-∆-universal hash function" ); |
252 | MODULE_LICENSE("GPL v2" ); |
253 | MODULE_AUTHOR("Eric Biggers <ebiggers@google.com>" ); |
254 | MODULE_ALIAS_CRYPTO("nhpoly1305" ); |
255 | MODULE_ALIAS_CRYPTO("nhpoly1305-generic" ); |
256 | |