• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3  * Copyright (c) 2013, Google Inc.
4  */
5 
6 #ifndef USE_HOSTCC
7 #include <common.h>
8 #include <fdtdec.h>
9 #include <asm/types.h>
10 #include <asm/byteorder.h>
11 #include <linux/errno.h>
12 #include <asm/types.h>
13 #include <asm/unaligned.h>
14 #else
15 #include "fdt_host.h"
16 #include "mkimage.h"
17 #include <fdt_support.h>
18 #endif
19 #include <u-boot/rsa.h>
20 #include <u-boot/rsa-mod-exp.h>
21 
22 #define UINT64_MULT32(v, multby)  (((uint64_t)(v)) * ((uint32_t)(multby)))
23 
24 #define get_unaligned_be32(a) fdt32_to_cpu(*(uint32_t *)a)
25 #define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_fdt32(a))
26 
27 /* Default public exponent for backward compatibility */
28 #define RSA_DEFAULT_PUBEXP	65537
29 
30 /**
31  * subtract_modulus() - subtract modulus from the given value
32  *
33  * @key:	Key containing modulus to subtract
34  * @num:	Number to subtract modulus from, as little endian word array
35  */
subtract_modulus(const struct rsa_public_key * key,uint32_t num[])36 static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[])
37 {
38 	int64_t acc = 0;
39 	uint i;
40 
41 	for (i = 0; i < key->len; i++) {
42 		acc += (uint64_t)num[i] - key->modulus[i];
43 		num[i] = (uint32_t)acc;
44 		acc >>= 32;
45 	}
46 }
47 
48 /**
49  * greater_equal_modulus() - check if a value is >= modulus
50  *
51  * @key:	Key containing modulus to check
52  * @num:	Number to check against modulus, as little endian word array
53  * @return 0 if num < modulus, 1 if num >= modulus
54  */
greater_equal_modulus(const struct rsa_public_key * key,uint32_t num[])55 static int greater_equal_modulus(const struct rsa_public_key *key,
56 				 uint32_t num[])
57 {
58 	int i;
59 
60 	for (i = (int)key->len - 1; i >= 0; i--) {
61 		if (num[i] < key->modulus[i])
62 			return 0;
63 		if (num[i] > key->modulus[i])
64 			return 1;
65 	}
66 
67 	return 1;  /* equal */
68 }
69 
70 /**
71  * montgomery_mul_add_step() - Perform montgomery multiply-add step
72  *
73  * Operation: montgomery result[] += a * b[] / n0inv % modulus
74  *
75  * @key:	RSA key
76  * @result:	Place to put result, as little endian word array
77  * @a:		Multiplier
78  * @b:		Multiplicand, as little endian word array
79  */
montgomery_mul_add_step(const struct rsa_public_key * key,uint32_t result[],const uint32_t a,const uint32_t b[])80 static void montgomery_mul_add_step(const struct rsa_public_key *key,
81 		uint32_t result[], const uint32_t a, const uint32_t b[])
82 {
83 	uint64_t acc_a, acc_b;
84 	uint32_t d0;
85 	uint i;
86 
87 	acc_a = (uint64_t)a * b[0] + result[0];
88 	d0 = (uint32_t)acc_a * key->n0inv;
89 	acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a;
90 	for (i = 1; i < key->len; i++) {
91 		acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i];
92 		acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] +
93 				(uint32_t)acc_a;
94 		result[i - 1] = (uint32_t)acc_b;
95 	}
96 
97 	acc_a = (acc_a >> 32) + (acc_b >> 32);
98 
99 	result[i - 1] = (uint32_t)acc_a;
100 
101 	if (acc_a >> 32)
102 		subtract_modulus(key, result);
103 }
104 
105 /**
106  * montgomery_mul() - Perform montgomery mutitply
107  *
108  * Operation: montgomery result[] = a[] * b[] / n0inv % modulus
109  *
110  * @key:	RSA key
111  * @result:	Place to put result, as little endian word array
112  * @a:		Multiplier, as little endian word array
113  * @b:		Multiplicand, as little endian word array
114  */
montgomery_mul(const struct rsa_public_key * key,uint32_t result[],uint32_t a[],const uint32_t b[])115 static void montgomery_mul(const struct rsa_public_key *key,
116 		uint32_t result[], uint32_t a[], const uint32_t b[])
117 {
118 	uint i;
119 
120 	for (i = 0; i < key->len; ++i)
121 		result[i] = 0;
122 	for (i = 0; i < key->len; ++i)
123 		montgomery_mul_add_step(key, result, a[i], b);
124 }
125 
126 /**
127  * num_pub_exponent_bits() - Number of bits in the public exponent
128  *
129  * @key:	RSA key
130  * @num_bits:	Storage for the number of public exponent bits
131  */
num_public_exponent_bits(const struct rsa_public_key * key,int * num_bits)132 static int num_public_exponent_bits(const struct rsa_public_key *key,
133 		int *num_bits)
134 {
135 	uint64_t exponent;
136 	int exponent_bits;
137 	const uint max_bits = (sizeof(exponent) * 8);
138 
139 	exponent = key->exponent;
140 	exponent_bits = 0;
141 
142 	if (!exponent) {
143 		*num_bits = exponent_bits;
144 		return 0;
145 	}
146 
147 	for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits)
148 		if (!(exponent >>= 1)) {
149 			*num_bits = exponent_bits;
150 			return 0;
151 		}
152 
153 	return -EINVAL;
154 }
155 
156 /**
157  * is_public_exponent_bit_set() - Check if a bit in the public exponent is set
158  *
159  * @key:	RSA key
160  * @pos:	The bit position to check
161  */
is_public_exponent_bit_set(const struct rsa_public_key * key,int pos)162 static int is_public_exponent_bit_set(const struct rsa_public_key *key,
163 		int pos)
164 {
165 	return key->exponent & (1ULL << pos);
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  */
pow_mod(const struct rsa_public_key * key,uint32_t * inout)174 static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
175 {
176 	uint32_t *result, *ptr;
177 	uint i;
178 	int j, k;
179 
180 	/* Sanity check for stack size - key->len is in 32-bit words */
181 	if (key->len > RSA_MAX_KEY_BITS / 32) {
182 		debug("RSA key words %u exceeds maximum %d\n", key->len,
183 		      RSA_MAX_KEY_BITS / 32);
184 		return -EINVAL;
185 	}
186 
187 	uint32_t val[key->len], acc[key->len], tmp[key->len];
188 	uint32_t a_scaled[key->len];
189 	result = tmp;  /* Re-use location. */
190 
191 	/* Convert from big endian byte array to little endian word array. */
192 	for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--)
193 		val[i] = get_unaligned_be32(ptr);
194 
195 	if (0 != num_public_exponent_bits(key, &k))
196 		return -EINVAL;
197 
198 	if (k < 2) {
199 		debug("Public exponent is too short (%d bits, minimum 2)\n",
200 		      k);
201 		return -EINVAL;
202 	}
203 
204 	if (!is_public_exponent_bit_set(key, 0)) {
205 		debug("LSB of RSA public exponent must be set.\n");
206 		return -EINVAL;
207 	}
208 
209 	/* the bit at e[k-1] is 1 by definition, so start with: C := M */
210 	montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */
211 	/* retain scaled version for intermediate use */
212 	memcpy(a_scaled, acc, key->len * sizeof(a_scaled[0]));
213 
214 	for (j = k - 2; j > 0; --j) {
215 		montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
216 
217 		if (is_public_exponent_bit_set(key, j)) {
218 			/* acc = tmp * val / R mod n */
219 			montgomery_mul(key, acc, tmp, a_scaled);
220 		} else {
221 			/* e[j] == 0, copy tmp back to acc for next operation */
222 			memcpy(acc, tmp, key->len * sizeof(acc[0]));
223 		}
224 	}
225 
226 	/* the bit at e[0] is always 1 */
227 	montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */
228 	montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */
229 	memcpy(result, acc, key->len * sizeof(result[0]));
230 
231 	/* Make sure result < mod; result is at most 1x mod too large. */
232 	if (greater_equal_modulus(key, result))
233 		subtract_modulus(key, result);
234 
235 	/* Convert to bigendian byte array */
236 	for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++)
237 		put_unaligned_be32(result[i], ptr);
238 	return 0;
239 }
240 
rsa_convert_big_endian(uint32_t * dst,const uint32_t * src,int len)241 static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len)
242 {
243 	int i;
244 
245 	for (i = 0; i < len; i++)
246 		dst[i] = fdt32_to_cpu(src[len - 1 - i]);
247 }
248 
rsa_mod_exp_sw(const uint8_t * sig,uint32_t sig_len,struct key_prop * prop,uint8_t * out)249 int rsa_mod_exp_sw(const uint8_t *sig, uint32_t sig_len,
250 		struct key_prop *prop, uint8_t *out)
251 {
252 	struct rsa_public_key key;
253 	int ret;
254 
255 	if (!prop) {
256 		debug("%s: Skipping invalid prop", __func__);
257 		return -EBADF;
258 	}
259 	key.n0inv = prop->n0inv;
260 	key.len = prop->num_bits;
261 
262 	if (!prop->public_exponent)
263 		key.exponent = RSA_DEFAULT_PUBEXP;
264 	else
265 		key.exponent =
266 			fdt64_to_cpu(*((uint64_t *)(prop->public_exponent)));
267 
268 	if (!key.len || !prop->modulus || !prop->rr) {
269 		debug("%s: Missing RSA key info", __func__);
270 		return -EFAULT;
271 	}
272 
273 	/* Sanity check for stack size */
274 	if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) {
275 		debug("RSA key bits %u outside allowed range %d..%d\n",
276 		      key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS);
277 		return -EFAULT;
278 	}
279 	key.len /= sizeof(uint32_t) * 8;
280 	uint32_t key1[key.len], key2[key.len];
281 
282 	key.modulus = key1;
283 	key.rr = key2;
284 	rsa_convert_big_endian(key.modulus, (uint32_t *)prop->modulus, key.len);
285 	rsa_convert_big_endian(key.rr, (uint32_t *)prop->rr, key.len);
286 	if (!key.modulus || !key.rr) {
287 		debug("%s: Out of memory", __func__);
288 		return -ENOMEM;
289 	}
290 
291 	uint32_t buf[sig_len / sizeof(uint32_t)];
292 
293 	memcpy(buf, sig, sig_len);
294 
295 	ret = pow_mod(&key, buf);
296 	if (ret)
297 		return ret;
298 
299 	memcpy(out, buf, sig_len);
300 
301 	return 0;
302 }
303