aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rwxr-xr-xa.outbin0 -> 40096 bytes
-rw-r--r--crypto.c6
-rw-r--r--crypto.h7
-rw-r--r--helper.c63
-rw-r--r--helper.h13
-rw-r--r--service_provider.c145
-rw-r--r--service_provider.h36
-rw-r--r--trusted_module.c39
-rw-r--r--trusted_module.h54
9 files changed, 273 insertions, 90 deletions
diff --git a/a.out b/a.out
new file mode 100755
index 0000000..c7aab9e
--- /dev/null
+++ b/a.out
Binary files differ
diff --git a/crypto.c b/crypto.c
index 6039b7f..da4ef61 100644
--- a/crypto.c
+++ b/crypto.c
@@ -59,6 +59,12 @@ hash_t hash_xor(hash_t a, hash_t b)
return a;
}
+void hash_zero(hash_t *h)
+{
+ for(int i = 0; i < 32; ++i)
+ h->hash[i] = 0;
+}
+
/* NOTE: we fail to distinguish between intermediate and leaf
* nodes, making a second-preimage attack possible */
/* order: 0: u is left, v is right, 1: u is right, v is left */
diff --git a/crypto.h b/crypto.h
index e120821..d536a39 100644
--- a/crypto.h
+++ b/crypto.h
@@ -16,12 +16,17 @@ struct iomt_node {
int idx, next_idx; /* idx cannot be zero */
hash_t val; /* all zero indicates placeholder */
};
+
+/* guaranteed to be zero */
+static const struct hash_t hash_null = { { 0 } };
+
bool encloses(int b, int bprime, int a);
bool hash_equals(hash_t a, hash_t b);
bool is_zero(hash_t u);
hash_t hash_node(const struct iomt_node *node);
hash_t hash_xor(hash_t a, hash_t b);
+void hash_zero(hash_t *h);
hash_t sha256(const void *data, size_t datalen);
hash_t hmac_sha256(const void *data, size_t datalen, const void *key, size_t keylen);
@@ -29,7 +34,7 @@ hash_t hmac_sha256(const void *data, size_t datalen, const void *key, size_t key
hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t n);
hash_t merkle_parent(hash_t u, hash_t v, int order);
-uint64_t hash_to_u64(hash_t h);
+uint64_t hash_to_u64(hash_t h);
void dump_hash(hash_t u);
#endif
diff --git a/helper.c b/helper.c
index 20b6ac9..6537c89 100644
--- a/helper.c
+++ b/helper.c
@@ -4,6 +4,8 @@
* certificates to function. This file provides various helper
* functions to handle the generation of these needed certificates. */
+#include <assert.h>
+
#include "crypto.h"
#include "trusted_module.h"
@@ -25,20 +27,59 @@ struct tm_cert cert_ru(struct trusted_module *tm,
}
struct tm_cert cert_rv(struct trusted_module *tm,
- const struct iomt_node *node,
- const hash_t *comp, const int *orders, size_t n,
- hash_t *hmac_out)
+ const struct iomt_node *node,
+ const hash_t *comp, const int *orders, size_t n,
+ hash_t *hmac_out)
{
hash_t nu_hmac;
struct tm_cert nu = tm_cert_node_update(tm,
- hash_node(node),
- hash_node(node),
- comp, orders, n,
- &nu_hmac);
+ hash_node(node),
+ hash_node(node),
+ comp, orders, n,
+ &nu_hmac);
return tm_cert_record_verify(tm,
- &nu, nu_hmac,
- node,
- hmac_out,
- 0, NULL, NULL);
+ &nu, nu_hmac,
+ node,
+ hmac_out,
+ 0, NULL, NULL);
+}
+
+/* generate an EQ certificate for inserting a placeholder with index
+ * a, given an encloser (which must actually enclose a) */
+struct tm_cert cert_eq(struct trusted_module *tm,
+ const struct iomt_node *encloser,
+ int a,
+ const hash_t *enc_comp, const int *enc_orders, size_t enc_n,
+ const hash_t *ins_comp, const int *ins_orders, size_t ins_n,
+ hash_t *hmac_out)
+{
+ assert(encloses(encloser->idx, encloser->next_idx, a));
+
+ struct iomt_node encloser_mod = *encloser;
+ encloser_mod.next_idx = a;
+
+ struct iomt_node insert;
+ insert.idx = a;
+ insert.next_idx = encloser->next_idx;
+ insert.val = hash_null;
+
+ hash_t h_enc = hash_node(encloser);
+ hash_t h_encmod = hash_node(&encloser_mod);
+
+ hash_t h_ins = hash_node(&insert);
+
+ /* we need two NU certificates */
+ hash_t nu1_hmac, nu2_hmac;
+
+ struct tm_cert nu1 = tm_cert_node_update(tm,
+ h_enc, h_encmod,
+ enc_comp, enc_orders, enc_n,
+ &nu1_hmac);
+
+ struct tm_cert nu2 = tm_cert_node_update(tm,
+ hash_null, h_ins,
+ ins_comp, ins_orders, ins_n,
+ &nu2_hmac);
+ return tm_cert_equiv(tm, &nu1, nu1_hmac, &nu2, nu2_hmac, encloser, a, hmac_out);
}
diff --git a/helper.h b/helper.h
index bc74442..6abda23 100644
--- a/helper.h
+++ b/helper.h
@@ -9,6 +9,13 @@ struct tm_cert cert_ru(struct trusted_module *tm,
struct tm_cert *nonexist, hash_t *hmac_nonexist);
struct tm_cert cert_rv(struct trusted_module *tm,
- const struct iomt_node *node,
- const hash_t *comp, const int *orders, size_t n,
- hash_t *hmac_out);
+ const struct iomt_node *node,
+ const hash_t *comp, const int *orders, size_t n,
+ hash_t *hmac_out);
+
+struct tm_cert cert_eq(struct trusted_module *tm,
+ const struct iomt_node *encloser,
+ int a,
+ const hash_t *enc_comp, const int *enc_orders, size_t enc_n,
+ const hash_t *ins_comp, const int *ins_orders, size_t ins_n,
+ hash_t *hmac_out);
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)));
}
diff --git a/service_provider.h b/service_provider.h
index ec12aaa..883c9ea 100644
--- a/service_provider.h
+++ b/service_provider.h
@@ -9,41 +9,7 @@
struct service_provider;
-struct user_request {
- int idx;
- int user_id; /* user id */
- enum { ACL_UPDATE, FILE_UPDATE } type;
- int counter;
- hash_t val; /* for ACL update, val=[root of ACL IOMT], for file
- * update, val is a commitment to the contents, key,
- * and index of the file */
- union {
- /* if counter = 0 and type = ACL_UPDATE, create a new file with given ACL */
- struct {
- struct tm_cert ru_cert;
- hash_t ru_hmac;
- } create;
-
- /* otherwise the request is to modify either the file or
- * ACL */
- struct {
- /* FR certificate verifying file ACL and counter */
- struct tm_cert fr_cert;
- hash_t fr_hmac;
-
- /* RV certificate verifying that user is in the ACL */
- struct tm_cert rv_cert;
- hash_t rv_hmac;
-
- /* RU certificate indicating updated counter value in
- * IOMT */
- struct tm_cert ru_cert;
- hash_t ru_hmac;
- } modify;
- };
-};
-
-struct service_provider *sp_new(const void *key, size_t keylen);
+struct service_provider *sp_new(const void *key, size_t keylen, int logleaves);
struct tm_cert sp_request(struct service_provider *sp,
const struct user_request *req, hash_t req_hmac,
hash_t *hmac_out,
diff --git a/trusted_module.c b/trusted_module.c
index bf1bf78..82016ef 100644
--- a/trusted_module.c
+++ b/trusted_module.c
@@ -58,7 +58,7 @@ struct trusted_module *tm_new(const void *key, size_t keylen)
memset(boot.val.hash, 0, sizeof(boot.val.hash));
boot.next_idx = 1;
tm->root = merkle_compute(hash_node(&boot), NULL, NULL, 0);
-
+
return tm;
}
@@ -90,9 +90,6 @@ struct tm_cert tm_cert_node_update(struct trusted_module *tm, hash_t orig, hash_
return cert;
}
-static const struct tm_cert cert_null = { NONE };
-static const struct hash_t hash_null = { { 0 } };
-
static const char *tm_error = NULL;
static void tm_seterror(const char *error)
{
@@ -127,7 +124,7 @@ struct tm_cert tm_cert_combine(struct trusted_module *tm,
tm_seterror("improper cert authentication");
return cert_null;
}
-
+
if(hash_equals(nu1->nu.new_node, nu2->nu.orig_node) &&
hash_equals(nu1->nu.new_root, nu2->nu.orig_root))
{
@@ -281,7 +278,7 @@ struct tm_cert tm_cert_record_update(struct trusted_module *tm,
tm_seterror("improper certificate authentication");
return cert_null;
}
-
+
hash_t orig_h = hash_node(node);
struct iomt_node new_node = *node;
@@ -294,7 +291,7 @@ struct tm_cert tm_cert_record_update(struct trusted_module *tm,
tm_seterror("NU hashes do not match node hashes");
return cert_null;
}
-
+
struct tm_cert cert;
memset(&cert, 0, sizeof(cert));
@@ -370,12 +367,12 @@ static hash_t req_ack(const struct trusted_module *tm, const struct user_request
hash_t hmac;
HMAC_Final(ctx, hmac.hash, NULL);
HMAC_CTX_free(ctx);
-
+
return hmac;
}
/* execute a user request, if possible */
-/*
+/*
* This function handles all transformations on the IOMT except
* inserting a placeholder (handled above). The function takes its
* parameter in the form of a user_request struct, which must be
@@ -439,7 +436,7 @@ struct tm_cert tm_request(struct trusted_module *tm,
tm_seterror("improper authentication");
return cert_null;
}
-
+
/* invalid request type */
if(req->type != ACL_UPDATE && req->type != FILE_UPDATE)
return cert_null;
@@ -485,7 +482,7 @@ struct tm_cert tm_request(struct trusted_module *tm,
dump_hash(tm->root);
return cert_null;
}
-
+
/* update the IOMT root */
tm->root = req->create.ru_cert.ru.new_root;
@@ -513,7 +510,7 @@ struct tm_cert tm_request(struct trusted_module *tm,
return cert_null;
if(!cert_verify(tm, &req->modify.ru_cert, req->modify.ru_hmac))
return cert_null;
-
+
/* check that FR and RU certificate indices match request index */
if(req->modify.fr_cert.fr.idx != req->idx ||
req->modify.ru_cert.ru.idx != req->idx)
@@ -531,7 +528,7 @@ struct tm_cert tm_request(struct trusted_module *tm,
* the counter value. */
if(hash_to_u64(req->modify.ru_cert.ru.orig_val) + 1 != hash_to_u64(req->modify.ru_cert.ru.new_val))
return cert_null;
-
+
/* check access level using RV cert, which verifies a record in
* the ACL tree. */
if(!hash_equals(req->modify.fr_cert.fr.acl, req->modify.rv_cert.rv.root))
@@ -546,7 +543,7 @@ struct tm_cert tm_request(struct trusted_module *tm,
/* no write access to file or ACL */
if(access < 2)
return cert_null;
-
+
/* file update */
if(req->type == FILE_UPDATE)
{
@@ -566,13 +563,13 @@ struct tm_cert tm_request(struct trusted_module *tm,
vr_cert.vr.idx = req->idx;
vr_cert.vr.version = req->modify.fr_cert.fr.version + 1;
vr_cert.vr.hash = req->val;
-
+
*vr_hmac = cert_sign(tm, &vr_cert);
*vr_out = vr_cert;
tm->root = req->modify.ru_cert.ru.new_root;
*hmac_ack = req_ack(tm, req);
-
+
return fr_cert;
}
else if(req->type == ACL_UPDATE)
@@ -584,7 +581,7 @@ struct tm_cert tm_request(struct trusted_module *tm,
cert.fr.counter = req->counter + 1;
cert.fr.version = req->modify.fr_cert.fr.version;
cert.fr.acl = req->val;
-
+
*hmac_out = cert_sign(tm, &cert);
tm->root = req->modify.ru_cert.ru.new_root;
@@ -680,7 +677,7 @@ void tm_test(void)
printf("Merkle compute: ");
check(hash_equals(root1, root2));
}
-
+
{
/* check NU certificate generation */
struct trusted_module *tm = tm_new("a", 1);
@@ -692,7 +689,7 @@ void tm_test(void)
hash_t root_1, root_2, root_3;
root_1 = merkle_compute(node, comp, orders, 1);
root_2 = merkle_compute(node_new, comp, orders, 1);
-
+
hash_t hmac;
struct tm_cert nu = tm_cert_node_update(tm, node, node_new, comp, orders, 1, &hmac);
printf("NU generation: ");
@@ -721,11 +718,11 @@ void tm_test(void)
hash_equals(cat.nu.new_root, root_3) &&
hash_equals(cat.nu.new_node, node_3) &&
cert_verify(tm, &cat, hmac_cat));
-
+
//tm_free(tm);
}
{
-
+
}
}
diff --git a/trusted_module.h b/trusted_module.h
index 7ecfa9f..2b3b56d 100644
--- a/trusted_module.h
+++ b/trusted_module.h
@@ -48,6 +48,42 @@ struct tm_cert {
};
};
+struct user_request {
+ int idx;
+ int user_id; /* user id */
+ enum { ACL_UPDATE, FILE_UPDATE } type;
+ int counter;
+ hash_t val; /* for ACL update, val=[root of ACL IOMT], for file
+ * update, val is a commitment to the contents, key,
+ * and index of the file */
+ union {
+ /* if counter = 0 and type = ACL_UPDATE, create a new file with given ACL */
+ struct {
+ struct tm_cert ru_cert;
+ hash_t ru_hmac;
+ } create;
+
+ /* otherwise the request is to modify either the file or
+ * ACL */
+ struct {
+ /* FR certificate verifying file ACL and counter */
+ struct tm_cert fr_cert;
+ hash_t fr_hmac;
+
+ /* RV certificate verifying that user is in the ACL */
+ struct tm_cert rv_cert;
+ hash_t rv_hmac;
+
+ /* RU certificate indicating updated counter value in
+ * IOMT */
+ struct tm_cert ru_cert;
+ hash_t ru_hmac;
+ } modify;
+ };
+};
+
+static const struct tm_cert cert_null = { NONE };
+
/* creates 1 user with given shared secret */
struct trusted_module *tm_new(const void *key, size_t keylen);
void tm_free(struct trusted_module *tm);
@@ -60,14 +96,28 @@ void tm_test(void);
* NULL). Passing the [return, orig, new, orig_root, new_root] to the
* module in the future will serve to verify this check. */
/* complementary nodes and order are passed as usual */
-struct tm_cert tm_cert_node_update(struct trusted_module *tm, hash_t orig, hash_t new, const hash_t *comp, const int *orders, size_t n, hash_t *hmac);
+struct tm_cert tm_cert_node_update(struct trusted_module *tm,
+ hash_t orig, hash_t new,
+ const hash_t *comp, const int *orders, size_t n,
+ hash_t *hmac);
/* takes two NU certificates, one stating [a is child of x]->[b is
* child of y], and one stating [b is child of y]->[c is child of z],
* and generate a certificate stating [a is child of x]->[c is child
* of z] */
-struct tm_cert tm_cert_combine(struct trusted_module *tm, const struct tm_cert *nu1, hash_t hmac1, const struct tm_cert *nu2, hash_t hmac2, hash_t *hmac_out);
+struct tm_cert tm_cert_combine(struct trusted_module *tm,
+ const struct tm_cert *nu1, hash_t hmac1,
+ const struct tm_cert *nu2, hash_t hmac2,
+ hash_t *hmac_out);
+/* Let ve = h(b, b', wb). */
+/* Let ve' = h(b, a, wb). */
+/* Let vi' = h(a, b', 0). */
+/* nu_encl should certify that given [ve is child of y], then [ve' is child of y'] */
+/* nu_ins should certify that given [0 is child of y'], then [vi' is child of y''] */
+/* this function will then issue a certificate verifying that y and
+ * y'' are equivalent roots, indicating that they differ only in y''
+ * having an additional placeholder node with index a */
struct tm_cert tm_cert_equiv(struct trusted_module *tm,
const struct tm_cert *nu_encl, hash_t hmac_encl,
const struct tm_cert *nu_ins, hash_t hmac_ins,