path: root/service_provider.c

/* implementation of a basic service provider for use with the trusted
 * module */

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "crypto.h"
#include "helper.h"
#include "service_provider.h"
#include "trusted_module.h"

struct file_version {
    hash_t kf; /* h(key, file_idx) */
    hash_t l; /* h(h(file contents), kf) */
    hash_t enc_key; /* XOR'd with h(kf, module secret) */

    struct tm_cert cert; /* VR certificate */
    hash_t cert_hmac;

    void *contents;
    size_t len;
};

struct file_record {
    int idx;
    int version;
    int counter;

    struct iomt_node *acl_leaves;
    int acl_nleaves;

    struct tm_cert fr_cert; /* issued by module */
    hash_t fr_hmac;

    struct file_version *versions;
    int n_versions;
};

struct service_provider {
    struct trusted_module *tm;

    /* stored in sorted order; eventually a hash table would be
     * wise */
    struct file_record *records;
    size_t nrecords;

    struct iomt_node *mt_leaves; /* leaves of CDI-IOMT, value is counter */
    int mt_leafcount, mt_logleaves; /* mt_logleaves must equal 2^mt_leafcount */

    /* Each level of the IOMT is stored sequentially from left to
     * right, top to bottom, as follows:
     *
     *  [0]: root
     *  [1]: root left child
     *  [2]: root right child
     *  [3]: left child of [1]
     *  [4]: right child of [1]
     *  [5]: left child of [2]
     *  [6]: right child of [2],
     *
     * and so on.
     */
    hash_t *mt_nodes; /* this has 2 * mt_leafcount - 1 elements. Note
                       * that the bottom level consists of hashes of
                       * the leaf nodes. */
};

/* A bit of a hack: our complement calculation returns the *indices*
 * complementary nodes, which is good because the indices are much
 * smaller than the actual nodes (which are 32 bytes each with
 * SHA-256). However, the trusted module requires an array of the
 * actual hash values of the complementary nodes. It would be optimal
 * to modify each function to take the array of all nodes in the tree
 * in addition to the complement indices, but this function will serve
 * as a shim in the meantime. */
static hash_t *lookup_nodes(const hash_t *nodes, const int *indices, int n)
{
    hash_t *ret = calloc(n, sizeof(hash_t));
    for(int i = 0; i < n; ++i)
        ret[i] = nodes[indices[i]];
    return ret;
}

/* Calculate the value of all the nodes of the tree, given the IOMT
 * leaves in mt_leaves. Leaf count *must* be an integer power of two,
 * otherwise bad things will happen. This function should only need to
 * be called once, namely when the service provider is created. */
static void fill_tree(struct service_provider *sp)
{
    for(int i = 0; i < sp->mt_leafcount; ++i)
    {
        int mt_idx = (1 << sp->mt_logleaves) - 1 + i;
        sp->mt_nodes[mt_idx] = hash_node(sp->mt_leaves + i);
    }
    /* now loop up from the bottom level, calculating the parent of
     * each pair of nodes */
    for(int i = sp->mt_logleaves - 1; i >= 0; --i)
    {
        int baseidx = (1 << i) - 1;
        for(int j = 0; j < (1 << i); ++j)
        {
            int mt_idx = baseidx + j;
            sp->mt_nodes[mt_idx] = merkle_parent(sp->mt_nodes[2 * mt_idx + 1],
                                                 sp->mt_nodes[2 * mt_idx + 2],
                                                 0);
        }
    }
}

/* leaf count will be 2^logleaves */
struct service_provider *sp_new(const void *key, size_t keylen, int logleaves)
{
    struct service_provider *sp = calloc(1, sizeof(*sp));

    sp->tm = tm_new(key, keylen);

    sp->mt_leafcount = 1 << logleaves;
    sp->mt_logleaves = logleaves;
    sp->mt_leaves = calloc(sp->mt_leafcount, sizeof(struct iomt_node));

    sp->mt_nodes = calloc(2 * sp->mt_leafcount - 1, sizeof(hash_t));

    /* The trusted module initializes itself with a single placeholder
     * node (1,0,1). We first update our list of IOMT leaves. Then we
     * insert our desired number of nodes by using EQ certificates to
     * update the internal IOMT root. Note that leaf indices are
     * 1-indexed. */
    for(int i = 0; i < sp->mt_leafcount - 1; ++i)
        sp->mt_leaves[i] = (struct iomt_node) { i + 1, i + 2, hash_null };

    /* loop around */
    sp->mt_leaves[sp->mt_leafcount - 1] = (struct iomt_node) { sp->mt_leafcount, 1, hash_null };

    fill_tree(sp);

    /* everything else is already zeroed by calloc */
    return sp;
}

/* linear search for record given idx */
static struct file_record *lookup_record(struct service_provider *sp, int idx)
{
    for(int i = 0; i < sp->nrecords; ++i)
        if(idx == sp->records[i].idx)
            return sp->records + i;
    return NULL;
}

/* Should we insert sorted (for O(logn) lookup), or just at the end to
 * avoid copying (O(n) lookup, O(1) insertion)? Probably better to use a hash
 * table. */
static void insert_record(struct service_provider *sp, struct file_record *rec)
{
    /* TODO */
}

/* this does the majority of the work that actually modifies or
 * creates a file */
struct tm_cert sp_request(struct service_provider *sp,
                          const struct user_request *req, hash_t req_hmac,
                          hash_t *hmac_out,
                          struct tm_cert *vr_out, hash_t *vr_hmac_out,
                          hash_t *ack_hmac_out)
{
    struct tm_cert vr = cert_null;
    hash_t vr_hmac, ack_hmac, fr_hmac;
    vr_hmac = ack_hmac = fr_hmac = hash_null;

    /* execute the request */
    struct tm_cert fr = tm_request(sp->tm, req, req_hmac, &fr_hmac, &vr, &vr_hmac, &ack_hmac);

    /* now update our databases based on the result */
    if(fr.type == FR)
    {
        /* update the corresponding file record */
        struct file_record *rec = lookup_record(sp, fr.fr.idx);
        bool need_insert = false;
        if(!rec)
        {
            rec = calloc(1, sizeof(struct file_record));
            need_insert = true;
        }

        rec->version = fr.fr.version;
        rec->counter = fr.fr.counter;
        rec->fr_cert = fr;
        rec->fr_hmac = fr_hmac;

        if(need_insert)
            insert_record(sp, rec);

        /* update our tree */
        /* TODO */
    }

    /* return values to caller */
    if(hmac_out)
        *hmac_out = fr_hmac;
    if(vr_out)
        *vr_out = vr;
    if(vr_hmac_out)
        *vr_hmac_out = vr_hmac;
    if(ack_hmac_out)
        *ack_hmac_out = ack_hmac;

    return fr;
}

/* in trusted_module.c */
void check(int condition);

void sp_test(void)
{
    /* 2^10 = 1024 leaves ought to be enough for anybody */
    int logleaves = 1;
    struct service_provider *sp = sp_new("a", 1, logleaves);
    /* construct a request to create a file */
    struct user_request req;
    req.idx = 1;
    req.user_id = 1;
    req.type = ACL_UPDATE;
    req.counter = 0;

    struct iomt_node acl_node;
    acl_node.idx = 1;
    memset(&acl_node.val, 0, sizeof(acl_node.val));
    acl_node.val.hash[0] = 3; /* full access */
    acl_node.next_idx = 1;
    req.val = merkle_compute(hash_node(&acl_node), NULL, NULL, 0);

    struct iomt_node node;
    node.idx = 1;
    memset(node.val.hash, 0, 32);
    node.next_idx = 1;

    hash_t one;
    memset(one.hash, 0, 32);
    one.hash[0] = 1;

    hash_t ru_hmac;

    /* we need a RU certificate of the form [f, 0, root, 1, new root],
     * which requires a NU certificate of the form [v, root, v', new
     * root], where v=h(original IOMT node) and v'=h(new IOMT node) */
    struct tm_cert ru = cert_ru(sp->tm, &node, one,
                                NULL, NULL, 0,
                                &ru_hmac,
                                0, NULL, NULL);
    printf("RU generation: ");
    check(ru.type == RU &&
          ru.ru.idx == 1 &&
          hash_equals(ru.ru.orig_val, node.val) &&
          hash_equals(ru.ru.new_val, one));

    /* now create a request */
    req.create.ru_cert = ru;
    req.create.ru_hmac = ru_hmac;
    hash_t req_hmac = hmac_sha256(&req, sizeof(req), "a", 1);
    hash_t fr_hmac;
    hash_t ack_hmac;

    struct tm_cert fr_cert = sp_request(sp, &req, req_hmac, &fr_hmac, NULL, NULL, &ack_hmac);

    printf("File creation: ");
    check(fr_cert.type == FR &&
          fr_cert.fr.counter == 1 &&
          fr_cert.fr.version == 0);

    /* modification */
    struct user_request mod;
    mod.type = FILE_UPDATE;
    mod.idx = 1;
    mod.user_id = 1;
    mod.counter = 1;
    mod.modify.fr_cert = fr_cert;
    mod.modify.fr_hmac = fr_hmac;

    mod.modify.rv_cert = cert_rv(sp->tm,
                                 &acl_node,
                                 NULL, NULL, 0,
                                 &mod.modify.rv_hmac);

    struct iomt_node node2;
    node2.idx = 1;
    node2.val = one;
    node2.next_idx = 1;

    hash_t two;
    memset(&two, 0, sizeof(two));
    two.hash[0] = 2;
    mod.modify.ru_cert = cert_ru(sp->tm, &node2, two,
                                NULL, NULL, 0,
                                &mod.modify.ru_hmac,
                                0, NULL, NULL);

    req_hmac = hmac_sha256(&mod, sizeof(mod), "a", 1);

    struct tm_cert vr;
    hash_t vr_hmac;

    struct tm_cert new_fr = sp_request(sp, &mod, req_hmac, &fr_hmac, &vr, &vr_hmac, &ack_hmac);
    printf("File modification: ");
    check(new_fr.type == FR);

    printf("Complement calculation: ");
    int *orders;
    int *comp = merkle_complement(6, 4, &orders);
    int correct[] = { 22, 9, 3, 2 };
    int correct_orders[] = { 1, 0, 0, 1 };
    check(!memcmp(comp, correct, 4 * sizeof(int)) && !memcmp(orders, correct_orders, 4 * sizeof(int)));

    /* broken */
#if 0
    {
        int *orders_enc, *orders_ins;
        int *compidx_enc, *compidx_ins;
        compidx_enc = merkle_complement(0, 1, &orders_enc);
        compidx_ins = merkle_complement(1, 1, &orders_ins);
        hash_t *comp_enc = lookup_nodes(sp->mt_nodes, compidx_enc, logleaves);
        hash_t *comp_ins = lookup_nodes(sp->mt_nodes, compidx_ins, logleaves);

        hash_t hmac;
        struct tm_cert eq = cert_eq(sp->tm, sp->mt_leaves + 0, 2,
                                    comp_enc, orders_enc, logleaves,
                                    comp_ins, orders_ins, logleaves,
                                    &hmac);
        /* broken */
        printf("EQ generation: ");
        check(eq.type == EQ);
    }
#endif

    /* test tree initilization (only simple case) */
    if(logleaves == 1)
    {
        struct iomt_node a = { 1, 2, hash_null };
        struct iomt_node b = { 2, 1, hash_null };
        printf("Merkle tree initialization: ");
        check(hash_equals(sp->mt_nodes[0], merkle_parent(hash_node(&a), hash_node(&b), 0)));
    }
}