lib/rsa/rsa-verify.c

   1 /*
   2  * Copyright (c) 2013, Google Inc.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of
   7  * the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
  17  * MA 02111-1307 USA
  18  */
  19
  20 #include <common.h>
  21 #include <fdtdec.h>
  22 #include <rsa.h>
  23 #include <sha1.h>
  24 #include <asm/byteorder.h>
  25 #include <asm/errno.h>
  26 #include <asm/unaligned.h>
  27
  28 /**
  29  * struct rsa_public_key - holder for a public key
  30  *
  31  * An RSA public key consists of a modulus (typically called N), the inverse
  32  * and R^2, where R is 2^(# key bits).
  33  */
  34 struct rsa_public_key {
  35         uint len;               /* Length of modulus[] in number of uint32_t */
  36         uint32_t n0inv;         /* -1 / modulus[0] mod 2^32 */
  37         uint32_t *modulus;      /* modulus as little endian array */
  38         uint32_t *rr;           /* R^2 as little endian array */
  39 };
  40
  41 #define UINT64_MULT32(v, multby)  (((uint64_t)(v)) * ((uint32_t)(multby)))
  42
  43 #define RSA2048_BYTES   (2048 / 8)
  44
  45 /* This is the minimum/maximum key size we support, in bits */
  46 #define RSA_MIN_KEY_BITS        2048
  47 #define RSA_MAX_KEY_BITS        2048
  48
  49 /* This is the maximum signature length that we support, in bits */
  50 #define RSA_MAX_SIG_BITS        2048
  51
  52 static const uint8_t padding_sha1_rsa2048[RSA2048_BYTES - SHA1_SUM_LEN] = {
  53         0x00, 0x01, 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, 0xff, 0xff, 0xff, 0xff,
  68         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  69         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  70         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  71         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  72         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  73         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  74         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  75         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  76         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  77         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  78         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  79         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  80         0xff, 0xff, 0xff, 0xff, 0x00, 0x30, 0x21, 0x30,
  81         0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a,
  82         0x05, 0x00, 0x04, 0x14
  83 };
  84
  85 /**
  86  * subtract_modulus() - subtract modulus from the given value
  87  *
  88  * @key:        Key containing modulus to subtract
  89  * @num:        Number to subtract modulus from, as little endian word array
  90  */
  91 static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[])
  92 {
  93         int64_t acc = 0;
  94         uint i;
  95
  96         for (i = 0; i < key->len; i++) {
  97                 acc += (uint64_t)num[i] - key->modulus[i];
  98                 num[i] = (uint32_t)acc;
  99                 acc >>= 32;
 100         }
 101 }
 102
 103 /**
 104  * greater_equal_modulus() - check if a value is >= modulus
 105  *
 106  * @key:        Key containing modulus to check
 107  * @num:        Number to check against modulus, as little endian word array
 108  * @return 0 if num < modulus, 1 if num >= modulus
 109  */
 110 static int greater_equal_modulus(const struct rsa_public_key *key,
 111                                  uint32_t num[])
 112 {
 113         uint32_t i;
 114
 115         for (i = key->len - 1; i >= 0; i--) {
 116                 if (num[i] < key->modulus[i])
 117                         return 0;
 118                 if (num[i] > key->modulus[i])
 119                         return 1;
 120         }
 121
 122         return 1;  /* equal */
 123 }
 124
 125 /**
 126  * montgomery_mul_add_step() - Perform montgomery multiply-add step
 127  *
 128  * Operation: montgomery result[] += a * b[] / n0inv % modulus
 129  *
 130  * @key:        RSA key
 131  * @result:     Place to put result, as little endian word array
 132  * @a:          Multiplier
 133  * @b:          Multiplicand, as little endian word array
 134  */
 135 static void montgomery_mul_add_step(const struct rsa_public_key *key,
 136                 uint32_t result[], const uint32_t a, const uint32_t b[])
 137 {
 138         uint64_t acc_a, acc_b;
 139         uint32_t d0;
 140         uint i;
 141
 142         acc_a = (uint64_t)a * b[0] + result[0];
 143         d0 = (uint32_t)acc_a * key->n0inv;
 144         acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a;
 145         for (i = 1; i < key->len; i++) {
 146                 acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i];
 147                 acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] +
 148                                 (uint32_t)acc_a;
 149                 result[i - 1] = (uint32_t)acc_b;
 150         }
 151
 152         acc_a = (acc_a >> 32) + (acc_b >> 32);
 153
 154         result[i - 1] = (uint32_t)acc_a;
 155
 156         if (acc_a >> 32)
 157                 subtract_modulus(key, result);
 158 }
 159
 160 /**
 161  * montgomery_mul() - Perform montgomery mutitply
 162  *
 163  * Operation: montgomery result[] = a[] * b[] / n0inv % modulus
 164  *
 165  * @key:        RSA key
 166  * @result:     Place to put result, as little endian word array
 167  * @a:          Multiplier, as little endian word array
 168  * @b:          Multiplicand, as little endian word array
 169  */
 170 static void montgomery_mul(const struct rsa_public_key *key,
 171                 uint32_t result[], uint32_t a[], const uint32_t b[])
 172 {
 173         uint i;
 174
 175         for (i = 0; i < key->len; ++i)
 176                 result[i] = 0;
 177         for (i = 0; i < key->len; ++i)
 178                 montgomery_mul_add_step(key, result, a[i], b);
 179 }
 180
 181 /**
 182  * pow_mod() - in-place public exponentiation
 183  *
 184  * @key:        RSA key
 185  * @inout:      Big-endian word array containing value and result
 186  */
 187 static int pow_mod(const struct rsa_public_key *key, uint32_t *inout)
 188 {
 189         uint32_t *result, *ptr;
 190         uint i;
 191
 192         /* Sanity check for stack size - key->len is in 32-bit words */
 193         if (key->len > RSA_MAX_KEY_BITS / 32) {
 194                 debug("RSA key words %u exceeds maximum %d\n", key->len,
 195                       RSA_MAX_KEY_BITS / 32);
 196                 return -EINVAL;
 197         }
 198
 199         uint32_t val[key->len], acc[key->len], tmp[key->len];
 200         result = tmp;  /* Re-use location. */
 201
 202         /* Convert from big endian byte array to little endian word array. */
 203         for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--)
 204                 val[i] = get_unaligned_be32(ptr);
 205
 206         montgomery_mul(key, acc, val, key->rr);  /* axx = a * RR / R mod M */
 207         for (i = 0; i < 16; i += 2) {
 208                 montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod M */
 209                 montgomery_mul(key, acc, tmp, tmp); /* acc = tmp^2 / R mod M */
 210         }
 211         montgomery_mul(key, result, acc, val);  /* result = XX * a / R mod M */
 212
 213         /* Make sure result < mod; result is at most 1x mod too large. */
 214         if (greater_equal_modulus(key, result))
 215                 subtract_modulus(key, result);
 216
 217         /* Convert to bigendian byte array */
 218         for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++)
 219                 put_unaligned_be32(result[i], ptr);
 220
 221         return 0;
 222 }
 223
 224 static int rsa_verify_key(const struct rsa_public_key *key, const uint8_t *sig,
 225                 const uint32_t sig_len, const uint8_t *hash)
 226 {
 227         const uint8_t *padding;
 228         int pad_len;
 229         int ret;
 230
 231         if (!key || !sig || !hash)
 232                 return -EIO;
 233
 234         if (sig_len != (key->len * sizeof(uint32_t))) {
 235                 debug("Signature is of incorrect length %d\n", sig_len);
 236                 return -EINVAL;
 237         }
 238
 239         /* Sanity check for stack size */
 240         if (sig_len > RSA_MAX_SIG_BITS / 8) {
 241                 debug("Signature length %u exceeds maximum %d\n", sig_len,
 242                       RSA_MAX_SIG_BITS / 8);
 243                 return -EINVAL;
 244         }
 245
 246         uint32_t buf[sig_len / sizeof(uint32_t)];
 247
 248         memcpy(buf, sig, sig_len);
 249
 250         ret = pow_mod(key, buf);
 251         if (ret)
 252                 return ret;
 253
 254         /* Determine padding to use depending on the signature type. */
 255         padding = padding_sha1_rsa2048;
 256         pad_len = RSA2048_BYTES - SHA1_SUM_LEN;
 257
 258         /* Check pkcs1.5 padding bytes. */
 259         if (memcmp(buf, padding, pad_len)) {
 260                 debug("In RSAVerify(): Padding check failed!\n");
 261                 return -EINVAL;
 262         }
 263
 264         /* Check hash. */
 265         if (memcmp((uint8_t *)buf + pad_len, hash, sig_len - pad_len)) {
 266                 debug("In RSAVerify(): Hash check failed!\n");
 267                 return -EACCES;
 268         }
 269
 270         return 0;
 271 }
 272
 273 static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len)
 274 {
 275         int i;
 276
 277         for (i = 0; i < len; i++)
 278                 dst[i] = fdt32_to_cpu(src[len - 1 - i]);
 279 }
 280
 281 static int rsa_verify_with_keynode(struct image_sign_info *info,
 282                 const void *hash, uint8_t *sig, uint sig_len, int node)
 283 {
 284         const void *blob = info->fdt_blob;
 285         struct rsa_public_key key;
 286         const void *modulus, *rr;
 287         int ret;
 288
 289         if (node < 0) {
 290                 debug("%s: Skipping invalid node", __func__);
 291                 return -EBADF;
 292         }
 293         if (!fdt_getprop(blob, node, "rsa,n0-inverse", NULL)) {
 294                 debug("%s: Missing rsa,n0-inverse", __func__);
 295                 return -EFAULT;
 296         }
 297         key.len = fdtdec_get_int(blob, node, "rsa,num-bits", 0);
 298         key.n0inv = fdtdec_get_int(blob, node, "rsa,n0-inverse", 0);
 299         modulus = fdt_getprop(blob, node, "rsa,modulus", NULL);
 300         rr = fdt_getprop(blob, node, "rsa,r-squared", NULL);
 301         if (!key.len || !modulus || !rr) {
 302                 debug("%s: Missing RSA key info", __func__);
 303                 return -EFAULT;
 304         }
 305
 306         /* Sanity check for stack size */
 307         if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) {
 308                 debug("RSA key bits %u outside allowed range %d..%d\n",
 309                       key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS);
 310                 return -EFAULT;
 311         }
 312         key.len /= sizeof(uint32_t) * 8;
 313         uint32_t key1[key.len], key2[key.len];
 314
 315         key.modulus = key1;
 316         key.rr = key2;
 317         rsa_convert_big_endian(key.modulus, modulus, key.len);
 318         rsa_convert_big_endian(key.rr, rr, key.len);
 319         if (!key.modulus || !key.rr) {
 320                 debug("%s: Out of memory", __func__);
 321                 return -ENOMEM;
 322         }
 323
 324         debug("key length %d\n", key.len);
 325         ret = rsa_verify_key(&key, sig, sig_len, hash);
 326         if (ret) {
 327                 printf("%s: RSA failed to verify: %d\n", __func__, ret);
 328                 return ret;
 329         }
 330
 331         return 0;
 332 }
 333
 334 int rsa_verify(struct image_sign_info *info,
 335                const struct image_region region[], int region_count,
 336                uint8_t *sig, uint sig_len)
 337 {
 338         const void *blob = info->fdt_blob;
 339         uint8_t hash[SHA1_SUM_LEN];
 340         int ndepth, noffset;
 341         int sig_node, node;
 342         char name[100];
 343         sha1_context ctx;
 344         int ret, i;
 345
 346         sig_node = fdt_subnode_offset(blob, 0, FIT_SIG_NODENAME);
 347         if (sig_node < 0) {
 348                 debug("%s: No signature node found\n", __func__);
 349                 return -ENOENT;
 350         }
 351
 352         sha1_starts(&ctx);
 353         for (i = 0; i < region_count; i++)
 354                 sha1_update(&ctx, region[i].data, region[i].size);
 355         sha1_finish(&ctx, hash);
 356
 357         /* See if we must use a particular key */
 358         if (info->required_keynode != -1) {
 359                 ret = rsa_verify_with_keynode(info, hash, sig, sig_len,
 360                         info->required_keynode);
 361                 if (!ret)
 362                         return ret;
 363         }
 364
 365         /* Look for a key that matches our hint */
 366         snprintf(name, sizeof(name), "key-%s", info->keyname);
 367         node = fdt_subnode_offset(blob, sig_node, name);
 368         ret = rsa_verify_with_keynode(info, hash, sig, sig_len, node);
 369         if (!ret)
 370                 return ret;
 371
 372         /* No luck, so try each of the keys in turn */
 373         for (ndepth = 0, noffset = fdt_next_node(info->fit, sig_node, &ndepth);
 374                         (noffset >= 0) && (ndepth > 0);
 375                         noffset = fdt_next_node(info->fit, noffset, &ndepth)) {
 376                 if (ndepth == 1 && noffset != node) {
 377                         ret = rsa_verify_with_keynode(info, hash, sig, sig_len,
 378                                                       noffset);
 379                         if (!ret)
 380                                 break;
 381                 }
 382         }
 383
 384         return ret;
 385 }