aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--crypto.c117
-rw-r--r--crypto.h20
-rw-r--r--helper.c25
-rw-r--r--helper.h9
-rw-r--r--service_provider.c68
-rw-r--r--service_provider.h8
-rw-r--r--test.c2
-rw-r--r--trusted_module.c163
8 files changed, 291 insertions, 121 deletions
diff --git a/crypto.c b/crypto.c
new file mode 100644
index 0000000..6039b7f
--- /dev/null
+++ b/crypto.c
@@ -0,0 +1,117 @@
+#include "crypto.h"
+
+#include <string.h>
+
+#include <openssl/hmac.h>
+#include <openssl/sha.h>
+
+/* return true iff [b, bprime] encloses a */
+bool encloses(int b, int bprime, int a)
+{
+ return (b < a && a < bprime) || (bprime <= b && b < a) || (a < bprime && bprime <= b);
+}
+
+hash_t hash_node(const struct iomt_node *node)
+{
+ return sha256(node, sizeof(*node));
+}
+
+hash_t hmac_sha256(const void *data, size_t datalen, const void *key, size_t keylen)
+{
+ hash_t h;
+ HMAC(EVP_sha256(), key, keylen, data, datalen, h.hash, NULL);
+ return h;
+}
+
+hash_t sha256(const void *data, size_t datalen)
+{
+ hash_t h;
+ SHA256(data, datalen, h.hash);
+ return h;
+}
+
+bool is_zero(hash_t u)
+{
+ /* constant-time comparison */
+ volatile char c = 0;
+ for(int i = 0; i < 32; ++i)
+ c |= u.hash[i];
+
+ return c == 0;
+}
+
+void dump_hash(hash_t u)
+{
+ for(int i = 0; i < 32; ++i)
+ printf("%02x", u.hash[i]);
+ printf("\n");
+}
+
+bool hash_equals(hash_t a, hash_t b)
+{
+ return !memcmp(a.hash, b.hash, 32);
+}
+
+hash_t hash_xor(hash_t a, hash_t b)
+{
+ for(int i = 0; i < 32; ++i)
+ a.hash[i] ^= b.hash[i];
+ return a;
+}
+
+/* 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 */
+hash_t merkle_parent(hash_t u, hash_t v, int order)
+{
+ if(is_zero(u))
+ return v;
+ if(is_zero(v))
+ return u;
+
+ /* append and hash */
+ SHA256_CTX ctx;
+ hash_t h;
+
+ SHA256_Init(&ctx);
+
+ if(order != 0)
+ SHA256_Update(&ctx, v.hash, 32);
+
+ SHA256_Update(&ctx, u.hash, 32);
+
+ if(order == 0)
+ SHA256_Update(&ctx, v.hash, 32);
+
+ SHA256_Final(h.hash, &ctx);
+
+ return h;
+}
+
+/* Calculate the root of a Merkle tree given the leaf node v, and n
+ * complementary nodes, ordered from the closest node (the sibling
+ * leaf node at the bottom of the tree) to most distant (the opposite
+ * half of the tree). orders[i] represents whether each complementarty
+ * node is a left or right child, which is necessary to compute the
+ * proper hash value at each stage. This is the f_bt() algorithm
+ * described in Mohanty et al. */
+
+/* orders: 0 indiciates that the complementary node is LEFT child, 1:
+ * node is RIGHT child */
+hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t n)
+{
+ hash_t parent = node;
+ for(size_t i = 0; i < n; ++i)
+ parent = merkle_parent(comp[i], parent, orders[i]);
+
+ return parent;
+}
+
+/* convert the first 8 bytes (little endian) to a 64-bit int */
+uint64_t hash_to_u64(hash_t h)
+{
+ uint64_t ret = 0;
+ for(int i = 0; i < 8; ++i)
+ ret |= h.hash[i] << (i * 8);
+ return ret;
+}
diff --git a/crypto.h b/crypto.h
index eb5b86c..e120821 100644
--- a/crypto.h
+++ b/crypto.h
@@ -1,5 +1,10 @@
#ifndef CSAA_CRYPTO_H
#define CSAA_CRYPTO_H
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+/* Various useful cryptographic functions; shared between TM and SP. */
/* we use SHA256 for h() */
typedef struct hash_t {
@@ -11,5 +16,20 @@ struct iomt_node {
int idx, next_idx; /* idx cannot be zero */
hash_t val; /* all zero indicates placeholder */
};
+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);
+
+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);
+
+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);
+void dump_hash(hash_t u);
#endif
diff --git a/helper.c b/helper.c
new file mode 100644
index 0000000..1a751e1
--- /dev/null
+++ b/helper.c
@@ -0,0 +1,25 @@
+/* Functions to help with certificate generation (untrusted). */
+
+/* Some of the certificate generation routines require multiple other
+ * certificates to function. This file provides various helper
+ * functions to handle the generation of these needed certificates. */
+
+#include "crypto.h"
+#include "trusted_module.h"
+
+struct tm_cert cert_ru(struct trusted_module *tm,
+ const struct iomt_node *node, hash_t new_val,
+ const hash_t *comp, const int *orders, size_t n,
+ hash_t *hmac_out)
+{
+ struct iomt_node new_node = *node;
+ new_node.val = new_val;
+ hash_t nu_hmac;
+ struct tm_cert nu = tm_cert_node_update(tm,
+ hash_node(node),
+ hash_node(&new_node),
+ comp, orders, n,
+ &nu_hmac);
+
+ return tm_cert_record_update(tm, &nu, nu_hmac, node, new_val, hmac_out);
+}
diff --git a/helper.h b/helper.h
new file mode 100644
index 0000000..1eb0113
--- /dev/null
+++ b/helper.h
@@ -0,0 +1,9 @@
+#include "trusted_module.h"
+#include "crypto.h"
+
+struct tm_cert cert_ru(struct trusted_module *tm,
+ const struct iomt_node *node, hash_t new_val,
+ const hash_t *comp, const int *orders, size_t n,
+ hash_t *hmac_out,
+ int b,
+ struct tm_cert *nonexist, hash_t *hmac_nonexist);
diff --git a/service_provider.c b/service_provider.c
index aaa58a1..4faf43f 100644
--- a/service_provider.c
+++ b/service_provider.c
@@ -2,8 +2,11 @@
* module */
#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
#include "crypto.h"
+#include "helper.h"
#include "service_provider.h"
#include "trusted_module.h"
@@ -53,7 +56,70 @@ struct service_provider *sp_new(const void *key, size_t keylen)
return sp;
}
-void sp_request(struct service_provider *sp, const struct user_request *req, hash_t hmac)
+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)
{
+ /* 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);
+}
+
+void check(int condition);
+void sp_test(void)
+{
+ struct service_provider *sp = sp_new("a", 1);
+ /* 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);
}
diff --git a/service_provider.h b/service_provider.h
index 2013dd1..ec12aaa 100644
--- a/service_provider.h
+++ b/service_provider.h
@@ -44,6 +44,12 @@ struct user_request {
};
struct service_provider *sp_new(const void *key, size_t keylen);
-void sp_request(struct service_provider *sp, const struct user_request *req, hash_t hmac);
+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);
+
+void sp_test(void);
#endif
diff --git a/test.c b/test.c
index 13664c4..17a9013 100644
--- a/test.c
+++ b/test.c
@@ -1,6 +1,8 @@
+#include "service_provider.h"
#include "trusted_module.h"
int main()
{
tm_test();
+ sp_test();
}
diff --git a/trusted_module.c b/trusted_module.c
index 78a010e..bf1bf78 100644
--- a/trusted_module.c
+++ b/trusted_module.c
@@ -34,49 +34,6 @@ struct trusted_module {
unsigned char secret[32];
};
-static hash_t hmac_sha256(const void *data, size_t datalen, const void *key, size_t keylen)
-{
- hash_t h;
- HMAC(EVP_sha256(), key, keylen, data, datalen, h.hash, NULL);
- return h;
-}
-
-static hash_t sha256(const void *data, size_t datalen)
-{
- hash_t h;
- SHA256(data, datalen, h.hash);
- return h;
-}
-
-bool is_zero(hash_t u)
-{
- /* constant-time comparison */
- volatile char c = 0;
- for(int i = 0; i < 32; ++i)
- c |= u.hash[i];
-
- return c == 0;
-}
-
-void dump_hash(hash_t u)
-{
- for(int i = 0; i < 32; ++i)
- printf("%02x", u.hash[i]);
- printf("\n");
-}
-
-bool hash_equals(hash_t a, hash_t b)
-{
- return !memcmp(a.hash, b.hash, 32);
-}
-
-hash_t hash_xor(hash_t a, hash_t b)
-{
- for(int i = 0; i < 32; ++i)
- a.hash[i] ^= b.hash[i];
- return a;
-}
-
struct trusted_module *tm_new(const void *key, size_t keylen)
{
struct trusted_module *tm = calloc(1, sizeof(struct trusted_module));
@@ -94,59 +51,17 @@ struct trusted_module *tm_new(const void *key, size_t keylen)
/* debugging */
memset(tm->secret, 0, sizeof(tm->secret));
- memset(tm->root.hash, 0, sizeof(tm->root.hash));
+ /* initialize with a node of (1, 0, 1) in the tree */
+ struct iomt_node boot;
+ boot.idx = 1;
+ 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;
}
-/* 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 */
-static hash_t merkle_parent(hash_t u, hash_t v, int order)
-{
- if(is_zero(u))
- return v;
- if(is_zero(v))
- return u;
-
- /* append and hash */
- SHA256_CTX ctx;
- hash_t h;
-
- SHA256_Init(&ctx);
-
- if(order != 0)
- SHA256_Update(&ctx, v.hash, 32);
-
- SHA256_Update(&ctx, u.hash, 32);
-
- if(order == 0)
- SHA256_Update(&ctx, v.hash, 32);
-
- SHA256_Final(h.hash, &ctx);
-
- return h;
-}
-
-/* Calculate the root of a Merkle tree given the leaf node v, and n
- * complementary nodes, ordered from the closest node (the sibling
- * leaf node at the bottom of the tree) to most distant (the opposite
- * half of the tree). orders[i] represents whether each complementarty
- * node is a left or right child, which is necessary to compute the
- * proper hash value at each stage. This is the f_bt() algorithm
- * described in Mohanty et al. */
-
-/* orders: 0 indiciates that the complementary node is LEFT child, 1:
- * node is RIGHT child */
-static hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t n)
-{
- hash_t parent = node;
- for(size_t i = 0; i < n; ++i)
- parent = merkle_parent(comp[i], parent, orders[i]);
-
- return parent;
-}
-
static hash_t cert_sign(struct trusted_module *tm, const struct tm_cert *cert)
{
return hmac_sha256(cert, sizeof(*cert), tm->secret, sizeof(tm->secret));
@@ -184,7 +99,7 @@ static void tm_seterror(const char *error)
tm_error = error;
}
-static const char *tm_geterror(void)
+const char *tm_geterror(void)
{
if(tm_error)
return tm_error;
@@ -233,17 +148,6 @@ struct tm_cert tm_cert_combine(struct trusted_module *tm,
}
}
-/* return true iff [b, bprime] encloses a */
-static bool encloses(int b, int bprime, int a)
-{
- return (b < a < bprime) || (bprime <= b && b < a) || (a < bprime && bprime <= b);
-}
-
-static hash_t hash_node(const struct iomt_node *node)
-{
- return sha256(node, sizeof(*node));
-}
-
/* Let ve = h(b, b', wb). */
/* Let ve' = h(b, a, wb). */
/* Let vi' = h(a, b', 0). */
@@ -363,12 +267,21 @@ struct tm_cert tm_cert_record_update(struct trusted_module *tm,
hash_t *hmac_out)
{
if(!nu)
+ {
+ tm_seterror("null certificate");
return cert_null;
+ }
if(nu->type != NU)
+ {
+ tm_seterror("not NU certificate");
return cert_null;
+ }
if(!cert_verify(tm, nu, nu_hmac))
+ {
+ tm_seterror("improper certificate authentication");
return cert_null;
-
+ }
+
hash_t orig_h = hash_node(node);
struct iomt_node new_node = *node;
@@ -377,8 +290,11 @@ struct tm_cert tm_cert_record_update(struct trusted_module *tm,
hash_t new_h = hash_node(&new_node);
if(!hash_equals(nu->nu.orig_node, orig_h) || !hash_equals(nu->nu.new_node, new_h))
+ {
+ tm_seterror("NU hashes do not match node hashes");
return cert_null;
-
+ }
+
struct tm_cert cert;
memset(&cert, 0, sizeof(cert));
@@ -421,7 +337,7 @@ bool tm_set_equiv_root(struct trusted_module *tm,
}
/* user id is 1-indexed */
-static hash_t req_sign(struct trusted_module *tm, const struct user_request *req, int id)
+hash_t req_sign(struct trusted_module *tm, const struct user_request *req, int id)
{
return hmac_sha256(req, sizeof(*req), tm->user_keys[id - 1].key, tm->user_keys[id - 1].len);
}
@@ -435,15 +351,6 @@ static bool req_verify(struct trusted_module *tm, const struct user_request *req
return hash_equals(calculated, hmac);
}
-/* convert the first 8 bytes (little endian) to a 64-bit int */
-static uint64_t hash_to_u64(hash_t h)
-{
- uint64_t ret = 0;
- for(int i = 0; i < 8; ++i)
- ret |= h.hash[i] << (i * 8);
- return ret;
-}
-
/* Generate a signed acknowledgement for successful completion of a
* request. We append a zero byte to the user request and take the
* HMAC. */
@@ -457,7 +364,7 @@ static hash_t req_ack(const struct trusted_module *tm, const struct user_request
HMAC_Update(ctx, (const unsigned char*)req, sizeof(*req));
- char zero = 0;
+ unsigned char zero = 0;
HMAC_Update(ctx, &zero, 1);
hash_t hmac;
@@ -528,8 +435,11 @@ struct tm_cert tm_request(struct trusted_module *tm,
if(!req)
return cert_null;
if(!req_verify(tm, req, req->user_id, req_hmac))
+ {
+ tm_seterror("improper authentication");
return cert_null;
-
+ }
+
/* invalid request type */
if(req->type != ACL_UPDATE && req->type != FILE_UPDATE)
return cert_null;
@@ -550,7 +460,10 @@ struct tm_cert tm_request(struct trusted_module *tm,
/* first check the validity of the certificate */
if(!cert_verify(tm, &req->create.ru_cert, req->create.ru_hmac))
+ {
+ tm_seterror("RU cert invalid");
return cert_null;
+ }
/* verify that:
- the certificate has the same file index as the request
@@ -562,8 +475,17 @@ struct tm_cert tm_request(struct trusted_module *tm,
!is_zero(req->create.ru_cert.ru.orig_val) ||
!hash_equals(req->create.ru_cert.ru.orig_root, tm->root) ||
!hash_equals(req->create.ru_cert.ru.new_val, one))
+ {
+ tm_seterror("RU cert does not show needed information");
+ printf("%d %d %d %d\n", req->create.ru_cert.ru.idx != req->idx,
+ !is_zero(req->create.ru_cert.ru.orig_val),
+ !hash_equals(req->create.ru_cert.ru.orig_root, tm->root),
+ !hash_equals(req->create.ru_cert.ru.new_val, one));
+ dump_hash(req->create.ru_cert.ru.orig_root);
+ dump_hash(tm->root);
return cert_null;
-
+ }
+
/* update the IOMT root */
tm->root = req->create.ru_cert.ru.new_root;
@@ -712,9 +634,12 @@ hash_t tm_verify_and_encrypt_secret(struct trusted_module *tm,
}
/* self-test */
+const char *tm_geterror(void);
void check(int condition)
{
printf(condition ? "PASS\n" : "FAIL\n");
+ if(!condition)
+ printf("%s\n", tm_geterror());
}
void tm_test(void)