lib/verity/verity_hash.c

   1 /*
   2  * dm-verity volume handling
   3  *
   4  * Copyright (C) 2012-2023 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 #define VERITY_MAX_DIGEST_SIZE  1024
  32
  33 static unsigned get_bits_up(size_t u)
  34 {
  35         unsigned i = 0;
  36         while ((1U << i) < u)
  37                 i++;
  38         return i;
  39 }
  40
  41 static unsigned get_bits_down(size_t u)
  42 {
  43         unsigned i = 0;
  44         while ((u >> i) > 1U)
  45                 i++;
  46         return i;
  47 }
  48
  49 static int verify_zero(struct crypt_device *cd, FILE *wr, size_t bytes)
  50 {
  51         char *block = NULL;
  52         size_t i;
  53         int r;
  54
  55         block = malloc(bytes);
  56         if (!block)
  57                 return -ENOMEM;
  58
  59         if (fread(block, bytes, 1, wr) != 1) {
  60                 log_dbg(cd, "EIO while reading spare area.");
  61                 r = -EIO;
  62                 goto out;
  63         }
  64         for (i = 0; i < bytes; i++)
  65                 if (block[i]) {
  66                         log_err(cd, _("Spare area is not zeroed at position %" PRIu64 "."),
  67                                 ftello(wr) - bytes);
  68                         r = -EPERM;
  69                         goto out;
  70                 }
  71         r = 0;
  72 out:
  73         free(block);
  74         return r;
  75 }
  76
  77 static int verify_hash_block(const char *hash_name, int version,
  78                               char *hash, size_t hash_size,
  79                               const char *data, size_t data_size,
  80                               const char *salt, size_t salt_size)
  81 {
  82         struct crypt_hash *ctx = NULL;
  83         int r;
  84
  85         if (crypt_hash_init(&ctx, hash_name))
  86                 return -EINVAL;
  87
  88         if (version == 1 && (r = crypt_hash_write(ctx, salt, salt_size)))
  89                 goto out;
  90
  91         if ((r = crypt_hash_write(ctx, data, data_size)))
  92                 goto out;
  93
  94         if (version == 0 && (r = crypt_hash_write(ctx, salt, salt_size)))
  95                 goto out;
  96
  97         r = crypt_hash_final(ctx, hash, hash_size);
  98 out:
  99         crypt_hash_destroy(ctx);
 100         return r;
 101 }
 102
 103 static int hash_levels(size_t hash_block_size, size_t digest_size,
 104                        uint64_t data_file_blocks, uint64_t *hash_position, int *levels,
 105                        uint64_t *hash_level_block, uint64_t *hash_level_size)
 106 {
 107         size_t hash_per_block_bits;
 108         uint64_t s, s_shift;
 109         int i;
 110
 111         if (!digest_size)
 112                 return -EINVAL;
 113
 114         hash_per_block_bits = get_bits_down(hash_block_size / digest_size);
 115         if (!hash_per_block_bits)
 116                 return -EINVAL;
 117
 118         *levels = 0;
 119         while (hash_per_block_bits * *levels < 64 &&
 120                (data_file_blocks - 1) >> (hash_per_block_bits * *levels))
 121                 (*levels)++;
 122
 123         if (*levels > VERITY_MAX_LEVELS)
 124                 return -EINVAL;
 125
 126         for (i = *levels - 1; i >= 0; i--) {
 127                 if (hash_level_block)
 128                         hash_level_block[i] = *hash_position;
 129                 // verity position of block data_file_blocks at level i
 130                 s_shift = (i + 1) * hash_per_block_bits;
 131                 if (s_shift > 63)
 132                         return -EINVAL;
 133                 s = (data_file_blocks + ((uint64_t)1 << s_shift) - 1) >> ((i + 1) * hash_per_block_bits);
 134                 if (hash_level_size)
 135                         hash_level_size[i] = s;
 136                 if ((*hash_position + s) < *hash_position)
 137                         return -EINVAL;
 138                 *hash_position += s;
 139         }
 140
 141         return 0;
 142 }
 143
 144 static int create_or_verify(struct crypt_device *cd, FILE *rd, FILE *wr,
 145                                    uint64_t data_block, size_t data_block_size,
 146                                    uint64_t hash_block, size_t hash_block_size,
 147                                    uint64_t blocks, int version,
 148                                    const char *hash_name, int verify,
 149                                    char *calculated_digest, size_t digest_size,
 150                                    const char *salt, size_t salt_size)
 151 {
 152         char *left_block, *data_buffer;
 153         char read_digest[VERITY_MAX_DIGEST_SIZE];
 154         size_t hash_per_block = 1 << get_bits_down(hash_block_size / digest_size);
 155         size_t digest_size_full = 1 << get_bits_up(digest_size);
 156         uint64_t blocks_to_write = (blocks + hash_per_block - 1) / hash_per_block;
 157         uint64_t seek_rd, seek_wr;
 158         size_t left_bytes;
 159         unsigned i;
 160         int r;
 161
 162         if (digest_size > sizeof(read_digest))
 163                 return -EINVAL;
 164
 165         if (uint64_mult_overflow(&seek_rd, data_block, data_block_size) ||
 166             uint64_mult_overflow(&seek_wr, hash_block, hash_block_size)) {
 167                 log_err(cd, _("Device offset overflow."));
 168                 return -EINVAL;
 169         }
 170
 171         if (fseeko(rd, seek_rd, SEEK_SET)) {
 172                 log_dbg(cd, "Cannot seek to requested position in data device.");
 173                 return -EIO;
 174         }
 175
 176         if (wr && fseeko(wr, seek_wr, SEEK_SET)) {
 177                 log_dbg(cd, "Cannot seek to requested position in hash device.");
 178                 return -EIO;
 179         }
 180
 181         left_block = malloc(hash_block_size);
 182         data_buffer = malloc(data_block_size);
 183         if (!left_block || !data_buffer) {
 184                 r = -ENOMEM;
 185                 goto out;
 186         }
 187
 188         memset(left_block, 0, hash_block_size);
 189         while (blocks_to_write--) {
 190                 left_bytes = hash_block_size;
 191                 for (i = 0; i < hash_per_block; i++) {
 192                         if (!blocks)
 193                                 break;
 194                         blocks--;
 195                         if (fread(data_buffer, data_block_size, 1, rd) != 1) {
 196                                 log_dbg(cd, "Cannot read data device block.");
 197                                 r = -EIO;
 198                                 goto out;
 199                         }
 200
 201                         if (verify_hash_block(hash_name, version,
 202                                         calculated_digest, digest_size,
 203                                         data_buffer, data_block_size,
 204                                         salt, salt_size)) {
 205                                 r = -EINVAL;
 206                                 goto out;
 207                         }
 208
 209                         if (!wr)
 210                                 break;
 211                         if (verify) {
 212                                 if (fread(read_digest, digest_size, 1, wr) != 1) {
 213                                         log_dbg(cd, "Cannot read digest form hash device.");
 214                                         r = -EIO;
 215                                         goto out;
 216                                 }
 217                                 if (crypt_backend_memeq(read_digest, calculated_digest, digest_size)) {
 218                                         log_err(cd, _("Verification failed at position %" PRIu64 "."),
 219                                                 ftello(rd) - data_block_size);
 220                                         r = -EPERM;
 221                                         goto out;
 222                                 }
 223                         } else {
 224                                 if (fwrite(calculated_digest, digest_size, 1, wr) != 1) {
 225                                         log_dbg(cd, "Cannot write digest to hash device.");
 226                                         r = -EIO;
 227                                         goto out;
 228                                 }
 229                         }
 230                         if (version == 0) {
 231                                 left_bytes -= digest_size;
 232                         } else {
 233                                 if (digest_size_full - digest_size) {
 234                                         if (verify) {
 235                                                 r = verify_zero(cd, wr, digest_size_full - digest_size);
 236                                                 if (r)
 237                                                         goto out;
 238                                         } else if (fwrite(left_block, digest_size_full - digest_size, 1, wr) != 1) {
 239                                                 log_dbg(cd, "Cannot write spare area to hash device.");
 240                                                 r = -EIO;
 241                                                 goto out;
 242                                         }
 243                                 }
 244                                 left_bytes -= digest_size_full;
 245                         }
 246                 }
 247                 if (wr && left_bytes) {
 248                         if (verify) {
 249                                 r = verify_zero(cd , wr, left_bytes);
 250                                 if (r)
 251                                         goto out;
 252                         } else if (fwrite(left_block, left_bytes, 1, wr) != 1) {
 253                                 log_dbg(cd, "Cannot write remaining spare area to hash device.");
 254                                 r = -EIO;
 255                                 goto out;
 256                         }
 257                 }
 258         }
 259         r = 0;
 260 out:
 261         free(left_block);
 262         free(data_buffer);
 263         return r;
 264 }
 265
 266 static int VERITY_create_or_verify_hash(struct crypt_device *cd, bool verify,
 267         struct crypt_params_verity *params,
 268         char *root_hash, size_t digest_size)
 269 {
 270         char calculated_digest[VERITY_MAX_DIGEST_SIZE];
 271         FILE *data_file = NULL;
 272         FILE *hash_file = NULL, *hash_file_2;
 273         uint64_t hash_level_block[VERITY_MAX_LEVELS];
 274         uint64_t hash_level_size[VERITY_MAX_LEVELS];
 275         uint64_t data_file_blocks;
 276         uint64_t data_device_offset_max = 0, hash_device_offset_max = 0;
 277         uint64_t hash_position = VERITY_hash_offset_block(params);
 278         uint64_t dev_size;
 279         int levels, i, r;
 280
 281         log_dbg(cd, "Hash %s %s, data device %s, data blocks %" PRIu64
 282                 ", hash_device %s, offset %" PRIu64 ".",
 283                 verify ? "verification" : "creation", params->hash_name,
 284                 device_path(crypt_data_device(cd)), params->data_size,
 285                 device_path(crypt_metadata_device(cd)), hash_position);
 286
 287         if (digest_size > sizeof(calculated_digest))
 288                 return -EINVAL;
 289
 290         if (!params->data_size) {
 291                 r = device_size(crypt_data_device(cd), &dev_size);
 292                 if (r < 0)
 293                         return r;
 294
 295                 data_file_blocks = dev_size / params->data_block_size;
 296         } else
 297                 data_file_blocks = params->data_size;
 298
 299         if (uint64_mult_overflow(&data_device_offset_max, params->data_size, params->data_block_size)) {
 300                 log_err(cd, _("Device offset overflow."));
 301                 return -EINVAL;
 302         }
 303         log_dbg(cd, "Data device size required: %" PRIu64 " bytes.", data_device_offset_max);
 304
 305         if (hash_levels(params->hash_block_size, digest_size, data_file_blocks, &hash_position,
 306                 &levels, &hash_level_block[0], &hash_level_size[0])) {
 307                 log_err(cd, _("Hash area overflow."));
 308                 return -EINVAL;
 309         }
 310         if (uint64_mult_overflow(&hash_device_offset_max, hash_position, params->hash_block_size)) {
 311                 log_err(cd, _("Device offset overflow."));
 312                 return -EINVAL;
 313         }
 314         log_dbg(cd, "Hash device size required: %" PRIu64 " bytes.",
 315                 hash_device_offset_max - params->hash_area_offset);
 316         log_dbg(cd, "Using %d hash levels.", levels);
 317
 318         data_file = fopen(device_path(crypt_data_device(cd)), "r");
 319         if (!data_file) {
 320                 log_err(cd, _("Cannot open device %s."),
 321                         device_path(crypt_data_device(cd))
 322                 );
 323                 r = -EIO;
 324                 goto out;
 325         }
 326
 327         hash_file = fopen(device_path(crypt_metadata_device(cd)), verify ? "r" : "r+");
 328         if (!hash_file) {
 329                 log_err(cd, _("Cannot open device %s."),
 330                         device_path(crypt_metadata_device(cd)));
 331                 r = -EIO;
 332                 goto out;
 333         }
 334
 335         memset(calculated_digest, 0, digest_size);
 336
 337         for (i = 0; i < levels; i++) {
 338                 if (!i) {
 339                         r = create_or_verify(cd, data_file, hash_file,
 340                                                     0, params->data_block_size,
 341                                                     hash_level_block[i], params->hash_block_size,
 342                                                     data_file_blocks, params->hash_type, params->hash_name, verify,
 343                                                     calculated_digest, digest_size, params->salt, params->salt_size);
 344                         if (r)
 345                                 goto out;
 346                 } else {
 347                         hash_file_2 = fopen(device_path(crypt_metadata_device(cd)), "r");
 348                         if (!hash_file_2) {
 349                                 log_err(cd, _("Cannot open device %s."),
 350                                         device_path(crypt_metadata_device(cd)));
 351                                 r = -EIO;
 352                                 goto out;
 353                         }
 354                         r = create_or_verify(cd, hash_file_2, hash_file,
 355                                                     hash_level_block[i - 1], params->hash_block_size,
 356                                                     hash_level_block[i], params->hash_block_size,
 357                                                     hash_level_size[i - 1], params->hash_type, params->hash_name, verify,
 358                                                     calculated_digest, digest_size, params->salt, params->salt_size);
 359                         fclose(hash_file_2);
 360                         if (r)
 361                                 goto out;
 362                 }
 363         }
 364
 365         if (levels)
 366                 r = create_or_verify(cd, hash_file, NULL,
 367                                             hash_level_block[levels - 1], params->hash_block_size,
 368                                             0, params->hash_block_size,
 369                                             1, params->hash_type, params->hash_name, verify,
 370                                             calculated_digest, digest_size, params->salt, params->salt_size);
 371         else
 372                 r = create_or_verify(cd, data_file, NULL,
 373                                             0, params->data_block_size,
 374                                             0, params->hash_block_size,
 375                                             data_file_blocks, params->hash_type, params->hash_name, verify,
 376                                             calculated_digest, digest_size, params->salt, params->salt_size);
 377 out:
 378         if (verify) {
 379                 if (r)
 380                         log_err(cd, _("Verification of data area failed."));
 381                 else {
 382                         log_dbg(cd, "Verification of data area succeeded.");
 383                         r = crypt_backend_memeq(root_hash, calculated_digest, digest_size) ? -EFAULT : 0;
 384                         if (r)
 385                                 log_err(cd, _("Verification of root hash failed."));
 386                         else
 387                                 log_dbg(cd, "Verification of root hash succeeded.");
 388                 }
 389         } else {
 390                 if (r == -EIO)
 391                         log_err(cd, _("Input/output error while creating hash area."));
 392                 else if (r)
 393                         log_err(cd, _("Creation of hash area failed."));
 394                 else {
 395                         fsync(fileno(hash_file));
 396                         memcpy(root_hash, calculated_digest, digest_size);
 397                 }
 398         }
 399
 400         if (data_file)
 401                 fclose(data_file);
 402         if (hash_file)
 403                 fclose(hash_file);
 404         return r;
 405 }
 406
 407 /* Verify verity device using userspace crypto backend */
 408 int VERITY_verify(struct crypt_device *cd,
 409                   struct crypt_params_verity *verity_hdr,
 410                   const char *root_hash,
 411                   size_t root_hash_size)
 412 {
 413         return VERITY_create_or_verify_hash(cd, 1, verity_hdr, CONST_CAST(char*)root_hash, root_hash_size);
 414 }
 415
 416 /* Create verity hash */
 417 int VERITY_create(struct crypt_device *cd,
 418                   struct crypt_params_verity *verity_hdr,
 419                   const char *root_hash,
 420                   size_t root_hash_size)
 421 {
 422         unsigned pgsize = (unsigned)crypt_getpagesize();
 423
 424         if (verity_hdr->salt_size > 256)
 425                 return -EINVAL;
 426
 427         if (verity_hdr->data_block_size > pgsize)
 428                 log_err(cd, _("WARNING: Kernel cannot activate device if data "
 429                               "block size exceeds page size (%u)."), pgsize);
 430
 431         return VERITY_create_or_verify_hash(cd, 0, verity_hdr, CONST_CAST(char*)root_hash, root_hash_size);
 432 }
 433
 434 uint64_t VERITY_hash_blocks(struct crypt_device *cd, struct crypt_params_verity *params)
 435 {
 436         uint64_t hash_position = 0;
 437         int levels = 0;
 438
 439         if (hash_levels(params->hash_block_size, crypt_get_volume_key_size(cd),
 440                 params->data_size, &hash_position, &levels, NULL, NULL))
 441                 return 0;
 442
 443         return (uint64_t)hash_position;
 444 }