fec_verity.cpp revision dadd5e33ac00df9a57114487f8441a59fd08bd89 
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   compares it to the expected value in `expected' */
140bool 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 */
159static 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' */
185static 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    v->hash = data_hashes.release();
316    return 0;
317}
318
319/* reads, corrects and parses the verity table, validates parameters, and if
320   `f->flags' does not have `FEC_VERITY_DISABLE' set, calls `verify_tree' to
321   load and validate the hash tree */
322static int parse_table(fec_handle *f, uint64_t offset, uint32_t size)
323{
324    check(f);
325    check(size >= VERITY_MIN_TABLE_SIZE);
326    check(size <= VERITY_MAX_TABLE_SIZE);
327
328    debug("offset = %" PRIu64 ", size = %u", offset, size);
329
330    verity_info *v = &f->verity;
331    std::unique_ptr<char[]> table(new (std::nothrow) char[size + 1]);
332
333    if (!table) {
334        errno = ENOMEM;
335        return -1;
336    }
337
338    if (fec_pread(f, table.get(), size, offset) != (ssize_t)size) {
339        error("failed to read verity table: %s", strerror(errno));
340        return -1;
341    }
342
343    table[size] = '\0';
344    debug("verity table: '%s'", table.get());
345
346    int i = 0;
347    std::unique_ptr<uint8_t[]> salt;
348    uint8_t root[SHA256_DIGEST_LENGTH];
349
350    auto tokens = android::base::Split(table.get(), " ");
351
352    for (const auto token : tokens) {
353        switch (i++) {
354        case 0: /* version */
355            if (token != stringify(VERITY_TABLE_VERSION)) {
356                error("unsupported verity table version: %s", token.c_str());
357                return -1;
358            }
359            break;
360        case 3: /* data_block_size */
361        case 4: /* hash_block_size */
362            /* assume 4 KiB block sizes for everything */
363            if (token != stringify(FEC_BLOCKSIZE)) {
364                error("unsupported verity block size: %s", token.c_str());
365                return -1;
366            }
367            break;
368        case 5: /* num_data_blocks */
369            if (parse_uint64(token.c_str(), f->data_size / FEC_BLOCKSIZE,
370                    &v->data_blocks) == -1) {
371                error("invalid number of verity data blocks: %s",
372                    token.c_str());
373                return -1;
374            }
375            break;
376        case 6: /* hash_start_block */
377            if (parse_uint64(token.c_str(), f->data_size / FEC_BLOCKSIZE,
378                    &v->hash_start) == -1) {
379                error("invalid verity hash start block: %s", token.c_str());
380                return -1;
381            }
382
383            v->hash_start *= FEC_BLOCKSIZE;
384            break;
385        case 7: /* algorithm */
386            if (token != "sha256") {
387                error("unsupported verity hash algorithm: %s", token.c_str());
388                return -1;
389            }
390            break;
391        case 8: /* digest */
392            if (parse_hex(root, sizeof(root), token.c_str()) == -1) {
393                error("invalid verity root hash: %s", token.c_str());
394                return -1;
395            }
396            break;
397        case 9: /* salt */
398            v->salt_size = token.size();
399            check(v->salt_size % 2 == 0);
400            v->salt_size /= 2;
401
402            salt.reset(new (std::nothrow) uint8_t[v->salt_size]);
403
404            if (!salt) {
405                errno = ENOMEM;
406                return -1;
407            }
408
409            if (parse_hex(salt.get(), v->salt_size, token.c_str()) == -1) {
410                error("invalid verity salt: %s", token.c_str());
411                return -1;
412            }
413            break;
414        default:
415            break;
416        }
417    }
418
419    if (i < VERITY_TABLE_ARGS) {
420        error("not enough arguments in verity table: %d; expected at least "
421            stringify(VERITY_TABLE_ARGS), i);
422        return -1;
423    }
424
425    check(v->hash_start < f->data_size);
426
427    if (v->metadata_start < v->hash_start) {
428        check(v->data_blocks == v->metadata_start / FEC_BLOCKSIZE);
429    } else {
430        check(v->data_blocks == v->hash_start / FEC_BLOCKSIZE);
431    }
432
433    v->salt = salt.release();
434    v->table = table.release();
435
436    if (!(f->flags & FEC_VERITY_DISABLE)) {
437        if (verify_tree(f, root) == -1) {
438            return -1;
439        }
440
441        check(v->hash);
442
443        uint8_t zero_block[FEC_BLOCKSIZE];
444        memset(zero_block, 0, FEC_BLOCKSIZE);
445
446        if (verity_hash(f, zero_block, v->zero_hash) == -1) {
447            error("failed to hash");
448            return -1;
449        }
450    }
451
452    return 0;
453}
454
455/* rewrites verity metadata block using error corrected data in `f->verity' */
456static int rewrite_metadata(fec_handle *f, uint64_t offset)
457{
458    check(f);
459    check(f->data_size > VERITY_METADATA_SIZE);
460    check(offset <= f->data_size - VERITY_METADATA_SIZE);
461
462    std::unique_ptr<uint8_t[]> metadata(
463        new (std::nothrow) uint8_t[VERITY_METADATA_SIZE]);
464
465    if (!metadata) {
466        errno = ENOMEM;
467        return -1;
468    }
469
470    memset(metadata.get(), 0, VERITY_METADATA_SIZE);
471
472    verity_info *v = &f->verity;
473    memcpy(metadata.get(), &v->header, sizeof(v->header));
474
475    check(v->table);
476    size_t len = strlen(v->table);
477
478    check(sizeof(v->header) + len <= VERITY_METADATA_SIZE);
479    memcpy(metadata.get() + sizeof(v->header), v->table, len);
480
481    return raw_pwrite(f, metadata.get(), VERITY_METADATA_SIZE, offset);
482}
483
484/* attempts to read verity metadata from `f->fd' position `offset'; if in r/w
485   mode, rewrites the metadata if it had errors */
486int verity_parse_header(fec_handle *f, uint64_t offset)
487{
488    check(f);
489    check(f->data_size > VERITY_METADATA_SIZE);
490
491    if (offset > f->data_size - VERITY_METADATA_SIZE) {
492        debug("failed to read verity header: offset %" PRIu64 " is too far",
493            offset);
494        return -1;
495    }
496
497    verity_info *v = &f->verity;
498    uint64_t errors = f->errors;
499
500    if (fec_pread(f, &v->header, sizeof(v->header), offset) !=
501            sizeof(v->header)) {
502        error("failed to read verity header: %s", strerror(errno));
503        return -1;
504    }
505
506    verity_header raw_header;
507
508    if (!raw_pread(f, &raw_header, sizeof(raw_header), offset)) {
509        error("failed to read verity header: %s", strerror(errno));
510        return -1;
511    }
512    /* use raw data to check for the alternative magic, because it will
513       be error corrected to VERITY_MAGIC otherwise */
514    if (raw_header.magic == VERITY_MAGIC_DISABLE) {
515        /* this value is not used by us, but can be used by a caller to
516           decide whether dm-verity should be enabled */
517        v->disabled = true;
518    } else if (v->header.magic != VERITY_MAGIC) {
519        return -1;
520    }
521
522    if (v->header.version != VERITY_VERSION) {
523        error("unsupported verity version %u", v->header.version);
524        return -1;
525    }
526
527    if (v->header.length < VERITY_MIN_TABLE_SIZE ||
528        v->header.length > VERITY_MAX_TABLE_SIZE) {
529        error("invalid verity table size: %u; expected ["
530            stringify(VERITY_MIN_TABLE_SIZE) ", "
531            stringify(VERITY_MAX_TABLE_SIZE) ")", v->header.length);
532        return -1;
533    }
534
535    v->metadata_start = offset;
536
537    /* signature is skipped, because for our purposes it won't matter from
538       where the data originates; the caller of the library is responsible
539       for signature verification */
540
541    if (offset > UINT64_MAX - v->header.length) {
542        error("invalid verity table length: %u", v->header.length);
543        return -1;
544    } else if (offset + v->header.length >= f->data_size) {
545        error("invalid verity table length: %u", v->header.length);
546        return -1;
547    }
548
549    if (parse_table(f, offset + sizeof(v->header), v->header.length) == -1) {
550        return -1;
551    }
552
553    /* if we corrected something while parsing metadata and we are in r/w
554       mode, rewrite the corrected metadata */
555    if (f->mode & O_RDWR && f->errors > errors &&
556            rewrite_metadata(f, offset) < 0) {
557        warn("failed to rewrite verity metadata: %s", strerror(errno));
558    }
559
560    if (v->metadata_start < v->hash_start) {
561        f->data_size = v->metadata_start;
562    } else {
563        f->data_size = v->hash_start;
564    }
565
566    return 0;
567}
568
569int fec_verity_set_status(struct fec_handle *f, bool enabled)
570{
571    check(f);
572
573    if (!(f->mode & O_RDWR)) {
574        error("cannot update verity magic: read-only handle");
575        errno = EBADF;
576        return -1;
577    }
578
579    verity_info *v = &f->verity;
580
581    if (!v->metadata_start) {
582        error("cannot update verity magic: no metadata found");
583        errno = EINVAL;
584        return -1;
585    }
586
587    if (v->disabled == !enabled) {
588        return 0; /* nothing to do */
589    }
590
591    uint32_t magic = enabled ? VERITY_MAGIC : VERITY_MAGIC_DISABLE;
592
593    if (!raw_pwrite(f, &magic, sizeof(magic), v->metadata_start)) {
594        error("failed to update verity magic to %08x: %s", magic,
595            strerror(errno));
596        return -1;
597    }
598
599    warn("updated verity magic to %08x (%s)", magic,
600        enabled ? "enabled" : "disabled");
601    v->disabled = !enabled;
602
603    return 0;
604}
605