aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranklin Wei <me@fwei.tk>2018-06-14 12:42:45 -0400
committerFranklin Wei <me@fwei.tk>2018-06-14 12:42:45 -0400
commit0b31788f9ef9bb760b56a4fd72bd618a276f0a70 (patch)
tree8028a24f7776ead870362ec312f811653c90f7e2
parent6ee13d7f3e0530f56215b134679aeb27a676543c (diff)
downloadcsaa-0b31788f9ef9bb760b56a4fd72bd618a276f0a70.zip
csaa-0b31788f9ef9bb760b56a4fd72bd618a276f0a70.tar.gz
csaa-0b31788f9ef9bb760b56a4fd72bd618a276f0a70.tar.bz2
csaa-0b31788f9ef9bb760b56a4fd72bd618a276f0a70.tar.xz
Working on EQ generation
-rw-r--r--crypto.c33
-rw-r--r--crypto.h7
-rw-r--r--helper.c40
-rw-r--r--helper.h7
-rw-r--r--service_provider.c90
5 files changed, 127 insertions, 50 deletions
diff --git a/crypto.c b/crypto.c
index e8759d5..ce88d0f 100644
--- a/crypto.c
+++ b/crypto.c
@@ -113,6 +113,18 @@ hash_t merkle_compute(hash_t node, const hash_t *comp, const int *orders, size_t
return parent;
}
+/* Given a node's index, return the index of the parent in an array
+ * representation of a binary tree. */
+int bintree_parent(int idx)
+{
+ return (idx - ((idx & 1) ? 1 : 2)) / 2;
+}
+
+int bintree_sibling(int idx)
+{
+ return idx + ((idx & 1) ? 1 : -1);
+}
+
/* 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
@@ -137,18 +149,33 @@ int *merkle_complement(int leafidx, int logleaves, int **orders)
for(int i = 0; i < logleaves; ++i)
{
/* output index of sibling node */
- comp[i] = idx + ((idx & 1) ? 1 : -1);
+ comp[i] = bintree_sibling(idx);
+ /* we really don't need the orders array */
if(orders)
- (*orders)[i] = ((idx&1) ? 1 : 0);
+ (*orders)[i] = idx & 1;
/* find parent index and loop */
- idx = (idx - ((idx & 1) ? 1 : 2)) / 2;
+ idx = bintree_parent(idx);
}
return comp;
}
+int *merkle_dependents(int leafidx, int logleaves)
+{
+ int *dep = calloc(logleaves, sizeof(int));
+
+ int idx = (1 << logleaves) - 1 + leafidx;
+ for(int i = 0; i < logleaves; ++i)
+ {
+ idx = bintree_parent(idx);
+ dep[i] = idx;
+ }
+
+ return dep;
+}
+
/* Shim to get only the orders */
int *merkle_complement_orders(int leafidx, int logleaves)
{
diff --git a/crypto.h b/crypto.h
index 03a90cd..3112571 100644
--- a/crypto.h
+++ b/crypto.h
@@ -48,6 +48,13 @@ hash_t merkle_parent(hash_t u, hash_t v, int order);
int *merkle_complement(int leafidx, int logleaves, int **orders);
int *merkle_complement_orders(int leafidx, int logleaves);
+/* Return an array of indices of tree nodes that are dependent on a
+ * given leaf node. Will be ordered from nearest relative to root. */
+int *merkle_dependents(int leafidx, int logleaves);
+
+int bintree_parent(int idx);
+int bintree_sibling(int idx);
+
uint64_t hash_to_u64(hash_t h);
void dump_hash(hash_t u);
diff --git a/helper.c b/helper.c
index 9b82e52..0e572db 100644
--- a/helper.c
+++ b/helper.c
@@ -44,43 +44,3 @@ struct tm_cert cert_rv(struct trusted_module *tm,
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);
- /* FIXME: the complement will change upon changing this node, so
- * cert_equiv() will fail. */
- 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 6abda23..73bd055 100644
--- a/helper.h
+++ b/helper.h
@@ -12,10 +12,3 @@ 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);
-
-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 f82681d..322f9a8 100644
--- a/service_provider.c
+++ b/service_provider.c
@@ -83,6 +83,88 @@ static hash_t *lookup_nodes(const hash_t *nodes, const int *indices, int n)
return ret;
}
+static void restore_nodes(hash_t *nodes, const int *indices, const hash_t *values, int n)
+{
+ for(int i = 0; i < n; ++i)
+ nodes[indices[i]] = values[i];
+}
+
+/* Update mt_nodes to reflect a change to a leaf node's
+ * value. Optionally, if old_dep is not NULL, *old_dep will be made to
+ * point to an array of length mt_logleaves that contains the old node
+ * values (whose indices are returned by merkle_dependents()). Untested. */
+static void update_tree(struct service_provider *sp, int leafidx, hash_t newval,
+ hash_t **old_dep)
+{
+ if(old_dep)
+ *old_dep = calloc(sp->mt_logleaves, sizeof(hash_t));
+
+ int idx = (1 << sp->mt_logleaves) - 1 + leafidx;
+
+ sp->mt_nodes[idx] = newval;
+ for(int i = 0; i < sp->mt_logleaves; ++i)
+ {
+ /* find the merkle parent of the two children first */
+ hash_t parent = merkle_parent(sp->mt_nodes[idx],
+ sp->mt_nodes[bintree_sibling(idx)],
+ (idx + 1) & 1);
+
+ idx = bintree_parent(idx);
+
+ /* save old value */
+ if(old_dep)
+ (*old_dep)[i] = sp->mt_nodes[idx];
+
+ sp->mt_nodes[idx] = parent;
+ }
+}
+
+/* Generate an EQ certificate for inserting a placeholder with index
+ * placeholder_idx, given an encloser (which must actually enclose
+ * a). Note: this function will modify the *mt_nodes array to reflect
+ * the modification of the encloser node. However, it will restore the
+ * original values before returning. This function belongs in here
+ * service_provider.c and not helper.c since it directly accesses
+ * service-provider specific functionality. */
+struct tm_cert cert_eq(struct trusted_module *tm,
+ const struct iomt_node *encloser,
+ int placeholder_idx,
+ hash_t *mt_nodes,
+ const int *enc_comp, const int *enc_orders, size_t enc_n,
+ const int *ins_comp, const int *ins_orders, size_t ins_n,
+ hash_t *hmac_out)
+{
+ assert(encloses(encloser->idx, encloser->next_idx, placeholder_idx));
+
+ struct iomt_node encloser_mod = *encloser;
+ encloser_mod.next_idx = placeholder_idx;
+
+ struct iomt_node insert;
+ insert.idx = placeholder_idx;
+ 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);
+ /* FIXME: the complement will change upon changing this node, so
+ * cert_equiv() will fail. */
+ 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, placeholder_idx, hmac_out);
+}
+
/* Calculate the value of all the nodes of the tree, given the IOMT
* leaves in mt_leaves. Leaf count *must* be an integer power of two,
* otherwise bad things will happen. This function should only need to
@@ -310,6 +392,14 @@ void sp_test(void)
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);
/* broken */
#if 0