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