aboutsummaryrefslogtreecommitdiff
path: root/service_provider.c
diff options
context:
space:
mode:
authorFranklin Wei <me@fwei.tk>2018-06-13 20:55:32 -0400
committerFranklin Wei <me@fwei.tk>2018-06-13 20:55:32 -0400
commit6ee13d7f3e0530f56215b134679aeb27a676543c (patch)
treefefb0277776ea4653724ecbca8975d026d9af165 /service_provider.c
parentb876b2e28a299217b5997ec8e885280ea5515bf7 (diff)
downloadcsaa-6ee13d7f3e0530f56215b134679aeb27a676543c.zip
csaa-6ee13d7f3e0530f56215b134679aeb27a676543c.tar.gz
csaa-6ee13d7f3e0530f56215b134679aeb27a676543c.tar.bz2
csaa-6ee13d7f3e0530f56215b134679aeb27a676543c.tar.xz
Working on service provider tree management routines
Diffstat (limited to 'service_provider.c')
-rw-r--r--service_provider.c144
1 files changed, 107 insertions, 37 deletions
diff --git a/service_provider.c b/service_provider.c
index 4d54bf4..f82681d 100644
--- a/service_provider.c
+++ b/service_provider.c
@@ -1,6 +1,7 @@
/* implementation of a basic service provider for use with the trusted
* module */
+#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
@@ -27,8 +28,8 @@ struct file_record {
int version;
int counter;
- struct iomt_node *acl;
- int acl_nodes;
+ struct iomt_node *acl_leaves;
+ int acl_nleaves;
struct tm_cert fr_cert; /* issued by module */
hash_t fr_hmac;
@@ -43,10 +44,10 @@ struct service_provider {
/* stored in sorted order; eventually a hash table would be
* wise */
struct file_record *records;
- size_t nrecords; /* must be an integer power of two */
+ size_t nrecords;
struct iomt_node *mt_leaves; /* leaves of CDI-IOMT, value is counter */
- int mt_leafcount;
+ 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:
@@ -66,6 +67,48 @@ struct service_provider {
* 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)
{
@@ -74,46 +117,35 @@ struct service_provider *sp_new(const void *key, size_t keylen, int logleaves)
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));
- /* everything else is already zeroed by calloc */
- return sp;
-}
+ /* 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 };
-/* Calculate the indicies of the complementary nodes to a
- * leaf. `leafidx' is 0 for the rightmost leaf node. This function
- * will return an array with a length equal to the number of levels in
- * the tree minus one (the root is not a complentary node). The 0th
- * element of the returned array will be the index of the immediate
- * sibling, while the 1st element will be the index of the
- * complementary node one level above the leaf node, and so on. Note
- * that logleaves = log2(nleaves) */
-static int *merkle_complement(int leafidx, int logleaves)
-{
- int *comp = calloc(logleaves, sizeof(int));
+ /* loop around */
+ sp->mt_leaves[sp->mt_leafcount - 1] = (struct iomt_node) { sp->mt_leafcount, 1, hash_null };
- /* true index of leaf */
- int idx = (1 << logleaves) - 1 + leafidx;
+ fill_tree(sp);
- /* progress up the tree */
- for(int i = 0; i < logleaves; ++i)
- {
- /* output index of sibling node */
- comp[i] = idx + ((idx & 1) ? 1 : -1);
-
- /* find parent index and loop */
- idx = (idx - ((idx & 1) ? 1 : 2)) / 2;
- }
-
- return comp;
+ /* 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)
{
- /* TODO */
+ 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
@@ -151,11 +183,16 @@ struct tm_cert sp_request(struct service_provider *sp,
need_insert = true;
}
+ rec->version = fr.fr.version;
+ rec->counter = fr.fr.counter;
+ rec->fr_cert = fr;
+ rec->fr_hmac = fr_hmac;
-
- /* TODO */
if(need_insert)
insert_record(sp, rec);
+
+ /* update our tree */
+ /* TODO */
}
/* return values to caller */
@@ -177,7 +214,8 @@ void check(int condition);
void sp_test(void)
{
/* 2^10 = 1024 leaves ought to be enough for anybody */
- struct service_provider *sp = sp_new("a", 1, 10);
+ 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;
@@ -267,7 +305,39 @@ void sp_test(void)
check(new_fr.type == FR);
printf("Complement calculation: ");
- int *comp = merkle_complement(6, 4);
+ int *orders;
+ int *comp = merkle_complement(6, 4, &orders);
int correct[] = { 22, 9, 3, 2 };
- check(!memcmp(comp, correct, 4 * sizeof(int)));
+ 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)));
+ }
}