Popa & Wagner Spring 2016
1 Sample Design
CS 161 Computer Security
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
all of their children) will not be able to access the file because they will not learn the new encryption key.
2 Test Case Explanations
Our autograder included numerous security tests. Here is an explanation of what each one is testing and some sample design flaws that might be responsible for failing that test case.
2.1 Part 1 test cases
CheckEncryptionMACDifferentKey. MAC keys and encryption keys should be differ- ent, and this test case checks just that.
CheckKeyNotStoredPlaintext. The point of creating an encryption key is to hide the content of a message. This test verifies that the encryption keys are never stored, in plaintext, on the server.
CheckPlainttextMAC. MACs provide integrity, but they don’t promise to provide con- fidentiality for their input. Therefore, you should generally avoid including plaintext data directly as part of the input to the MAC, if the MAC is not encrypted, as this might leak plaintext bits. Also, computing a MAC solely on the file contents loses IND-CPA security: the same file contents will always yield the same MAC.
CreateFakeKey. It is important to bind the name of a file to its contents. Otherwise, if a user creates files A and B, a malicious server could swap the names and have downloads for A return the content of B and vice versa.
EncryptionHasNoncesBlackBox. Verifies that encrypted messages are correctly ran- domized, using IVs or nonces.
CBCIVsNotReused. Verifies that you don’t reuse the same IV more than once for CBC mode encryption. Such reuse is insecure and can leak partial information about the plain- texts: the same contents will encrypt to the same ciphertext, which violates IND-CPA security, and if two plaintexts start with the same 16 bytes, then an adversary can detect this (by noticing that the ciphertexts start with the same 16 bytes). Use a fresh, random IV for each CBC encryption you do. Generate the IV using get random bytes().
Project 2 Page 3 of 7 CS 161 – Sp 16
KeysAreChosenFresh. Keys should be chosen randomly using get random bytes() and should not be generated via any other means. In particular, hashing the private key is poor practice and makes rotating keys difficult if the private key were ever to be compromised.
NameIsNotFromECB. Ids should not be generated by encrypting the filename with ECB mode or CBC/CTR mode with constant IV, as this leaks partial information. In particular, if two filenames start with the same 16 bytes, then the adversary can detect this (by noticing that the ciphertexts start with the same 16 bytes). Also, these modes allow dictionary attacks: an adversary who can convince you to upload files under a name of the attacker’s choice will be able to exploit the properties of ECB/CBC/CTR to figure out the filename of your secret file, if the attacker can identify a list of candidate names for the secret file. Finally, CTR mode with a constant IV is especially bad: it is vulnerable to the attacks on pad reuse with the one-time pad.
NameIsNotFromHash. Verifies that ids are not generated by hashing the filename. That has the same problems outlined above.
SmallCTRUsed. When using CTR mode, the counter should be at least 64 bits, to prevent repetition of the counter value.
CTRUsesUniqueValues. When using CTR mode, the counter values used should be unique. Give either a unique prefix, suffix, or initial value.
StringNotPlaintext. The filename should not directly appear in plaintext on the server. Similarly, the contents of the file should not appear in plaintext on the server.
StringNotPlaintextBoth. You fail this test if both the name and the contents of the file appear in plaintext on the server.
TestBadCrypto. You fail this test if you use insecure cryptographic algorithms. DES and RC4 are broken; you should not use those algorithms. Encrypted messages stored with these algorithms can be decrypted without the key. MD2, MD5, and SHA are cryptographically weak hash functions and should not be used. They shouldn’t be used for HMAC-based schemes, either: though no attack is known that can forge MAC tags for these schemes, their use to build a MAC is discouraged. Instead, use strong algorithms like AES, SHA256, and SHA256-HMAC.
Project 2 Page 4 of 7 CS 161 – Sp 16
2.2 Part 2 test cases
Tests were weighted by importance. For tests which are duplicates of each other, you lose points if you fail any of the tests and do not lose extra points for failing multiple versions of the same test.
ApplyEditsToNewFile If your Q3 solution involves a log to make updates efficient, this test case checks if it is possible to add fake entries to the log and result in invalid files uploaded. That is, we upload on the server (F, V ) and (G, W ), then we update F to V ′ with an update of D, this test checks if it is possible to apply D to G to obtain some W′.
CorrelateUpdateSize This was the second most difficult test case to pass (with over half of the class not passing it). It checks if your efficient upload scheme allows for an attacker to cause your client to upload the same file over and over and monitor the size of the uploads in order to completely decrypt the contents of the message. This test was not worth any points, unless you otherwise would get 100 on this project and then you only got 99.
EfficientPutHasHashes This test tries to make sure that it is not possible to remove selective edits from occurring during efficient updates. That is, we first upload (F, V ) and then (F, V ′) and finally (F, V ′′). We then randomly modify the state to see if it is possible that downloading F will result in a file that is not one of V, V′, or V′′.
KeysAreNotReused This test ensures that when a different files are shared with different people, they do not see the same keys. That is, Alice uploads files F and G and shares F with Bob and G with Carol. If Bob and Carol share any keys then you fail this test case.
LieAboutTreeStructure By far the most complicated test case, this verifies that there is no way for a user to make it so that he can never be revoked. Alice creates a file F and shares it with Bob who shares it with Carol. Specifically, we test that it is not possible for Carol to make it so that when Alice tries to revoke Bob, she is not revoked.
NoReadAfterRevoke This test verifies that it is not possible for a client to remember encryption keys so that after they are revoked, they can still read the modified file on the server by re-using the old keys they remembered.
NoRollbackPartialPuts This test makes sure that updates are always consistent even if an adversary tries to block some writes from occurring. That is, if Alice uploads (F, V ) and then (F, V ′) where V ′ modifies many portions of F , this test checks if it is possible to stop some writes so that the result of downloading F returns some contents intermediate between V andV′.
Project 2 Page 5 of 7 CS 161 – Sp 16
NoRollbackPartialPuts2 Simply another way of testing NoRollbackPartialPuts.
NoSharedKeysAfterRevoke After a user’s access to a file has been revoked, this user should no longer share any keys in use with the parent. That is, if Alice shares a file with Bob, then after Alice revokes Bob’s access, Alice should never try to use a key that Bob knows, and Bob should never try to use a key that Alice knows.
ReplayAlreadyReceivedMessage This is the most difficult test case to pass, with only 15% of submissions passing. Alice creates files F and G. Alice shares F with Bob, who accepts it. Alice then shares G with Bob, but a man in the middle swaps out the share message with the first share message to share F. If Bob does not detect this, he will be in an invalid state. This test was not worth any points, unless you otherwise would get 100 on this project and then you only got 99.
RevokedDataIsReEncrypted Once a user’s access to a file has been revoked, the original file must be re-encrypted under a new key. This test verifies that this occurrs and all modifications to the file are done under the new encryption key.
RevokedDataIsReEncrypted2 A different way of testing RevokedDataIsReEncrypted. ShareMessageDoesntLeakKeys Share messages should be encrypted and keys should
not be sent plaintext in these share messages.
ShareMessagesAreSigned When Alice shares a file with Bob, it should not be possible for Mallory to switch out the message with one of her own so that Bob instead receives a file owned by Malory instead of Alice.
ShareWithSameName If Alice shares a file she calls F with Carol (who calls it F1), and then Bob shares a file he calls F with Carol (who calls it F2), then it should still be possible for Alice and Bob to revoke Carol’s access of their own files without breaking Carol’s client.
SharingMessageCantBeReplayed This test verifies that a user can’t replay a share message to herself after having been revoked in order to re-grant herself access. That is, if Alice shares a file with Bob with share message S, and then later revokes Bob’s access, it should not be possible for Bob to call receive share on himself with S again and re-grant himself access.
SharingMessageCantBeReplayed2 Another way of testing SharingMessageCantBeRe- played.
Project 2 Page 6 of 7 CS 161 – Sp 16
SharingMessageIsEncrypted This test verifies that sharing a file from Alice to Bob does not allow a man in the middle to learn the name of the file being shared.
SilentDropPuts Another way of testing NoRollbackPartialPuts.
Project 2 Page 7 of 7 CS 161 – Sp 16