add some certificate generation routines (WIP)

5 files changed, 214 insertions, 12 deletions

diff --git a/crypto.h b/crypto.h
index f73fc1d..5c19b8e 100644
--- a/crypto.h
+++ b/crypto.h
@@ -1,5 +1,10 @@
+#ifndef CSAA_CRYPTO_H
+#define CSAA_CRYPTO_H
+
 /* we use SHA256 for h() */
 typedef struct hash_t {
     /* a hash of all zeros is given a special meaning */
     unsigned char hash[32];
 } hash_t;
+
+#endif
diff --git a/service_provider.c b/service_provider.c
index 420d526..5b9c00f 100644
--- a/service_provider.c
+++ b/service_provider.c
@@ -5,13 +5,6 @@
 #include "trusted_module.h"
 #include "crypto.h"
 
-struct iomt_node {
-    int idx, next_idx; /* idx cannot be zero */
-    hash_t value; /* all zero indicates placeholder */
-};
-
 struct service_provider {
     struct trusted_module *tm;
-
-
 };
diff --git a/service_provider.h b/service_provider.h
index 5d722cb..a0b9bd9 100644
--- a/service_provider.h
+++ b/service_provider.h
@@ -1,5 +1,16 @@
 /* implementation of a basic service provider for use with the trusted
  * module */
 
-struct iomt_node;
+#ifndef CSAA_SERVICE_PROVIDER_H
+#define CSAA_SERVICE_PROVIDER_H
+
+#include "crypto.h"
+
+struct iomt_node {
+    int idx, next_idx; /* idx cannot be zero */
+    hash_t value; /* all zero indicates placeholder */
+};
+
 struct service_provider;
+
+#endif
diff --git a/trusted_module.c b/trusted_module.c
index ca6bd79..7a79a8f 100644
--- a/trusted_module.c
+++ b/trusted_module.c
@@ -14,6 +14,7 @@
 #include <openssl/sha.h>
 
 #include "crypto.h"
+#include "service_provider.h"
 #include "trusted_module.h"
 
 struct trusted_module {
@@ -24,17 +25,17 @@ struct trusted_module {
     size_t keylen;
 
     /* secret for signing self-certificates */
-    char secret[32];
+    unsigned char secret[32];
 };
 
-static hash_t hmac_sha256(const char *data, size_t datalen, const char *key, size_t keylen)
+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 char *data, size_t datalen)
+static hash_t sha256(const void *data, size_t datalen)
 {
     hash_t h;
     SHA256(data, datalen, h.hash);
@@ -121,7 +122,7 @@ static hash_t merkle_parent(hash_t u, hash_t v, int order)
 
 /* orders: 0 indiciates that the complementary node is LEFT child, 1:
  * node is RIGHT child */
-static hash_t merkle_compute(hash_t node, hash_t *comp, int *orders, size_t n)
+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)
@@ -130,6 +131,152 @@ static hash_t merkle_compute(hash_t node, hash_t *comp, int *orders, size_t n)
     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));
+}
+
+static bool cert_verify(struct trusted_module *tm, const struct tm_cert *cert, hash_t hmac)
+{
+    hash_t calculated = cert_sign(tm, cert);
+    return hash_equals(calculated, 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)
+{
+    struct tm_cert cert;
+    cert.type = NU;
+    cert.nu.orig_node = orig;
+    cert.nu.new_node = new;
+
+    cert.nu.orig_root = cert.nu.new_root = merkle_compute(orig, comp, orders, n);
+
+    if(!hash_equals(orig, new))
+        cert.nu.new_root = merkle_compute(new, comp, orders, n);
+
+    *hmac = cert_sign(tm, &cert);
+
+    return cert;
+}
+
+static struct tm_cert cert_null = { NONE };
+
+/* combine two NU certificates */
+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)
+{
+    if(!nu1 || !nu2)
+        return cert_null;
+    if(nu1->type != NU || nu2->type != NU)
+        return cert_null;
+    if(!cert_verify(tm, nu1, hmac1) || !cert_verify(tm, nu2, hmac2))
+        return cert_null;
+
+    if(hash_equals(nu1->nu.new_node, nu2->nu.orig_node) &&
+       hash_equals(nu2->nu.new_root, nu2->nu.orig_root))
+    {
+        struct tm_cert cert;
+        cert.type = NU;
+        cert.nu.orig_node = nu1->nu.orig_node;
+        cert.nu.orig_root = nu1->nu.orig_root;
+        cert.nu.new_node = nu2->nu.new_node;
+        cert.nu.new_root = nu2->nu.new_root;
+
+        *hmac_out = cert_sign(tm, &cert);
+        return cert;
+    }
+    else
+        return cert_null;
+}
+
+/* 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). */
+/* 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,
+                             const struct iomt_node *encloser,
+                             int a, hash_t *hmac_out)
+{
+    if(!nu_encl || !nu_ins)
+        return cert_null;
+    if(nu_encl->type != NU || nu_ins->type != NU)
+        return cert_null;
+    if(!cert_verify(tm, nu_encl, hmac_encl) || !cert_verify(tm, nu_ins, hmac_ins))
+        return cert_null;
+    if(!encloses(encloser->idx, encloser->next_idx, a))
+        return cert_null;
+    if(!hash_equals(nu_encl->nu.new_root, nu_ins->nu.orig_root))
+        return cert_null;
+
+    hash_t ve = hash_node(encloser);
+    struct iomt_node encloser_mod = *encloser;
+    encloser_mod.next_idx = a;
+    hash_t veprime = hash_node(&encloser_mod);
+
+    struct iomt_node ins;
+    ins.idx = a;
+    ins.next_idx = encloser->next_idx;
+    memset(ins.value.hash, 0, sizeof(ins.value.hash));
+
+    hash_t viprime = hash_node(&ins);
+
+    if(!hash_equals(nu_encl->nu.orig_node, ve))
+        return cert_null;
+    if(!hash_equals(nu_encl->nu.new_node, veprime))
+        return cert_null;
+    if(!is_zero(nu_ins->nu.orig_node))
+        return cert_null;
+    if(!hash_equals(nu_ins->nu.new_node, viprime))
+        return cert_null;
+
+    /* we can now certify that y and y'' are equivalent roots */
+    struct tm_cert cert;
+    memset(&cert, 0, sizeof(cert));
+    cert.type = EQ;
+    cert.eq.orig_root = nu_encl->nu.orig_root;
+    cert.eq.new_root = nu_ins->nu.new_root;
+
+    *hmac_out = cert_sign(tm, &cert);
+    return cert;
+}
+
+/* nu must be of the form [x,y,x,y] to indicate that x is a child of y */
+struct tm_cert tm_cert_record_verify(struct trusted_module *tm,
+                                     const struct tm_cert *nu, hash_t hmac,
+                                     const struct iomt_node *node,
+                                     hash_t *hmac_out)
+{
+    if(!nu)
+        return cert_null;
+    if(!hash_equals(nu->nu.orig_node, nu->nu.new_node) || !hash_equals(nu->nu.orig_root, nu->nu.new_root))
+        return cert_null;
+
+    hash_t node_h = hash_node(node);
+    if(!hash_equals(nu->nu.orig_node, node_h))
+        return cert_null;
+
+
+}
+
 void check(int condition)
 {
     printf(condition ? "PASS\n" : "FAIL\n");
diff --git a/trusted_module.h b/trusted_module.h
index b99246a..0799132 100644
--- a/trusted_module.h
+++ b/trusted_module.h
@@ -1,10 +1,56 @@
 /* interface to the trusted module */
 
 #include <stddef.h>
+#include "crypto.h"
+#include "service_provider.h"
 
 struct trusted_module;
 
+struct tm_cert {
+    enum { NONE = 0, NU, EQ, RV, RU } type;
+    union {
+        struct {
+            hash_t orig_node, new_node;
+            hash_t orig_root, new_root;
+        } nu; /* node update */
+        struct {
+            /* new_root has an additional placeholder */
+            hash_t orig_root, new_root;
+            char zero[2 * 32];
+        } eq; /* equivalence */
+        struct {
+            /* proof that there is a node with given idx,val that is a
+             * child of root; if val=0, proof that there is no such
+             * node */
+            int idx;
+            hash_t val;
+            hash_t root;
+            } rv; /* record verify */
+    };
+};
+
 /* dynamically allocated */
 struct trusted_module *tm_new(const char *key, size_t keylen);
 void tm_free(struct trusted_module *tm);
 void tm_test(void);
+
+/* certificate generation routines */
+/* generate a symmetric certificate indicating that the module has
+ * verified that updating the node `orig' to `new' changes the root
+ * from `orig_root' to `new_root' (neither of these can be
+ * 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);
+
+/* 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_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,
+                             const struct iomt_node *encloser,
+                             int a, hash_t *hmac_out);