David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2016 The Android Open Source Project |
| 3 | * |
David Zeuthen | c612e2e | 2016-09-16 16:44:08 -0400 | [diff] [blame] | 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: |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 11 | * |
David Zeuthen | c612e2e | 2016-09-16 16:44:08 -0400 | [diff] [blame] | 12 | * The above copyright notice and this permission notice shall be |
| 13 | * included in all copies or substantial portions of the Software. |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 14 | * |
David Zeuthen | c612e2e | 2016-09-16 16:44:08 -0400 | [diff] [blame] | 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. |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 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 Key { |
| 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 | } Key; |
| 46 | |
| 47 | Key* parse_key_data(const uint8_t* data, size_t length) { |
| 48 | AvbRSAPublicKeyHeader h; |
| 49 | Key* 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 = (Key*)(avb_malloc(sizeof(Key) + 2 * h.key_num_bits / 8)); |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 80 | if (key == NULL) { |
| 81 | goto fail; |
| 82 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 83 | |
| 84 | key->len = h.key_num_bits / 32; |
| 85 | key->n0inv = h.n0inv; |
| 86 | key->n = (uint32_t*)(key + 1); /* Skip ahead sizeof(Key) 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: |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 100 | if (key != NULL) { |
| 101 | avb_free(key); |
| 102 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 103 | return NULL; |
| 104 | } |
| 105 | |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 106 | void free_parsed_key(Key* key) { |
| 107 | avb_free(key); |
| 108 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 109 | |
| 110 | /* a[] -= mod */ |
| 111 | static void subM(const Key* 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 Key* key, uint32_t* a) { |
| 123 | uint32_t i; |
| 124 | for (i = key->len; i;) { |
| 125 | --i; |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 126 | if (a[i] < key->n[i]) { |
| 127 | return 0; |
| 128 | } |
| 129 | if (a[i] > key->n[i]) { |
| 130 | return 1; |
| 131 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 132 | } |
| 133 | return 1; /* equal */ |
| 134 | } |
| 135 | |
| 136 | /* montgomery c[] += a * b[] / R % mod */ |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 137 | static void montMulAdd(const Key* key, |
| 138 | uint32_t* c, |
| 139 | const uint32_t a, |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 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 Key* 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 Key* 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)); |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 179 | if (a == NULL || aR == NULL || aaR == NULL) { |
| 180 | goto out; |
| 181 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 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: |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 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 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 226 | } |
| 227 | |
| 228 | /* Verify a RSA PKCS1.5 signature against an expected hash. |
| 229 | * Returns false on failure, true on success. |
| 230 | */ |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 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) { |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 239 | uint8_t* buf = NULL; |
| 240 | Key* 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 = 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: |
David Zeuthen | 4b6a634 | 2017-01-03 15:19:56 -0500 | [diff] [blame] | 292 | if (parsed_key != NULL) { |
| 293 | free_parsed_key(parsed_key); |
| 294 | } |
| 295 | if (buf != NULL) { |
| 296 | avb_free(buf); |
| 297 | } |
David Zeuthen | 21e9526 | 2016-07-27 17:58:40 -0400 | [diff] [blame] | 298 | return success; |
| 299 | } |