diff options
author | Franklin Wei <me@fwei.tk> | 2018-06-12 22:39:53 -0400 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2018-06-12 22:39:53 -0400 |
commit | 96f1240471dd75638f2a53b769a4a63e5e083b7e (patch) | |
tree | 5aefcfaaf3596033dfca8df745ce4fabab823748 /service_provider.c | |
parent | cae99b638f54748e52a10ca613c1758c9646e2d0 (diff) | |
download | csaa-96f1240471dd75638f2a53b769a4a63e5e083b7e.zip csaa-96f1240471dd75638f2a53b769a4a63e5e083b7e.tar.gz csaa-96f1240471dd75638f2a53b769a4a63e5e083b7e.tar.bz2 csaa-96f1240471dd75638f2a53b769a4a63e5e083b7e.tar.xz |
Various changes; also implement binary tree complement calculation
Diffstat (limited to 'service_provider.c')
-rw-r--r-- | service_provider.c | 145 |
1 files changed, 128 insertions, 17 deletions
diff --git a/service_provider.c b/service_provider.c index 34f8027..4d54bf4 100644 --- a/service_provider.c +++ b/service_provider.c @@ -23,6 +23,7 @@ struct file_version { }; struct file_record { + int idx; int version; int counter; @@ -39,31 +40,135 @@ struct file_record { struct service_provider { struct trusted_module *tm; + /* stored in sorted order; eventually a hash table would be + * wise */ struct file_record *records; - int n_records; + size_t nrecords; /* must be an integer power of two */ - struct iomt_node *mt; /* leaves of CDI-IOMT, value is counter */ - int mt_nodes; + struct iomt_node *mt_leaves; /* leaves of CDI-IOMT, value is counter */ + int 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. */ }; -struct service_provider *sp_new(const void *key, size_t keylen) +/* 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_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; } +/* 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)); + + /* true index of leaf */ + int idx = (1 << logleaves) - 1 + leafidx; + + /* 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; +} + +/* linear search for record given idx */ +static struct file_record *lookup_record(struct service_provider *sp, int idx) +{ + /* TODO */ +} + +/* 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, - hash_t *ack_hmac) + struct tm_cert *vr_out, hash_t *vr_hmac_out, + hash_t *ack_hmac_out) { - /* see if module succeeds; if so, update the databases */ - return tm_request(sp->tm, req, req_hmac, hmac_out, vr_out, vr_hmac, ack_hmac); + 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; + } + + + + /* TODO */ + if(need_insert) + insert_record(sp, rec); + } + + /* 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 */ @@ -71,7 +176,8 @@ void check(int condition); void sp_test(void) { - struct service_provider *sp = sp_new("a", 1); + /* 2^10 = 1024 leaves ought to be enough for anybody */ + struct service_provider *sp = sp_new("a", 1, 10); /* construct a request to create a file */ struct user_request req; req.idx = 1; @@ -85,7 +191,7 @@ void sp_test(void) 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); @@ -96,7 +202,7 @@ void sp_test(void) 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) */ @@ -116,7 +222,7 @@ void sp_test(void) 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: "); @@ -134,15 +240,15 @@ void sp_test(void) mod.modify.fr_hmac = fr_hmac; mod.modify.rv_cert = cert_rv(sp->tm, - &acl_node, - NULL, NULL, 0, - &mod.modify.rv_hmac); + &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; @@ -155,8 +261,13 @@ void sp_test(void) 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 *comp = merkle_complement(6, 4); + int correct[] = { 22, 9, 3, 2 }; + check(!memcmp(comp, correct, 4 * sizeof(int))); } |