1 /* Copyright (c) 2014 The Chromium OS Authors. All rights reserved. 2 * Use of this source code is governed by a BSD-style license that can be 3 * found in the LICENSE file. 4 */ 5 6 /* 7 * Implementation of RSA signature verification which uses a pre-processed key 8 * for computation. The code extends Android's RSA verification code to support 9 * multiple RSA key lengths and hash digest algorithms. 10 */ 11 12 #include "2sysincludes.h" 13 #include "2common.h" 14 #include "2rsa.h" 15 #include "2sha.h" 16 17 /** 18 * a[] -= mod 19 */ 20 static void subM(const struct vb2_public_key *key, uint32_t *a) 21 { 22 int64_t A = 0; 23 uint32_t i; 24 for (i = 0; i < key->arrsize; ++i) { 25 A += (uint64_t)a[i] - key->n[i]; 26 a[i] = (uint32_t)A; 27 A >>= 32; 28 } 29 } 30 31 /** 32 * Return a[] >= mod 33 */ 34 int vb2_mont_ge(const struct vb2_public_key *key, uint32_t *a) 35 { 36 uint32_t i; 37 for (i = key->arrsize; i;) { 38 --i; 39 if (a[i] < key->n[i]) 40 return 0; 41 if (a[i] > key->n[i]) 42 return 1; 43 } 44 return 1; /* equal */ 45 } 46 47 /** 48 * Montgomery c[] += a * b[] / R % mod 49 */ 50 static void montMulAdd(const struct vb2_public_key *key, 51 uint32_t *c, 52 const uint32_t a, 53 const uint32_t *b) 54 { 55 uint64_t A = (uint64_t)a * b[0] + c[0]; 56 uint32_t d0 = (uint32_t)A * key->n0inv; 57 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; 58 uint32_t i; 59 60 for (i = 1; i < key->arrsize; ++i) { 61 A = (A >> 32) + (uint64_t)a * b[i] + c[i]; 62 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; 63 c[i - 1] = (uint32_t)B; 64 } 65 66 A = (A >> 32) + (B >> 32); 67 68 c[i - 1] = (uint32_t)A; 69 70 if (A >> 32) { 71 subM(key, c); 72 } 73 } 74 75 /** 76 * Montgomery c[] = a[] * b[] / R % mod 77 */ 78 static void montMul(const struct vb2_public_key *key, 79 uint32_t *c, 80 const uint32_t *a, 81 const uint32_t *b) 82 { 83 uint32_t i; 84 for (i = 0; i < key->arrsize; ++i) { 85 c[i] = 0; 86 } 87 for (i = 0; i < key->arrsize; ++i) { 88 montMulAdd(key, c, a[i], b); 89 } 90 } 91 92 /** 93 * In-place public exponentiation. (65537} 94 * 95 * @param key Key to use in signing 96 * @param inout Input and output big-endian byte array 97 * @param workbuf32 Work buffer; caller must verify this is 98 * (3 * key->arrsize) elements long. 99 */ 100 static void modpowF4(const struct vb2_public_key *key, uint8_t *inout, 101 uint32_t *workbuf32) 102 { 103 uint32_t *a = workbuf32; 104 uint32_t *aR = a + key->arrsize; 105 uint32_t *aaR = aR + key->arrsize; 106 uint32_t *aaa = aaR; /* Re-use location. */ 107 int i; 108 109 /* Convert from big endian byte array to little endian word array. */ 110 for (i = 0; i < (int)key->arrsize; ++i) { 111 uint32_t tmp = 112 (inout[((key->arrsize - 1 - i) * 4) + 0] << 24) | 113 (inout[((key->arrsize - 1 - i) * 4) + 1] << 16) | 114 (inout[((key->arrsize - 1 - i) * 4) + 2] << 8) | 115 (inout[((key->arrsize - 1 - i) * 4) + 3] << 0); 116 a[i] = tmp; 117 } 118 119 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ 120 for (i = 0; i < 16; i+=2) { 121 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ 122 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ 123 } 124 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ 125 126 127 /* Make sure aaa < mod; aaa is at most 1x mod too large. */ 128 if (vb2_mont_ge(key, aaa)) { 129 subM(key, aaa); 130 } 131 132 /* Convert to bigendian byte array */ 133 for (i = (int)key->arrsize - 1; i >= 0; --i) { 134 uint32_t tmp = aaa[i]; 135 *inout++ = (uint8_t)(tmp >> 24); 136 *inout++ = (uint8_t)(tmp >> 16); 137 *inout++ = (uint8_t)(tmp >> 8); 138 *inout++ = (uint8_t)(tmp >> 0); 139 } 140 } 141 142 143 static const uint8_t crypto_to_sig[] = { 144 VB2_SIG_RSA1024, 145 VB2_SIG_RSA1024, 146 VB2_SIG_RSA1024, 147 VB2_SIG_RSA2048, 148 VB2_SIG_RSA2048, 149 VB2_SIG_RSA2048, 150 VB2_SIG_RSA4096, 151 VB2_SIG_RSA4096, 152 VB2_SIG_RSA4096, 153 VB2_SIG_RSA8192, 154 VB2_SIG_RSA8192, 155 VB2_SIG_RSA8192, 156 }; 157 158 /** 159 * Convert vb2_crypto_algorithm to vb2_signature_algorithm. 160 * 161 * @param algorithm Crypto algorithm (vb2_crypto_algorithm) 162 * 163 * @return The signature algorithm for that crypto algorithm, or 164 * VB2_SIG_INVALID if the crypto algorithm or its corresponding signature 165 * algorithm is invalid or not supported. 166 */ 167 enum vb2_signature_algorithm vb2_crypto_to_signature(uint32_t algorithm) 168 { 169 if (algorithm < ARRAY_SIZE(crypto_to_sig)) 170 return crypto_to_sig[algorithm]; 171 else 172 return VB2_SIG_INVALID; 173 } 174 175 uint32_t vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg) 176 { 177 switch (sig_alg) { 178 case VB2_SIG_RSA1024: 179 return 1024 / 8; 180 case VB2_SIG_RSA2048: 181 return 2048 / 8; 182 case VB2_SIG_RSA4096: 183 return 4096 / 8; 184 case VB2_SIG_RSA8192: 185 return 8192 / 8; 186 default: 187 return 0; 188 } 189 } 190 191 uint32_t vb2_packed_key_size(enum vb2_signature_algorithm sig_alg) 192 { 193 uint32_t sig_size = vb2_rsa_sig_size(sig_alg); 194 195 if (!sig_size) 196 return 0; 197 198 /* 199 * Total size needed by a RSAPublicKey buffer is = 200 * 2 * key_len bytes for the n and rr arrays 201 * + sizeof len + sizeof n0inv. 202 */ 203 return 2 * sig_size + 2 * sizeof(uint32_t); 204 } 205 206 /* 207 * PKCS 1.5 padding (from the RSA PKCS#1 v2.1 standard) 208 * 209 * Depending on the RSA key size and hash function, the padding is calculated 210 * as follows: 211 * 212 * 0x00 || 0x01 || PS || 0x00 || T 213 * 214 * T: DER Encoded DigestInfo value which depends on the hash function used. 215 * 216 * SHA-1: (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H. 217 * SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H. 218 * SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H. 219 * 220 * Length(T) = 35 octets for SHA-1 221 * Length(T) = 51 octets for SHA-256 222 * Length(T) = 83 octets for SHA-512 223 * 224 * PS: octet string consisting of {Length(RSA Key) - Length(T) - 3} 0xFF 225 */ 226 static const uint8_t sha1_tail[] = { 227 0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b, 228 0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14 229 }; 230 231 static const uint8_t sha256_tail[] = { 232 0x00,0x30,0x31,0x30,0x0d,0x06,0x09,0x60, 233 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01, 234 0x05,0x00,0x04,0x20 235 }; 236 237 static const uint8_t sha512_tail[] = { 238 0x00,0x30,0x51,0x30,0x0d,0x06,0x09,0x60, 239 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03, 240 0x05,0x00,0x04,0x40 241 }; 242 243 int vb2_check_padding(const uint8_t *sig, const struct vb2_public_key *key) 244 { 245 /* Determine padding to use depending on the signature type */ 246 uint32_t sig_size = vb2_rsa_sig_size(key->sig_alg); 247 uint32_t hash_size = vb2_digest_size(key->hash_alg); 248 uint32_t pad_size = sig_size - hash_size; 249 const uint8_t *tail; 250 uint32_t tail_size; 251 int result = 0; 252 int i; 253 254 if (!sig_size || !hash_size || hash_size > sig_size) 255 return VB2_ERROR_RSA_PADDING_SIZE; 256 257 switch (key->hash_alg) { 258 case VB2_HASH_SHA1: 259 tail = sha1_tail; 260 tail_size = sizeof(sha1_tail); 261 break; 262 case VB2_HASH_SHA256: 263 tail = sha256_tail; 264 tail_size = sizeof(sha256_tail); 265 break; 266 case VB2_HASH_SHA512: 267 tail = sha512_tail; 268 tail_size = sizeof(sha512_tail); 269 break; 270 default: 271 return VB2_ERROR_RSA_PADDING_ALGORITHM; 272 } 273 274 /* First 2 bytes are always 0x00 0x01 */ 275 result |= *sig++ ^ 0x00; 276 result |= *sig++ ^ 0x01; 277 278 /* Then 0xff bytes until the tail */ 279 for (i = 0; i < pad_size - tail_size - 2; i++) 280 result |= *sig++ ^ 0xff; 281 282 /* 283 * Then the tail. Even though there are probably no timing issues 284 * here, we use vb2_safe_memcmp() just to be on the safe side. 285 */ 286 result |= vb2_safe_memcmp(sig, tail, tail_size); 287 288 return result ? VB2_ERROR_RSA_PADDING : VB2_SUCCESS; 289 } 290 291 int vb2_rsa_verify_digest(const struct vb2_public_key *key, 292 uint8_t *sig, 293 const uint8_t *digest, 294 const struct vb2_workbuf *wb) 295 { 296 struct vb2_workbuf wblocal = *wb; 297 uint32_t *workbuf32; 298 uint32_t key_bytes; 299 int sig_size; 300 int pad_size; 301 int rv; 302 303 if (!key || !sig || !digest) 304 return VB2_ERROR_RSA_VERIFY_PARAM; 305 306 sig_size = vb2_rsa_sig_size(key->sig_alg); 307 if (!sig_size) { 308 VB2_DEBUG("Invalid signature type!\n"); 309 return VB2_ERROR_RSA_VERIFY_ALGORITHM; 310 } 311 312 /* Signature length should be same as key length */ 313 key_bytes = key->arrsize * sizeof(uint32_t); 314 if (key_bytes != sig_size) { 315 VB2_DEBUG("Signature is of incorrect length!\n"); 316 return VB2_ERROR_RSA_VERIFY_SIG_LEN; 317 } 318 319 workbuf32 = vb2_workbuf_alloc(&wblocal, 3 * key_bytes); 320 if (!workbuf32) 321 return VB2_ERROR_RSA_VERIFY_WORKBUF; 322 323 modpowF4(key, sig, workbuf32); 324 325 vb2_workbuf_free(&wblocal, 3 * key_bytes); 326 327 /* 328 * Check padding. Only fail immediately if the padding size is bad. 329 * Otherwise, continue on to check the digest to reduce the risk of 330 * timing based attacks. 331 */ 332 rv = vb2_check_padding(sig, key); 333 if (rv == VB2_ERROR_RSA_PADDING_SIZE) 334 return rv; 335 336 /* 337 * Check digest. Even though there are probably no timing issues here, 338 * use vb2_safe_memcmp() just to be on the safe side. (That's also why 339 * we don't return before this check if the padding check failed.) 340 */ 341 pad_size = sig_size - vb2_digest_size(key->hash_alg); 342 if (vb2_safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) { 343 VB2_DEBUG("Digest check failed!\n"); 344 if (!rv) 345 rv = VB2_ERROR_RSA_VERIFY_DIGEST; 346 } 347 348 return rv; 349 } 350
