1 /* Copyright (c) 2011 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 /* Implementation of RSA signature verification which uses a pre-processed 7 * key for computation. The code extends Android's RSA verification code to 8 * support multiple RSA key lengths and hash digest algorithms. 9 */ 10 11 #include "sysincludes.h" 12 13 #include "cryptolib.h" 14 #include "vboot_api.h" 15 #include "utility.h" 16 17 /* a[] -= mod */ 18 static void subM(const RSAPublicKey *key, uint32_t *a) { 19 int64_t A = 0; 20 uint32_t i; 21 for (i = 0; i < key->len; ++i) { 22 A += (uint64_t)a[i] - key->n[i]; 23 a[i] = (uint32_t)A; 24 A >>= 32; 25 } 26 } 27 28 /* return a[] >= mod */ 29 static int geM(const RSAPublicKey *key, uint32_t *a) { 30 uint32_t i; 31 for (i = key->len; i;) { 32 --i; 33 if (a[i] < key->n[i]) return 0; 34 if (a[i] > key->n[i]) return 1; 35 } 36 return 1; /* equal */ 37 } 38 39 /* montgomery c[] += a * b[] / R % mod */ 40 static void montMulAdd(const RSAPublicKey *key, 41 uint32_t* c, 42 const uint32_t a, 43 const uint32_t* b) { 44 uint64_t A = (uint64_t)a * b[0] + c[0]; 45 uint32_t d0 = (uint32_t)A * key->n0inv; 46 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; 47 uint32_t i; 48 49 for (i = 1; i < key->len; ++i) { 50 A = (A >> 32) + (uint64_t)a * b[i] + c[i]; 51 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; 52 c[i - 1] = (uint32_t)B; 53 } 54 55 A = (A >> 32) + (B >> 32); 56 57 c[i - 1] = (uint32_t)A; 58 59 if (A >> 32) { 60 subM(key, c); 61 } 62 } 63 64 /* montgomery c[] = a[] * b[] / R % mod */ 65 static void montMul(const RSAPublicKey *key, 66 uint32_t* c, 67 uint32_t* a, 68 uint32_t* b) { 69 uint32_t i; 70 for (i = 0; i < key->len; ++i) { 71 c[i] = 0; 72 } 73 for (i = 0; i < key->len; ++i) { 74 montMulAdd(key, c, a[i], b); 75 } 76 } 77 78 /* In-place public exponentiation. (65537} 79 * Input and output big-endian byte array in inout. 80 */ 81 static void modpowF4(const RSAPublicKey *key, 82 uint8_t* inout) { 83 uint32_t* a = (uint32_t*) VbExMalloc(key->len * sizeof(uint32_t)); 84 uint32_t* aR = (uint32_t*) VbExMalloc(key->len * sizeof(uint32_t)); 85 uint32_t* aaR = (uint32_t*) VbExMalloc(key->len * sizeof(uint32_t)); 86 87 uint32_t* aaa = aaR; /* Re-use location. */ 88 int i; 89 90 /* Convert from big endian byte array to little endian word array. */ 91 for (i = 0; i < (int)key->len; ++i) { 92 uint32_t tmp = 93 (inout[((key->len - 1 - i) * 4) + 0] << 24) | 94 (inout[((key->len - 1 - i) * 4) + 1] << 16) | 95 (inout[((key->len - 1 - i) * 4) + 2] << 8) | 96 (inout[((key->len - 1 - i) * 4) + 3] << 0); 97 a[i] = tmp; 98 } 99 100 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ 101 for (i = 0; i < 16; i+=2) { 102 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ 103 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ 104 } 105 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ 106 107 108 /* Make sure aaa < mod; aaa is at most 1x mod too large. */ 109 if (geM(key, aaa)) { 110 subM(key, aaa); 111 } 112 113 /* Convert to bigendian byte array */ 114 for (i = (int)key->len - 1; i >= 0; --i) { 115 uint32_t tmp = aaa[i]; 116 *inout++ = (uint8_t)(tmp >> 24); 117 *inout++ = (uint8_t)(tmp >> 16); 118 *inout++ = (uint8_t)(tmp >> 8); 119 *inout++ = (uint8_t)(tmp >> 0); 120 } 121 122 VbExFree(a); 123 VbExFree(aR); 124 VbExFree(aaR); 125 } 126 127 /* Verify a RSA PKCS1.5 signature against an expected hash. 128 * Returns 0 on failure, 1 on success. 129 */ 130 int RSAVerify(const RSAPublicKey *key, 131 const uint8_t *sig, 132 const uint32_t sig_len, 133 const uint8_t sig_type, 134 const uint8_t *hash) { 135 uint8_t* buf; 136 const uint8_t* padding; 137 int padding_len; 138 int success = 1; 139 140 if (!key || !sig || !hash) 141 return 0; 142 143 if (sig_len != (key->len * sizeof(uint32_t))) { 144 VBDEBUG(("Signature is of incorrect length!\n")); 145 return 0; 146 } 147 148 if (sig_type >= kNumAlgorithms) { 149 VBDEBUG(("Invalid signature type!\n")); 150 return 0; 151 } 152 153 if (key->len != siglen_map[sig_type] / sizeof(uint32_t)) { 154 VBDEBUG(("Wrong key passed in!\n")); 155 return 0; 156 } 157 158 buf = (uint8_t*) VbExMalloc(sig_len); 159 if (!buf) 160 return 0; 161 Memcpy(buf, sig, sig_len); 162 163 modpowF4(key, buf); 164 165 /* Determine padding to use depending on the signature type. */ 166 padding = padding_map[sig_type]; 167 padding_len = padding_size_map[sig_type]; 168 169 /* Even though there are probably no timing issues here, we use 170 * SafeMemcmp() just to be on the safe side. */ 171 172 /* Check pkcs1.5 padding bytes. */ 173 if (SafeMemcmp(buf, padding, padding_len)) { 174 VBDEBUG(("In RSAVerify(): Padding check failed!\n")); 175 success = 0; 176 } 177 178 /* Check hash. */ 179 if (SafeMemcmp(buf + padding_len, hash, sig_len - padding_len)) { 180 VBDEBUG(("In RSAVerify(): Hash check failed!\n")); 181 success = 0; 182 } 183 VbExFree(buf); 184 185 return success; 186 } 187
