lib/libavb/avb_rsa.c

   1 // SPDX-License-Identifier: MIT OR BSD-3-Clause
   2 /*
   3  * Copyright (C) 2016 The Android Open Source Project
   4  */
   5
   6 /* Implementation of RSA signature verification which uses a pre-processed
   7  * key for computation. The code extends libmincrypt RSA verification code to
   8  * support multiple RSA key lengths and hash digest algorithms.
   9  */
  10
  11 #include "avb_rsa.h"
  12 #include "avb_sha.h"
  13 #include "avb_util.h"
  14 #include "avb_vbmeta_image.h"
  15 #include <malloc.h>
  16
  17 typedef struct IAvbKey {
  18   unsigned int len; /* Length of n[] in number of uint32_t */
  19   uint32_t n0inv;   /* -1 / n[0] mod 2^32 */
  20   uint32_t* n;      /* modulus as array (host-byte order) */
  21   uint32_t* rr;     /* R^2 as array (host-byte order) */
  22 } IAvbKey;
  23
  24 static IAvbKey* iavb_parse_key_data(const uint8_t* data, size_t length) {
  25   AvbRSAPublicKeyHeader h;
  26   IAvbKey* key = NULL;
  27   size_t expected_length;
  28   unsigned int i;
  29   const uint8_t* n;
  30   const uint8_t* rr;
  31
  32   if (!avb_rsa_public_key_header_validate_and_byteswap(
  33           (const AvbRSAPublicKeyHeader*)data, &h)) {
  34     avb_error("Invalid key.\n");
  35     goto fail;
  36   }
  37
  38   if (!(h.key_num_bits == 2048 || h.key_num_bits == 4096 ||
  39         h.key_num_bits == 8192)) {
  40     avb_error("Unexpected key length.\n");
  41     goto fail;
  42   }
  43
  44   expected_length = sizeof(AvbRSAPublicKeyHeader) + 2 * h.key_num_bits / 8;
  45   if (length != expected_length) {
  46     avb_error("Key does not match expected length.\n");
  47     goto fail;
  48   }
  49
  50   n = data + sizeof(AvbRSAPublicKeyHeader);
  51   rr = data + sizeof(AvbRSAPublicKeyHeader) + h.key_num_bits / 8;
  52
  53   /* Store n and rr following the key header so we only have to do one
  54    * allocation.
  55    */
  56   key = (IAvbKey*)(avb_malloc(sizeof(IAvbKey) + 2 * h.key_num_bits / 8));
  57   if (key == NULL) {
  58     goto fail;
  59   }
  60
  61   key->len = h.key_num_bits / 32;
  62   key->n0inv = h.n0inv;
  63   key->n = (uint32_t*)(key + 1); /* Skip ahead sizeof(IAvbKey) bytes. */
  64   key->rr = key->n + key->len;
  65
  66   /* Crypto-code below (modpowF4() and friends) expects the key in
  67    * little-endian format (rather than the format we're storing the
  68    * key in), so convert it.
  69    */
  70   for (i = 0; i < key->len; i++) {
  71     key->n[i] = avb_be32toh(((uint32_t*)n)[key->len - i - 1]);
  72     key->rr[i] = avb_be32toh(((uint32_t*)rr)[key->len - i - 1]);
  73   }
  74   return key;
  75
  76 fail:
  77   if (key != NULL) {
  78     avb_free(key);
  79   }
  80   return NULL;
  81 }
  82
  83 static void iavb_free_parsed_key(IAvbKey* key) {
  84   avb_free(key);
  85 }
  86
  87 /* a[] -= mod */
  88 static void subM(const IAvbKey* key, uint32_t* a) {
  89   int64_t A = 0;
  90   uint32_t i;
  91   for (i = 0; i < key->len; ++i) {
  92     A += (uint64_t)a[i] - key->n[i];
  93     a[i] = (uint32_t)A;
  94     A >>= 32;
  95   }
  96 }
  97
  98 /* return a[] >= mod */
  99 static int geM(const IAvbKey* key, uint32_t* a) {
 100   uint32_t i;
 101   for (i = key->len; i;) {
 102     --i;
 103     if (a[i] < key->n[i]) {
 104       return 0;
 105     }
 106     if (a[i] > key->n[i]) {
 107       return 1;
 108     }
 109   }
 110   return 1; /* equal */
 111 }
 112
 113 /* montgomery c[] += a * b[] / R % mod */
 114 static void montMulAdd(const IAvbKey* key,
 115                        uint32_t* c,
 116                        const uint32_t a,
 117                        const uint32_t* b) {
 118   uint64_t A = (uint64_t)a * b[0] + c[0];
 119   uint32_t d0 = (uint32_t)A * key->n0inv;
 120   uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
 121   uint32_t i;
 122
 123   for (i = 1; i < key->len; ++i) {
 124     A = (A >> 32) + (uint64_t)a * b[i] + c[i];
 125     B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
 126     c[i - 1] = (uint32_t)B;
 127   }
 128
 129   A = (A >> 32) + (B >> 32);
 130
 131   c[i - 1] = (uint32_t)A;
 132
 133   if (A >> 32) {
 134     subM(key, c);
 135   }
 136 }
 137
 138 /* montgomery c[] = a[] * b[] / R % mod */
 139 static void montMul(const IAvbKey* key, uint32_t* c, uint32_t* a, uint32_t* b) {
 140   uint32_t i;
 141   for (i = 0; i < key->len; ++i) {
 142     c[i] = 0;
 143   }
 144   for (i = 0; i < key->len; ++i) {
 145     montMulAdd(key, c, a[i], b);
 146   }
 147 }
 148
 149 /* In-place public exponentiation. (65537}
 150  * Input and output big-endian byte array in inout.
 151  */
 152 static void modpowF4(const IAvbKey* key, uint8_t* inout) {
 153   uint32_t* a = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
 154   uint32_t* aR = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
 155   uint32_t* aaR = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
 156   if (a == NULL || aR == NULL || aaR == NULL) {
 157     goto out;
 158   }
 159
 160   uint32_t* aaa = aaR; /* Re-use location. */
 161   int i;
 162
 163   /* Convert from big endian byte array to little endian word array. */
 164   for (i = 0; i < (int)key->len; ++i) {
 165     uint32_t tmp = (inout[((key->len - 1 - i) * 4) + 0] << 24) |
 166                    (inout[((key->len - 1 - i) * 4) + 1] << 16) |
 167                    (inout[((key->len - 1 - i) * 4) + 2] << 8) |
 168                    (inout[((key->len - 1 - i) * 4) + 3] << 0);
 169     a[i] = tmp;
 170   }
 171
 172   montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M   */
 173   for (i = 0; i < 16; i += 2) {
 174     montMul(key, aaR, aR, aR);  /* aaR = aR * aR / R mod M */
 175     montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */
 176   }
 177   montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */
 178
 179   /* Make sure aaa < mod; aaa is at most 1x mod too large. */
 180   if (geM(key, aaa)) {
 181     subM(key, aaa);
 182   }
 183
 184   /* Convert to bigendian byte array */
 185   for (i = (int)key->len - 1; i >= 0; --i) {
 186     uint32_t tmp = aaa[i];
 187     *inout++ = (uint8_t)(tmp >> 24);
 188     *inout++ = (uint8_t)(tmp >> 16);
 189     *inout++ = (uint8_t)(tmp >> 8);
 190     *inout++ = (uint8_t)(tmp >> 0);
 191   }
 192
 193 out:
 194   if (a != NULL) {
 195     avb_free(a);
 196   }
 197   if (aR != NULL) {
 198     avb_free(aR);
 199   }
 200   if (aaR != NULL) {
 201     avb_free(aaR);
 202   }
 203 }
 204
 205 /* Verify a RSA PKCS1.5 signature against an expected hash.
 206  * Returns false on failure, true on success.
 207  */
 208 bool avb_rsa_verify(const uint8_t* key,
 209                     size_t key_num_bytes,
 210                     const uint8_t* sig,
 211                     size_t sig_num_bytes,
 212                     const uint8_t* hash,
 213                     size_t hash_num_bytes,
 214                     const uint8_t* padding,
 215                     size_t padding_num_bytes) {
 216   uint8_t* buf = NULL;
 217   IAvbKey* parsed_key = NULL;
 218   bool success = false;
 219
 220   if (key == NULL || sig == NULL || hash == NULL || padding == NULL) {
 221     avb_error("Invalid input.\n");
 222     goto out;
 223   }
 224
 225   parsed_key = iavb_parse_key_data(key, key_num_bytes);
 226   if (parsed_key == NULL) {
 227     avb_error("Error parsing key.\n");
 228     goto out;
 229   }
 230
 231   if (sig_num_bytes != (parsed_key->len * sizeof(uint32_t))) {
 232     avb_error("Signature length does not match key length.\n");
 233     goto out;
 234   }
 235
 236   if (padding_num_bytes != sig_num_bytes - hash_num_bytes) {
 237     avb_error("Padding length does not match hash and signature lengths.\n");
 238     goto out;
 239   }
 240
 241   buf = (uint8_t*)avb_malloc(sig_num_bytes);
 242   if (buf == NULL) {
 243     avb_error("Error allocating memory.\n");
 244     goto out;
 245   }
 246   avb_memcpy(buf, sig, sig_num_bytes);
 247
 248   modpowF4(parsed_key, buf);
 249
 250   /* Check padding bytes.
 251    *
 252    * Even though there are probably no timing issues here, we use
 253    * avb_safe_memcmp() just to be on the safe side.
 254    */
 255   if (avb_safe_memcmp(buf, padding, padding_num_bytes)) {
 256     avb_error("Padding check failed.\n");
 257     goto out;
 258   }
 259
 260   /* Check hash. */
 261   if (avb_safe_memcmp(buf + padding_num_bytes, hash, hash_num_bytes)) {
 262     avb_error("Hash check failed.\n");
 263     goto out;
 264   }
 265
 266   success = true;
 267
 268 out:
 269   if (parsed_key != NULL) {
 270     iavb_free_parsed_key(parsed_key);
 271   }
 272   if (buf != NULL) {
 273     avb_free(buf);
 274   }
 275   return success;
 276 }