diff options
| -rw-r--r-- | crypto.c | 65 | ||||
| -rw-r--r-- | crypto.h | 18 | ||||
| -rw-r--r-- | service_provider.c | 179 | ||||
| -rw-r--r-- | service_provider.h | 18 | ||||
| -rw-r--r-- | test.c | 13 | ||||
| -rw-r--r-- | test.h | 2 | ||||
| -rw-r--r-- | trusted_module.c | 48 | ||||
| -rw-r--r-- | trusted_module.h | 13 |
8 files changed, 266 insertions, 90 deletions
@@ -1,4 +1,5 @@ #include "crypto.h" +#include "test.h" #include <string.h> @@ -262,6 +263,24 @@ void merkle_update(struct iomt *tree, uint64_t leafidx, hash_t newval, hash_t ** } } +/* find a node with given idx */ +struct iomt_node *lookup_leaf(struct iomt *tree, int idx) +{ + for(int i = 0; i < tree->mt_leafcount; ++i) + if(idx == tree->mt_leaves[i].idx) + return tree->mt_leaves + i; + return NULL; +} + +void iomt_update(struct iomt *tree, uint64_t idx, hash_t newval) +{ + /* update the leaf first, then use merkle_update */ + struct iomt_node *leaf = lookup_leaf(tree, idx); + leaf->val = newval; + + merkle_update(tree, idx, hash_node(leaf), NULL); +} + /* Create a merkle tree with 2^logleaves leaves, each initialized to a * zero leaf (not a placeholder!) */ struct iomt *iomt_new(int logleaves) @@ -276,6 +295,36 @@ struct iomt *iomt_new(int logleaves) return tree; } +void iomt_free(struct iomt *tree) +{ + /* TODO */ + if(tree) + { + } +} + +struct hashstring hash_format(hash_t h, int n) +{ + struct hashstring ret; + for(int i = 0; i < n; ++i) + { + sprintf(ret.str + 2 * i, "%02x", h.hash[i]); + } + return ret; +} + +void iomt_dump(struct iomt *tree) +{ + for(int i = 0; i < tree->mt_leafcount; ++i) + { + printf("(%d, %s, %d)%s", + tree->mt_leaves[i].idx, + hash_format(tree->mt_leaves[i].val, 4).str, + tree->mt_leaves[i].next_idx, + (i == tree->mt_leafcount - 1) ? "\n" : ", "); + } +} + /* convert the first 8 bytes (little endian) to a 64-bit int */ uint64_t hash_to_u64(hash_t h) { @@ -295,3 +344,19 @@ hash_t u64_to_hash(uint64_t n) } return ret; } + +void crypto_test(void) +{ + int *orders; + int *comp = merkle_complement(6, 4, &orders); + int correct[] = { 22, 9, 3, 2 }; + int correct_orders[] = { 1, 0, 0, 1 }; + check("Complement calculation", !memcmp(comp, correct, 4 * sizeof(int)) && !memcmp(orders, correct_orders, 4 * sizeof(int))); + free(orders); + free(comp); + + int *dep = merkle_dependents(6, 4); + int correct_dep[] = { 10, 4, 1, 0 }; + check("Dependency calculation", !memcmp(dep, correct_dep, 4 * sizeof(int))); + free(dep); +} @@ -78,15 +78,19 @@ int *merkle_dependents(int leafidx, int logleaves); hash_t *lookup_nodes(const hash_t *nodes, const int *indices, int n); void restore_nodes(hash_t *nodes, const int *indices, const hash_t *values, int n); -/* IOMT: */ -struct iomt *iomt_new(int logleaves); - /* This function is prefixed merkle_ because it does not know about * any IOMT-specific properties (though it is still passed an iomt * struct) */ void merkle_update(struct iomt *tree, uint64_t leafidx, hash_t newval, hash_t **old_dep); +struct iomt *iomt_new(int logleaves); +void iomt_update(struct iomt *tree, uint64_t idx, hash_t newval); void iomt_fill(struct iomt *tree); +void iomt_dump(struct iomt *tree); +struct iomt_node *lookup_leaf(struct iomt *tree, int idx); +void iomt_free(struct iomt *tree); + +struct iomt_node *lookup_leaf(struct iomt *tree, int idx); int bintree_parent(int idx); int bintree_sibling(int idx); @@ -95,4 +99,12 @@ uint64_t hash_to_u64(hash_t h); hash_t u64_to_hash(uint64_t n); void dump_hash(hash_t u); +struct hashstring { + char str[32 * 2 + 1]; +}; + +struct hashstring hash_format(hash_t h, int n); + +/* self-test */ +void crypto_test(void); #endif diff --git a/service_provider.c b/service_provider.c index f211309..32d4fe2 100644 --- a/service_provider.c +++ b/service_provider.c @@ -9,8 +9,11 @@ #include "crypto.h" #include "helper.h" #include "service_provider.h" +#include "test.h" #include "trusted_module.h" +#define ACL_LOGLEAVES 4 + struct file_version { hash_t kf; /* HMAC(key, file_idx) */ hash_t l; /* HMAC(h(encrypted contents), kf) */ @@ -28,8 +31,7 @@ struct file_record { uint64_t version; uint64_t counter; - struct iomt_node *acl_leaves; - int acl_nleaves; + struct iomt *acl; struct tm_cert fr_cert; /* issued by module */ hash_t fr_hmac; @@ -113,9 +115,6 @@ struct tm_cert cert_eq(struct service_provider *sp, return tm_cert_equiv(sp->tm, &nu1, nu1_hmac, &nu2, nu2_hmac, encloser, placeholder_nodeidx, hmac_out); } -/* in trusted_module.c */ -void check(int condition); - /* leaf count will be 2^logleaves */ struct service_provider *sp_new(const void *key, size_t keylen, int logleaves) { @@ -177,7 +176,6 @@ static struct file_record *lookup_record(struct service_provider *sp, int idx) /* 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. */ - /* We do not check to ensure that there are no duplicate file indices; * this is up to the caller */ static void append_record(struct service_provider *sp, const struct file_record *rec) @@ -204,6 +202,10 @@ static void append_version(struct file_record *rec, const struct file_version *v * (otherwise they are ignored). `encrypted_secret' should be the file * encryption key XOR'd with HMAC(file index | file counter, * user_key). kf should be HMAC(encryption secret, file index). + * + * If the request is to either modify the ACL or create a file (which + * is essentially an ACL update), the ACL will be set to + * new_acl. `new_acl' must be in persistent storage. */ struct tm_cert sp_request(struct service_provider *sp, const struct user_request *req, hash_t req_hmac, @@ -211,8 +213,8 @@ struct tm_cert sp_request(struct service_provider *sp, struct tm_cert *vr_out, hash_t *vr_hmac_out, hash_t *ack_hmac_out, hash_t encrypted_secret, hash_t kf, - const void *encrypted_contents, - size_t contents_len) + const void *encrypted_contents, size_t contents_len, + struct iomt *new_acl) { struct tm_cert vr = cert_null; hash_t vr_hmac, ack_hmac, fr_hmac; @@ -233,10 +235,21 @@ struct tm_cert sp_request(struct service_provider *sp, need_insert = true; } + rec->idx = fr.fr.idx; rec->counter = fr.fr.counter; rec->fr_cert = fr; rec->fr_hmac = fr_hmac; + if(req->type == ACL_UPDATE) + { + /* update our ACL */ + iomt_free(rec->acl); + rec->acl = new_acl; + + /* check that the passed value matches the calculated root */ + assert(hash_equals(req->val, new_acl->mt_nodes[0])); + } + if(rec->version != fr.fr.version) { rec->version = fr.fr.version; @@ -298,76 +311,134 @@ struct tm_cert sp_request(struct service_provider *sp, return fr; } -void sp_test(void) +struct user_request sp_createfile(struct service_provider *sp, + uint64_t user_id, const void *key, size_t keylen, + hash_t *ack_hmac) { - /* 2^10 = 1024 leaves ought to be enough for anybody */ - int logleaves = 4; - struct service_provider *sp = sp_new("a", 1, logleaves); + int i; + for(i = 0; i < sp->iomt->mt_leafcount; ++i) + { + if(is_zero(sp->iomt->mt_leaves[i].val)) + break; + } + + /* fail */ + if(i == sp->iomt->mt_leafcount) + { + return req_null; + } - /* construct a request to create a file */ - printf("File creation: "); int *file_compidx, *file_orders; - file_compidx = merkle_complement(0, sp->iomt->mt_logleaves, &file_orders); + file_compidx = merkle_complement(i, sp->iomt->mt_logleaves, &file_orders); hash_t *file_comp = lookup_nodes(sp->iomt->mt_nodes, file_compidx, sp->iomt->mt_logleaves); - struct user_request req = req_filecreate(sp->tm, 1, - sp->iomt->mt_leaves + 0, - file_comp, file_orders, sp->iomt->mt_logleaves); + struct iomt *acl = iomt_new(ACL_LOGLEAVES); + acl->mt_leaves[0] = (struct iomt_node) { user_id, user_id, u64_to_hash(3) }; + merkle_update(acl, 0, hash_node(acl->mt_leaves + 0), NULL); - hash_t req_hmac = hmac_sha256(&req, sizeof(req), "a", 1); + struct user_request req = req_filecreate(sp->tm, + i + 1, + sp->iomt->mt_leaves + i, + file_comp, file_orders, sp->iomt->mt_logleaves); + hash_t req_hmac = hmac_sha256(&req, sizeof(req), key, keylen); 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, - hash_null, hash_null, NULL, 0); + struct tm_cert fr_cert = sp_request(sp, + &req, req_hmac, + &fr_hmac, + NULL, NULL, + ack_hmac, + hash_null, hash_null, NULL, 0, + acl); + if(fr_cert.type == FR) + return req; + return req_null; +} + +struct user_request sp_modifyfile(struct service_provider *sp, + uint64_t user_id, const void *key, size_t keylen, + uint64_t file_idx, + hash_t encrypted_secret, + const void *encrypted_file, size_t filelen, + hash_t *ack_hmac) +{ + /* modification */ + struct file_record *rec = lookup_record(sp, file_idx); + if(!rec) + return req_null; - check(fr_cert.type == FR && - fr_cert.fr.counter == 1 && - fr_cert.fr.version == 0); + struct iomt_node *file_node = lookup_leaf(sp->iomt, file_idx); - struct iomt_node acl_node = (struct iomt_node) { 1, 1, u64_to_hash(3) }; + /* hack */ + int leaf_idx = file_node - sp->iomt->mt_leaves; + + int *file_compidx, *file_orders; + file_compidx = merkle_complement(leaf_idx, sp->iomt->mt_logleaves, &file_orders); + + hash_t *file_comp = lookup_nodes(sp->iomt->mt_nodes, file_compidx, sp->iomt->mt_logleaves); + + /* get ACL node and its complement */ + struct iomt_node *acl_node = lookup_leaf(rec->acl, user_id); + int aclnode_idx = acl_node - rec->acl->mt_leaves; + int *acl_orders; + int *acl_compidx = merkle_complement(aclnode_idx, rec->acl->mt_logleaves, &acl_orders); + + hash_t *acl_comp = lookup_nodes(rec->acl->mt_nodes, acl_compidx, rec->acl->mt_logleaves); - /* modification */ struct user_request mod = req_filemodify(sp->tm, - &fr_cert, fr_hmac, - sp->iomt->mt_leaves + 0, + &rec->fr_cert, rec->fr_hmac, + file_node, file_comp, file_orders, sp->iomt->mt_logleaves, - &acl_node, - NULL, NULL, 0, + acl_node, + acl_comp, acl_orders, rec->acl->mt_logleaves, hash_null); - req_hmac = hmac_sha256(&mod, sizeof(mod), "a", 1); + hash_t req_hmac = hmac_sha256(&mod, sizeof(mod), key, keylen); struct tm_cert vr; - hash_t vr_hmac; + hash_t vr_hmac, fr_hmac; + + struct tm_cert new_fr = sp_request(sp, &mod, req_hmac, &fr_hmac, &vr, &vr_hmac, ack_hmac, + hash_null, hash_null, "contents", 8, NULL); + if(new_fr.type == FR) + return mod; + return req_null; +} + +static bool ack_verify(const struct user_request *req, + const void *secret, size_t secret_len, + hash_t hmac) +{ + hash_t correct = ack_sign(req, secret, secret_len); + return hash_equals(hmac, correct); +} + +void sp_test(void) +{ + /* 2^10 = 1024 leaves ought to be enough for anybody */ + int logleaves = 2; + struct service_provider *sp = sp_new("a", 1, logleaves); + + check("Tree initialization", sp != NULL); + + hash_t ack_hmac; + struct user_request req = sp_createfile(sp, 1, "a", 1, &ack_hmac); + + check("File creation", ack_verify(&req, "a", 1, ack_hmac)); + + req = sp_modifyfile(sp, 1, "a", 1, 1, hash_null, NULL, 0, &ack_hmac); + + check("File modification", ack_verify(&req, "a", 1, ack_hmac)); - struct tm_cert new_fr = sp_request(sp, &mod, req_hmac, &fr_hmac, &vr, &vr_hmac, &ack_hmac, - hash_null, hash_null, "contents", 8); - 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))); - free(orders); - free(comp); - - printf("Dependency calculation: "); - int *dep = merkle_dependents(6, 4); - int correct_dep[] = { 10, 4, 1, 0 }; - check(!memcmp(dep, correct_dep, 4 * sizeof(int))); - free(dep); + printf("CDI-IOMT contents: "); + iomt_dump(sp->iomt); /* 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->iomt->mt_nodes[0], merkle_parent(hash_node(&a), hash_node(&b), 0))); + check("Merkle tree initialization", hash_equals(sp->iomt->mt_nodes[0], merkle_parent(hash_node(&a), hash_node(&b), 0))); } } diff --git a/service_provider.h b/service_provider.h index 6deb814..a9860cc 100644 --- a/service_provider.h +++ b/service_provider.h @@ -18,8 +18,22 @@ struct tm_cert sp_request(struct service_provider *sp, struct tm_cert *vr_out, hash_t *vr_hmac_out, hash_t *ack_hmac_out, hash_t encrypted_secret, hash_t kf, - const void *encrypted_contents, - size_t contents_len); + const void *encrypted_contents, size_t contents_len, + struct iomt *new_acl); + +/* Reserve a new file index with user_id added to the ACL. Returns + * cert on failure. Authenticated with ack_hmac, which is the returned + * request with a zero byte appended, signed by the module. */ +struct user_request sp_createfile(struct service_provider *sp, + uint64_t user_id, const void *key, size_t keylen, + hash_t *ack_hmac); + +struct user_request sp_modifyfile(struct service_provider *sp, + uint64_t user_id, const void *key, size_t keylen, + uint64_t file_idx, + hash_t encrypted_secret, + const void *encrypted_file, size_t filelen, + hash_t *ack_hmac); void sp_test(void); @@ -1,8 +1,21 @@ +#include <stdio.h> + #include "service_provider.h" #include "trusted_module.h" +void check(const char *name, int condition) +{ + printf("%s: %s", name, condition ? "\033[32;1mPASS\033[0m\n" : "\033[31;1mFAIL\033[0m\n"); + if(!condition) + { + printf("%s\n", tm_geterror()); + tm_seterror(NULL); + } +} + int main() { tm_test(); sp_test(); + crypto_test(); } @@ -0,0 +1,2 @@ +/* testing */ +void check(const char *name, int condition); diff --git a/trusted_module.c b/trusted_module.c index b3db5b2..ec3d286 100644 --- a/trusted_module.c +++ b/trusted_module.c @@ -16,6 +16,7 @@ #include "crypto.h" #include "service_provider.h" +#include "test.h" #include "trusted_module.h" struct user_key { @@ -36,9 +37,8 @@ struct trusted_module { static void tm_setroot(struct trusted_module *tm, hash_t newroot) { - //printf("New root: "); + printf("TM: %s -> %s\n", hash_format(tm->root, 4).str, hash_format(newroot, 4).str); tm->root = newroot; - //dump_hash(tm->root); } struct trusted_module *tm_new(const void *key, size_t keylen) @@ -99,7 +99,7 @@ struct tm_cert tm_cert_node_update(const struct trusted_module *tm, } static const char *tm_error = NULL; -static void tm_seterror(const char *error) +void tm_seterror(const char *error) { tm_error = error; } @@ -386,12 +386,11 @@ static bool req_verify(const struct trusted_module *tm, const struct user_reques /* Generate a signed acknowledgement for successful completion of a * request. We append a zero byte to the user request and take the * HMAC. */ -static hash_t req_ack(const struct trusted_module *tm, const struct user_request *req) +hash_t ack_sign(const struct user_request *req, const void *key, size_t keylen) { HMAC_CTX *ctx = HMAC_CTX_new(); HMAC_Init_ex(ctx, - tm->user_keys[req->user_id - 1].key, - tm->user_keys[req->user_id - 1].len, + key, keylen, EVP_sha256(), NULL); HMAC_Update(ctx, (const unsigned char*)req, sizeof(*req)); @@ -406,6 +405,13 @@ static hash_t req_ack(const struct trusted_module *tm, const struct user_request return hmac; } +static hash_t req_ack(const struct trusted_module *tm, const struct user_request *req) +{ + return ack_sign(req, + tm->user_keys[req->user_id - 1].key, + tm->user_keys[req->user_id - 1].len); +} + /* execute a user request, if possible */ /* * This function handles all transformations on the IOMT except @@ -790,14 +796,6 @@ hash_t tm_retrieve_secret(const struct trusted_module *tm, } /* self-test */ -const char *tm_geterror(void); -void check(int condition) -{ - printf(condition ? "\033[32;1mPASS\033[0m\n" : "\033[31;1mFAIL\033[0m\n"); - if(!condition) - printf("%s\n", tm_geterror()); -} - void tm_test(void) { { @@ -809,8 +807,7 @@ void tm_test(void) /* this should return zero */ hash_t res1 = merkle_compute(zero1, &zero2, orders, 1); - printf("Merkle parent with zeros: "); - check(is_zero(res1)); + check("Merkle parent with zeros", is_zero(res1)); hash_t a = sha256("a", 1); hash_t b = sha256("b", 1); @@ -822,8 +819,7 @@ void tm_test(void) memcpy(buf, c.hash, 32); memcpy(buf + 32, d.hash, 32); //dump_hash(sha256(buf, 64)); - printf("Merkle parent: "); - check(hash_equals(sha256(buf, 64), cd)); + check("Merkle parent", hash_equals(sha256(buf, 64), cd)); hash_t a_comp[] = { b, cd }; int a_orders[] = { 1, 1 }; @@ -833,8 +829,7 @@ void tm_test(void) hash_t root2 = merkle_parent(ab, cd, 0); //dump_hash(root1); //dump_hash(root2); - printf("Merkle compute: "); - check(hash_equals(root1, root2)); + check("Merkle compute", hash_equals(root1, root2)); } { @@ -851,17 +846,14 @@ void tm_test(void) hash_t hmac; struct tm_cert nu = tm_cert_node_update(tm, node, node_new, comp, orders, 1, &hmac); - printf("NU generation: "); - check(nu.type == NU && + check("NU generation", nu.type == NU && hash_equals(nu.nu.orig_node, node) && hash_equals(nu.nu.orig_root, merkle_compute(node, comp, orders, 1)) && hash_equals(nu.nu.new_node, node_new) && hash_equals(nu.nu.new_root, merkle_compute(node_new, comp, orders, 1))); - printf("Certificate verification 1: "); - check(cert_verify(tm, &nu, hmac)); + check("Certificate verification 1", cert_verify(tm, &nu, hmac)); hash_t bogus = { { 0 } }; - printf("Certificate verification 2: "); - check(!cert_verify(tm, &nu, bogus)); + check("Certificate verification 2", !cert_verify(tm, &nu, bogus)); /* test combining NU certificates */ hash_t node_3 = sha256("c", 1); @@ -869,8 +861,8 @@ void tm_test(void) hash_t hmac2, hmac_cat; struct tm_cert nu2 = tm_cert_node_update(tm, node_new, node_3, comp, orders, 1, &hmac2); struct tm_cert cat = tm_cert_combine(tm, &nu, hmac, &nu2, hmac2, &hmac_cat); - printf("Combine NU certificates: "); - check(nu2.type == NU && + check("Combine NU certificates", + nu2.type == NU && cat.type == NU && hash_equals(cat.nu.orig_root, root_1) && hash_equals(cat.nu.orig_node, node) && diff --git a/trusted_module.h b/trusted_module.h index 8cdf65a..27dc8ec 100644 --- a/trusted_module.h +++ b/trusted_module.h @@ -11,7 +11,7 @@ struct trusted_module; struct user_request; struct tm_cert { - enum { NONE = 0, NU, EQ, RV, RU, FR, VR } type; + enum { CERT_NONE = 0, NU, EQ, RV, RU, FR, VR } type; union { struct { hash_t orig_node, new_node; @@ -51,7 +51,7 @@ struct tm_cert { struct user_request { uint64_t idx; /* file index */ uint64_t user_id; /* user id */ - enum { ACL_UPDATE, FILE_UPDATE } type; + enum { REQ_NONE = 0, ACL_UPDATE, FILE_UPDATE } type; uint64_t counter; /* current counter value, 0 for creation */ hash_t val; /* for ACL update, val=[root of ACL IOMT], for file * update, val is a commitment to the contents, key, @@ -85,7 +85,8 @@ struct user_request { }; }; -static const struct tm_cert cert_null = { NONE }; +static const struct user_request req_null = { REQ_NONE }; +static const struct tm_cert cert_null = { CERT_NONE }; /* creates 1 user with given shared secret */ struct trusted_module *tm_new(const void *key, size_t keylen); @@ -183,4 +184,10 @@ hash_t tm_retrieve_secret(const struct trusted_module *tm, const struct tm_cert *rv2, hash_t rv2_hmac, const struct tm_cert *fr, hash_t fr_hmac, hash_t secret, hash_t kf); + +hash_t ack_sign(const struct user_request *req, const void *key, size_t keylen); + +const char *tm_geterror(void); + +void tm_seterror(const char *error); #endif |