lib/verity/verity_hash.c

   1 /*
   2  * dm-verity volume handling
   3  *
   4  * Copyright (C) 2012, Red Hat, Inc. All rights reserved.
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * version 2 as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19
  20 #include <errno.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <stdint.h>
  25
  26 #include "verity.h"
  27 #include "internal.h"
  28
  29 #define VERITY_MAX_LEVELS       63
  30
  31 static unsigned get_bits_up(size_t u)
  32 {
  33         unsigned i = 0;
  34         while ((1U << i) < u)
  35                 i++;
  36         return i;
  37 }
  38
  39 static unsigned get_bits_down(size_t u)
  40 {
  41         unsigned i = 0;
  42         while ((u >> i) > 1U)
  43                 i++;
  44         return i;
  45 }
  46
  47 static int verify_zero(struct crypt_device *cd, FILE *wr, size_t bytes)
  48 {
  49         char block[bytes];
  50         size_t i;
  51
  52         if (fread(block, bytes, 1, wr) != 1) {
  53                 log_dbg("EIO while reading spare area.");
  54                 return -EIO;
  55         }
  56         for (i = 0; i < bytes; i++)
  57                 if (block[i]) {
  58                         log_err(cd, _("Spare area is not zeroed at position %" PRIu64 ".\n"),
  59                                 ftello(wr) - bytes);
  60                         return -EPERM;
  61                 }
  62         return 0;
  63 }
  64
  65 static int verify_hash_block(const char *hash_name, int version,
  66                               char *hash, size_t hash_size,
  67                               const char *data, size_t data_size,
  68                               const char *salt, size_t salt_size)
  69 {
  70         struct crypt_hash *ctx = NULL;
  71         int r;
  72
  73         if (crypt_hash_init(&ctx, hash_name))
  74                 return -EINVAL;
  75
  76         if (version == 1 && (r = crypt_hash_write(ctx, salt, salt_size)))
  77                 goto out;
  78
  79         if ((r = crypt_hash_write(ctx, data, data_size)))
  80                 goto out;
  81
  82         if (version == 0 && (r = crypt_hash_write(ctx, salt, salt_size)))
  83                 goto out;
  84
  85         r = crypt_hash_final(ctx, hash, hash_size);
  86 out:
  87         crypt_hash_destroy(ctx);
  88         return r;
  89 }
  90
  91 static int mult_overflow(off_t *u, off_t b, size_t size)
  92 {
  93         *u = (uint64_t)b * size;
  94         if ((off_t)(*u / size) != b || (off_t)*u < 0)
  95                 return 1;
  96         return 0;
  97 }
  98
  99 static int create_or_verify(struct crypt_device *cd, FILE *rd, FILE *wr,
 100                                    off_t data_block, size_t data_block_size,
 101                                    off_t hash_block, size_t hash_block_size,
 102                                    off_t blocks, int version,
 103                                    const char *hash_name, int verify,
 104                                    char *calculated_digest, size_t digest_size,
 105                                    const char *salt, size_t salt_size)
 106 {
 107         char left_block[hash_block_size];
 108         char data_buffer[data_block_size];
 109         char read_digest[digest_size];
 110         size_t hash_per_block = 1 << get_bits_down(hash_block_size / digest_size);
 111         size_t digest_size_full = 1 << get_bits_up(digest_size);
 112         off_t blocks_to_write = (blocks + hash_per_block - 1) / hash_per_block;
 113         off_t seek_rd, seek_wr;
 114         size_t left_bytes;
 115         unsigned i;
 116         int r;
 117
 118         if (mult_overflow(&seek_rd, data_block, data_block_size) ||
 119             mult_overflow(&seek_wr, hash_block, hash_block_size)) {
 120                 log_err(cd, _("Device offset overflow.\n"));
 121                 return -EINVAL;
 122         }
 123
 124         if (fseeko(rd, seek_rd, SEEK_SET)) {
 125                 log_dbg("Cannot seek to requested position in data device.");
 126                 return -EIO;
 127         }
 128
 129         if (wr && fseeko(wr, seek_wr, SEEK_SET)) {
 130                 log_dbg("Cannot seek to requested position in hash device.");
 131                 return -EIO;
 132         }
 133
 134         memset(left_block, 0, hash_block_size);
 135         while (blocks_to_write--) {
 136                 left_bytes = hash_block_size;
 137                 for (i = 0; i < hash_per_block; i++) {
 138                         if (!blocks)
 139                                 break;
 140                         blocks--;
 141                         if (fread(data_buffer, data_block_size, 1, rd) != 1) {
 142                                 log_dbg("Cannot read data device block.");
 143                                 return -EIO;
 144                         }
 145
 146                         if (verify_hash_block(hash_name, version,
 147                                         calculated_digest, digest_size,
 148                                         data_buffer, data_block_size,
 149                                         salt, salt_size))
 150                                 return -EINVAL;
 151
 152                         if (!wr)
 153                                 break;
 154                         if (verify) {
 155                                 if (fread(read_digest, digest_size, 1, wr) != 1) {
 156                                         log_dbg("Cannot read digest form hash device.");
 157                                         return -EIO;
 158                                 }
 159                                 if (memcmp(read_digest, calculated_digest, digest_size)) {
 160                                         log_err(cd, _("Verification failed at position %" PRIu64 ".\n"),
 161                                                 ftello(rd) - data_block_size);
 162                                         return -EPERM;
 163                                 }
 164                         } else {
 165                                 if (fwrite(calculated_digest, digest_size, 1, wr) != 1) {
 166                                         log_dbg("Cannot write digest to hash device.");
 167                                         return -EIO;
 168                                 }
 169                         }
 170                         if (version == 0) {
 171                                 left_bytes -= digest_size;
 172                         } else {
 173                                 if (digest_size_full - digest_size) {
 174                                         if (verify) {
 175                                                 r = verify_zero(cd, wr, digest_size_full - digest_size);
 176                                                 if (r)
 177                                                         return r;
 178                                         } else if (fwrite(left_block, digest_size_full - digest_size, 1, wr) != 1) {
 179                                                 log_dbg("Cannot write spare area to hash device.");
 180                                                 return -EIO;
 181                                         }
 182                                 }
 183                                 left_bytes -= digest_size_full;
 184                         }
 185                 }
 186                 if (wr && left_bytes) {
 187                         if (verify) {
 188                                 r = verify_zero(cd , wr, left_bytes);
 189                                 if (r)
 190                                         return r;
 191                         } else if (fwrite(left_block, left_bytes, 1, wr) != 1) {
 192                                 log_dbg("Cannot write remaining spare area to hash device.");
 193                                 return -EIO;
 194                         }
 195                 }
 196         }
 197
 198         return 0;
 199 }
 200
 201 static int VERITY_create_or_verify_hash(struct crypt_device *cd,
 202         int verify,
 203         int version,
 204         const char *hash_name,
 205         struct device *hash_device,
 206         struct device *data_device,
 207         size_t hash_block_size,
 208         size_t data_block_size,
 209         off_t data_blocks,
 210         off_t hash_position,
 211         char *root_hash,
 212         size_t digest_size,
 213         const char *salt,
 214         size_t salt_size)
 215 {
 216         char calculated_digest[digest_size];
 217         FILE *data_file = NULL;
 218         FILE *hash_file = NULL, *hash_file_2;
 219         off_t hash_level_block[VERITY_MAX_LEVELS];
 220         off_t hash_level_size[VERITY_MAX_LEVELS];
 221         off_t data_file_blocks, s;
 222         size_t hash_per_block, hash_per_block_bits;
 223         off_t data_device_size = 0, hash_device_size = 0;
 224         uint64_t dev_size;
 225         int levels, i, r;
 226
 227         log_dbg("Hash %s %s, data device %s, data blocks %" PRIu64
 228                 ", hash_device %s, offset %" PRIu64 ".",
 229                 verify ? "verification" : "creation", hash_name,
 230                 device_path(data_device), data_blocks,
 231                 device_path(hash_device), hash_position);
 232
 233         if (data_blocks < 0 || hash_position < 0) {
 234                 log_err(cd, _("Invalid size parameters for verity device.\n"));
 235                 return -EINVAL;
 236         }
 237
 238         if (!data_blocks) {
 239                 r = device_size(data_device, &dev_size);
 240                 if (r < 0)
 241                         return r;
 242
 243                 data_file_blocks = dev_size / data_block_size;
 244         } else
 245                 data_file_blocks = data_blocks;
 246
 247         if (mult_overflow(&data_device_size, data_blocks, data_block_size)) {
 248                 log_err(cd, _("Device offset overflow.\n"));
 249                 return -EINVAL;
 250         }
 251
 252         hash_per_block_bits = get_bits_down(hash_block_size / digest_size);
 253         hash_per_block = 1 << hash_per_block_bits;
 254         if (!hash_per_block_bits)
 255                 return -EINVAL;
 256
 257         levels = 0;
 258         if (data_file_blocks) {
 259                 while (hash_per_block_bits * levels < 64 &&
 260                        (data_file_blocks - 1) >> (hash_per_block_bits * levels))
 261                         levels++;
 262         }
 263         log_dbg("Using %d hash levels.", levels);
 264
 265         if (levels > VERITY_MAX_LEVELS) {
 266                 log_err(cd, _("Too many tree levels for verity volume.\n"));
 267                 return -EINVAL;
 268         }
 269
 270         for (i = levels - 1; i >= 0; i--) {
 271                 hash_level_block[i] = hash_position;
 272                 // verity position of block data_file_blocks at level i
 273                 s = data_file_blocks >> (i * hash_per_block_bits);
 274                 s = (s + hash_per_block - 1) / hash_per_block;
 275                 hash_level_size[i] = s;
 276                 if ((hash_position + s) < hash_position ||
 277                     (hash_position + s) < 0) {
 278                         log_err(cd, _("Device offset overflow.\n"));
 279                         return -EINVAL;
 280                 }
 281                 hash_position += s;
 282         }
 283
 284         if (mult_overflow(&hash_device_size, hash_position, hash_block_size)) {
 285                 log_err(cd, _("Device offset overflow.\n"));
 286                 return -EINVAL;
 287         }
 288
 289         log_dbg("Data device size required: %" PRIu64 " bytes.",
 290                 data_device_size);
 291         data_file = fopen(device_path(data_device), "r");
 292         if (!data_file) {
 293                 log_err(cd, _("Cannot open device %s.\n"),
 294                         device_path(data_device)
 295                 );
 296                 r = -EIO;
 297                 goto out;
 298         }
 299
 300         log_dbg("Hash device size required: %" PRIu64 " bytes.",
 301                 hash_device_size);
 302         hash_file = fopen(device_path(hash_device), verify ? "r" : "r+");
 303         if (!hash_file) {
 304                 log_err(cd, _("Cannot open device %s.\n"),
 305                         device_path(hash_device));
 306                 r = -EIO;
 307                 goto out;
 308         }
 309
 310         memset(calculated_digest, 0, digest_size);
 311
 312         for (i = 0; i < levels; i++) {
 313                 if (!i) {
 314                         r = create_or_verify(cd, data_file, hash_file,
 315                                                     0, data_block_size,
 316                                                     hash_level_block[i], hash_block_size,
 317                                                     data_file_blocks, version, hash_name, verify,
 318                                                     calculated_digest, digest_size, salt, salt_size);
 319                         if (r)
 320                                 goto out;
 321                 } else {
 322                         hash_file_2 = fopen(device_path(hash_device), "r");
 323                         if (!hash_file_2) {
 324                                 log_err(cd, _("Cannot open device %s.\n"),
 325                                         device_path(hash_device));
 326                                 r = -EIO;
 327                                 goto out;
 328                         }
 329                         r = create_or_verify(cd, hash_file_2, hash_file,
 330                                                     hash_level_block[i - 1], hash_block_size,
 331                                                     hash_level_block[i], hash_block_size,
 332                                                     hash_level_size[i - 1], version, hash_name, verify,
 333                                                     calculated_digest, digest_size, salt, salt_size);
 334                         fclose(hash_file_2);
 335                         if (r)
 336                                 goto out;
 337                 }
 338         }
 339
 340         if (levels)
 341                 r = create_or_verify(cd, hash_file, NULL,
 342                                             hash_level_block[levels - 1], hash_block_size,
 343                                             0, hash_block_size,
 344                                             1, version, hash_name, verify,
 345                                             calculated_digest, digest_size, salt, salt_size);
 346         else
 347                 r = create_or_verify(cd, data_file, NULL,
 348                                             0, data_block_size,
 349                                             0, hash_block_size,
 350                                             data_file_blocks, version, hash_name, verify,
 351                                             calculated_digest, digest_size, salt, salt_size);
 352 out:
 353         if (verify) {
 354                 if (r)
 355                         log_err(cd, _("Verification of data area failed.\n"));
 356                 else {
 357                         log_dbg("Verification of data area succeeded.");
 358                         r = memcmp(root_hash, calculated_digest, digest_size) ? -EPERM : 0;
 359                         if (r)
 360                                 log_err(cd, _("Verification of root hash failed.\n"));
 361                         else
 362                                 log_dbg("Verification of root hash succeeded.");
 363                 }
 364         } else {
 365                 if (r == -EIO)
 366                         log_err(cd, _("Input/output error while creating hash area.\n"));
 367                 else if (r)
 368                         log_err(cd, _("Creation of hash area failed.\n"));
 369                 else {
 370                         fsync(fileno(hash_file));
 371                         memcpy(root_hash, calculated_digest, digest_size);
 372                 }
 373         }
 374
 375         if (data_file)
 376                 fclose(data_file);
 377         if (hash_file)
 378                 fclose(hash_file);
 379         return r;
 380 }
 381
 382 /* Verify verity device using userspace crypto backend */
 383 int VERITY_verify(struct crypt_device *cd,
 384                   struct crypt_params_verity *verity_hdr,
 385                   const char *root_hash,
 386                   size_t root_hash_size)
 387 {
 388         return VERITY_create_or_verify_hash(cd, 1,
 389                 verity_hdr->hash_type,
 390                 verity_hdr->hash_name,
 391                 crypt_metadata_device(cd),
 392                 crypt_data_device(cd),
 393                 verity_hdr->hash_block_size,
 394                 verity_hdr->data_block_size,
 395                 verity_hdr->data_size,
 396                 VERITY_hash_offset_block(verity_hdr),
 397                 CONST_CAST(char*)root_hash,
 398                 root_hash_size,
 399                 verity_hdr->salt,
 400                 verity_hdr->salt_size);
 401 }
 402
 403 /* Create verity hash */
 404 int VERITY_create(struct crypt_device *cd,
 405                   struct crypt_params_verity *verity_hdr,
 406                   char *root_hash,
 407                   size_t root_hash_size)
 408 {
 409         unsigned pgsize = crypt_getpagesize();
 410
 411         if (verity_hdr->salt_size > 256)
 412                 return -EINVAL;
 413
 414         if (verity_hdr->data_block_size > pgsize)
 415                 log_err(cd, _("WARNING: Kernel cannot activate device if data "
 416                               "block size exceeds page size (%u).\n"), pgsize);
 417
 418         return VERITY_create_or_verify_hash(cd, 0,
 419                 verity_hdr->hash_type,
 420                 verity_hdr->hash_name,
 421                 crypt_metadata_device(cd),
 422                 crypt_data_device(cd),
 423                 verity_hdr->hash_block_size,
 424                 verity_hdr->data_block_size,
 425                 verity_hdr->data_size,
 426                 VERITY_hash_offset_block(verity_hdr),
 427                 root_hash,
 428                 root_hash_size,
 429                 verity_hdr->salt,
 430                 verity_hdr->salt_size);
 431 }