Popa & Wagner CS 161
Computer Security Project 2
Spring 2016
1 Sample Design
Our design mimics the sample insecure client provided in the student framework. Our
efficient update scheme is inspired by Merkle trees. As in the solutions to Part 1, when
we encrypt something we always do an “authenticated encryption” by encrypting and then
MACing the ciphertext.
To initialize a client, we create a client encryption key and MACing key, and store them
on the server encrypted under our public key.
To create afile initially, a client creates two new keys (ke , ka ) and two files on the storage
server at random IDs.
• The data node contains a pointer to the tree file data-structure (described later) which
will be encrypted and MACd under ke and ka .
• The key node contains the two keys encrypted and MACd under the user’s symmetric
keys, a pointer to the data node, and the name of the file.
To share a file with another user, we create a new share node containing the ID of
the data node, and the encryption and MAC keys which are used at the data node. We
encrypt the share node with two fresh new keys. We then send the other user the following
information, encrypted with their public key:
1. A unique nonce.
2. The ID of the share node
3. The two new keys we have generated
We also send a signature over the ciphertext using our private key.
To receive a share message, the receiving user first verifies the signature and then
decrypts the ciphertext. The receiving user ensures this message has not been seen before
by storing all nonces used previously and ensuring this nonce is fresh. Then, they create
a new key node with the two encryption keys that they have received, and makes this key
node point to the share node. That is, the share node acts as if it were a data node, but
instead of actually containing data it contains yet another pointer to another node (which
is either another share node, or actually a data node).
Page 1 of 7
, To access a file a user has received access to, the user proceeds as usual and decrypts
the key node for the file. This will contain symmetric keys and a pointer to a new file. The
user then decrypts this file. If it is a data node we stop and read the contents; if another
share node, we recurse.
To perform efficient updates, we use a tree-based approach. When a file is initially
uploaded, we create a binary tree. Internal nodes of the tree contain several pieces of
information (all stored with authenticated encryption):
1. A pointer to the left and right sub-trees, or None to indicate a leaf.
2. A cryptographic MAC of all the data at this node and below.
3. A cryptographic hash of all the data at this node and below.
4. The length of the data stored at this node and below.
We describe our update procedure recursively. To update a file we compare the hash of the
new file against the hash stored at the root node on the server. If the hashes are equal, then
we have no more work to do. If they differ, then we split our file into two pieces according
to the lengths of the sub-trees stored on the server. We then recursively call update on the
left and right child. When we reach a leaf node, if the hash does not match, we replace the
leaf with the new data. Our leaf nodes are 128 bytes. Then, we recompute the hash for each
node as the hash of the concatenation of the hash of the left child and the right child. If
the upload would result in a larger file than simply re-uploading the entire file, we do that
instead.
Our scheme is efficient even in the case that Alice uploads a file F, shares it with Bob, and
Bob makes a small update, even if Bob has not downloaded the file ahead of time.
To download a file, we walk the tree post-order. At each leaf we simply return the data
stored there if the MAC is valid. At each internal node we return the left and right sub-trees
concatenated if the MAC of the internal node is valid, and if the MAC of all the data is
correct.
To revoke a user’s access, we re-encrypt the file with new symmetric keys, and distribute
these new keys to all of our children except the revoked user.
Specifically, we start out by re-generating two new encryption keys and store them in the
key node. We then download the entire file, and re-upload it using these new encryption and
MACing keys. We place these keys in the key node so we will have access to it in the future.
Then, we iterate over all of our children for this file. For each child, using the shared
symmetric key we share with them, we place the new keys in the share node.
This results in the functionality and security properties being satisfied. All of our children
(and their children) will still be able to access the new file. However, the revoked user (and
Project 2 Page 2 of 7 CS 161 – Sp 16
Computer Security Project 2
Spring 2016
1 Sample Design
Our design mimics the sample insecure client provided in the student framework. Our
efficient update scheme is inspired by Merkle trees. As in the solutions to Part 1, when
we encrypt something we always do an “authenticated encryption” by encrypting and then
MACing the ciphertext.
To initialize a client, we create a client encryption key and MACing key, and store them
on the server encrypted under our public key.
To create afile initially, a client creates two new keys (ke , ka ) and two files on the storage
server at random IDs.
• The data node contains a pointer to the tree file data-structure (described later) which
will be encrypted and MACd under ke and ka .
• The key node contains the two keys encrypted and MACd under the user’s symmetric
keys, a pointer to the data node, and the name of the file.
To share a file with another user, we create a new share node containing the ID of
the data node, and the encryption and MAC keys which are used at the data node. We
encrypt the share node with two fresh new keys. We then send the other user the following
information, encrypted with their public key:
1. A unique nonce.
2. The ID of the share node
3. The two new keys we have generated
We also send a signature over the ciphertext using our private key.
To receive a share message, the receiving user first verifies the signature and then
decrypts the ciphertext. The receiving user ensures this message has not been seen before
by storing all nonces used previously and ensuring this nonce is fresh. Then, they create
a new key node with the two encryption keys that they have received, and makes this key
node point to the share node. That is, the share node acts as if it were a data node, but
instead of actually containing data it contains yet another pointer to another node (which
is either another share node, or actually a data node).
Page 1 of 7
, To access a file a user has received access to, the user proceeds as usual and decrypts
the key node for the file. This will contain symmetric keys and a pointer to a new file. The
user then decrypts this file. If it is a data node we stop and read the contents; if another
share node, we recurse.
To perform efficient updates, we use a tree-based approach. When a file is initially
uploaded, we create a binary tree. Internal nodes of the tree contain several pieces of
information (all stored with authenticated encryption):
1. A pointer to the left and right sub-trees, or None to indicate a leaf.
2. A cryptographic MAC of all the data at this node and below.
3. A cryptographic hash of all the data at this node and below.
4. The length of the data stored at this node and below.
We describe our update procedure recursively. To update a file we compare the hash of the
new file against the hash stored at the root node on the server. If the hashes are equal, then
we have no more work to do. If they differ, then we split our file into two pieces according
to the lengths of the sub-trees stored on the server. We then recursively call update on the
left and right child. When we reach a leaf node, if the hash does not match, we replace the
leaf with the new data. Our leaf nodes are 128 bytes. Then, we recompute the hash for each
node as the hash of the concatenation of the hash of the left child and the right child. If
the upload would result in a larger file than simply re-uploading the entire file, we do that
instead.
Our scheme is efficient even in the case that Alice uploads a file F, shares it with Bob, and
Bob makes a small update, even if Bob has not downloaded the file ahead of time.
To download a file, we walk the tree post-order. At each leaf we simply return the data
stored there if the MAC is valid. At each internal node we return the left and right sub-trees
concatenated if the MAC of the internal node is valid, and if the MAC of all the data is
correct.
To revoke a user’s access, we re-encrypt the file with new symmetric keys, and distribute
these new keys to all of our children except the revoked user.
Specifically, we start out by re-generating two new encryption keys and store them in the
key node. We then download the entire file, and re-upload it using these new encryption and
MACing keys. We place these keys in the key node so we will have access to it in the future.
Then, we iterate over all of our children for this file. For each child, using the shared
symmetric key we share with them, we place the new keys in the share node.
This results in the functionality and security properties being satisfied. All of our children
(and their children) will still be able to access the new file. However, the revoked user (and
Project 2 Page 2 of 7 CS 161 – Sp 16
