]>
Commit | Line | Data |
---|---|---|
19c402af SG |
1 | /* |
2 | * Copyright (c) 2013, Google Inc. | |
3 | * | |
1a459660 | 4 | * SPDX-License-Identifier: GPL-2.0+ |
19c402af SG |
5 | */ |
6 | ||
29a23f9d | 7 | #ifndef USE_HOSTCC |
19c402af SG |
8 | #include <common.h> |
9 | #include <fdtdec.h> | |
29a23f9d | 10 | #include <asm/types.h> |
19c402af SG |
11 | #include <asm/byteorder.h> |
12 | #include <asm/errno.h> | |
29a23f9d | 13 | #include <asm/types.h> |
19c402af | 14 | #include <asm/unaligned.h> |
29a23f9d HS |
15 | #else |
16 | #include "fdt_host.h" | |
17 | #include "mkimage.h" | |
18 | #include <fdt_support.h> | |
19 | #endif | |
2b9912e6 JH |
20 | #include <u-boot/rsa.h> |
21 | #include <u-boot/sha1.h> | |
22 | #include <u-boot/sha256.h> | |
19c402af | 23 | |
19c402af SG |
24 | #define UINT64_MULT32(v, multby) (((uint64_t)(v)) * ((uint32_t)(multby))) |
25 | ||
29a23f9d HS |
26 | #define get_unaligned_be32(a) fdt32_to_cpu(*(uint32_t *)a) |
27 | #define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_fdt32(a)) | |
28 | ||
e0f2f155 MW |
29 | /* Default public exponent for backward compatibility */ |
30 | #define RSA_DEFAULT_PUBEXP 65537 | |
31 | ||
19c402af SG |
32 | /** |
33 | * subtract_modulus() - subtract modulus from the given value | |
34 | * | |
35 | * @key: Key containing modulus to subtract | |
36 | * @num: Number to subtract modulus from, as little endian word array | |
37 | */ | |
38 | static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[]) | |
39 | { | |
40 | int64_t acc = 0; | |
41 | uint i; | |
42 | ||
43 | for (i = 0; i < key->len; i++) { | |
44 | acc += (uint64_t)num[i] - key->modulus[i]; | |
45 | num[i] = (uint32_t)acc; | |
46 | acc >>= 32; | |
47 | } | |
48 | } | |
49 | ||
50 | /** | |
51 | * greater_equal_modulus() - check if a value is >= modulus | |
52 | * | |
53 | * @key: Key containing modulus to check | |
54 | * @num: Number to check against modulus, as little endian word array | |
55 | * @return 0 if num < modulus, 1 if num >= modulus | |
56 | */ | |
57 | static int greater_equal_modulus(const struct rsa_public_key *key, | |
58 | uint32_t num[]) | |
59 | { | |
60 | uint32_t i; | |
61 | ||
62 | for (i = key->len - 1; i >= 0; i--) { | |
63 | if (num[i] < key->modulus[i]) | |
64 | return 0; | |
65 | if (num[i] > key->modulus[i]) | |
66 | return 1; | |
67 | } | |
68 | ||
69 | return 1; /* equal */ | |
70 | } | |
71 | ||
72 | /** | |
73 | * montgomery_mul_add_step() - Perform montgomery multiply-add step | |
74 | * | |
75 | * Operation: montgomery result[] += a * b[] / n0inv % modulus | |
76 | * | |
77 | * @key: RSA key | |
78 | * @result: Place to put result, as little endian word array | |
79 | * @a: Multiplier | |
80 | * @b: Multiplicand, as little endian word array | |
81 | */ | |
82 | static void montgomery_mul_add_step(const struct rsa_public_key *key, | |
83 | uint32_t result[], const uint32_t a, const uint32_t b[]) | |
84 | { | |
85 | uint64_t acc_a, acc_b; | |
86 | uint32_t d0; | |
87 | uint i; | |
88 | ||
89 | acc_a = (uint64_t)a * b[0] + result[0]; | |
90 | d0 = (uint32_t)acc_a * key->n0inv; | |
91 | acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a; | |
92 | for (i = 1; i < key->len; i++) { | |
93 | acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i]; | |
94 | acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] + | |
95 | (uint32_t)acc_a; | |
96 | result[i - 1] = (uint32_t)acc_b; | |
97 | } | |
98 | ||
99 | acc_a = (acc_a >> 32) + (acc_b >> 32); | |
100 | ||
101 | result[i - 1] = (uint32_t)acc_a; | |
102 | ||
103 | if (acc_a >> 32) | |
104 | subtract_modulus(key, result); | |
105 | } | |
106 | ||
107 | /** | |
108 | * montgomery_mul() - Perform montgomery mutitply | |
109 | * | |
110 | * Operation: montgomery result[] = a[] * b[] / n0inv % modulus | |
111 | * | |
112 | * @key: RSA key | |
113 | * @result: Place to put result, as little endian word array | |
114 | * @a: Multiplier, as little endian word array | |
115 | * @b: Multiplicand, as little endian word array | |
116 | */ | |
117 | static void montgomery_mul(const struct rsa_public_key *key, | |
118 | uint32_t result[], uint32_t a[], const uint32_t b[]) | |
119 | { | |
120 | uint i; | |
121 | ||
122 | for (i = 0; i < key->len; ++i) | |
123 | result[i] = 0; | |
124 | for (i = 0; i < key->len; ++i) | |
125 | montgomery_mul_add_step(key, result, a[i], b); | |
126 | } | |
127 | ||
e0f2f155 MW |
128 | /** |
129 | * num_pub_exponent_bits() - Number of bits in the public exponent | |
130 | * | |
131 | * @key: RSA key | |
132 | * @num_bits: Storage for the number of public exponent bits | |
133 | */ | |
134 | static int num_public_exponent_bits(const struct rsa_public_key *key, | |
135 | int *num_bits) | |
136 | { | |
137 | uint64_t exponent; | |
138 | int exponent_bits; | |
139 | const uint max_bits = (sizeof(exponent) * 8); | |
140 | ||
141 | exponent = key->exponent; | |
142 | exponent_bits = 0; | |
143 | ||
144 | if (!exponent) { | |
145 | *num_bits = exponent_bits; | |
146 | return 0; | |
147 | } | |
148 | ||
149 | for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits) | |
150 | if (!(exponent >>= 1)) { | |
151 | *num_bits = exponent_bits; | |
152 | return 0; | |
153 | } | |
154 | ||
155 | return -EINVAL; | |
156 | } | |
157 | ||
158 | /** | |
159 | * is_public_exponent_bit_set() - Check if a bit in the public exponent is set | |
160 | * | |
161 | * @key: RSA key | |
162 | * @pos: The bit position to check | |
163 | */ | |
164 | static int is_public_exponent_bit_set(const struct rsa_public_key *key, | |
165 | int pos) | |
166 | { | |
167 | return key->exponent & (1ULL << pos); | |
168 | } | |
169 | ||
19c402af SG |
170 | /** |
171 | * pow_mod() - in-place public exponentiation | |
172 | * | |
173 | * @key: RSA key | |
174 | * @inout: Big-endian word array containing value and result | |
175 | */ | |
176 | static int pow_mod(const struct rsa_public_key *key, uint32_t *inout) | |
177 | { | |
178 | uint32_t *result, *ptr; | |
179 | uint i; | |
e0f2f155 | 180 | int j, k; |
19c402af SG |
181 | |
182 | /* Sanity check for stack size - key->len is in 32-bit words */ | |
183 | if (key->len > RSA_MAX_KEY_BITS / 32) { | |
184 | debug("RSA key words %u exceeds maximum %d\n", key->len, | |
185 | RSA_MAX_KEY_BITS / 32); | |
186 | return -EINVAL; | |
187 | } | |
188 | ||
189 | uint32_t val[key->len], acc[key->len], tmp[key->len]; | |
e0f2f155 | 190 | uint32_t a_scaled[key->len]; |
19c402af SG |
191 | result = tmp; /* Re-use location. */ |
192 | ||
193 | /* Convert from big endian byte array to little endian word array. */ | |
194 | for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--) | |
195 | val[i] = get_unaligned_be32(ptr); | |
196 | ||
e0f2f155 MW |
197 | if (0 != num_public_exponent_bits(key, &k)) |
198 | return -EINVAL; | |
199 | ||
200 | if (k < 2) { | |
201 | debug("Public exponent is too short (%d bits, minimum 2)\n", | |
202 | k); | |
203 | return -EINVAL; | |
204 | } | |
205 | ||
206 | if (!is_public_exponent_bit_set(key, 0)) { | |
207 | debug("LSB of RSA public exponent must be set.\n"); | |
208 | return -EINVAL; | |
19c402af | 209 | } |
e0f2f155 MW |
210 | |
211 | /* the bit at e[k-1] is 1 by definition, so start with: C := M */ | |
212 | montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */ | |
213 | /* retain scaled version for intermediate use */ | |
214 | memcpy(a_scaled, acc, key->len * sizeof(a_scaled[0])); | |
215 | ||
216 | for (j = k - 2; j > 0; --j) { | |
217 | montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */ | |
218 | ||
219 | if (is_public_exponent_bit_set(key, j)) { | |
220 | /* acc = tmp * val / R mod n */ | |
221 | montgomery_mul(key, acc, tmp, a_scaled); | |
222 | } else { | |
223 | /* e[j] == 0, copy tmp back to acc for next operation */ | |
224 | memcpy(acc, tmp, key->len * sizeof(acc[0])); | |
225 | } | |
226 | } | |
227 | ||
228 | /* the bit at e[0] is always 1 */ | |
229 | montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */ | |
230 | montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */ | |
231 | memcpy(result, acc, key->len * sizeof(result[0])); | |
19c402af SG |
232 | |
233 | /* Make sure result < mod; result is at most 1x mod too large. */ | |
234 | if (greater_equal_modulus(key, result)) | |
235 | subtract_modulus(key, result); | |
236 | ||
237 | /* Convert to bigendian byte array */ | |
238 | for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++) | |
239 | put_unaligned_be32(result[i], ptr); | |
19c402af SG |
240 | return 0; |
241 | } | |
242 | ||
243 | static int rsa_verify_key(const struct rsa_public_key *key, const uint8_t *sig, | |
646257d1 HS |
244 | const uint32_t sig_len, const uint8_t *hash, |
245 | struct checksum_algo *algo) | |
19c402af SG |
246 | { |
247 | const uint8_t *padding; | |
248 | int pad_len; | |
249 | int ret; | |
250 | ||
646257d1 | 251 | if (!key || !sig || !hash || !algo) |
19c402af SG |
252 | return -EIO; |
253 | ||
254 | if (sig_len != (key->len * sizeof(uint32_t))) { | |
255 | debug("Signature is of incorrect length %d\n", sig_len); | |
256 | return -EINVAL; | |
257 | } | |
258 | ||
646257d1 HS |
259 | debug("Checksum algorithm: %s", algo->name); |
260 | ||
19c402af SG |
261 | /* Sanity check for stack size */ |
262 | if (sig_len > RSA_MAX_SIG_BITS / 8) { | |
263 | debug("Signature length %u exceeds maximum %d\n", sig_len, | |
264 | RSA_MAX_SIG_BITS / 8); | |
265 | return -EINVAL; | |
266 | } | |
267 | ||
268 | uint32_t buf[sig_len / sizeof(uint32_t)]; | |
269 | ||
270 | memcpy(buf, sig, sig_len); | |
271 | ||
272 | ret = pow_mod(key, buf); | |
273 | if (ret) | |
274 | return ret; | |
275 | ||
646257d1 | 276 | padding = algo->rsa_padding; |
db1b5f3d | 277 | pad_len = algo->pad_len - algo->checksum_len; |
19c402af SG |
278 | |
279 | /* Check pkcs1.5 padding bytes. */ | |
280 | if (memcmp(buf, padding, pad_len)) { | |
281 | debug("In RSAVerify(): Padding check failed!\n"); | |
282 | return -EINVAL; | |
283 | } | |
284 | ||
285 | /* Check hash. */ | |
286 | if (memcmp((uint8_t *)buf + pad_len, hash, sig_len - pad_len)) { | |
287 | debug("In RSAVerify(): Hash check failed!\n"); | |
288 | return -EACCES; | |
289 | } | |
290 | ||
291 | return 0; | |
292 | } | |
293 | ||
294 | static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len) | |
295 | { | |
296 | int i; | |
297 | ||
298 | for (i = 0; i < len; i++) | |
299 | dst[i] = fdt32_to_cpu(src[len - 1 - i]); | |
300 | } | |
301 | ||
302 | static int rsa_verify_with_keynode(struct image_sign_info *info, | |
303 | const void *hash, uint8_t *sig, uint sig_len, int node) | |
304 | { | |
305 | const void *blob = info->fdt_blob; | |
306 | struct rsa_public_key key; | |
307 | const void *modulus, *rr; | |
e0f2f155 MW |
308 | const uint64_t *public_exponent; |
309 | int length; | |
19c402af SG |
310 | int ret; |
311 | ||
312 | if (node < 0) { | |
313 | debug("%s: Skipping invalid node", __func__); | |
314 | return -EBADF; | |
315 | } | |
316 | if (!fdt_getprop(blob, node, "rsa,n0-inverse", NULL)) { | |
317 | debug("%s: Missing rsa,n0-inverse", __func__); | |
318 | return -EFAULT; | |
319 | } | |
320 | key.len = fdtdec_get_int(blob, node, "rsa,num-bits", 0); | |
321 | key.n0inv = fdtdec_get_int(blob, node, "rsa,n0-inverse", 0); | |
e0f2f155 MW |
322 | public_exponent = fdt_getprop(blob, node, "rsa,exponent", &length); |
323 | if (!public_exponent || length < sizeof(*public_exponent)) | |
324 | key.exponent = RSA_DEFAULT_PUBEXP; | |
325 | else | |
326 | key.exponent = fdt64_to_cpu(*public_exponent); | |
19c402af SG |
327 | modulus = fdt_getprop(blob, node, "rsa,modulus", NULL); |
328 | rr = fdt_getprop(blob, node, "rsa,r-squared", NULL); | |
329 | if (!key.len || !modulus || !rr) { | |
330 | debug("%s: Missing RSA key info", __func__); | |
331 | return -EFAULT; | |
332 | } | |
333 | ||
334 | /* Sanity check for stack size */ | |
335 | if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) { | |
336 | debug("RSA key bits %u outside allowed range %d..%d\n", | |
337 | key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS); | |
338 | return -EFAULT; | |
339 | } | |
340 | key.len /= sizeof(uint32_t) * 8; | |
341 | uint32_t key1[key.len], key2[key.len]; | |
342 | ||
343 | key.modulus = key1; | |
344 | key.rr = key2; | |
345 | rsa_convert_big_endian(key.modulus, modulus, key.len); | |
346 | rsa_convert_big_endian(key.rr, rr, key.len); | |
347 | if (!key.modulus || !key.rr) { | |
348 | debug("%s: Out of memory", __func__); | |
349 | return -ENOMEM; | |
350 | } | |
351 | ||
352 | debug("key length %d\n", key.len); | |
646257d1 | 353 | ret = rsa_verify_key(&key, sig, sig_len, hash, info->algo->checksum); |
19c402af SG |
354 | if (ret) { |
355 | printf("%s: RSA failed to verify: %d\n", __func__, ret); | |
356 | return ret; | |
357 | } | |
358 | ||
359 | return 0; | |
360 | } | |
361 | ||
362 | int rsa_verify(struct image_sign_info *info, | |
363 | const struct image_region region[], int region_count, | |
364 | uint8_t *sig, uint sig_len) | |
365 | { | |
366 | const void *blob = info->fdt_blob; | |
646257d1 | 367 | /* Reserve memory for maximum checksum-length */ |
db1b5f3d | 368 | uint8_t hash[info->algo->checksum->pad_len]; |
19c402af SG |
369 | int ndepth, noffset; |
370 | int sig_node, node; | |
371 | char name[100]; | |
646257d1 HS |
372 | int ret; |
373 | ||
374 | /* | |
375 | * Verify that the checksum-length does not exceed the | |
376 | * rsa-signature-length | |
377 | */ | |
db1b5f3d HS |
378 | if (info->algo->checksum->checksum_len > |
379 | info->algo->checksum->pad_len) { | |
380 | debug("%s: invlaid checksum-algorithm %s for %s\n", | |
381 | __func__, info->algo->checksum->name, info->algo->name); | |
646257d1 HS |
382 | return -EINVAL; |
383 | } | |
19c402af SG |
384 | |
385 | sig_node = fdt_subnode_offset(blob, 0, FIT_SIG_NODENAME); | |
386 | if (sig_node < 0) { | |
387 | debug("%s: No signature node found\n", __func__); | |
388 | return -ENOENT; | |
389 | } | |
390 | ||
646257d1 HS |
391 | /* Calculate checksum with checksum-algorithm */ |
392 | info->algo->checksum->calculate(region, region_count, hash); | |
19c402af SG |
393 | |
394 | /* See if we must use a particular key */ | |
395 | if (info->required_keynode != -1) { | |
396 | ret = rsa_verify_with_keynode(info, hash, sig, sig_len, | |
397 | info->required_keynode); | |
398 | if (!ret) | |
399 | return ret; | |
400 | } | |
401 | ||
402 | /* Look for a key that matches our hint */ | |
403 | snprintf(name, sizeof(name), "key-%s", info->keyname); | |
404 | node = fdt_subnode_offset(blob, sig_node, name); | |
405 | ret = rsa_verify_with_keynode(info, hash, sig, sig_len, node); | |
406 | if (!ret) | |
407 | return ret; | |
408 | ||
409 | /* No luck, so try each of the keys in turn */ | |
410 | for (ndepth = 0, noffset = fdt_next_node(info->fit, sig_node, &ndepth); | |
411 | (noffset >= 0) && (ndepth > 0); | |
412 | noffset = fdt_next_node(info->fit, noffset, &ndepth)) { | |
413 | if (ndepth == 1 && noffset != node) { | |
414 | ret = rsa_verify_with_keynode(info, hash, sig, sig_len, | |
415 | noffset); | |
416 | if (!ret) | |
417 | break; | |
418 | } | |
419 | } | |
420 | ||
421 | return ret; | |
422 | } |