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