]>
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 | ||
7 | #include <common.h> | |
8 | #include <fdtdec.h> | |
9 | #include <rsa.h> | |
10 | #include <sha1.h> | |
11 | #include <asm/byteorder.h> | |
12 | #include <asm/errno.h> | |
13 | #include <asm/unaligned.h> | |
14 | ||
15 | /** | |
16 | * struct rsa_public_key - holder for a public key | |
17 | * | |
18 | * An RSA public key consists of a modulus (typically called N), the inverse | |
19 | * and R^2, where R is 2^(# key bits). | |
20 | */ | |
21 | struct rsa_public_key { | |
22 | uint len; /* Length of modulus[] in number of uint32_t */ | |
23 | uint32_t n0inv; /* -1 / modulus[0] mod 2^32 */ | |
24 | uint32_t *modulus; /* modulus as little endian array */ | |
25 | uint32_t *rr; /* R^2 as little endian array */ | |
26 | }; | |
27 | ||
28 | #define UINT64_MULT32(v, multby) (((uint64_t)(v)) * ((uint32_t)(multby))) | |
29 | ||
30 | #define RSA2048_BYTES (2048 / 8) | |
31 | ||
32 | /* This is the minimum/maximum key size we support, in bits */ | |
33 | #define RSA_MIN_KEY_BITS 2048 | |
34 | #define RSA_MAX_KEY_BITS 2048 | |
35 | ||
36 | /* This is the maximum signature length that we support, in bits */ | |
37 | #define RSA_MAX_SIG_BITS 2048 | |
38 | ||
39 | static const uint8_t padding_sha1_rsa2048[RSA2048_BYTES - SHA1_SUM_LEN] = { | |
40 | 0x00, 0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
41 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
42 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
43 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
44 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
45 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
46 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
47 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
48 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
49 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
50 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
51 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
52 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
53 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
54 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
55 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
56 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
57 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
58 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
59 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
60 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
61 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
62 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
63 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
64 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
65 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
66 | 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, | |
67 | 0xff, 0xff, 0xff, 0xff, 0x00, 0x30, 0x21, 0x30, | |
68 | 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, | |
69 | 0x05, 0x00, 0x04, 0x14 | |
70 | }; | |
71 | ||
72 | /** | |
73 | * subtract_modulus() - subtract modulus from the given value | |
74 | * | |
75 | * @key: Key containing modulus to subtract | |
76 | * @num: Number to subtract modulus from, as little endian word array | |
77 | */ | |
78 | static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[]) | |
79 | { | |
80 | int64_t acc = 0; | |
81 | uint i; | |
82 | ||
83 | for (i = 0; i < key->len; i++) { | |
84 | acc += (uint64_t)num[i] - key->modulus[i]; | |
85 | num[i] = (uint32_t)acc; | |
86 | acc >>= 32; | |
87 | } | |
88 | } | |
89 | ||
90 | /** | |
91 | * greater_equal_modulus() - check if a value is >= modulus | |
92 | * | |
93 | * @key: Key containing modulus to check | |
94 | * @num: Number to check against modulus, as little endian word array | |
95 | * @return 0 if num < modulus, 1 if num >= modulus | |
96 | */ | |
97 | static int greater_equal_modulus(const struct rsa_public_key *key, | |
98 | uint32_t num[]) | |
99 | { | |
100 | uint32_t i; | |
101 | ||
102 | for (i = key->len - 1; i >= 0; i--) { | |
103 | if (num[i] < key->modulus[i]) | |
104 | return 0; | |
105 | if (num[i] > key->modulus[i]) | |
106 | return 1; | |
107 | } | |
108 | ||
109 | return 1; /* equal */ | |
110 | } | |
111 | ||
112 | /** | |
113 | * montgomery_mul_add_step() - Perform montgomery multiply-add step | |
114 | * | |
115 | * Operation: montgomery result[] += a * b[] / n0inv % modulus | |
116 | * | |
117 | * @key: RSA key | |
118 | * @result: Place to put result, as little endian word array | |
119 | * @a: Multiplier | |
120 | * @b: Multiplicand, as little endian word array | |
121 | */ | |
122 | static void montgomery_mul_add_step(const struct rsa_public_key *key, | |
123 | uint32_t result[], const uint32_t a, const uint32_t b[]) | |
124 | { | |
125 | uint64_t acc_a, acc_b; | |
126 | uint32_t d0; | |
127 | uint i; | |
128 | ||
129 | acc_a = (uint64_t)a * b[0] + result[0]; | |
130 | d0 = (uint32_t)acc_a * key->n0inv; | |
131 | acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a; | |
132 | for (i = 1; i < key->len; i++) { | |
133 | acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i]; | |
134 | acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] + | |
135 | (uint32_t)acc_a; | |
136 | result[i - 1] = (uint32_t)acc_b; | |
137 | } | |
138 | ||
139 | acc_a = (acc_a >> 32) + (acc_b >> 32); | |
140 | ||
141 | result[i - 1] = (uint32_t)acc_a; | |
142 | ||
143 | if (acc_a >> 32) | |
144 | subtract_modulus(key, result); | |
145 | } | |
146 | ||
147 | /** | |
148 | * montgomery_mul() - Perform montgomery mutitply | |
149 | * | |
150 | * Operation: montgomery result[] = a[] * b[] / n0inv % modulus | |
151 | * | |
152 | * @key: RSA key | |
153 | * @result: Place to put result, as little endian word array | |
154 | * @a: Multiplier, as little endian word array | |
155 | * @b: Multiplicand, as little endian word array | |
156 | */ | |
157 | static void montgomery_mul(const struct rsa_public_key *key, | |
158 | uint32_t result[], uint32_t a[], const uint32_t b[]) | |
159 | { | |
160 | uint i; | |
161 | ||
162 | for (i = 0; i < key->len; ++i) | |
163 | result[i] = 0; | |
164 | for (i = 0; i < key->len; ++i) | |
165 | montgomery_mul_add_step(key, result, a[i], b); | |
166 | } | |
167 | ||
168 | /** | |
169 | * pow_mod() - in-place public exponentiation | |
170 | * | |
171 | * @key: RSA key | |
172 | * @inout: Big-endian word array containing value and result | |
173 | */ | |
174 | static int pow_mod(const struct rsa_public_key *key, uint32_t *inout) | |
175 | { | |
176 | uint32_t *result, *ptr; | |
177 | uint i; | |
178 | ||
179 | /* Sanity check for stack size - key->len is in 32-bit words */ | |
180 | if (key->len > RSA_MAX_KEY_BITS / 32) { | |
181 | debug("RSA key words %u exceeds maximum %d\n", key->len, | |
182 | RSA_MAX_KEY_BITS / 32); | |
183 | return -EINVAL; | |
184 | } | |
185 | ||
186 | uint32_t val[key->len], acc[key->len], tmp[key->len]; | |
187 | result = tmp; /* Re-use location. */ | |
188 | ||
189 | /* Convert from big endian byte array to little endian word array. */ | |
190 | for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--) | |
191 | val[i] = get_unaligned_be32(ptr); | |
192 | ||
193 | montgomery_mul(key, acc, val, key->rr); /* axx = a * RR / R mod M */ | |
194 | for (i = 0; i < 16; i += 2) { | |
195 | montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod M */ | |
196 | montgomery_mul(key, acc, tmp, tmp); /* acc = tmp^2 / R mod M */ | |
197 | } | |
198 | montgomery_mul(key, result, acc, val); /* result = XX * a / R mod M */ | |
199 | ||
200 | /* Make sure result < mod; result is at most 1x mod too large. */ | |
201 | if (greater_equal_modulus(key, result)) | |
202 | subtract_modulus(key, result); | |
203 | ||
204 | /* Convert to bigendian byte array */ | |
205 | for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++) | |
206 | put_unaligned_be32(result[i], ptr); | |
207 | ||
208 | return 0; | |
209 | } | |
210 | ||
211 | static int rsa_verify_key(const struct rsa_public_key *key, const uint8_t *sig, | |
212 | const uint32_t sig_len, const uint8_t *hash) | |
213 | { | |
214 | const uint8_t *padding; | |
215 | int pad_len; | |
216 | int ret; | |
217 | ||
218 | if (!key || !sig || !hash) | |
219 | return -EIO; | |
220 | ||
221 | if (sig_len != (key->len * sizeof(uint32_t))) { | |
222 | debug("Signature is of incorrect length %d\n", sig_len); | |
223 | return -EINVAL; | |
224 | } | |
225 | ||
226 | /* Sanity check for stack size */ | |
227 | if (sig_len > RSA_MAX_SIG_BITS / 8) { | |
228 | debug("Signature length %u exceeds maximum %d\n", sig_len, | |
229 | RSA_MAX_SIG_BITS / 8); | |
230 | return -EINVAL; | |
231 | } | |
232 | ||
233 | uint32_t buf[sig_len / sizeof(uint32_t)]; | |
234 | ||
235 | memcpy(buf, sig, sig_len); | |
236 | ||
237 | ret = pow_mod(key, buf); | |
238 | if (ret) | |
239 | return ret; | |
240 | ||
241 | /* Determine padding to use depending on the signature type. */ | |
242 | padding = padding_sha1_rsa2048; | |
243 | pad_len = RSA2048_BYTES - SHA1_SUM_LEN; | |
244 | ||
245 | /* Check pkcs1.5 padding bytes. */ | |
246 | if (memcmp(buf, padding, pad_len)) { | |
247 | debug("In RSAVerify(): Padding check failed!\n"); | |
248 | return -EINVAL; | |
249 | } | |
250 | ||
251 | /* Check hash. */ | |
252 | if (memcmp((uint8_t *)buf + pad_len, hash, sig_len - pad_len)) { | |
253 | debug("In RSAVerify(): Hash check failed!\n"); | |
254 | return -EACCES; | |
255 | } | |
256 | ||
257 | return 0; | |
258 | } | |
259 | ||
260 | static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len) | |
261 | { | |
262 | int i; | |
263 | ||
264 | for (i = 0; i < len; i++) | |
265 | dst[i] = fdt32_to_cpu(src[len - 1 - i]); | |
266 | } | |
267 | ||
268 | static int rsa_verify_with_keynode(struct image_sign_info *info, | |
269 | const void *hash, uint8_t *sig, uint sig_len, int node) | |
270 | { | |
271 | const void *blob = info->fdt_blob; | |
272 | struct rsa_public_key key; | |
273 | const void *modulus, *rr; | |
274 | int ret; | |
275 | ||
276 | if (node < 0) { | |
277 | debug("%s: Skipping invalid node", __func__); | |
278 | return -EBADF; | |
279 | } | |
280 | if (!fdt_getprop(blob, node, "rsa,n0-inverse", NULL)) { | |
281 | debug("%s: Missing rsa,n0-inverse", __func__); | |
282 | return -EFAULT; | |
283 | } | |
284 | key.len = fdtdec_get_int(blob, node, "rsa,num-bits", 0); | |
285 | key.n0inv = fdtdec_get_int(blob, node, "rsa,n0-inverse", 0); | |
286 | modulus = fdt_getprop(blob, node, "rsa,modulus", NULL); | |
287 | rr = fdt_getprop(blob, node, "rsa,r-squared", NULL); | |
288 | if (!key.len || !modulus || !rr) { | |
289 | debug("%s: Missing RSA key info", __func__); | |
290 | return -EFAULT; | |
291 | } | |
292 | ||
293 | /* Sanity check for stack size */ | |
294 | if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) { | |
295 | debug("RSA key bits %u outside allowed range %d..%d\n", | |
296 | key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS); | |
297 | return -EFAULT; | |
298 | } | |
299 | key.len /= sizeof(uint32_t) * 8; | |
300 | uint32_t key1[key.len], key2[key.len]; | |
301 | ||
302 | key.modulus = key1; | |
303 | key.rr = key2; | |
304 | rsa_convert_big_endian(key.modulus, modulus, key.len); | |
305 | rsa_convert_big_endian(key.rr, rr, key.len); | |
306 | if (!key.modulus || !key.rr) { | |
307 | debug("%s: Out of memory", __func__); | |
308 | return -ENOMEM; | |
309 | } | |
310 | ||
311 | debug("key length %d\n", key.len); | |
312 | ret = rsa_verify_key(&key, sig, sig_len, hash); | |
313 | if (ret) { | |
314 | printf("%s: RSA failed to verify: %d\n", __func__, ret); | |
315 | return ret; | |
316 | } | |
317 | ||
318 | return 0; | |
319 | } | |
320 | ||
321 | int rsa_verify(struct image_sign_info *info, | |
322 | const struct image_region region[], int region_count, | |
323 | uint8_t *sig, uint sig_len) | |
324 | { | |
325 | const void *blob = info->fdt_blob; | |
326 | uint8_t hash[SHA1_SUM_LEN]; | |
327 | int ndepth, noffset; | |
328 | int sig_node, node; | |
329 | char name[100]; | |
330 | sha1_context ctx; | |
331 | int ret, i; | |
332 | ||
333 | sig_node = fdt_subnode_offset(blob, 0, FIT_SIG_NODENAME); | |
334 | if (sig_node < 0) { | |
335 | debug("%s: No signature node found\n", __func__); | |
336 | return -ENOENT; | |
337 | } | |
338 | ||
339 | sha1_starts(&ctx); | |
340 | for (i = 0; i < region_count; i++) | |
341 | sha1_update(&ctx, region[i].data, region[i].size); | |
342 | sha1_finish(&ctx, hash); | |
343 | ||
344 | /* See if we must use a particular key */ | |
345 | if (info->required_keynode != -1) { | |
346 | ret = rsa_verify_with_keynode(info, hash, sig, sig_len, | |
347 | info->required_keynode); | |
348 | if (!ret) | |
349 | return ret; | |
350 | } | |
351 | ||
352 | /* Look for a key that matches our hint */ | |
353 | snprintf(name, sizeof(name), "key-%s", info->keyname); | |
354 | node = fdt_subnode_offset(blob, sig_node, name); | |
355 | ret = rsa_verify_with_keynode(info, hash, sig, sig_len, node); | |
356 | if (!ret) | |
357 | return ret; | |
358 | ||
359 | /* No luck, so try each of the keys in turn */ | |
360 | for (ndepth = 0, noffset = fdt_next_node(info->fit, sig_node, &ndepth); | |
361 | (noffset >= 0) && (ndepth > 0); | |
362 | noffset = fdt_next_node(info->fit, noffset, &ndepth)) { | |
363 | if (ndepth == 1 && noffset != node) { | |
364 | ret = rsa_verify_with_keynode(info, hash, sig, sig_len, | |
365 | noffset); | |
366 | if (!ret) | |
367 | break; | |
368 | } | |
369 | } | |
370 | ||
371 | return ret; | |
372 | } |