1 /* 2 * Copyright (c) 2013, Google Inc. 3 * 4 * SPDX-License-Identifier: GPL-2.0+ 5 */ 6 7 #ifndef USE_HOSTCC 8 #include <common.h> 9 #include <fdtdec.h> 10 #include <asm/types.h> 11 #include <asm/byteorder.h> 12 #include <asm/errno.h> 13 #include <asm/types.h> 14 #include <asm/unaligned.h> 15 #else 16 #include "fdt_host.h" 17 #include "mkimage.h" 18 #include <fdt_support.h> 19 #endif 20 #include <u-boot/rsa.h> 21 #include <u-boot/sha1.h> 22 #include <u-boot/sha256.h> 23 24 #define UINT64_MULT32(v, multby) (((uint64_t)(v)) * ((uint32_t)(multby))) 25 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 29 /* Default public exponent for backward compatibility */ 30 #define RSA_DEFAULT_PUBEXP 65537 31 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 int i; 61 62 for (i = (int)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 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 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; 180 int j, k; 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]; 190 uint32_t a_scaled[key->len]; 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 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; 209 } 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])); 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); 240 return 0; 241 } 242 243 static int rsa_verify_key(const struct rsa_public_key *key, const uint8_t *sig, 244 const uint32_t sig_len, const uint8_t *hash, 245 struct checksum_algo *algo) 246 { 247 const uint8_t *padding; 248 int pad_len; 249 int ret; 250 251 if (!key || !sig || !hash || !algo) 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 259 debug("Checksum algorithm: %s", algo->name); 260 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 276 padding = algo->rsa_padding; 277 pad_len = algo->pad_len - algo->checksum_len; 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; 308 const uint64_t *public_exponent; 309 int length; 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); 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); 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); 353 ret = rsa_verify_key(&key, sig, sig_len, hash, info->algo->checksum); 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; 367 /* Reserve memory for maximum checksum-length */ 368 uint8_t hash[info->algo->checksum->pad_len]; 369 int ndepth, noffset; 370 int sig_node, node; 371 char name[100]; 372 int ret; 373 374 /* 375 * Verify that the checksum-length does not exceed the 376 * rsa-signature-length 377 */ 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); 382 return -EINVAL; 383 } 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 391 /* Calculate checksum with checksum-algorithm */ 392 info->algo->checksum->calculate(region, region_count, hash); 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 } 423