fec_verity.cpp revision 83cda15b15269721aa4c5680af2fc33ffd30dfa3
1/* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include <ctype.h> 18#include <stdlib.h> 19#include <base/strings.h> 20#include "fec_private.h" 21 22/* converts a hex nibble into an int */ 23static inline int hextobin(char c) 24{ 25 if (c >= '0' && c <= '9') { 26 return c - '0'; 27 } else if (c >= 'a' && c <= 'f') { 28 return c - 'a' + 10; 29 } else { 30 errno = EINVAL; 31 return -1; 32 } 33} 34 35/* converts a hex string `src' of `size' characters to binary and copies the 36 the result into `dst' */ 37static int parse_hex(uint8_t *dst, uint32_t size, const char *src) 38{ 39 int l, h; 40 41 check(dst); 42 check(src); 43 check(2 * size == strlen(src)); 44 45 while (size) { 46 h = hextobin(tolower(*src++)); 47 l = hextobin(tolower(*src++)); 48 49 check(l >= 0); 50 check(h >= 0); 51 52 *dst++ = (h << 4) | l; 53 --size; 54 } 55 56 return 0; 57} 58 59/* parses a 64-bit unsigned integer from string `src' into `dst' and if 60 `maxval' is >0, checks that `dst' <= `maxval' */ 61static int parse_uint64(const char *src, uint64_t maxval, uint64_t *dst) 62{ 63 char *end; 64 unsigned long long int value; 65 66 check(src); 67 check(dst); 68 69 errno = 0; 70 value = strtoull(src, &end, 0); 71 72 if (*src == '\0' || *end != '\0' || 73 (errno == ERANGE && value == ULLONG_MAX)) { 74 errno = EINVAL; 75 return -1; 76 } 77 78 if (maxval && value > maxval) { 79 errno = EINVAL; 80 return -1; 81 } 82 83 *dst = (uint64_t)value; 84 return 0; 85} 86 87/* computes the size of verity hash tree for `file_size' bytes and returns the 88 number of hash tree levels in `verity_levels,' and the number of hashes per 89 level in `level_hashes', if the parameters are non-NULL */ 90uint64_t verity_get_size(uint64_t file_size, uint32_t *verity_levels, 91 uint32_t *level_hashes) 92{ 93 /* we assume a known metadata size, 4 KiB block size, and SHA-256 to avoid 94 relying on disk content */ 95 96 uint32_t level = 0; 97 uint64_t total = 0; 98 uint64_t hashes = file_size / FEC_BLOCKSIZE; 99 100 do { 101 if (level_hashes) { 102 level_hashes[level] = hashes; 103 } 104 105 hashes = fec_div_round_up(hashes * SHA256_DIGEST_LENGTH, FEC_BLOCKSIZE); 106 total += hashes; 107 108 ++level; 109 } while (hashes > 1); 110 111 if (verity_levels) { 112 *verity_levels = level; 113 } 114 115 return total * FEC_BLOCKSIZE; 116} 117 118/* computes a SHA-256 salted with `f->verity.salt' from a FEC_BLOCKSIZE byte 119 buffer `block', and copies the hash to `hash' */ 120static inline int verity_hash(fec_handle *f, const uint8_t *block, 121 uint8_t *hash) 122{ 123 SHA256_CTX ctx; 124 SHA256_Init(&ctx); 125 126 check(f); 127 check(f->verity.salt); 128 SHA256_Update(&ctx, f->verity.salt, f->verity.salt_size); 129 130 check(block); 131 SHA256_Update(&ctx, block, FEC_BLOCKSIZE); 132 133 check(hash); 134 SHA256_Final(hash, &ctx); 135 return 0; 136} 137 138/* computes a verity hash for FEC_BLOCKSIZE bytes from buffer `block' and 139 compres it to the expected value in `expected'; if `index' has a value 140 different from `VERITY_NO_CACHE', uses `f->cache' to cache the results */ 141bool verity_check_block(fec_handle *f, uint64_t index, const uint8_t *expected, 142 const uint8_t *block) 143{ 144 check(f); 145 146 if (index != VERITY_NO_CACHE) { 147 pthread_mutex_lock(&f->mutex); 148 auto cached = f->cache.find(index); 149 150 if (cached != f->cache.end()) { 151 verity_block_info vbi = *(cached->second); 152 153 f->lru.erase(cached->second); 154 f->lru.push_front(vbi); 155 f->cache[index] = f->lru.begin(); 156 157 pthread_mutex_unlock(&f->mutex); 158 return vbi.valid; 159 } 160 161 pthread_mutex_unlock(&f->mutex); 162 } 163 164 uint8_t hash[SHA256_DIGEST_LENGTH]; 165 166 if (unlikely(verity_hash(f, block, hash) == -1)) { 167 error("failed to hash"); 168 return false; 169 } 170 171 check(expected); 172 bool valid = !memcmp(expected, hash, SHA256_DIGEST_LENGTH); 173 174 if (index != VERITY_NO_CACHE) { 175 pthread_mutex_lock(&f->mutex); 176 177 verity_block_info vbi; 178 vbi.index = index; 179 vbi.valid = valid; 180 181 if (f->lru.size() >= VERITY_CACHE_BLOCKS) { 182 f->cache.erase(f->lru.rbegin()->index); 183 f->lru.pop_back(); 184 } 185 186 f->lru.push_front(vbi); 187 f->cache[index] = f->lru.begin(); 188 pthread_mutex_unlock(&f->mutex); 189 } 190 191 return valid; 192} 193 194/* reads a verity hash and the corresponding data block using error correction, 195 if available */ 196static bool ecc_read_hashes(fec_handle *f, uint64_t hash_offset, 197 uint8_t *hash, uint64_t data_offset, uint8_t *data) 198{ 199 check(f); 200 201 if (hash && fec_pread(f, hash, SHA256_DIGEST_LENGTH, hash_offset) != 202 SHA256_DIGEST_LENGTH) { 203 error("failed to read hash tree: offset %" PRIu64 ": %s", hash_offset, 204 strerror(errno)); 205 return false; 206 } 207 208 check(data); 209 210 if (fec_pread(f, data, FEC_BLOCKSIZE, data_offset) != FEC_BLOCKSIZE) { 211 error("failed to read hash tree: data_offset %" PRIu64 ": %s", 212 data_offset, strerror(errno)); 213 return false; 214 } 215 216 return true; 217} 218 219/* reads the verity hash tree, validates it against the root hash in `root', 220 corrects errors if necessary, and copies valid data blocks for later use 221 to `f->verity.hash' */ 222static int verify_tree(fec_handle *f, const uint8_t *root) 223{ 224 uint8_t data[FEC_BLOCKSIZE]; 225 uint8_t hash[SHA256_DIGEST_LENGTH]; 226 227 check(f); 228 check(root); 229 230 verity_info *v = &f->verity; 231 uint32_t levels = 0; 232 233 /* calculate the size and the number of levels in the hash tree */ 234 v->hash_size = 235 verity_get_size(v->data_blocks * FEC_BLOCKSIZE, &levels, NULL); 236 237 check(v->hash_start < UINT64_MAX - v->hash_size); 238 check(v->hash_start + v->hash_size <= f->data_size); 239 240 uint64_t hash_offset = v->hash_start; 241 uint64_t data_offset = hash_offset + FEC_BLOCKSIZE; 242 243 v->hash_data_offset = data_offset; 244 245 /* validate the root hash */ 246 if (!raw_pread(f, data, FEC_BLOCKSIZE, hash_offset) || 247 !verity_check_block(f, VERITY_NO_CACHE, root, data)) { 248 /* try to correct */ 249 if (!ecc_read_hashes(f, 0, NULL, hash_offset, data) || 250 !verity_check_block(f, VERITY_NO_CACHE, root, data)) { 251 error("root hash invalid"); 252 return -1; 253 } else if (f->mode & O_RDWR && 254 !raw_pwrite(f, data, FEC_BLOCKSIZE, hash_offset)) { 255 error("failed to rewrite the root block: %s", strerror(errno)); 256 return -1; 257 } 258 } 259 260 debug("root hash valid"); 261 262 /* calculate the number of hashes on each level */ 263 uint32_t hashes[levels]; 264 265 verity_get_size(v->data_blocks * FEC_BLOCKSIZE, NULL, hashes); 266 267 /* calculate the size and offset for the data hashes */ 268 for (uint32_t i = 1; i < levels; ++i) { 269 uint32_t blocks = hashes[levels - i]; 270 debug("%u hash blocks on level %u", blocks, levels - i); 271 272 v->hash_data_offset = data_offset; 273 v->hash_data_blocks = blocks; 274 275 data_offset += blocks * FEC_BLOCKSIZE; 276 } 277 278 check(v->hash_data_blocks); 279 check(v->hash_data_blocks <= v->hash_size / FEC_BLOCKSIZE); 280 281 check(v->hash_data_offset); 282 check(v->hash_data_offset <= 283 UINT64_MAX - (v->hash_data_blocks * FEC_BLOCKSIZE)); 284 check(v->hash_data_offset < f->data_size); 285 check(v->hash_data_offset + v->hash_data_blocks * FEC_BLOCKSIZE <= 286 f->data_size); 287 288 /* copy data hashes to memory in case they are corrupted, so we don't 289 have to correct them every time they are needed */ 290 std::unique_ptr<uint8_t[]> data_hashes( 291 new (std::nothrow) uint8_t[f->verity.hash_data_blocks * FEC_BLOCKSIZE]); 292 293 if (!data_hashes) { 294 errno = ENOMEM; 295 return -1; 296 } 297 298 /* validate the rest of the hash tree */ 299 data_offset = hash_offset + FEC_BLOCKSIZE; 300 301 for (uint32_t i = 1; i < levels; ++i) { 302 uint32_t blocks = hashes[levels - i]; 303 304 for (uint32_t j = 0; j < blocks; ++j) { 305 /* ecc reads are very I/O intensive, so read raw hash tree and do 306 error correcting only if it doesn't validate */ 307 if (!raw_pread(f, hash, SHA256_DIGEST_LENGTH, 308 hash_offset + j * SHA256_DIGEST_LENGTH) || 309 !raw_pread(f, data, FEC_BLOCKSIZE, 310 data_offset + j * FEC_BLOCKSIZE)) { 311 error("failed to read hashes: %s", strerror(errno)); 312 return -1; 313 } 314 315 if (!verity_check_block(f, VERITY_NO_CACHE, hash, data)) { 316 /* try to correct */ 317 if (!ecc_read_hashes(f, 318 hash_offset + j * SHA256_DIGEST_LENGTH, hash, 319 data_offset + j * FEC_BLOCKSIZE, data) || 320 !verity_check_block(f, VERITY_NO_CACHE, hash, data)) { 321 error("invalid hash tree: hash_offset %" PRIu64 ", " 322 "data_offset %" PRIu64 ", block %u", 323 hash_offset, data_offset, j); 324 return -1; 325 } 326 327 /* update the corrected blocks to the file if we are in r/w 328 mode */ 329 if (f->mode & O_RDWR) { 330 if (!raw_pwrite(f, hash, SHA256_DIGEST_LENGTH, 331 hash_offset + j * SHA256_DIGEST_LENGTH) || 332 !raw_pwrite(f, data, FEC_BLOCKSIZE, 333 data_offset + j * FEC_BLOCKSIZE)) { 334 error("failed to write hashes: %s", strerror(errno)); 335 return -1; 336 } 337 } 338 } 339 340 if (blocks == v->hash_data_blocks) { 341 memcpy(data_hashes.get() + j * FEC_BLOCKSIZE, data, 342 FEC_BLOCKSIZE); 343 } 344 } 345 346 hash_offset = data_offset; 347 data_offset += blocks * FEC_BLOCKSIZE; 348 } 349 350 debug("valid"); 351 352 v->hash = data_hashes.release(); 353 return 0; 354} 355 356/* reads, corrects and parses the verity table, validates parameters, and if 357 `f->flags' does not have `FEC_VERITY_DISABLE' set, calls `verify_tree' to 358 load and validate the hash tree */ 359static int parse_table(fec_handle *f, uint64_t offset, uint32_t size) 360{ 361 check(f); 362 check(size >= VERITY_MIN_TABLE_SIZE); 363 check(size <= VERITY_MAX_TABLE_SIZE); 364 365 debug("offset = %" PRIu64 ", size = %u", offset, size); 366 367 verity_info *v = &f->verity; 368 std::unique_ptr<char[]> table(new (std::nothrow) char[size + 1]); 369 370 if (!table) { 371 errno = ENOMEM; 372 return -1; 373 } 374 375 if (fec_pread(f, table.get(), size, offset) != (ssize_t)size) { 376 error("failed to read verity table: %s", strerror(errno)); 377 return -1; 378 } 379 380 table[size] = '\0'; 381 debug("verity table: '%s'", table.get()); 382 383 int i = 0; 384 std::unique_ptr<uint8_t[]> salt; 385 uint8_t root[SHA256_DIGEST_LENGTH]; 386 387 auto tokens = android::base::Split(table.get(), " "); 388 389 for (const auto token : tokens) { 390 switch (i++) { 391 case 0: /* version */ 392 if (token != stringify(VERITY_TABLE_VERSION)) { 393 error("unsupported verity table version: %s", token.c_str()); 394 return -1; 395 } 396 break; 397 case 3: /* data_block_size */ 398 case 4: /* hash_block_size */ 399 /* assume 4 KiB block sizes for everything */ 400 if (token != stringify(FEC_BLOCKSIZE)) { 401 error("unsupported verity block size: %s", token.c_str()); 402 return -1; 403 } 404 break; 405 case 5: /* num_data_blocks */ 406 if (parse_uint64(token.c_str(), f->data_size / FEC_BLOCKSIZE, 407 &v->data_blocks) == -1) { 408 error("invalid number of verity data blocks: %s", 409 token.c_str()); 410 return -1; 411 } 412 break; 413 case 6: /* hash_start_block */ 414 if (parse_uint64(token.c_str(), f->data_size / FEC_BLOCKSIZE, 415 &v->hash_start) == -1) { 416 error("invalid verity hash start block: %s", token.c_str()); 417 return -1; 418 } 419 420 v->hash_start *= FEC_BLOCKSIZE; 421 break; 422 case 7: /* algorithm */ 423 if (token != "sha256") { 424 error("unsupported verity hash algorithm: %s", token.c_str()); 425 return -1; 426 } 427 break; 428 case 8: /* digest */ 429 if (parse_hex(root, sizeof(root), token.c_str()) == -1) { 430 error("invalid verity root hash: %s", token.c_str()); 431 return -1; 432 } 433 break; 434 case 9: /* salt */ 435 v->salt_size = token.size(); 436 check(v->salt_size % 2 == 0); 437 v->salt_size /= 2; 438 439 salt.reset(new (std::nothrow) uint8_t[v->salt_size]); 440 441 if (!salt) { 442 errno = ENOMEM; 443 return -1; 444 } 445 446 if (parse_hex(salt.get(), v->salt_size, token.c_str()) == -1) { 447 error("invalid verity salt: %s", token.c_str()); 448 return -1; 449 } 450 break; 451 default: 452 break; 453 } 454 } 455 456 if (i < VERITY_TABLE_ARGS) { 457 error("not enough arguments in verity table: %d; expected at least " 458 stringify(VERITY_TABLE_ARGS), i); 459 return -1; 460 } 461 462 check(v->hash_start < f->data_size); 463 464 if (v->metadata_start < v->hash_start) { 465 check(v->data_blocks == v->metadata_start / FEC_BLOCKSIZE); 466 } else { 467 check(v->data_blocks == v->hash_start / FEC_BLOCKSIZE); 468 } 469 470 v->salt = salt.release(); 471 v->table = table.release(); 472 473 if (!(f->flags & FEC_VERITY_DISABLE)) { 474 if (verify_tree(f, root) == -1) { 475 return -1; 476 } 477 478 check(v->hash); 479 480 uint8_t zero_block[FEC_BLOCKSIZE]; 481 memset(zero_block, 0, FEC_BLOCKSIZE); 482 483 if (verity_hash(f, zero_block, v->zero_hash) == -1) { 484 error("failed to hash"); 485 return -1; 486 } 487 } 488 489 return 0; 490} 491 492/* rewrites verity metadata block using error corrected data in `f->verity' */ 493static int rewrite_metadata(fec_handle *f, uint64_t offset) 494{ 495 check(f); 496 check(f->data_size > VERITY_METADATA_SIZE); 497 check(offset <= f->data_size - VERITY_METADATA_SIZE); 498 499 std::unique_ptr<uint8_t[]> metadata( 500 new (std::nothrow) uint8_t[VERITY_METADATA_SIZE]); 501 502 if (!metadata) { 503 errno = ENOMEM; 504 return -1; 505 } 506 507 memset(metadata.get(), 0, VERITY_METADATA_SIZE); 508 509 verity_info *v = &f->verity; 510 memcpy(metadata.get(), &v->header, sizeof(v->header)); 511 512 check(v->table); 513 size_t len = strlen(v->table); 514 515 check(sizeof(v->header) + len <= VERITY_METADATA_SIZE); 516 memcpy(metadata.get() + sizeof(v->header), v->table, len); 517 518 return raw_pwrite(f, metadata.get(), VERITY_METADATA_SIZE, offset); 519} 520 521/* attempts to read verity metadata from `f->fd' position `offset'; if in r/w 522 mode, rewrites the metadata if it had errors */ 523int verity_parse_header(fec_handle *f, uint64_t offset) 524{ 525 check(f); 526 check(f->data_size > VERITY_METADATA_SIZE); 527 528 if (offset > f->data_size - VERITY_METADATA_SIZE) { 529 debug("failed to read verity header: offset %" PRIu64 " is too far", 530 offset); 531 return -1; 532 } 533 534 verity_info *v = &f->verity; 535 uint64_t errors = f->errors; 536 537 if (fec_pread(f, &v->header, sizeof(v->header), offset) != 538 sizeof(v->header)) { 539 error("failed to read verity header: %s", strerror(errno)); 540 return -1; 541 } 542 543 verity_header raw_header; 544 545 if (!raw_pread(f, &raw_header, sizeof(raw_header), offset)) { 546 error("failed to read verity header: %s", strerror(errno)); 547 return -1; 548 } 549 /* use raw data to check for the alternative magic, because it will 550 be error corrected to VERITY_MAGIC otherwise */ 551 if (raw_header.magic == VERITY_MAGIC_DISABLE) { 552 /* this value is not used by us, but can be used by a caller to 553 decide whether dm-verity should be enabled */ 554 v->disabled = true; 555 } else if (v->header.magic != VERITY_MAGIC) { 556 return -1; 557 } 558 559 if (v->header.version != VERITY_VERSION) { 560 error("unsupported verity version %u", v->header.version); 561 return -1; 562 } 563 564 if (v->header.length < VERITY_MIN_TABLE_SIZE || 565 v->header.length > VERITY_MAX_TABLE_SIZE) { 566 error("invalid verity table size: %u; expected [" 567 stringify(VERITY_MIN_TABLE_SIZE) ", " 568 stringify(VERITY_MAX_TABLE_SIZE) ")", v->header.length); 569 return -1; 570 } 571 572 v->metadata_start = offset; 573 574 /* signature is skipped, because for our purposes it won't matter from 575 where the data originates; the caller of the library is responsible 576 for signature verification */ 577 578 if (offset > UINT64_MAX - v->header.length) { 579 error("invalid verity table length: %u", v->header.length); 580 return -1; 581 } else if (offset + v->header.length >= f->data_size) { 582 error("invalid verity table length: %u", v->header.length); 583 return -1; 584 } 585 586 if (parse_table(f, offset + sizeof(v->header), v->header.length) == -1) { 587 return -1; 588 } 589 590 /* if we corrected something while parsing metadata and we are in r/w 591 mode, rewrite the corrected metadata */ 592 if (f->mode & O_RDWR && f->errors > errors && 593 rewrite_metadata(f, offset) < 0) { 594 warn("failed to rewrite verity metadata: %s", strerror(errno)); 595 } 596 597 if (v->metadata_start < v->hash_start) { 598 f->data_size = v->metadata_start; 599 } else { 600 f->data_size = v->hash_start; 601 } 602 603 return 0; 604} 605 606int fec_verity_set_status(struct fec_handle *f, bool enabled) 607{ 608 check(f); 609 610 if (!(f->mode & O_RDWR)) { 611 error("cannot update verity magic: read-only handle"); 612 errno = EBADF; 613 return -1; 614 } 615 616 verity_info *v = &f->verity; 617 618 if (!v->metadata_start) { 619 error("cannot update verity magic: no metadata found"); 620 errno = EINVAL; 621 return -1; 622 } 623 624 if (v->disabled == !enabled) { 625 return 0; /* nothing to do */ 626 } 627 628 uint32_t magic = enabled ? VERITY_MAGIC : VERITY_MAGIC_DISABLE; 629 630 if (!raw_pwrite(f, &magic, sizeof(magic), v->metadata_start)) { 631 error("failed to update verity magic to %08x: %s", magic, 632 strerror(errno)); 633 return -1; 634 } 635 636 warn("updated verity magic to %08x (%s)", magic, 637 enabled ? "enabled" : "disabled"); 638 v->disabled = !enabled; 639 640 return 0; 641} 642