aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorElliott Hughes2016-04-13 18:39:56 -0500
committerElliott Hughes2016-04-13 18:39:56 -0500
commit8febafa67e93b2159804b1130a41f15b009de1cd (patch)
treedfc6e4e42d45f1766fe35f82929d190b74b21d64 /verifier.cpp
parenta58a6dbe3d06aace0d1419838e162aa5267a4fc0 (diff)
downloadplatform-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.cpp320
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
34extern RecoveryUI* ui; 33extern RecoveryUI* ui;
35 34
35static 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
295std::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
367struct BNDeleter {
368 void operator()(BIGNUM* bn) {
369 BN_free(bn);
370 }
371};
372
373std::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;