diff options
author | Elliott Hughes | 2016-04-13 18:39:56 -0500 |
---|---|---|
committer | Elliott Hughes | 2016-04-13 18:39:56 -0500 |
commit | 8febafa67e93b2159804b1130a41f15b009de1cd (patch) | |
tree | dfc6e4e42d45f1766fe35f82929d190b74b21d64 /verifier.cpp | |
parent | a58a6dbe3d06aace0d1419838e162aa5267a4fc0 (diff) | |
download | platform-bootable-recovery-8febafa67e93b2159804b1130a41f15b009de1cd.tar.gz platform-bootable-recovery-8febafa67e93b2159804b1130a41f15b009de1cd.tar.xz platform-bootable-recovery-8febafa67e93b2159804b1130a41f15b009de1cd.zip |
Use BoringSSL instead of mincrypt to speed up package verification.
This changes the verification code in bootable/recovery to use
BoringSSL instead of mincrypt.
Cherry-pick of 452df6d99c81c4eeee3d2c7b2171901e8b7bc54a, with
merge conflict resolution, extra logging in verifier.cpp, and
an increase in the hash chunk size from 4KiB to 1MiB.
Bug: http://b/28135231
Change-Id: I1ed7efd52223dd6f6a4629cad187cbc383d5aa84
Diffstat (limited to 'verifier.cpp')
-rw-r--r-- | verifier.cpp | 320 |
1 files changed, 209 insertions, 111 deletions
diff --git a/verifier.cpp b/verifier.cpp index 9a2d60c6..4004b022 100644 --- a/verifier.cpp +++ b/verifier.cpp | |||
@@ -14,25 +14,26 @@ | |||
14 | * limitations under the License. | 14 | * limitations under the License. |
15 | */ | 15 | */ |
16 | 16 | ||
17 | #include "asn1_decoder.h" | ||
18 | #include "common.h" | ||
19 | #include "ui.h" | ||
20 | #include "verifier.h" | ||
21 | |||
22 | #include "mincrypt/dsa_sig.h" | ||
23 | #include "mincrypt/p256.h" | ||
24 | #include "mincrypt/p256_ecdsa.h" | ||
25 | #include "mincrypt/rsa.h" | ||
26 | #include "mincrypt/sha.h" | ||
27 | #include "mincrypt/sha256.h" | ||
28 | |||
29 | #include <errno.h> | 17 | #include <errno.h> |
30 | #include <malloc.h> | 18 | #include <malloc.h> |
31 | #include <stdio.h> | 19 | #include <stdio.h> |
32 | #include <string.h> | 20 | #include <string.h> |
33 | 21 | ||
22 | #include <algorithm> | ||
23 | #include <memory> | ||
24 | |||
25 | #include <openssl/ecdsa.h> | ||
26 | #include <openssl/obj_mac.h> | ||
27 | |||
28 | #include "asn1_decoder.h" | ||
29 | #include "common.h" | ||
30 | #include "ui.h" | ||
31 | #include "verifier.h" | ||
32 | |||
34 | extern RecoveryUI* ui; | 33 | extern RecoveryUI* ui; |
35 | 34 | ||
35 | static constexpr size_t MiB = 1024 * 1024; | ||
36 | |||
36 | /* | 37 | /* |
37 | * Simple version of PKCS#7 SignedData extraction. This extracts the | 38 | * Simple version of PKCS#7 SignedData extraction. This extracts the |
38 | * signature OCTET STRING to be used for signature verification. | 39 | * signature OCTET STRING to be used for signature verification. |
@@ -188,30 +189,30 @@ int verify_file(unsigned char* addr, size_t length, | |||
188 | } | 189 | } |
189 | } | 190 | } |
190 | 191 | ||
191 | #define BUFFER_SIZE 4096 | ||
192 | |||
193 | bool need_sha1 = false; | 192 | bool need_sha1 = false; |
194 | bool need_sha256 = false; | 193 | bool need_sha256 = false; |
195 | for (const auto& key : keys) { | 194 | for (const auto& key : keys) { |
196 | switch (key.hash_len) { | 195 | switch (key.hash_len) { |
197 | case SHA_DIGEST_SIZE: need_sha1 = true; break; | 196 | case SHA_DIGEST_LENGTH: need_sha1 = true; break; |
198 | case SHA256_DIGEST_SIZE: need_sha256 = true; break; | 197 | case SHA256_DIGEST_LENGTH: need_sha256 = true; break; |
199 | } | 198 | } |
200 | } | 199 | } |
201 | 200 | ||
202 | SHA_CTX sha1_ctx; | 201 | SHA_CTX sha1_ctx; |
203 | SHA256_CTX sha256_ctx; | 202 | SHA256_CTX sha256_ctx; |
204 | SHA_init(&sha1_ctx); | 203 | SHA1_Init(&sha1_ctx); |
205 | SHA256_init(&sha256_ctx); | 204 | SHA256_Init(&sha256_ctx); |
206 | 205 | ||
207 | double frac = -1.0; | 206 | double frac = -1.0; |
208 | size_t so_far = 0; | 207 | size_t so_far = 0; |
209 | while (so_far < signed_len) { | 208 | while (so_far < signed_len) { |
210 | size_t size = signed_len - so_far; | 209 | // On a Nexus 9, experiment didn't show any performance improvement with |
211 | if (size > BUFFER_SIZE) size = BUFFER_SIZE; | 210 | // larger sizes past 1MiB, and they reduce the granularity of the progress |
211 | // bar. http://b/28135231. | ||
212 | size_t size = std::min(signed_len - so_far, 1 * MiB); | ||
212 | 213 | ||
213 | if (need_sha1) SHA_update(&sha1_ctx, addr + so_far, size); | 214 | if (need_sha1) SHA1_Update(&sha1_ctx, addr + so_far, size); |
214 | if (need_sha256) SHA256_update(&sha256_ctx, addr + so_far, size); | 215 | if (need_sha256) SHA256_Update(&sha256_ctx, addr + so_far, size); |
215 | so_far += size; | 216 | so_far += size; |
216 | 217 | ||
217 | double f = so_far / (double)signed_len; | 218 | double f = so_far / (double)signed_len; |
@@ -221,8 +222,10 @@ int verify_file(unsigned char* addr, size_t length, | |||
221 | } | 222 | } |
222 | } | 223 | } |
223 | 224 | ||
224 | const uint8_t* sha1 = SHA_final(&sha1_ctx); | 225 | uint8_t sha1[SHA_DIGEST_LENGTH]; |
225 | const uint8_t* sha256 = SHA256_final(&sha256_ctx); | 226 | SHA1_Final(sha1, &sha1_ctx); |
227 | uint8_t sha256[SHA256_DIGEST_LENGTH]; | ||
228 | SHA256_Final(sha256, &sha256_ctx); | ||
226 | 229 | ||
227 | uint8_t* sig_der = nullptr; | 230 | uint8_t* sig_der = nullptr; |
228 | size_t sig_der_length = 0; | 231 | size_t sig_der_length = 0; |
@@ -242,23 +245,25 @@ int verify_file(unsigned char* addr, size_t length, | |||
242 | size_t i = 0; | 245 | size_t i = 0; |
243 | for (const auto& key : keys) { | 246 | for (const auto& key : keys) { |
244 | const uint8_t* hash; | 247 | const uint8_t* hash; |
248 | int hash_nid; | ||
245 | switch (key.hash_len) { | 249 | switch (key.hash_len) { |
246 | case SHA_DIGEST_SIZE: hash = sha1; break; | 250 | case SHA_DIGEST_LENGTH: |
247 | case SHA256_DIGEST_SIZE: hash = sha256; break; | 251 | hash = sha1; |
248 | default: continue; | 252 | hash_nid = NID_sha1; |
253 | break; | ||
254 | case SHA256_DIGEST_LENGTH: | ||
255 | hash = sha256; | ||
256 | hash_nid = NID_sha256; | ||
257 | break; | ||
258 | default: | ||
259 | continue; | ||
249 | } | 260 | } |
250 | 261 | ||
251 | // The 6 bytes is the "(signature_start) $ff $ff (comment_size)" that | 262 | // The 6 bytes is the "(signature_start) $ff $ff (comment_size)" that |
252 | // the signing tool appends after the signature itself. | 263 | // the signing tool appends after the signature itself. |
253 | if (key.key_type == Certificate::RSA) { | 264 | if (key.key_type == Certificate::KEY_TYPE_RSA) { |
254 | if (sig_der_length < RSANUMBYTES) { | 265 | if (!RSA_verify(hash_nid, hash, key.hash_len, sig_der, |
255 | // "signature" block isn't big enough to contain an RSA block. | 266 | sig_der_length, key.rsa.get())) { |
256 | LOGI("signature is too short for RSA key %zu\n", i); | ||
257 | continue; | ||
258 | } | ||
259 | |||
260 | if (!RSA_verify(key.rsa.get(), sig_der, RSANUMBYTES, | ||
261 | hash, key.hash_len)) { | ||
262 | LOGI("failed to verify against RSA key %zu\n", i); | 267 | LOGI("failed to verify against RSA key %zu\n", i); |
263 | continue; | 268 | continue; |
264 | } | 269 | } |
@@ -266,18 +271,10 @@ int verify_file(unsigned char* addr, size_t length, | |||
266 | LOGI("whole-file signature verified against RSA key %zu\n", i); | 271 | LOGI("whole-file signature verified against RSA key %zu\n", i); |
267 | free(sig_der); | 272 | free(sig_der); |
268 | return VERIFY_SUCCESS; | 273 | return VERIFY_SUCCESS; |
269 | } else if (key.key_type == Certificate::EC | 274 | } else if (key.key_type == Certificate::KEY_TYPE_EC |
270 | && key.hash_len == SHA256_DIGEST_SIZE) { | 275 | && key.hash_len == SHA256_DIGEST_LENGTH) { |
271 | p256_int r, s; | 276 | if (!ECDSA_verify(0, hash, key.hash_len, sig_der, |
272 | if (!dsa_sig_unpack(sig_der, sig_der_length, &r, &s)) { | 277 | sig_der_length, key.ec.get())) { |
273 | LOGI("Not a DSA signature block for EC key %zu\n", i); | ||
274 | continue; | ||
275 | } | ||
276 | |||
277 | p256_int p256_hash; | ||
278 | p256_from_bin(hash, &p256_hash); | ||
279 | if (!p256_ecdsa_verify(&(key.ec->x), &(key.ec->y), | ||
280 | &p256_hash, &r, &s)) { | ||
281 | LOGI("failed to verify against EC key %zu\n", i); | 278 | LOGI("failed to verify against EC key %zu\n", i); |
282 | continue; | 279 | continue; |
283 | } | 280 | } |
@@ -295,6 +292,144 @@ int verify_file(unsigned char* addr, size_t length, | |||
295 | return VERIFY_FAILURE; | 292 | return VERIFY_FAILURE; |
296 | } | 293 | } |
297 | 294 | ||
295 | std::unique_ptr<RSA, RSADeleter> parse_rsa_key(FILE* file, uint32_t exponent) { | ||
296 | // Read key length in words and n0inv. n0inv is a precomputed montgomery | ||
297 | // parameter derived from the modulus and can be used to speed up | ||
298 | // verification. n0inv is 32 bits wide here, assuming the verification logic | ||
299 | // uses 32 bit arithmetic. However, BoringSSL may use a word size of 64 bits | ||
300 | // internally, in which case we don't have a valid n0inv. Thus, we just | ||
301 | // ignore the montgomery parameters and have BoringSSL recompute them | ||
302 | // internally. If/When the speedup from using the montgomery parameters | ||
303 | // becomes relevant, we can add more sophisticated code here to obtain a | ||
304 | // 64-bit n0inv and initialize the montgomery parameters in the key object. | ||
305 | uint32_t key_len_words = 0; | ||
306 | uint32_t n0inv = 0; | ||
307 | if (fscanf(file, " %i , 0x%x", &key_len_words, &n0inv) != 2) { | ||
308 | return nullptr; | ||
309 | } | ||
310 | |||
311 | if (key_len_words > 8192 / 32) { | ||
312 | LOGE("key length (%d) too large\n", key_len_words); | ||
313 | return nullptr; | ||
314 | } | ||
315 | |||
316 | // Read the modulus. | ||
317 | std::unique_ptr<uint32_t[]> modulus(new uint32_t[key_len_words]); | ||
318 | if (fscanf(file, " , { %u", &modulus[0]) != 1) { | ||
319 | return nullptr; | ||
320 | } | ||
321 | for (uint32_t i = 1; i < key_len_words; ++i) { | ||
322 | if (fscanf(file, " , %u", &modulus[i]) != 1) { | ||
323 | return nullptr; | ||
324 | } | ||
325 | } | ||
326 | |||
327 | // Cconvert from little-endian array of little-endian words to big-endian | ||
328 | // byte array suitable as input for BN_bin2bn. | ||
329 | std::reverse((uint8_t*)modulus.get(), | ||
330 | (uint8_t*)(modulus.get() + key_len_words)); | ||
331 | |||
332 | // The next sequence of values is the montgomery parameter R^2. Since we | ||
333 | // generally don't have a valid |n0inv|, we ignore this (see comment above). | ||
334 | uint32_t rr_value; | ||
335 | if (fscanf(file, " } , { %u", &rr_value) != 1) { | ||
336 | return nullptr; | ||
337 | } | ||
338 | for (uint32_t i = 1; i < key_len_words; ++i) { | ||
339 | if (fscanf(file, " , %u", &rr_value) != 1) { | ||
340 | return nullptr; | ||
341 | } | ||
342 | } | ||
343 | if (fscanf(file, " } } ") != 0) { | ||
344 | return nullptr; | ||
345 | } | ||
346 | |||
347 | // Initialize the key. | ||
348 | std::unique_ptr<RSA, RSADeleter> key(RSA_new()); | ||
349 | if (!key) { | ||
350 | return nullptr; | ||
351 | } | ||
352 | |||
353 | key->n = BN_bin2bn((uint8_t*)modulus.get(), | ||
354 | key_len_words * sizeof(uint32_t), NULL); | ||
355 | if (!key->n) { | ||
356 | return nullptr; | ||
357 | } | ||
358 | |||
359 | key->e = BN_new(); | ||
360 | if (!key->e || !BN_set_word(key->e, exponent)) { | ||
361 | return nullptr; | ||
362 | } | ||
363 | |||
364 | return key; | ||
365 | } | ||
366 | |||
367 | struct BNDeleter { | ||
368 | void operator()(BIGNUM* bn) { | ||
369 | BN_free(bn); | ||
370 | } | ||
371 | }; | ||
372 | |||
373 | std::unique_ptr<EC_KEY, ECKEYDeleter> parse_ec_key(FILE* file) { | ||
374 | uint32_t key_len_bytes = 0; | ||
375 | if (fscanf(file, " %i", &key_len_bytes) != 1) { | ||
376 | return nullptr; | ||
377 | } | ||
378 | |||
379 | std::unique_ptr<EC_GROUP, void (*)(EC_GROUP*)> group( | ||
380 | EC_GROUP_new_by_curve_name(NID_X9_62_prime256v1), EC_GROUP_free); | ||
381 | if (!group) { | ||
382 | return nullptr; | ||
383 | } | ||
384 | |||
385 | // Verify that |key_len| matches the group order. | ||
386 | if (key_len_bytes != BN_num_bytes(EC_GROUP_get0_order(group.get()))) { | ||
387 | return nullptr; | ||
388 | } | ||
389 | |||
390 | // Read the public key coordinates. Note that the byte order in the file is | ||
391 | // little-endian, so we convert to big-endian here. | ||
392 | std::unique_ptr<uint8_t[]> bytes(new uint8_t[key_len_bytes]); | ||
393 | std::unique_ptr<BIGNUM, BNDeleter> point[2]; | ||
394 | for (int i = 0; i < 2; ++i) { | ||
395 | unsigned int byte = 0; | ||
396 | if (fscanf(file, " , { %u", &byte) != 1) { | ||
397 | return nullptr; | ||
398 | } | ||
399 | bytes[key_len_bytes - 1] = byte; | ||
400 | |||
401 | for (size_t i = 1; i < key_len_bytes; ++i) { | ||
402 | if (fscanf(file, " , %u", &byte) != 1) { | ||
403 | return nullptr; | ||
404 | } | ||
405 | bytes[key_len_bytes - i - 1] = byte; | ||
406 | } | ||
407 | |||
408 | point[i].reset(BN_bin2bn(bytes.get(), key_len_bytes, nullptr)); | ||
409 | if (!point[i]) { | ||
410 | return nullptr; | ||
411 | } | ||
412 | |||
413 | if (fscanf(file, " }") != 0) { | ||
414 | return nullptr; | ||
415 | } | ||
416 | } | ||
417 | |||
418 | if (fscanf(file, " } ") != 0) { | ||
419 | return nullptr; | ||
420 | } | ||
421 | |||
422 | // Create and initialize the key. | ||
423 | std::unique_ptr<EC_KEY, ECKEYDeleter> key(EC_KEY_new()); | ||
424 | if (!key || !EC_KEY_set_group(key.get(), group.get()) || | ||
425 | !EC_KEY_set_public_key_affine_coordinates(key.get(), point[0].get(), | ||
426 | point[1].get())) { | ||
427 | return nullptr; | ||
428 | } | ||
429 | |||
430 | return key; | ||
431 | } | ||
432 | |||
298 | // Reads a file containing one or more public keys as produced by | 433 | // Reads a file containing one or more public keys as produced by |
299 | // DumpPublicKey: this is an RSAPublicKey struct as it would appear | 434 | // DumpPublicKey: this is an RSAPublicKey struct as it would appear |
300 | // as a C source literal, eg: | 435 | // as a C source literal, eg: |
@@ -335,94 +470,57 @@ bool load_keys(const char* filename, std::vector<Certificate>& certs) { | |||
335 | } | 470 | } |
336 | 471 | ||
337 | while (true) { | 472 | while (true) { |
338 | certs.emplace_back(0, Certificate::RSA, nullptr, nullptr); | 473 | certs.emplace_back(0, Certificate::KEY_TYPE_RSA, nullptr, nullptr); |
339 | Certificate& cert = certs.back(); | 474 | Certificate& cert = certs.back(); |
475 | uint32_t exponent = 0; | ||
340 | 476 | ||
341 | char start_char; | 477 | char start_char; |
342 | if (fscanf(f.get(), " %c", &start_char) != 1) return false; | 478 | if (fscanf(f.get(), " %c", &start_char) != 1) return false; |
343 | if (start_char == '{') { | 479 | if (start_char == '{') { |
344 | // a version 1 key has no version specifier. | 480 | // a version 1 key has no version specifier. |
345 | cert.key_type = Certificate::RSA; | 481 | cert.key_type = Certificate::KEY_TYPE_RSA; |
346 | cert.rsa = std::unique_ptr<RSAPublicKey>(new RSAPublicKey); | 482 | exponent = 3; |
347 | cert.rsa->exponent = 3; | 483 | cert.hash_len = SHA_DIGEST_LENGTH; |
348 | cert.hash_len = SHA_DIGEST_SIZE; | ||
349 | } else if (start_char == 'v') { | 484 | } else if (start_char == 'v') { |
350 | int version; | 485 | int version; |
351 | if (fscanf(f.get(), "%d {", &version) != 1) return false; | 486 | if (fscanf(f.get(), "%d {", &version) != 1) return false; |
352 | switch (version) { | 487 | switch (version) { |
353 | case 2: | 488 | case 2: |
354 | cert.key_type = Certificate::RSA; | 489 | cert.key_type = Certificate::KEY_TYPE_RSA; |
355 | cert.rsa = std::unique_ptr<RSAPublicKey>(new RSAPublicKey); | 490 | exponent = 65537; |
356 | cert.rsa->exponent = 65537; | 491 | cert.hash_len = SHA_DIGEST_LENGTH; |
357 | cert.hash_len = SHA_DIGEST_SIZE; | ||
358 | break; | 492 | break; |
359 | case 3: | 493 | case 3: |
360 | cert.key_type = Certificate::RSA; | 494 | cert.key_type = Certificate::KEY_TYPE_RSA; |
361 | cert.rsa = std::unique_ptr<RSAPublicKey>(new RSAPublicKey); | 495 | exponent = 3; |
362 | cert.rsa->exponent = 3; | 496 | cert.hash_len = SHA256_DIGEST_LENGTH; |
363 | cert.hash_len = SHA256_DIGEST_SIZE; | ||
364 | break; | 497 | break; |
365 | case 4: | 498 | case 4: |
366 | cert.key_type = Certificate::RSA; | 499 | cert.key_type = Certificate::KEY_TYPE_RSA; |
367 | cert.rsa = std::unique_ptr<RSAPublicKey>(new RSAPublicKey); | 500 | exponent = 65537; |
368 | cert.rsa->exponent = 65537; | 501 | cert.hash_len = SHA256_DIGEST_LENGTH; |
369 | cert.hash_len = SHA256_DIGEST_SIZE; | ||
370 | break; | 502 | break; |
371 | case 5: | 503 | case 5: |
372 | cert.key_type = Certificate::EC; | 504 | cert.key_type = Certificate::KEY_TYPE_EC; |
373 | cert.ec = std::unique_ptr<ECPublicKey>(new ECPublicKey); | 505 | cert.hash_len = SHA256_DIGEST_LENGTH; |
374 | cert.hash_len = SHA256_DIGEST_SIZE; | ||
375 | break; | 506 | break; |
376 | default: | 507 | default: |
377 | return false; | 508 | return false; |
378 | } | 509 | } |
379 | } | 510 | } |
380 | 511 | ||
381 | if (cert.key_type == Certificate::RSA) { | 512 | if (cert.key_type == Certificate::KEY_TYPE_RSA) { |
382 | RSAPublicKey* key = cert.rsa.get(); | 513 | cert.rsa = parse_rsa_key(f.get(), exponent); |
383 | if (fscanf(f.get(), " %i , 0x%x , { %u", &(key->len), &(key->n0inv), | 514 | if (!cert.rsa) { |
384 | &(key->n[0])) != 3) { | 515 | return false; |
385 | return false; | ||
386 | } | ||
387 | if (key->len != RSANUMWORDS) { | ||
388 | LOGE("key length (%d) does not match expected size\n", key->len); | ||
389 | return false; | ||
390 | } | ||
391 | for (int i = 1; i < key->len; ++i) { | ||
392 | if (fscanf(f.get(), " , %u", &(key->n[i])) != 1) return false; | ||
393 | } | 516 | } |
394 | if (fscanf(f.get(), " } , { %u", &(key->rr[0])) != 1) return false; | 517 | |
395 | for (int i = 1; i < key->len; ++i) { | 518 | LOGI("read key e=%d hash=%d\n", exponent, cert.hash_len); |
396 | if (fscanf(f.get(), " , %u", &(key->rr[i])) != 1) return false; | 519 | } else if (cert.key_type == Certificate::KEY_TYPE_EC) { |
397 | } | 520 | cert.ec = parse_ec_key(f.get()); |
398 | fscanf(f.get(), " } } "); | 521 | if (!cert.ec) { |
399 | 522 | return false; | |
400 | LOGI("read key e=%d hash=%d\n", key->exponent, cert.hash_len); | ||
401 | } else if (cert.key_type == Certificate::EC) { | ||
402 | ECPublicKey* key = cert.ec.get(); | ||
403 | int key_len; | ||
404 | unsigned int byte; | ||
405 | uint8_t x_bytes[P256_NBYTES]; | ||
406 | uint8_t y_bytes[P256_NBYTES]; | ||
407 | if (fscanf(f.get(), " %i , { %u", &key_len, &byte) != 2) return false; | ||
408 | if (key_len != P256_NBYTES) { | ||
409 | LOGE("Key length (%d) does not match expected size %d\n", key_len, P256_NBYTES); | ||
410 | return false; | ||
411 | } | ||
412 | x_bytes[P256_NBYTES - 1] = byte; | ||
413 | for (int i = P256_NBYTES - 2; i >= 0; --i) { | ||
414 | if (fscanf(f.get(), " , %u", &byte) != 1) return false; | ||
415 | x_bytes[i] = byte; | ||
416 | } | ||
417 | if (fscanf(f.get(), " } , { %u", &byte) != 1) return false; | ||
418 | y_bytes[P256_NBYTES - 1] = byte; | ||
419 | for (int i = P256_NBYTES - 2; i >= 0; --i) { | ||
420 | if (fscanf(f.get(), " , %u", &byte) != 1) return false; | ||
421 | y_bytes[i] = byte; | ||
422 | } | 523 | } |
423 | fscanf(f.get(), " } } "); | ||
424 | p256_from_bin(x_bytes, &key->x); | ||
425 | p256_from_bin(y_bytes, &key->y); | ||
426 | } else { | 524 | } else { |
427 | LOGE("Unknown key type %d\n", cert.key_type); | 525 | LOGE("Unknown key type %d\n", cert.key_type); |
428 | return false; | 526 | return false; |