Home | History | Annotate | Download | only in libavb 
      1 /*
      2  * Copyright (C) 2016 The Android Open Source Project
      3  *
      4  * Permission is hereby granted, free of charge, to any person
      5  * obtaining a copy of this software and associated documentation
      6  * files (the "Software"), to deal in the Software without
      7  * restriction, including without limitation the rights to use, copy,
      8  * modify, merge, publish, distribute, sublicense, and/or sell copies
      9  * of the Software, and to permit persons to whom the Software is
     10  * furnished to do so, subject to the following conditions:
     11  *
     12  * The above copyright notice and this permission notice shall be
     13  * included in all copies or substantial portions of the Software.
     14  *
     15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
     16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
     17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
     18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
     19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
     20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
     21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
     22  * SOFTWARE.
     23  */
     24 
     25 /* Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
     26  * Use of this source code is governed by a BSD-style license that can be
     27  * found in the LICENSE file.
     28  */
     29 
     30 /* Implementation of RSA signature verification which uses a pre-processed
     31  * key for computation. The code extends libmincrypt RSA verification code to
     32  * support multiple RSA key lengths and hash digest algorithms.
     33  */
     34 
     35 #include "avb_rsa.h"
     36 #include "avb_sha.h"
     37 #include "avb_util.h"
     38 #include "avb_vbmeta_image.h"
     39 
     40 typedef struct IAvbKey {
     41   unsigned int len; /* Length of n[] in number of uint32_t */
     42   uint32_t n0inv;   /* -1 / n[0] mod 2^32 */
     43   uint32_t* n;      /* modulus as array (host-byte order) */
     44   uint32_t* rr;     /* R^2 as array (host-byte order) */
     45 } IAvbKey;
     46 
     47 static IAvbKey* iavb_parse_key_data(const uint8_t* data, size_t length) {
     48   AvbRSAPublicKeyHeader h;
     49   IAvbKey* key = NULL;
     50   size_t expected_length;
     51   unsigned int i;
     52   const uint8_t* n;
     53   const uint8_t* rr;
     54 
     55   if (!avb_rsa_public_key_header_validate_and_byteswap(
     56           (const AvbRSAPublicKeyHeader*)data, &h)) {
     57     avb_error("Invalid key.\n");
     58     goto fail;
     59   }
     60 
     61   if (!(h.key_num_bits == 2048 || h.key_num_bits == 4096 ||
     62         h.key_num_bits == 8192)) {
     63     avb_error("Unexpected key length.\n");
     64     goto fail;
     65   }
     66 
     67   expected_length = sizeof(AvbRSAPublicKeyHeader) + 2 * h.key_num_bits / 8;
     68   if (length != expected_length) {
     69     avb_error("Key does not match expected length.\n");
     70     goto fail;
     71   }
     72 
     73   n = data + sizeof(AvbRSAPublicKeyHeader);
     74   rr = data + sizeof(AvbRSAPublicKeyHeader) + h.key_num_bits / 8;
     75 
     76   /* Store n and rr following the key header so we only have to do one
     77    * allocation.
     78    */
     79   key = (IAvbKey*)(avb_malloc(sizeof(IAvbKey) + 2 * h.key_num_bits / 8));
     80   if (key == NULL) {
     81     goto fail;
     82   }
     83 
     84   key->len = h.key_num_bits / 32;
     85   key->n0inv = h.n0inv;
     86   key->n = (uint32_t*)(key + 1); /* Skip ahead sizeof(IAvbKey) bytes. */
     87   key->rr = key->n + key->len;
     88 
     89   /* Crypto-code below (modpowF4() and friends) expects the key in
     90    * little-endian format (rather than the format we're storing the
     91    * key in), so convert it.
     92    */
     93   for (i = 0; i < key->len; i++) {
     94     key->n[i] = avb_be32toh(((uint32_t*)n)[key->len - i - 1]);
     95     key->rr[i] = avb_be32toh(((uint32_t*)rr)[key->len - i - 1]);
     96   }
     97   return key;
     98 
     99 fail:
    100   if (key != NULL) {
    101     avb_free(key);
    102   }
    103   return NULL;
    104 }
    105 
    106 static void iavb_free_parsed_key(IAvbKey* key) {
    107   avb_free(key);
    108 }
    109 
    110 /* a[] -= mod */
    111 static void subM(const IAvbKey* key, uint32_t* a) {
    112   int64_t A = 0;
    113   uint32_t i;
    114   for (i = 0; i < key->len; ++i) {
    115     A += (uint64_t)a[i] - key->n[i];
    116     a[i] = (uint32_t)A;
    117     A >>= 32;
    118   }
    119 }
    120 
    121 /* return a[] >= mod */
    122 static int geM(const IAvbKey* key, uint32_t* a) {
    123   uint32_t i;
    124   for (i = key->len; i;) {
    125     --i;
    126     if (a[i] < key->n[i]) {
    127       return 0;
    128     }
    129     if (a[i] > key->n[i]) {
    130       return 1;
    131     }
    132   }
    133   return 1; /* equal */
    134 }
    135 
    136 /* montgomery c[] += a * b[] / R % mod */
    137 static void montMulAdd(const IAvbKey* key,
    138                        uint32_t* c,
    139                        const uint32_t a,
    140                        const uint32_t* b) {
    141   uint64_t A = (uint64_t)a * b[0] + c[0];
    142   uint32_t d0 = (uint32_t)A * key->n0inv;
    143   uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
    144   uint32_t i;
    145 
    146   for (i = 1; i < key->len; ++i) {
    147     A = (A >> 32) + (uint64_t)a * b[i] + c[i];
    148     B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
    149     c[i - 1] = (uint32_t)B;
    150   }
    151 
    152   A = (A >> 32) + (B >> 32);
    153 
    154   c[i - 1] = (uint32_t)A;
    155 
    156   if (A >> 32) {
    157     subM(key, c);
    158   }
    159 }
    160 
    161 /* montgomery c[] = a[] * b[] / R % mod */
    162 static void montMul(const IAvbKey* key, uint32_t* c, uint32_t* a, uint32_t* b) {
    163   uint32_t i;
    164   for (i = 0; i < key->len; ++i) {
    165     c[i] = 0;
    166   }
    167   for (i = 0; i < key->len; ++i) {
    168     montMulAdd(key, c, a[i], b);
    169   }
    170 }
    171 
    172 /* In-place public exponentiation. (65537}
    173  * Input and output big-endian byte array in inout.
    174  */
    175 static void modpowF4(const IAvbKey* key, uint8_t* inout) {
    176   uint32_t* a = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
    177   uint32_t* aR = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
    178   uint32_t* aaR = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
    179   if (a == NULL || aR == NULL || aaR == NULL) {
    180     goto out;
    181   }
    182 
    183   uint32_t* aaa = aaR; /* Re-use location. */
    184   int i;
    185 
    186   /* Convert from big endian byte array to little endian word array. */
    187   for (i = 0; i < (int)key->len; ++i) {
    188     uint32_t tmp = (inout[((key->len - 1 - i) * 4) + 0] << 24) |
    189                    (inout[((key->len - 1 - i) * 4) + 1] << 16) |
    190                    (inout[((key->len - 1 - i) * 4) + 2] << 8) |
    191                    (inout[((key->len - 1 - i) * 4) + 3] << 0);
    192     a[i] = tmp;
    193   }
    194 
    195   montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M   */
    196   for (i = 0; i < 16; i += 2) {
    197     montMul(key, aaR, aR, aR);  /* aaR = aR * aR / R mod M */
    198     montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */
    199   }
    200   montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */
    201 
    202   /* Make sure aaa < mod; aaa is at most 1x mod too large. */
    203   if (geM(key, aaa)) {
    204     subM(key, aaa);
    205   }
    206 
    207   /* Convert to bigendian byte array */
    208   for (i = (int)key->len - 1; i >= 0; --i) {
    209     uint32_t tmp = aaa[i];
    210     *inout++ = (uint8_t)(tmp >> 24);
    211     *inout++ = (uint8_t)(tmp >> 16);
    212     *inout++ = (uint8_t)(tmp >> 8);
    213     *inout++ = (uint8_t)(tmp >> 0);
    214   }
    215 
    216 out:
    217   if (a != NULL) {
    218     avb_free(a);
    219   }
    220   if (aR != NULL) {
    221     avb_free(aR);
    222   }
    223   if (aaR != NULL) {
    224     avb_free(aaR);
    225   }
    226 }
    227 
    228 /* Verify a RSA PKCS1.5 signature against an expected hash.
    229  * Returns false on failure, true on success.
    230  */
    231 bool avb_rsa_verify(const uint8_t* key,
    232                     size_t key_num_bytes,
    233                     const uint8_t* sig,
    234                     size_t sig_num_bytes,
    235                     const uint8_t* hash,
    236                     size_t hash_num_bytes,
    237                     const uint8_t* padding,
    238                     size_t padding_num_bytes) {
    239   uint8_t* buf = NULL;
    240   IAvbKey* parsed_key = NULL;
    241   bool success = false;
    242 
    243   if (key == NULL || sig == NULL || hash == NULL || padding == NULL) {
    244     avb_error("Invalid input.\n");
    245     goto out;
    246   }
    247 
    248   parsed_key = iavb_parse_key_data(key, key_num_bytes);
    249   if (parsed_key == NULL) {
    250     avb_error("Error parsing key.\n");
    251     goto out;
    252   }
    253 
    254   if (sig_num_bytes != (parsed_key->len * sizeof(uint32_t))) {
    255     avb_error("Signature length does not match key length.\n");
    256     goto out;
    257   }
    258 
    259   if (padding_num_bytes != sig_num_bytes - hash_num_bytes) {
    260     avb_error("Padding length does not match hash and signature lengths.\n");
    261     goto out;
    262   }
    263 
    264   buf = (uint8_t*)avb_malloc(sig_num_bytes);
    265   if (buf == NULL) {
    266     avb_error("Error allocating memory.\n");
    267     goto out;
    268   }
    269   avb_memcpy(buf, sig, sig_num_bytes);
    270 
    271   modpowF4(parsed_key, buf);
    272 
    273   /* Check padding bytes.
    274    *
    275    * Even though there are probably no timing issues here, we use
    276    * avb_safe_memcmp() just to be on the safe side.
    277    */
    278   if (avb_safe_memcmp(buf, padding, padding_num_bytes)) {
    279     avb_error("Padding check failed.\n");
    280     goto out;
    281   }
    282 
    283   /* Check hash. */
    284   if (avb_safe_memcmp(buf + padding_num_bytes, hash, hash_num_bytes)) {
    285     avb_error("Hash check failed.\n");
    286     goto out;
    287   }
    288 
    289   success = true;
    290 
    291 out:
    292   if (parsed_key != NULL) {
    293     iavb_free_parsed_key(parsed_key);
    294   }
    295   if (buf != NULL) {
    296     avb_free(buf);
    297   }
    298   return success;
    299 }
    300