libfec/fec_verity.cpp

   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 <android-base/strings.h>
  20 #include "fec_private.h"
  21
  22 /* converts a hex nibble into an int */
  23 static 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' */
  37 static 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' */
  61 static 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 */
  90 uint64_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' */
 120 static 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    compares it to the expected value in `expected' */
 140 bool verity_check_block(fec_handle *f, const uint8_t *expected,
 141         const uint8_t *block)
 142 {
 143     check(f);
 144     check(block);
 145
 146     uint8_t hash[SHA256_DIGEST_LENGTH];
 147
 148     if (unlikely(verity_hash(f, block, hash) == -1)) {
 149         error("failed to hash");
 150         return false;
 151     }
 152
 153     check(expected);
 154     return !memcmp(expected, hash, SHA256_DIGEST_LENGTH);
 155 }
 156
 157 /* reads a verity hash and the corresponding data block using error correction,
 158    if available */
 159 static bool ecc_read_hashes(fec_handle *f, uint64_t hash_offset,
 160         uint8_t *hash, uint64_t data_offset, uint8_t *data)
 161 {
 162     check(f);
 163
 164     if (hash && fec_pread(f, hash, SHA256_DIGEST_LENGTH, hash_offset) !=
 165                     SHA256_DIGEST_LENGTH) {
 166         error("failed to read hash tree: offset %" PRIu64 ": %s", hash_offset,
 167             strerror(errno));
 168         return false;
 169     }
 170
 171     check(data);
 172
 173     if (fec_pread(f, data, FEC_BLOCKSIZE, data_offset) != FEC_BLOCKSIZE) {
 174         error("failed to read hash tree: data_offset %" PRIu64 ": %s",
 175             data_offset, strerror(errno));
 176         return false;
 177     }
 178
 179     return true;
 180 }
 181
 182 /* reads the verity hash tree, validates it against the root hash in `root',
 183    corrects errors if necessary, and copies valid data blocks for later use
 184    to `f->verity.hash' */
 185 static int verify_tree(fec_handle *f, const uint8_t *root)
 186 {
 187     uint8_t data[FEC_BLOCKSIZE];
 188     uint8_t hash[SHA256_DIGEST_LENGTH];
 189
 190     check(f);
 191     check(root);
 192
 193     verity_info *v = &f->verity;
 194     uint32_t levels = 0;
 195
 196     /* calculate the size and the number of levels in the hash tree */
 197     v->hash_size =
 198         verity_get_size(v->data_blocks * FEC_BLOCKSIZE, &levels, NULL);
 199
 200     check(v->hash_start < UINT64_MAX - v->hash_size);
 201     check(v->hash_start + v->hash_size <= f->data_size);
 202
 203     uint64_t hash_offset = v->hash_start;
 204     uint64_t data_offset = hash_offset + FEC_BLOCKSIZE;
 205
 206     v->hash_data_offset = data_offset;
 207
 208     /* validate the root hash */
 209     if (!raw_pread(f, data, FEC_BLOCKSIZE, hash_offset) ||
 210             !verity_check_block(f, root, data)) {
 211         /* try to correct */
 212         if (!ecc_read_hashes(f, 0, NULL, hash_offset, data) ||
 213                 !verity_check_block(f, root, data)) {
 214             error("root hash invalid");
 215             return -1;
 216         } else if (f->mode & O_RDWR &&
 217                     !raw_pwrite(f, data, FEC_BLOCKSIZE, hash_offset)) {
 218             error("failed to rewrite the root block: %s", strerror(errno));
 219             return -1;
 220         }
 221     }
 222
 223     debug("root hash valid");
 224
 225     /* calculate the number of hashes on each level */
 226     uint32_t hashes[levels];
 227
 228     verity_get_size(v->data_blocks * FEC_BLOCKSIZE, NULL, hashes);
 229
 230     /* calculate the size and offset for the data hashes */
 231     for (uint32_t i = 1; i < levels; ++i) {
 232         uint32_t blocks = hashes[levels - i];
 233         debug("%u hash blocks on level %u", blocks, levels - i);
 234
 235         v->hash_data_offset = data_offset;
 236         v->hash_data_blocks = blocks;
 237
 238         data_offset += blocks * FEC_BLOCKSIZE;
 239     }
 240
 241     check(v->hash_data_blocks);
 242     check(v->hash_data_blocks <= v->hash_size / FEC_BLOCKSIZE);
 243
 244     check(v->hash_data_offset);
 245     check(v->hash_data_offset <=
 246         UINT64_MAX - (v->hash_data_blocks * FEC_BLOCKSIZE));
 247     check(v->hash_data_offset < f->data_size);
 248     check(v->hash_data_offset + v->hash_data_blocks * FEC_BLOCKSIZE <=
 249         f->data_size);
 250
 251     /* copy data hashes to memory in case they are corrupted, so we don't
 252        have to correct them every time they are needed */
 253     std::unique_ptr<uint8_t[]> data_hashes(
 254        new (std::nothrow) uint8_t[f->verity.hash_data_blocks * FEC_BLOCKSIZE]);
 255
 256     if (!data_hashes) {
 257         errno = ENOMEM;
 258         return -1;
 259     }
 260
 261     /* validate the rest of the hash tree */
 262     data_offset = hash_offset + FEC_BLOCKSIZE;
 263
 264     for (uint32_t i = 1; i < levels; ++i) {
 265         uint32_t blocks = hashes[levels - i];
 266
 267         for (uint32_t j = 0; j < blocks; ++j) {
 268             /* ecc reads are very I/O intensive, so read raw hash tree and do
 269                error correcting only if it doesn't validate */
 270             if (!raw_pread(f, hash, SHA256_DIGEST_LENGTH,
 271                     hash_offset + j * SHA256_DIGEST_LENGTH) ||
 272                 !raw_pread(f, data, FEC_BLOCKSIZE,
 273                     data_offset + j * FEC_BLOCKSIZE)) {
 274                 error("failed to read hashes: %s", strerror(errno));
 275                 return -1;
 276             }
 277
 278             if (!verity_check_block(f, hash, data)) {
 279                 /* try to correct */
 280                 if (!ecc_read_hashes(f,
 281                         hash_offset + j * SHA256_DIGEST_LENGTH, hash,
 282                         data_offset + j * FEC_BLOCKSIZE, data) ||
 283                     !verity_check_block(f, hash, data)) {
 284                     error("invalid hash tree: hash_offset %" PRIu64 ", "
 285                         "data_offset %" PRIu64 ", block %u",
 286                         hash_offset, data_offset, j);
 287                     return -1;
 288                 }
 289
 290                 /* update the corrected blocks to the file if we are in r/w
 291                    mode */
 292                 if (f->mode & O_RDWR) {
 293                     if (!raw_pwrite(f, hash, SHA256_DIGEST_LENGTH,
 294                             hash_offset + j * SHA256_DIGEST_LENGTH) ||
 295                         !raw_pwrite(f, data, FEC_BLOCKSIZE,
 296                             data_offset + j * FEC_BLOCKSIZE)) {
 297                         error("failed to write hashes: %s", strerror(errno));
 298                         return -1;
 299                     }
 300                 }
 301             }
 302
 303             if (blocks == v->hash_data_blocks) {
 304                 memcpy(data_hashes.get() + j * FEC_BLOCKSIZE, data,
 305                     FEC_BLOCKSIZE);
 306             }
 307         }
 308
 309         hash_offset = data_offset;
 310         data_offset += blocks * FEC_BLOCKSIZE;
 311     }
 312
 313     debug("valid");
 314
 315     if (v->hash) {
 316         delete[] v->hash;
 317         v->hash = NULL;
 318     }
 319
 320     v->hash = data_hashes.release();
 321     return 0;
 322 }
 323
 324 /* reads, corrects and parses the verity table, validates parameters, and if
 325    `f->flags' does not have `FEC_VERITY_DISABLE' set, calls `verify_tree' to
 326    load and validate the hash tree */
 327 static int parse_table(fec_handle *f, uint64_t offset, uint32_t size, bool useecc)
 328 {
 329     check(f);
 330     check(size >= VERITY_MIN_TABLE_SIZE);
 331     check(size <= VERITY_MAX_TABLE_SIZE);
 332
 333     debug("offset = %" PRIu64 ", size = %u", offset, size);
 334
 335     verity_info *v = &f->verity;
 336     std::unique_ptr<char[]> table(new (std::nothrow) char[size + 1]);
 337
 338     if (!table) {
 339         errno = ENOMEM;
 340         return -1;
 341     }
 342
 343     if (!useecc) {
 344         if (!raw_pread(f, table.get(), size, offset)) {
 345             error("failed to read verity table: %s", strerror(errno));
 346             return -1;
 347         }
 348     } else if (fec_pread(f, table.get(), size, offset) != (ssize_t)size) {
 349         error("failed to ecc read verity table: %s", strerror(errno));
 350         return -1;
 351     }
 352
 353     table[size] = '\0';
 354     debug("verity table: '%s'", table.get());
 355
 356     int i = 0;
 357     std::unique_ptr<uint8_t[]> salt;
 358     uint8_t root[SHA256_DIGEST_LENGTH];
 359
 360     auto tokens = android::base::Split(table.get(), " ");
 361
 362     for (const auto& token : tokens) {
 363         switch (i++) {
 364         case 0: /* version */
 365             if (token != stringify(VERITY_TABLE_VERSION)) {
 366                 error("unsupported verity table version: %s", token.c_str());
 367                 return -1;
 368             }
 369             break;
 370         case 3: /* data_block_size */
 371         case 4: /* hash_block_size */
 372             /* assume 4 KiB block sizes for everything */
 373             if (token != stringify(FEC_BLOCKSIZE)) {
 374                 error("unsupported verity block size: %s", token.c_str());
 375                 return -1;
 376             }
 377             break;
 378         case 5: /* num_data_blocks */
 379             if (parse_uint64(token.c_str(), f->data_size / FEC_BLOCKSIZE,
 380                     &v->data_blocks) == -1) {
 381                 error("invalid number of verity data blocks: %s",
 382                     token.c_str());
 383                 return -1;
 384             }
 385             break;
 386         case 6: /* hash_start_block */
 387             if (parse_uint64(token.c_str(), f->data_size / FEC_BLOCKSIZE,
 388                     &v->hash_start) == -1) {
 389                 error("invalid verity hash start block: %s", token.c_str());
 390                 return -1;
 391             }
 392
 393             v->hash_start *= FEC_BLOCKSIZE;
 394             break;
 395         case 7: /* algorithm */
 396             if (token != "sha256") {
 397                 error("unsupported verity hash algorithm: %s", token.c_str());
 398                 return -1;
 399             }
 400             break;
 401         case 8: /* digest */
 402             if (parse_hex(root, sizeof(root), token.c_str()) == -1) {
 403                 error("invalid verity root hash: %s", token.c_str());
 404                 return -1;
 405             }
 406             break;
 407         case 9: /* salt */
 408             v->salt_size = token.size();
 409             check(v->salt_size % 2 == 0);
 410             v->salt_size /= 2;
 411
 412             salt.reset(new (std::nothrow) uint8_t[v->salt_size]);
 413
 414             if (!salt) {
 415                 errno = ENOMEM;
 416                 return -1;
 417             }
 418
 419             if (parse_hex(salt.get(), v->salt_size, token.c_str()) == -1) {
 420                 error("invalid verity salt: %s", token.c_str());
 421                 return -1;
 422             }
 423             break;
 424         default:
 425             break;
 426         }
 427     }
 428
 429     if (i < VERITY_TABLE_ARGS) {
 430         error("not enough arguments in verity table: %d; expected at least "
 431             stringify(VERITY_TABLE_ARGS), i);
 432         return -1;
 433     }
 434
 435     check(v->hash_start < f->data_size);
 436
 437     if (v->metadata_start < v->hash_start) {
 438         check(v->data_blocks == v->metadata_start / FEC_BLOCKSIZE);
 439     } else {
 440         check(v->data_blocks == v->hash_start / FEC_BLOCKSIZE);
 441     }
 442
 443     if (v->salt) {
 444         delete[] v->salt;
 445         v->salt = NULL;
 446     }
 447
 448     v->salt = salt.release();
 449
 450     if (v->table) {
 451         delete[] v->table;
 452         v->table = NULL;
 453     }
 454
 455     v->table = table.release();
 456
 457     if (!(f->flags & FEC_VERITY_DISABLE)) {
 458         if (verify_tree(f, root) == -1) {
 459             return -1;
 460         }
 461
 462         check(v->hash);
 463
 464         uint8_t zero_block[FEC_BLOCKSIZE];
 465         memset(zero_block, 0, FEC_BLOCKSIZE);
 466
 467         if (verity_hash(f, zero_block, v->zero_hash) == -1) {
 468             error("failed to hash");
 469             return -1;
 470         }
 471     }
 472
 473     return 0;
 474 }
 475
 476 /* rewrites verity metadata block using error corrected data in `f->verity' */
 477 static int rewrite_metadata(fec_handle *f, uint64_t offset)
 478 {
 479     check(f);
 480     check(f->data_size > VERITY_METADATA_SIZE);
 481     check(offset <= f->data_size - VERITY_METADATA_SIZE);
 482
 483     std::unique_ptr<uint8_t[]> metadata(
 484         new (std::nothrow) uint8_t[VERITY_METADATA_SIZE]);
 485
 486     if (!metadata) {
 487         errno = ENOMEM;
 488         return -1;
 489     }
 490
 491     memset(metadata.get(), 0, VERITY_METADATA_SIZE);
 492
 493     verity_info *v = &f->verity;
 494     memcpy(metadata.get(), &v->header, sizeof(v->header));
 495
 496     check(v->table);
 497     size_t len = strlen(v->table);
 498
 499     check(sizeof(v->header) + len <= VERITY_METADATA_SIZE);
 500     memcpy(metadata.get() + sizeof(v->header), v->table, len);
 501
 502     return raw_pwrite(f, metadata.get(), VERITY_METADATA_SIZE, offset);
 503 }
 504
 505 static int validate_header(const fec_handle *f, const verity_header *header,
 506         uint64_t offset)
 507 {
 508     check(f);
 509     check(header);
 510
 511     if (header->magic != VERITY_MAGIC &&
 512         header->magic != VERITY_MAGIC_DISABLE) {
 513         return -1;
 514     }
 515
 516     if (header->version != VERITY_VERSION) {
 517         error("unsupported verity version %u", header->version);
 518         return -1;
 519     }
 520
 521     if (header->length < VERITY_MIN_TABLE_SIZE ||
 522         header->length > VERITY_MAX_TABLE_SIZE) {
 523         error("invalid verity table size: %u; expected ["
 524             stringify(VERITY_MIN_TABLE_SIZE) ", "
 525             stringify(VERITY_MAX_TABLE_SIZE) ")", header->length);
 526         return -1;
 527     }
 528
 529     /* signature is skipped, because for our purposes it won't matter from
 530        where the data originates; the caller of the library is responsible
 531        for signature verification */
 532
 533     if (offset > UINT64_MAX - header->length) {
 534         error("invalid verity table length: %u", header->length);
 535         return -1;
 536     } else if (offset + header->length >= f->data_size) {
 537         error("invalid verity table length: %u", header->length);
 538         return -1;
 539     }
 540
 541     return 0;
 542 }
 543
 544 /* attempts to read verity metadata from `f->fd' position `offset'; if in r/w
 545    mode, rewrites the metadata if it had errors */
 546 int verity_parse_header(fec_handle *f, uint64_t offset)
 547 {
 548     check(f);
 549     check(f->data_size > VERITY_METADATA_SIZE);
 550
 551     if (offset > f->data_size - VERITY_METADATA_SIZE) {
 552         debug("failed to read verity header: offset %" PRIu64 " is too far",
 553             offset);
 554         return -1;
 555     }
 556
 557     verity_info *v = &f->verity;
 558     uint64_t errors = f->errors;
 559
 560     if (!raw_pread(f, &v->header, sizeof(v->header), offset)) {
 561         error("failed to read verity header: %s", strerror(errno));
 562         return -1;
 563     }
 564
 565     /* use raw data to check for the alternative magic, because it will
 566        be error corrected to VERITY_MAGIC otherwise */
 567     if (v->header.magic == VERITY_MAGIC_DISABLE) {
 568         /* this value is not used by us, but can be used by a caller to
 569            decide whether dm-verity should be enabled */
 570         v->disabled = true;
 571     }
 572
 573     if (fec_pread(f, &v->ecc_header, sizeof(v->ecc_header), offset) !=
 574             sizeof(v->ecc_header)) {
 575         warn("failed to read verity header: %s", strerror(errno));
 576         return -1;
 577     }
 578
 579     if (validate_header(f, &v->header, offset)) {
 580         /* raw verity header is invalid; this could be due to corruption, or
 581            due to missing verity metadata */
 582
 583         if (validate_header(f, &v->ecc_header, offset)) {
 584             return -1; /* either way, we cannot recover */
 585         }
 586
 587         /* report mismatching fields */
 588         if (!v->disabled && v->header.magic != v->ecc_header.magic) {
 589             warn("corrected verity header magic");
 590             v->header.magic = v->ecc_header.magic;
 591         }
 592
 593         if (v->header.version != v->ecc_header.version) {
 594             warn("corrected verity header version");
 595             v->header.version = v->ecc_header.version;
 596         }
 597
 598         if (v->header.length != v->ecc_header.length) {
 599             warn("corrected verity header length");
 600             v->header.length = v->ecc_header.length;
 601         }
 602
 603         if (memcmp(v->header.signature, v->ecc_header.signature,
 604                 sizeof(v->header.signature))) {
 605             warn("corrected verity header signature");
 606             /* we have no way of knowing which signature is correct, if either
 607                of them is */
 608         }
 609     }
 610
 611     v->metadata_start = offset;
 612
 613     if (parse_table(f, offset + sizeof(v->header), v->header.length,
 614             false) == -1 &&
 615         parse_table(f, offset + sizeof(v->header), v->header.length,
 616             true)  == -1) {
 617         return -1;
 618     }
 619
 620     /* if we corrected something while parsing metadata and we are in r/w
 621        mode, rewrite the corrected metadata */
 622     if (f->mode & O_RDWR && f->errors > errors &&
 623             rewrite_metadata(f, offset) < 0) {
 624         warn("failed to rewrite verity metadata: %s", strerror(errno));
 625     }
 626
 627     if (v->metadata_start < v->hash_start) {
 628         f->data_size = v->metadata_start;
 629     } else {
 630         f->data_size = v->hash_start;
 631     }
 632
 633     return 0;
 634 }
 635
 636 int fec_verity_set_status(struct fec_handle *f, bool enabled)
 637 {
 638     check(f);
 639
 640     if (!(f->mode & O_RDWR)) {
 641         error("cannot update verity magic: read-only handle");
 642         errno = EBADF;
 643         return -1;
 644     }
 645
 646     verity_info *v = &f->verity;
 647
 648     if (!v->metadata_start) {
 649         error("cannot update verity magic: no metadata found");
 650         errno = EINVAL;
 651         return -1;
 652     }
 653
 654     if (v->disabled == !enabled) {
 655         return 0; /* nothing to do */
 656     }
 657
 658     uint32_t magic = enabled ? VERITY_MAGIC : VERITY_MAGIC_DISABLE;
 659
 660     if (!raw_pwrite(f, &magic, sizeof(magic), v->metadata_start)) {
 661         error("failed to update verity magic to %08x: %s", magic,
 662             strerror(errno));
 663         return -1;
 664     }
 665
 666     warn("updated verity magic to %08x (%s)", magic,
 667         enabled ? "enabled" : "disabled");
 668     v->disabled = !enabled;
 669
 670     return 0;
 671 }