rsa-verify.c 11 KB

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