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