lkml.org 
[lkml]   [2012]   [Mar]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Subjectuserspace hashing utility for dm-verity
This is an userspace utility that creates or verifies hashes for the 
verity target.

The original utility was created by Google and it is located at
http://git.chromium.org/chromiumos/platform/dm-verity.git

The original utility has some problems:
* the code is really overengineered, they took the kernel code and built
an emulation layer in userspace that emulates some of the kernel
functions
* it dosn't use library implementations of hash functions, rather it
provides its own md5, sha1, sha256 and sha512 implementation
* it is not portable (produces bad result on big-endian machines)

This is much smaller implementation that is portable and uses the crypto
library.

This code creates compatible format with the original Google code under
these conditions:
- data block size and hash block size are 4096
- salt has exactly 32 bytes (64 hex digits)

Example use:
Create filesystem on /dev/sdc2 and fill it with some data. Block size must
be 4096
Unmount the filesystem

Run: ./verity -c /dev/sdc2 /dev/sdc3 sha256 --salt
1234000000000000000000000000000000000000000000000000000000000000
- This creates hash tree on /dev/sdc3 and prints the root block hash

Run: dmsetup -r create verity --table "0 `blockdev --getsize /dev/sdc2`
verity 0 /dev/sdc2 /dev/sdc3 0 4096 sha256
f4c97f1f2e6b6757d033b2062268e0b6b42cbe4ff5a5fcc0017305b145cae4de
1234000000000000000000000000000000000000000000000000000000000000 "
(note: use the real hash reported by "verity" tool instead of f4c9...)

mount -o ro -t ext2 /dev/mapper/verity /mnt/test

Now, the device is mounted and dm-verity target is verifying the hashes.
All data integrity depends only on the root hash
(f4c97f1f2e6b6757d033b2062268e0b6b42cbe4ff5a5fcc0017305b145cae4de) and
salt (1234000000000000000000000000000000000000000000000000000000000000).
If either the data or hash partitions become silently corrupted and
you read invalid data, dm-verity will return -EIO.

Mikulas

---

/* link with -lpopt -lcrypto */

#define _FILE_OFFSET_BITS 64

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <sys/mount.h>
#include <popt.h>
#include <openssl/evp.h>

#define DEFAULT_BLOCK_SIZE 4096
#define DM_VERITY_MAX_LEVELS 63

#define MODE_VERIFY 0
#define MODE_CREATE 1

static int mode = -1;

static const char *data_device;
static const char *hash_device;
static const char *hash_algorithm;
static const char *root_hash;

static int data_block_size = 0;
static int hash_block_size = 0;
static long long hash_start = 0;
static long long data_blocks = 0;
static const char *salt_string = NULL;

static FILE *data_file;
static FILE *hash_file;

static off_t data_file_blocks;
static off_t hash_file_blocks;
static off_t used_hash_blocks;

static const EVP_MD *evp;

static unsigned char *root_hash_bytes;
static unsigned char *calculated_digest;

static unsigned char *salt_bytes;
static unsigned salt_size;

static unsigned digest_size;
static unsigned char levels;
static unsigned char hash_per_block_bits;

static off_t hash_level_block[DM_VERITY_MAX_LEVELS];
static off_t hash_level_size[DM_VERITY_MAX_LEVELS];

static int retval = 0;

static void help(poptContext popt_context,
enum poptCallbackReason reason,
struct poptOption *key,
const char *arg,
void *data)
{
poptPrintHelp(popt_context, stdout, 0);
exit(0);
}

static struct poptOption popt_help_options[] = {
{ NULL, 0, POPT_ARG_CALLBACK, help, 0, NULL, NULL },
{ "help", '?', POPT_ARG_NONE, NULL, 0, "Show help", NULL },
POPT_TABLEEND
};

static struct poptOption popt_options[] = {
{ NULL, '\0', POPT_ARG_INCLUDE_TABLE, popt_help_options, 0, NULL, NULL },
{ "create", 'c', POPT_ARG_VAL, &mode, MODE_CREATE, "Create hash", NULL },
{ "verify", 'v', POPT_ARG_VAL, &mode, MODE_VERIFY, "Verify integrity", NULL },
{ "data-block-size", 0, POPT_ARG_INT, &data_block_size, 0, "Block size on the data device", "bytes" },
{ "hash-block-size", 0, POPT_ARG_INT, &hash_block_size, 0, "Block size on the hash device", "bytes" },
{ "hash-start", 0, POPT_ARG_LONGLONG, &hash_start, 0, "Starting sector on the hash device", "sectors" },
{ "data-blocks", 0, POPT_ARG_LONGLONG, &data_blocks, 0, "The number of blocks in the data file", "blocks" },
{ "salt", 0, POPT_ARG_STRING, &salt_string, 0, "Salt", "hex string" },
POPT_TABLEEND
};

static void exit_err(const char *msg, ...)
{
va_list args;
va_start(args, msg);
vfprintf(stderr, msg, args);
va_end(args);
fputc('\n', stderr);
exit(2);
}

static void stream_err(FILE *f, const char *msg)
{
if (ferror(f)) {
perror(msg);
exit(2);
} else if (feof(f)) {
exit_err("eof on %s", msg);
} else {
exit_err("unknown error on %s", msg);
}
}

static void *xmalloc(size_t s)
{
void *ptr = malloc(s);
if (!ptr) exit_err("out of memory");
return ptr;
}

static off_t get_size(FILE *f, const char *name)
{
struct stat st;
int h = fileno(f);
if (h < 0) {
perror("fileno");
exit(2);
}
if (fstat(h, &st)) {
perror("fstat");
exit(2);
}
if (S_ISREG(st.st_mode)) {
return st.st_size;
} else if (S_ISBLK(st.st_mode)) {
unsigned long long size64;
unsigned long sizeul;
if (!ioctl(h, BLKGETSIZE64, &size64)) {
return_size64:
if ((off_t)size64 < 0 || (off_t)size64 != size64) {
size_overflow:
exit_err("%s: device size overflow", name);
}
return size64;
}
if (!ioctl(h, BLKGETSIZE, &sizeul)) {
size64 = (unsigned long long)sizeul * 512;
if (size64 / 512 != sizeul) goto size_overflow;
goto return_size64;
}
perror("BLKGETSIZE");
exit(2);
} else {
exit_err("%s is not a file or a block device", name);
}
return -1; /* never reached, shut up warning */
}

static void block_fseek(FILE *f, off_t block, int block_size)
{
unsigned long long pos = (unsigned long long)block * block_size;
if (pos / block_size != block ||
(off_t)pos < 0 ||
(off_t)pos != pos)
exit_err("seek position overflow");
if (fseeko(f, pos, SEEK_SET)) {
perror("fseek");
exit(2);
}
}

static off_t verity_position_at_level(off_t block, int level)
{
return block >> (level * hash_per_block_bits);
}

static void calculate_positions(void)
{
unsigned long long hash_position;
int i;

hash_per_block_bits = 0;
while (((hash_block_size / digest_size) >> hash_per_block_bits) > 1)
hash_per_block_bits++;
if (!hash_per_block_bits)
exit_err("at least two hashes must fit in a hash file block");
levels = 0;

if (data_file_blocks) {
while (hash_per_block_bits * levels < 64 &&
(unsigned long long)(data_file_blocks - 1) >>
(hash_per_block_bits * levels))
levels++;
}

if (levels > DM_VERITY_MAX_LEVELS) exit_err("too many tree levels");

hash_position = hash_start * 512 / hash_block_size;
for (i = levels - 1; i >= 0; i--) {
off_t s;
hash_level_block[i] = hash_position;
s = verity_position_at_level(data_file_blocks, i);
s = (s >> hash_per_block_bits) +
!!(s & ((1 << hash_per_block_bits) - 1));
hash_level_size[i] = s;
if (hash_position + s < hash_position ||
(off_t)(hash_position + s) < 0 ||
(off_t)(hash_position + s) != hash_position + s)
exit_err("hash device offset overflow");
hash_position += s;
}
used_hash_blocks = hash_position;
}

static void create_or_verify_stream(FILE *rd, FILE *wr, int block_size, off_t blocks)
{
unsigned char *left_block = xmalloc(hash_block_size);
unsigned char *data_buffer = xmalloc(block_size);
unsigned char *read_digest = mode == MODE_VERIFY ? xmalloc(digest_size) : NULL;
off_t blocks_to_write = (blocks >> hash_per_block_bits) +
!!(blocks & ((1 << hash_per_block_bits) - 1));
EVP_MD_CTX ctx;
EVP_MD_CTX_init(&ctx);
memset(left_block, 0, hash_block_size);
while (blocks_to_write--) {
unsigned x;
unsigned left_bytes;
for (x = 0; x < 1 << hash_per_block_bits; x++) {
if (!blocks)
break;
blocks--;
if (fread(data_buffer, block_size, 1, rd) != 1)
stream_err(rd, "read");
if (EVP_DigestInit_ex(&ctx, evp, NULL) != 1)
exit_err("EVP_DigestInit_ex failed");
if (EVP_DigestUpdate(&ctx, data_buffer, block_size) != 1)
exit_err("EVP_DigestUpdate failed");
if (EVP_DigestUpdate(&ctx, salt_bytes, salt_size) != 1)
exit_err("EVP_DigestUpdate failed");
if (EVP_DigestFinal_ex(&ctx, calculated_digest, NULL) != 1)
exit_err("EVP_DigestFinal_ex failed");
if (!wr)
break;
if (mode == MODE_VERIFY) {
if (fread(read_digest, digest_size, 1, wr) != 1)
stream_err(wr, "read");
if (memcmp(read_digest, calculated_digest, digest_size)) {
retval = 1;
fprintf(stderr, "verification failed at position %lld in %s file\n", (long long)ftello(rd) - block_size, rd == data_file ? "data" : "metadata");
}
} else {
if (fwrite(calculated_digest, digest_size, 1, wr) != 1)
stream_err(wr, "write");
}
}
left_bytes = hash_block_size - x * digest_size;
if (left_bytes && wr) {
if (mode == MODE_VERIFY) {
if (fread(left_block, left_bytes, 1, wr) != 1)
stream_err(wr, "read");
for (x = 0; x < left_bytes; x++) if (left_block[x]) {
retval = 1;
fprintf(stderr, "spare area is not zeroed at position %lld\n", (long long)ftello(wr) - left_bytes);
}
} else {
if (fwrite(left_block, left_bytes, 1, wr) != 1)
stream_err(wr, "write");
}
}
}
if (mode != MODE_VERIFY && wr) {
if (fflush(wr)) {
perror("fflush");
exit(1);
}
if (ferror(wr)) {
stream_err(wr, "write");
}
}
if (EVP_MD_CTX_cleanup(&ctx) != 1)
exit_err("EVP_MD_CTX_cleanup failed");
free(left_block);
free(data_buffer);
if (mode == MODE_VERIFY) free(read_digest);
}

static void create_or_verify(void)
{
int i;
for (i = 0; i < levels; i++) {
block_fseek(hash_file, hash_level_block[i], hash_block_size);
if (!i) {
block_fseek(data_file, 0, data_block_size);
create_or_verify_stream(data_file, hash_file, data_block_size, data_file_blocks);
} else {
FILE *hash_file_2 = fopen(hash_device, "r");
if (!hash_file_2) {
perror(hash_device);
exit(2);
}
block_fseek(hash_file_2, hash_level_block[i - 1], hash_block_size);
create_or_verify_stream(hash_file_2, hash_file, hash_block_size, hash_level_size[i - 1]);
fclose(hash_file_2);
}
}

if (levels) {
block_fseek(hash_file, hash_level_block[levels - 1], hash_block_size);
create_or_verify_stream(hash_file, NULL, hash_block_size, 1);
} else {
block_fseek(data_file, 0, data_block_size);
create_or_verify_stream(data_file, NULL, data_block_size, data_file_blocks);
}

if (mode == MODE_VERIFY) {
if (memcmp(calculated_digest, root_hash_bytes, digest_size)) {
fprintf(stderr, "verification failed in the root block\n");
retval = 1;
}
if (!retval)
fprintf(stderr, "hash successfully verified\n");
} else {
if (fsync(fileno(hash_file))) {
perror("fsync");
exit(1);
}
printf("hash device size: %llu\n", (unsigned long long)used_hash_blocks * hash_block_size);
printf("data block size %u, hash block size %u, %u tree levels\n", data_block_size, hash_block_size, levels);
printf("root hash: ");
for (i = 0; i < digest_size; i++) printf("%02x", calculated_digest[i]);
printf("\n");
printf("device mapper target line: 0 %llu verity 0 %s %s %llu %u %s ",
(unsigned long long)data_file_blocks * data_block_size / 512,
data_device,
hash_device,
hash_start,
data_block_size,
hash_algorithm
);
for (i = 0; i < digest_size; i++) printf("%02x", calculated_digest[i]);
printf(" ");
if (!salt_size) printf("-");
else for (i = 0; i < salt_size; i++) printf("%02x", salt_bytes[i]);
if (hash_block_size != data_block_size) printf(" %u", hash_block_size);
printf("\n");
if (data_block_size == 4096 && hash_block_size == 4096 && salt_size == 32)
printf("compatible with the original Google code\n");
else {
printf("incompatible with the original Google code:\n");
if (!(data_block_size == 4096 && hash_block_size == 4096)) printf("\tdata and hash block size must be 4096\n");
if (!(salt_size == 32)) printf("\tsalt must have exactly 32 bytes (64 hex digits)\n");
}
}
}

static void get_hex(const char *string, unsigned char **result, size_t len, const char *description)
{
size_t rl = strlen(string);
unsigned u;
if (strspn(string, "0123456789ABCDEFabcdef") != rl)
exit_err("invalid %s", description);
if (rl != len * 2)
exit_err("invalid length of %s", description);
*result = xmalloc(len);
memset(*result, 0, len);
for (u = 0; u < rl; u++) {
unsigned char c = (string[u] & 15) + (string[u] > '9' ? 9 : 0);
(*result)[u / 2] |= c << (((u & 1) ^ 1) << 2);
}
}

int main(int argc, const char **argv)
{
poptContext popt_context;
int r;
const char *s;

popt_context = poptGetContext("verity", argc, argv, popt_options, 0);

poptSetOtherOptionHelp(popt_context, "[-c | -v] <data device> <hash device> <algorithm> [<root hash> if verifying] [OPTION...]");

if (argc <= 1) {
poptPrintHelp(popt_context, stdout, 0);
exit(1);
}

r = poptGetNextOpt(popt_context);
if (r < -1) exit_err("bad option %s", poptBadOption(popt_context, 0));

if (mode < 0) exit_err("verify or create mode not specified");

if (!data_block_size) data_block_size = DEFAULT_BLOCK_SIZE;
if (!hash_block_size) hash_block_size = data_block_size;

if (data_block_size <= 0 || (data_block_size & (data_block_size - 1)))
exit_err("invalid data block size");

if (hash_block_size <= 0 || (hash_block_size & (hash_block_size - 1)))
exit_err("invalid hash block size");

if (hash_start < 0 ||
(unsigned long long)hash_start * 512 / 512 != hash_start) exit_err("invalid hash start");
if (data_blocks < 0 || (off_t)data_blocks < 0 || (off_t)data_blocks != data_blocks) exit_err("invalid number of data blocks");

data_device = poptGetArg(popt_context);
if (!data_device) exit_err("data device is missing");

hash_device = poptGetArg(popt_context);
if (!hash_device) exit_err("metadata device is missing");

hash_algorithm = poptGetArg(popt_context);
if (!hash_algorithm) exit_err("hash algorithm not specified");

if (mode == MODE_VERIFY) {
root_hash = poptGetArg(popt_context);
if (!root_hash) exit_err("root hash not specified");
}

s = poptGetArg(popt_context);
if (s) exit_err("extra argument %s", s);

data_file = fopen(data_device, "r");
if (!data_file) {
perror(data_device);
exit(2);
}

hash_file = fopen(hash_device, mode == MODE_VERIFY ? "r" : "r+");
if (!hash_file && errno == ENOENT && mode != MODE_VERIFY)
hash_file = fopen(hash_device, "w+");
if (!hash_file) {
perror(hash_device);
exit(2);
}

data_file_blocks = get_size(data_file, data_device) / data_block_size;
hash_file_blocks = get_size(hash_file, hash_device) / hash_block_size;

if ((unsigned long long)hash_start * 512 % hash_block_size) exit_err("hash start not aligned on block size");
if (data_file_blocks < data_blocks) exit_err("data file is too small");
if (data_blocks) data_file_blocks = data_blocks;

OpenSSL_add_all_digests();
evp = EVP_get_digestbyname(hash_algorithm);
if (!evp) exit_err("hash algorithm %s not found", hash_algorithm);
digest_size = EVP_MD_size(evp);

salt_size = 0;
if (salt_string && *salt_string) {
salt_size = strlen(salt_string) / 2;
get_hex(salt_string, &salt_bytes, salt_size, "salt");
}

calculated_digest = xmalloc(digest_size);

if (mode == MODE_VERIFY) {
get_hex(root_hash, &root_hash_bytes, digest_size, "root_hash");
}

calculate_positions();

create_or_verify();

fclose(data_file);
fclose(hash_file);

if (salt_size)
free(salt_bytes);
free(calculated_digest);
if (mode == MODE_VERIFY)
free(root_hash_bytes);
poptFreeContext(popt_context);

return retval;
}


\
 
 \ /
  Last update: 2012-03-04 20:39    [W:0.102 / U:8.352 seconds]
©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site