[Qemu-devel] [PATCH v1 04/15] crypto: add support for anti-forensic split algorithm

["Daniel P. Berrange" <berrange@redhat.com>]

The LUKS format specifies an anti-forensic split algorithm which
is used to artificially expand the size of the key material on
disk. This is an implementation of that algorithm.

Signed-off-by: Daniel P. Berrange <berrange@redhat.com>
---
 crypto/Makefile.objs        |   1 +
 crypto/afsplit.c            | 194 ++++++++++++++++++++++++++++++++++++++++++++
 include/crypto/afsplit.h    | 133 ++++++++++++++++++++++++++++++
 tests/.gitignore            |   1 +
 tests/Makefile              |   2 +
 tests/test-crypto-afsplit.c | 176 ++++++++++++++++++++++++++++++++++++++++
 6 files changed, 507 insertions(+)
 create mode 100644 crypto/afsplit.c
 create mode 100644 include/crypto/afsplit.h
 create mode 100644 tests/test-crypto-afsplit.c

diff --git a/crypto/Makefile.objs b/crypto/Makefile.objs
index a973483..1e08a3a 100644
--- a/crypto/Makefile.objs
+++ b/crypto/Makefile.objs
@@ -14,6 +14,7 @@ crypto-obj-y += ivgen.o
 crypto-obj-y += ivgen-essiv.o
 crypto-obj-y += ivgen-plain.o
 crypto-obj-y += ivgen-plain64.o
+crypto-obj-y += afsplit.o
 
 # Let the userspace emulators avoid linking gnutls/etc
 crypto-aes-obj-y = aes.o
diff --git a/crypto/afsplit.c b/crypto/afsplit.c
new file mode 100644
index 0000000..7131622
--- /dev/null
+++ b/crypto/afsplit.c
@@ -0,0 +1,194 @@
+/*
+ * QEMU Crypto anti forensic information splitter
+ *
+ * Copyright (c) 2015 Red Hat, Inc.
+ *
+ * Derived from cryptsetup package lib/lusk1/af.c
+ *
+ * Copyright (C) 2004, Clemens Fruhwirth <clemens@endorphin.org>
+ * Copyright (C) 2009-2012, Red Hat, Inc. All rights reserved.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "crypto/afsplit.h"
+#include "crypto/random.h"
+
+
+static void qcrypto_afsplit_xor(size_t blocklen,
+                                const uint8_t *in1,
+                                const uint8_t *in2,
+                                uint8_t *out)
+{
+    size_t i;
+    for (i = 0; i < blocklen; i++) {
+        out[i] = in1[i] ^ in2[i];
+    }
+}
+
+
+static int qcrypto_afsplit_hash(QCryptoHashAlgorithm hash,
+                                size_t blocklen,
+                                uint8_t *block,
+                                Error **errp)
+{
+    size_t digestlen = qcrypto_hash_digest_len(hash);
+
+    size_t hashcount = blocklen / digestlen;
+    size_t finallen = blocklen % digestlen;
+    uint32_t i;
+
+    if (finallen) {
+        hashcount++;
+    } else {
+        finallen = blocklen;
+    }
+
+    for (i = 0; i < hashcount; i++) {
+        uint8_t *out = NULL;
+        size_t outlen = 0;
+        uint32_t iv = cpu_to_be32(i);
+        struct iovec in[] = {
+            { .iov_base = &iv,
+              .iov_len = sizeof(iv) },
+            { .iov_base = block + (i * digestlen),
+              .iov_len = (i == (hashcount - 1)) ? finallen : digestlen },
+        };
+
+        if (qcrypto_hash_bytesv(hash,
+                                in,
+                                G_N_ELEMENTS(in),
+                                &out, &outlen,
+                                errp) < 0) {
+            return -1;
+        }
+
+        if (outlen != digestlen) {
+            error_setg(errp, "Hash output %zu not %zu",
+                       outlen, digestlen);
+            g_free(out);
+            return -1;
+        }
+        memcpy(block + (i * digestlen), out,
+               (i == (hashcount - 1)) ? finallen : digestlen);
+        g_free(out);
+    }
+
+    return 0;
+}
+
+
+/**
+ * qcrypto_afsplit_encode:
+ * @hash: the hash function to use when splitting
+ * @blocklen: the length of @in in bytes
+ * @stripes: the number of stripes to split @in into
+ * @in: the input data, @blocklen bytes
+ * @out: the output data, @blocklen * @stripes bytes
+ * @errp: pointer to an uninitialized error object
+ *
+ * Transform the data (key material) in @in which is @blocklen
+ * bytes long, into data that is (@blocklen * @stripes)  bytes
+ * long. The caller is responsible for allocating @out with
+ * @blocklen * @stripes bytes of memory.
+ *
+ * Returns: 0 on success, -1 on error
+ */
+int qcrypto_afsplit_encode(QCryptoHashAlgorithm hash,
+                           size_t blocklen,
+                           uint32_t stripes,
+                           const uint8_t *in,
+                           uint8_t *out,
+                           Error **errp)
+{
+    uint8_t *block = g_new0(uint8_t, blocklen);
+    size_t i;
+    int ret = -1;
+
+    for (i = 0; i < (stripes - 1); i++) {
+        if (qcrypto_random_bytes(out + (i * blocklen), blocklen, errp) < 0) {
+            goto cleanup;
+        }
+
+        qcrypto_afsplit_xor(blocklen,
+                            out + (i * blocklen),
+                            block,
+                            block);
+        if (qcrypto_afsplit_hash(hash, blocklen, block,
+                                 errp) < 0) {
+            goto cleanup;
+        }
+    }
+    qcrypto_afsplit_xor(blocklen,
+                        in,
+                        block,
+                        out + (i * blocklen));
+    ret = 0;
+
+ cleanup:
+    g_free(block);
+    return ret;
+}
+
+
+/**
+ * qcrypto_afsplit_decode:
+ * @hash: the hash function to use when splitting
+ * @blocklen: the length of @iout in bytes
+ * @stripes: the number of stripes to split @in into
+ * @in: the input data, @blocklen * @stripes bytes
+ * @out: the output data, @blocklen bytes
+ * @errp: pointer to an uninitialized error object
+ *
+ * Transform the split data in @in which is (@blocklen * @stripes)
+ * bytes long, into the original data (key material) that is
+ * @blocklen bytes long. The caller is responsible for allocating
+ * @out with @blocklen bytes of memory.
+ *
+ * Returns: 0 on success, -1 on error
+ */
+int qcrypto_afsplit_decode(QCryptoHashAlgorithm hash,
+                           size_t blocklen,
+                           uint32_t stripes,
+                           const uint8_t *in,
+                           uint8_t *out,
+                           Error **errp)
+{
+    uint8_t *block = g_new0(uint8_t, blocklen);
+    size_t i;
+    int ret = -1;
+
+    for (i = 0; i < (stripes - 1); i++) {
+        qcrypto_afsplit_xor(blocklen,
+                            in + (i * blocklen),
+                            block,
+                            block);
+        if (qcrypto_afsplit_hash(hash, blocklen, block,
+                                 errp) < 0) {
+            goto cleanup;
+        }
+    }
+
+    qcrypto_afsplit_xor(blocklen,
+                        in + (i * blocklen),
+                        block,
+                        out);
+
+    ret = 0;
+
+ cleanup:
+    g_free(block);
+    return ret;
+}
diff --git a/include/crypto/afsplit.h b/include/crypto/afsplit.h
new file mode 100644
index 0000000..a331d8a
--- /dev/null
+++ b/include/crypto/afsplit.h
@@ -0,0 +1,133 @@
+/*
+ * QEMU Crypto anti forensic information splitter
+ *
+ * Copyright (c) 2015 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#ifndef QCRYPTO_AFSPLIT_H__
+#define QCRYPTO_AFSPLIT_H__
+
+#include "crypto/hash.h"
+
+/**
+ * This module implements the anti-forensic splitter that is specified
+ * as part of the LUKS format:
+ *
+ *   http://clemens.endorphin.org/cryptography
+ *   http://clemens.endorphin.org/TKS1-draft.pdf
+ *
+ * The core idea is to take a short piece of data (key material)
+ * and process it to expand it to a much larger piece of data.
+ * The expansion process is reversable, to obtain the original
+ * short data. The key property of the expansion is that if any
+ * byte in the larger data set is changed / missing, it should be
+ * impossible to recreate the original short data.
+ *
+ * <example>
+ *    <title>Creating a large split key for storage</title>
+ *    <programlisting>
+ * size_t nkey = 32;
+ * uint32_t stripes = 32768; // To produce a 1 MB split key
+ * uint8_t *masterkey = ....a 32-byte AES key...
+ * uint8_t *splitkey;
+ *
+ * splitkey = g_new0(uint8_t, nkey * stripes);
+ *
+ * if (qcrypto_afsplit_encode(QCRYPTO_HASH_ALG_SHA256,
+ *                            nkey, stripes,
+ *                            masterkey, splitkey, errp) < 0) {
+ *     g_free(splitkey);
+ *     g_free(masterkey);
+ *     return -1;
+ * }
+ *
+ * ...store splitkey somewhere...
+ *
+ * g_free(splitkey);
+ * g_free(masterkey);
+ *    </programlisting>
+ * </example>
+ *
+ * <example>
+ *    <title>Retrieving a master key from storage</title>
+ *    <programlisting>
+ * size_t nkey = 32;
+ * uint32_t stripes = 32768; // To produce a 1 MB split key
+ * uint8_t *masterkey;
+ * uint8_t *splitkey = .... read in 1 MB of data...
+ *
+ * masterkey = g_new0(uint8_t, nkey);
+ *
+ * if (qcrypto_afsplit_decode(QCRYPTO_HASH_ALG_SHA256,
+ *                            nkey, stripes,
+ *                            splitkey, masterkey, errp) < 0) {
+ *     g_free(splitkey);
+ *     g_free(masterkey);
+ *     return -1;
+ * }
+ *
+ * ..decrypt data with masterkey...
+ *
+ * g_free(splitkey);
+ * g_free(masterkey);
+ *    </programlisting>
+ * </example>
+ */
+
+/**
+ * qcrypto_afsplit_encode:
+ * @hash: the hash algorithm to use for data expansion
+ * @blocklen: the size of @in in bytes
+ * @stripes: the number of times to expand @in in size
+ * @in: the master key to be expanded in size
+ * @out: preallocted buffer to hold the split key
+ *
+ * Split the data in @in, which is @blocklen bytes in
+ * size, to form a larger piece of data @out, which is
+ * @blocklen * @stripes bytes in size.
+ *
+ * Returns: 0 on success, -1 on error;
+ */
+int qcrypto_afsplit_encode(QCryptoHashAlgorithm hash,
+                           size_t blocklen,
+                           uint32_t stripes,
+                           const uint8_t *in,
+                           uint8_t *out,
+                           Error **errp);
+
+/**
+ * qcrypto_afsplit_decode:
+ * @hash: the hash algorithm to use for data compression
+ * @blocklen: the size of @out in bytes
+ * @stripes: the number of times to decrease @in in size
+ * @in: the master key to be expanded in size
+ * @out: preallocted buffer to hold the split key
+ *
+ * Join the data in @in, which is @blocklen * @stripes
+ * bytes in size, to form the original small piece o
+ * data @out, which is @blocklen bytes in size.
+ *
+ * Returns: 0 on success, -1 on error;
+ */
+int qcrypto_afsplit_decode(QCryptoHashAlgorithm hash,
+                           size_t blocklen,
+                           uint32_t stripes,
+                           const uint8_t *in,
+                           uint8_t *out,
+                           Error **errp);
+
+#endif /* QCRYPTO_AFSPLIT_H__ */
diff --git a/tests/.gitignore b/tests/.gitignore
index 369f848..5b97e8c 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -12,6 +12,7 @@ test-base64
 test-bitops
 test-blockjob-txn
 test-coroutine
+test-crypto-afsplit
 test-crypto-cipher
 test-crypto-hash
 test-crypto-ivgen
diff --git a/tests/Makefile b/tests/Makefile
index 5fdbaf0..80847b9 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -94,6 +94,7 @@ check-unit-y += tests/test-io-channel-buffer$(EXESUF)
 check-unit-y += tests/test-base64$(EXESUF)
 check-unit-y += tests/test-crypto-pbkdf$(EXESUF)
 check-unit-y += tests/test-crypto-ivgen$(EXESUF)
+check-unit-y += tests/test-crypto-afsplit$(EXESUF)
 
 check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh
 
@@ -499,6 +500,7 @@ tests/test-io-channel-buffer$(EXESUF): tests/test-io-channel-buffer.o \
         tests/io-channel-helpers.o $(test-io-obj-y)
 tests/test-crypto-pbkdf$(EXESUF): tests/test-crypto-pbkdf.o $(test-crypto-obj-y)
 tests/test-crypto-ivgen$(EXESUF): tests/test-crypto-ivgen.o $(test-crypto-obj-y)
+tests/test-crypto-afsplit$(EXESUF): tests/test-crypto-afsplit.o $(test-crypto-obj-y)
 
 libqos-obj-y = tests/libqos/pci.o tests/libqos/fw_cfg.o tests/libqos/malloc.o
 libqos-obj-y += tests/libqos/i2c.o tests/libqos/libqos.o
diff --git a/tests/test-crypto-afsplit.c b/tests/test-crypto-afsplit.c
new file mode 100644
index 0000000..da301b8
--- /dev/null
+++ b/tests/test-crypto-afsplit.c
@@ -0,0 +1,176 @@
+/*
+ * QEMU Crypto anti-forensic splitter
+ *
+ * Copyright (c) 2015 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <glib.h>
+
+#include "crypto/init.h"
+#include "crypto/afsplit.h"
+
+typedef struct QCryptoAFSplitTestData QCryptoAFSplitTestData;
+struct QCryptoAFSplitTestData {
+    const char *path;
+    QCryptoHashAlgorithm hash;
+    uint32_t stripes;
+    size_t blocklen;
+    const uint8_t *key;
+    const uint8_t *splitkey;
+};
+
+static QCryptoAFSplitTestData test_data[] = {
+    {
+        .path = "/crypto/afsplit/sha256/5",
+        .hash = QCRYPTO_HASH_ALG_SHA256,
+        .stripes = 5,
+        .blocklen = 32,
+        .key = (const uint8_t *)
+            "\x00\x01\x02\x03\x04\x05\x06\x07"
+            "\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f"
+            "\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7"
+            "\xa8\xa9\xaa\xab\xac\xad\xae\xaf",
+        .splitkey = (const uint8_t *)
+            "\xfd\xd2\x73\xb1\x7d\x99\x93\x34"
+            "\x70\xde\xfa\x07\xc5\xac\x58\xd2"
+            "\x30\x67\x2f\x1a\x35\x43\x60\x7d"
+            "\x77\x02\xdb\x62\x3c\xcb\x2c\x33"
+            "\x48\x08\xb6\xf1\x7c\xa3\x20\xa0"
+            "\xad\x2d\x4c\xf3\xcd\x18\x6f\x53"
+            "\xf9\xe8\xe7\x59\x27\x3c\xa9\x54"
+            "\x61\x87\xb3\xaf\xf6\xf7\x7e\x64"
+            "\x86\xaa\x89\x7f\x1f\x9f\xdb\x86"
+            "\xf4\xa2\x16\xff\xa3\x4f\x8c\xa1"
+            "\x59\xc4\x23\x34\x28\xc4\x77\x71"
+            "\x83\xd4\xcd\x8e\x89\x1b\xc7\xc5"
+            "\xae\x4d\xa9\xcd\xc9\x72\x85\x70"
+            "\x13\x68\x52\x83\xfc\xb8\x11\x72"
+            "\xba\x3d\xc6\x4a\x28\xfa\xe2\x86"
+            "\x7b\x27\xab\x58\xe1\xa4\xca\xf6"
+            "\x9e\xbc\xfe\x0c\x92\x79\xb3\xec"
+            "\x1c\x5f\x79\x3b\x0d\x1e\xaa\x1a"
+            "\x77\x0f\x70\x19\x4b\xc8\x80\xee"
+            "\x27\x7c\x6e\x4a\x91\x96\x5c\xf4"
+    },
+    {
+        .path = "/crypto/afsplit/sha256/5000",
+        .hash = QCRYPTO_HASH_ALG_SHA256,
+        .stripes = 5000,
+        .blocklen = 16,
+        .key = (const uint8_t *)
+            "\x00\x01\x02\x03\x04\x05\x06\x07"
+            "\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f",
+    },
+    {
+        .path = "/crypto/afsplit/sha1/1000",
+        .hash = QCRYPTO_HASH_ALG_SHA1,
+        .stripes = 1000,
+        .blocklen = 32,
+        .key = (const uint8_t *)
+            "\x00\x01\x02\x03\x04\x05\x06\x07"
+            "\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f"
+            "\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7"
+            "\xa8\xa9\xaa\xab\xac\xad\xae\xaf",
+    },
+};
+
+
+static inline char hex(int i)
+{
+    if (i < 10) {
+        return '0' + i;
+    }
+    return 'a' + (i - 10);
+}
+
+static char *hex_string(const uint8_t *bytes,
+                        size_t len)
+{
+    char *hexstr = g_new0(char, len * 2 + 1);
+    size_t i;
+
+    for (i = 0; i < len; i++) {
+        hexstr[i*2] = hex((bytes[i] >> 4) & 0xf);
+        hexstr[i*2+1] = hex(bytes[i] & 0xf);
+    }
+    hexstr[len*2] = '\0';
+
+    return hexstr;
+}
+
+static void test_afsplit(const void *opaque)
+{
+    const QCryptoAFSplitTestData *data = opaque;
+    size_t splitlen = data->blocklen * data->stripes;
+    uint8_t *splitkey = g_new0(uint8_t, splitlen);
+    uint8_t *key = g_new0(uint8_t, data->blocklen);
+    gchar *expect, *actual;
+
+    /* First time we round-trip the key */
+    qcrypto_afsplit_encode(data->hash,
+                           data->blocklen, data->stripes,
+                           data->key, splitkey,
+                           &error_abort);
+
+    qcrypto_afsplit_decode(data->hash,
+                           data->blocklen, data->stripes,
+                           splitkey, key,
+                           &error_abort);
+
+    expect = hex_string(data->key, data->blocklen);
+    actual = hex_string(key, data->blocklen);
+
+    g_assert_cmpstr(actual, ==, expect);
+
+    g_free(actual);
+    g_free(expect);
+
+    /* Second time we merely try decoding a previous split */
+    if (data->splitkey) {
+        memset(key, 0, data->blocklen);
+
+        qcrypto_afsplit_decode(data->hash,
+                               data->blocklen, data->stripes,
+                               data->splitkey, key,
+                               &error_abort);
+
+        expect = hex_string(data->key, data->blocklen);
+        actual = hex_string(key, data->blocklen);
+
+        g_assert_cmpstr(actual, ==, expect);
+
+        g_free(actual);
+        g_free(expect);
+    }
+
+    g_free(key);
+    g_free(splitkey);
+}
+
+int main(int argc, char **argv)
+{
+    size_t i;
+
+    g_test_init(&argc, &argv, NULL);
+
+    g_assert(qcrypto_init(NULL) == 0);
+
+    for (i = 0; i < G_N_ELEMENTS(test_data); i++) {
+        g_test_add_data_func(test_data[i].path, &test_data[i], test_afsplit);
+    }
+    return g_test_run();
+}
-- 
2.5.0