]>
Commit | Line | Data |
---|---|---|
26609a21 EB |
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 | * | |
c6018e1a | 12 | * H_L ← Poly1305_{K_L}(NH_{K_N}(pad_{128}(L))) |
26609a21 | 13 | * |
c6018e1a EB |
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 | |
26609a21 EB |
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 | |
c6018e1a | 20 | * evaluation by itself would suffice to achieve the ε-∆U property; NH is used |
26609a21 EB |
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"); |