lib/rsa/rsa-verify.c

   1 /*
   2  * Copyright (c) 2013, Google Inc.
   3  *
   4  * SPDX-License-Identifier:     GPL-2.0+
   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 }