1 /* Copyright 2014 The ChromiumOS Authors
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 "2common.h"
13 #include "2rsa.h"
14 #include "2rsa_private.h"
15 #include "2sha.h"
16 #include "2sysincludes.h"
17
18 /**
19 * a[] -= mod
20 */
subM(const struct vb2_public_key * key,uint32_t * a)21 static void subM(const struct vb2_public_key *key, uint32_t *a)
22 {
23 int64_t A = 0;
24 uint32_t i;
25 for (i = 0; i < key->arrsize; ++i) {
26 A += (uint64_t)a[i] - key->n[i];
27 a[i] = (uint32_t)A;
28 A >>= 32;
29 }
30 }
31
32 /**
33 * Return a[] >= mod
34 */
vb2_mont_ge(const struct vb2_public_key * key,uint32_t * a)35 int vb2_mont_ge(const struct vb2_public_key *key, uint32_t *a)
36 {
37 uint32_t i;
38 for (i = key->arrsize; i;) {
39 --i;
40 if (a[i] < key->n[i])
41 return 0;
42 if (a[i] > key->n[i])
43 return 1;
44 }
45 return 1; /* equal */
46 }
47
48 /**
49 * Montgomery c[] += a * b[] / R % mod
50 */
montMulAdd(const struct vb2_public_key * key,uint32_t * c,const uint32_t a,const uint32_t * b)51 static void montMulAdd(const struct vb2_public_key *key,
52 uint32_t *c,
53 const uint32_t a,
54 const uint32_t *b)
55 {
56 uint64_t A = (uint64_t)a * b[0] + c[0];
57 uint32_t d0 = (uint32_t)A * key->n0inv;
58 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
59 uint32_t i;
60
61 for (i = 1; i < key->arrsize; ++i) {
62 A = (A >> 32) + (uint64_t)a * b[i] + c[i];
63 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
64 c[i - 1] = (uint32_t)B;
65 }
66
67 A = (A >> 32) + (B >> 32);
68
69 c[i - 1] = (uint32_t)A;
70
71 if (A >> 32) {
72 subM(key, c);
73 }
74 }
75
76 /**
77 * Montgomery c[] += 0 * b[] / R % mod
78 */
montMulAdd0(const struct vb2_public_key * key,uint32_t * c,const uint32_t * b)79 static void montMulAdd0(const struct vb2_public_key *key,
80 uint32_t *c,
81 const uint32_t *b)
82 {
83 uint32_t d0 = c[0] * key->n0inv;
84 uint64_t B = (uint64_t)d0 * key->n[0] + c[0];
85 uint32_t i;
86
87 for (i = 1; i < key->arrsize; ++i) {
88 B = (B >> 32) + (uint64_t)d0 * key->n[i] + c[i];
89 c[i - 1] = (uint32_t)B;
90 }
91
92 c[i - 1] = B >> 32;
93 }
94
95 /**
96 * Montgomery c[] = a[] * b[] / R % mod
97 */
montMul(const struct vb2_public_key * key,uint32_t * c,const uint32_t * a,const uint32_t * b)98 static void montMul(const struct vb2_public_key *key,
99 uint32_t *c,
100 const uint32_t *a,
101 const uint32_t *b)
102 {
103 uint32_t i;
104 for (i = 0; i < key->arrsize; ++i) {
105 c[i] = 0;
106 }
107 for (i = 0; i < key->arrsize; ++i) {
108 montMulAdd(key, c, a[i], b);
109 }
110 }
111
112 /* Montgomery c[] = a[] * 1 / R % key. */
montMul1(const struct vb2_public_key * key,uint32_t * c,const uint32_t * a)113 static void montMul1(const struct vb2_public_key *key,
114 uint32_t *c,
115 const uint32_t *a)
116 {
117 int i;
118
119 for (i = 0; i < key->arrsize; ++i)
120 c[i] = 0;
121
122 montMulAdd(key, c, 1, a);
123 for (i = 1; i < key->arrsize; ++i)
124 montMulAdd0(key, c, a);
125 }
126
127 test_mockable
vb2_modexp(const struct vb2_public_key * key,uint8_t * inout,void * workbuf,int exp)128 void vb2_modexp(const struct vb2_public_key *key, uint8_t *inout,
129 void *workbuf, int exp)
130 {
131 uint32_t *a = workbuf;
132 uint32_t *aR = a + key->arrsize;
133 uint32_t *aaR = aR + key->arrsize;
134 uint32_t *aaa = aaR; /* Re-use location. */
135 int i;
136
137 /* Convert from big endian byte array to little endian word array. */
138 for (i = 0; i < (int)key->arrsize; ++i) {
139 uint32_t tmp =
140 ((uint32_t)inout[((key->arrsize - 1 - i) * 4) + 0]
141 << 24) |
142 (inout[((key->arrsize - 1 - i) * 4) + 1] << 16) |
143 (inout[((key->arrsize - 1 - i) * 4) + 2] << 8) |
144 (inout[((key->arrsize - 1 - i) * 4) + 3] << 0);
145 a[i] = tmp;
146 }
147
148 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */
149 if (exp == 3) {
150 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
151 montMul(key, a, aaR, aR); /* a = aaR * aR / R mod M */
152 montMul1(key, aaa, a); /* aaa = a * 1 / R mod M */
153 } else {
154 /* Exponent 65537 */
155 for (i = 0; i < 16; i+=2) {
156 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
157 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */
158 }
159 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */
160 }
161
162 /* Make sure aaa < mod; aaa is at most 1x mod too large. */
163 if (vb2_mont_ge(key, aaa)) {
164 subM(key, aaa);
165 }
166
167 /* Convert to bigendian byte array */
168 for (i = (int)key->arrsize - 1; i >= 0; --i) {
169 uint32_t tmp = aaa[i];
170 *inout++ = (uint8_t)(tmp >> 24);
171 *inout++ = (uint8_t)(tmp >> 16);
172 *inout++ = (uint8_t)(tmp >> 8);
173 *inout++ = (uint8_t)(tmp >> 0);
174 }
175 }
176
vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg)177 uint32_t vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg)
178 {
179 switch (sig_alg) {
180 case VB2_SIG_RSA1024:
181 return 1024 / 8;
182 case VB2_SIG_RSA2048:
183 case VB2_SIG_RSA2048_EXP3:
184 return 2048 / 8;
185 case VB2_SIG_RSA3072_EXP3:
186 return 3072 / 8;
187 case VB2_SIG_RSA4096:
188 return 4096 / 8;
189 case VB2_SIG_RSA8192:
190 return 8192 / 8;
191 default:
192 return 0;
193 }
194 }
195
196 /**
197 * Return the exponent used by an RSA algorithm
198 *
199 * @param sig_alg Signature algorithm
200 * @return The exponent to use (3 or 65537(F4)), or 0 if error.
201 */
vb2_rsa_exponent(enum vb2_signature_algorithm sig_alg)202 static uint32_t vb2_rsa_exponent(enum vb2_signature_algorithm sig_alg)
203 {
204 switch (sig_alg) {
205 case VB2_SIG_RSA1024:
206 case VB2_SIG_RSA2048:
207 case VB2_SIG_RSA4096:
208 case VB2_SIG_RSA8192:
209 return 65537;
210 case VB2_SIG_RSA2048_EXP3:
211 case VB2_SIG_RSA3072_EXP3:
212 return 3;
213 default:
214 return 0;
215 }
216 }
217
vb2_packed_key_size(enum vb2_signature_algorithm sig_alg)218 uint32_t vb2_packed_key_size(enum vb2_signature_algorithm sig_alg)
219 {
220 uint32_t sig_size = vb2_rsa_sig_size(sig_alg);
221
222 if (!sig_size)
223 return 0;
224
225 /*
226 * Total size needed by a RSAPublicKey buffer is =
227 * 2 * key_len bytes for the n and rr arrays
228 * + sizeof len + sizeof n0inv.
229 */
230 return 2 * sig_size + 2 * sizeof(uint32_t);
231 }
232
233 /*
234 * PKCS 1.5 padding (from the RSA PKCS#1 v2.1 standard)
235 *
236 * Depending on the RSA key size and hash function, the padding is calculated
237 * as follows:
238 *
239 * 0x00 || 0x01 || PS || 0x00 || T
240 *
241 * T: DER Encoded DigestInfo value which depends on the hash function used.
242 *
243 * SHA-1: (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.
244 * SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H.
245 * SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H.
246 *
247 * Length(T) = 35 octets for SHA-1
248 * Length(T) = 51 octets for SHA-256
249 * Length(T) = 83 octets for SHA-512
250 *
251 * PS: octet string consisting of {Length(RSA Key) - Length(T) - 3} 0xFF
252 */
253 static const uint8_t sha1_tail[] = {
254 0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b,
255 0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14
256 };
257
258 static const uint8_t sha256_tail[] = {
259 0x00,0x30,0x31,0x30,0x0d,0x06,0x09,0x60,
260 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01,
261 0x05,0x00,0x04,0x20
262 };
263
264 static const uint8_t sha512_tail[] = {
265 0x00,0x30,0x51,0x30,0x0d,0x06,0x09,0x60,
266 0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03,
267 0x05,0x00,0x04,0x40
268 };
269
270 /**
271 * Check pkcs 1.5 padding bytes
272 *
273 * @param sig Signature to verify
274 * @param key Key to take signature and hash algorithms from
275 * @return VB2_SUCCESS, or non-zero if error.
276 */
277 test_mockable
vb2_check_padding(const uint8_t * sig,const struct vb2_public_key * key)278 vb2_error_t vb2_check_padding(const uint8_t *sig,
279 const struct vb2_public_key *key)
280 {
281 /* Determine padding to use depending on the signature type */
282 uint32_t sig_size = vb2_rsa_sig_size(key->sig_alg);
283 uint32_t hash_size = vb2_digest_size(key->hash_alg);
284 uint32_t pad_size = sig_size - hash_size;
285 const uint8_t *tail;
286 uint32_t tail_size;
287 int result = 0;
288 int i;
289
290 if (!sig_size || !hash_size || hash_size > sig_size)
291 return VB2_ERROR_RSA_PADDING_SIZE;
292
293 switch (key->hash_alg) {
294 case VB2_HASH_SHA1:
295 tail = sha1_tail;
296 tail_size = sizeof(sha1_tail);
297 break;
298 case VB2_HASH_SHA256:
299 tail = sha256_tail;
300 tail_size = sizeof(sha256_tail);
301 break;
302 case VB2_HASH_SHA512:
303 tail = sha512_tail;
304 tail_size = sizeof(sha512_tail);
305 break;
306 default:
307 return VB2_ERROR_RSA_PADDING_ALGORITHM;
308 }
309
310 /* First 2 bytes are always 0x00 0x01 */
311 result |= *sig++ ^ 0x00;
312 result |= *sig++ ^ 0x01;
313
314 /* Then 0xff bytes until the tail */
315 for (i = 0; i < pad_size - tail_size - 2; i++)
316 result |= *sig++ ^ 0xff;
317
318 /*
319 * Then the tail. Even though there are probably no timing issues
320 * here, we use vb2_safe_memcmp() just to be on the safe side.
321 */
322 result |= vb2_safe_memcmp(sig, tail, tail_size);
323
324 return result ? VB2_ERROR_RSA_PADDING : VB2_SUCCESS;
325 }
326
vb2_rsa_verify_digest(const struct vb2_public_key * key,uint8_t * sig,const uint8_t * digest,const struct vb2_workbuf * wb)327 vb2_error_t vb2_rsa_verify_digest(const struct vb2_public_key *key,
328 uint8_t *sig, const uint8_t *digest,
329 const struct vb2_workbuf *wb)
330 {
331 struct vb2_workbuf wblocal = *wb;
332 void *workbuf;
333 uint32_t key_bytes;
334 int sig_size;
335 int pad_size;
336 size_t workbuf_size;
337 int exp;
338 vb2_error_t rv = VB2_ERROR_EX_HWCRYPTO_UNSUPPORTED;
339
340 if (!key || !sig || !digest)
341 return VB2_ERROR_RSA_VERIFY_PARAM;
342
343 sig_size = vb2_rsa_sig_size(key->sig_alg);
344 exp = vb2_rsa_exponent(key->sig_alg);
345 if (!sig_size || !exp) {
346 VB2_DEBUG("Invalid signature type!\n");
347 return VB2_ERROR_RSA_VERIFY_ALGORITHM;
348 }
349
350 /* Signature length should be same as key length */
351 key_bytes = key->arrsize * sizeof(uint32_t);
352 if (key_bytes != sig_size || key->arrsize > key_bytes) {
353 VB2_DEBUG("Signature is of incorrect length!\n");
354 return VB2_ERROR_RSA_VERIFY_SIG_LEN;
355 }
356
357 workbuf_size = VB2_MAX(3 * key_bytes, vb2_wb_round_down(wblocal.size));
358 workbuf = vb2_workbuf_alloc(&wblocal, workbuf_size);
359 if (!workbuf) {
360 VB2_DEBUG("ERROR - vboot2 %zd bytes work buffer allocation failed!\n",
361 workbuf_size);
362 return VB2_ERROR_RSA_VERIFY_WORKBUF;
363 }
364
365 if (key->allow_hwcrypto) {
366 rv = vb2ex_hwcrypto_modexp(key, sig, workbuf, workbuf_size, exp);
367
368 if (rv == VB2_SUCCESS)
369 VB2_DEBUG("Using HW modexp engine for sig_alg %d\n",
370 key->sig_alg);
371 else
372 VB2_DEBUG("HW modexp for sig_alg %d not supported, using SW\n",
373 key->sig_alg);
374 } else {
375 VB2_DEBUG("HW modexp forbidden, using SW\n");
376 }
377
378 if (rv != VB2_SUCCESS) {
379 vb2_modexp(key, sig, workbuf, exp);
380 }
381
382 vb2_workbuf_free(&wblocal, workbuf_size);
383
384 /*
385 * Check padding. Only fail immediately if the padding size is bad.
386 * Otherwise, continue on to check the digest to reduce the risk of
387 * timing based attacks.
388 */
389 rv = vb2_check_padding(sig, key);
390 if (rv == VB2_ERROR_RSA_PADDING_SIZE)
391 return rv;
392
393 /*
394 * Check digest. Even though there are probably no timing issues here,
395 * use vb2_safe_memcmp() just to be on the safe side. (That's also why
396 * we don't return before this check if the padding check failed.)
397 */
398 pad_size = sig_size - vb2_digest_size(key->hash_alg);
399 if (vb2_safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) {
400 VB2_DEBUG("Digest check failed!\n");
401 if (!rv)
402 rv = VB2_ERROR_RSA_VERIFY_DIGEST;
403 }
404
405 return rv;
406 }
407