Insights from Paper - Secure Untrusted Data Repository (SUNDR)
1. Abstract
What is SUNDR?
It is a network file system. It is designed to store data securely on untrusted servers.
The clients can detect if a server or user attempts to modify a file unauthorizedly.
It provides a guarantee called fork consistency. It states that clients can detect integrity or consistency failures if they see each other’s file modifications.
2. Introduction
File system data can be protected by providing better fencing around storage servers. These fencing measures include limiting users' access to the server, disabling software on the server, and updating security patches quickly.
This approach has two challenges. First, most fences are not high enough, and second, they are inconvenient.
Let’s take an example of open-source code repositories. Developers across the world commit change to it. It is impractical to fend off it using firewalls. These repositories require different tools which may have remotely exploitable bugs.
Many of these repositories rely on third-party hosting services. If an attacker can compromise such a service (like sourceforge), he can introduce subtle vulnerabilities in the software hosted.
The paper gives an example of the Debian GNU/Linux development cluster compromised in 2003.
SUNDR reduces the need to trust storage servers in the first place. It uses cryptography to protect all file system contents so that clients can detect any unauthorized attempts to change files.
SUNDR vests the authority to write files entirely in users’ public keys. A user who gains complete administrative control of a SUNDR server cannot convince clients to accept altered contents of files he lacks permission to write.
Because of the above security, a SUNDR server can recover file system data from untrusted clients’ file caches. The paper describes two things: the SUNDR protocol and prototype implementation, which is comparable to NFS.
3. Setting
SUNDR provides a file system interface for remote storage.
The diagram above shows SUNDR’s basic architecture.
When an application accesses the file system, the client software internally translates its system calls into fetch and modify operations.
Here, fetch means retrieving a file’s contents or validating a cached local copy, and modify means making a new file system state visible to other users.
The fetch and modify are implemented regarding SUNDR protocol RPCs to the server.
Server Set up
To set up a SUNDR server, the server software runs on a networked machine with dedicated SUNDR disks or partitions. The server can host one or more filesystems.
To create a file system, a public/private superuser signature key pair is generated and the public key is given to the server.
The private key provides exclusive write access to the file system's root directory. It also directly or indirectly allows access to any file below the root.
These privileges are confined to one file system.
Client Set up
Each user of a SUNDR file system has a signature key. The user can either own the private key of the signature or be a client using the key to act on behalf of the user.
To create an account, users exchange public keys with the superuser.
The superuser manages accounts using two superuser-owned files in the file system's root directory.
.sundr.users - It lists users’ public keys and numeric IDs
.sundr.group - It designates groups and their membership.
Now, let’s take an example to see these setups.
Assume we have many users who want to use a source code repository. They can mount a remote SUNDR file system on directory /sundr and use /sundr/cvsroot as a CVS repository.
A user mounts a file system by specifying the superuser’s public key as a command-line argument to the client. The user also needs to give the client access to their private key.
SUNDR assumes a user is aware of the last operation he or she has performed.
Typically, the client remembers the last operation performed on each user's behalf. A user needs this ( and, of course, the private key) to move between clients.
There is a clear distinction between the administration of servers and the administration of file systems. The server administrator does not need any private superuser keys.
4. The SUNDR protocol
Let’s discuss the protocol.
If the server behaves correctly, a client’s fetch reflects exactly the authorized modifications that happened before it. It is called the fetch-modify consistency property.
Clients enforce a slightly weaker property called fork consistency if the server is dishonest. A dishonest server could cause a user's fetch to miss a modification by B, but the user will detect the attack upon seeing a subsequent operation by the other.
The SUNDR team has formally specified fork consistency and proved that SUNDR’s protocol achieves this.
We will discuss three steps to understand the implications of fork consistency.
Start with a simple straw-man file system that achieves fork consistency at the cost of significant inefficiency.
Work with an improved system with more reasonable bandwidth requirements
called “Serialized SUNDR.”
Finally, work with relaxed serialization requirements to arrive at “concurrent
SUNDR.”
4.1 A straw-man file system
Let’s assume an environment where concurrent operations are now allowed.
The server maintains a single, untrusted global lock on the file system. To fetch or modify a file, a user first acquires the lock, performs the desired operation, and then releases it.
So long as the server is honest, the operations are ordered, and each operation is completed before the next begins.
The straw-man file server stores a complete, ordered list of every fetch or modify operation. Each operation also contains a digital signature from the user who performed it, which has the complete history of all operations that preceded it.
An example is shown below after five operations. The history will be below:
To fetch or modify a file, a client acquires the global lock, downloads the entire history of the file system, and validates each user’s most recent signature and its operations.
The client then traverses the operation history to construct a local copy of the file system. The client checks that the modification operation was permitted, using the user and group file to validate the signing user against the file’s owner or group.
If all checks succeed, the client appends a new operation to the list, signs the latest history, sends it to the server, and releases the lock.
Now, let’s see a server’s malicious attack. If the server failed to show user B the most recent modification to file f2 in the previous diagram, Users A and B would sign the following histories:
Neither history is a prefix of the other. A will sign only extensions of the first history, and B will sign only extensions of the second from the diagram. Users could see fetch-modify consistency before the attack, but the users are forked after the server’s malicious work (attack).
4.2 Implications of fork consistency
Fork consistency is the most robust notion of integrity without online trusted parties.
Given fork consistency, one can leverage any trusted online parties to gain stronger consistency, even fetch-modify consistency.
The paper discusses one example solution using a “time stamp box,” which has the permission to write to a single file.
The box can update that file through SUNDR every 5 seconds. All users who see the box’s updates know they could only have been partitioned from each other in the past 5 seconds.
4.3 Serialized SUNDR
The straw-man file system is impractical. It has two problems:
It must record and ship around complete file system operation histories.
The serialization of operations through a global lock is impractical for multi-users.
In the Serialized SUNDR approach, we have overcome the first issue. This is done by effectively signing file system snapshots instead of all operations.
All files writable by a particular user or group are efficiently aggregated into a
A single hash value called the i-handle uses hash trees.
Each i-handle is tied to the latest version of every other i-handle using version vectors.
Data structures
The block store indexes most persistent data structures by their 20-byte SHA-1 hashes. One benefit of hash-based storage is that blocks common to multiple files must be stored only once.
SUNDR stores messages signed by users. A public key hash and an index number index these.
The diagram below shows the persistent data structures SUNDR stores and indexes by hash, as well as the algorithm for computing i-handles.
An i-handle is the root of a hash tree containing a user or group i-table. In the diagram, H denotes SHA-1, while H∗ denotes the recursive application of SHA-1 to compute the root of a hash tree.
A per-principal data structure called the i-table maps each i-number used for the corresponding inode.
A group i-table maps group inode numbers to user inode numbers.
A user i-table maps a user’s inode numbers to i-hashes.
An i-hash is the hash of an inode, which in turn contains hashes of file data blocks.
Every file is identified by a <principal, i-number> pair. Here, the principal is the user or group allowed to write the file, and the i-number is the principal inode number.
Directory entries map file names onto <principal, i-number> pairs.
Each i-table is stored as a B+-tree, where internal nodes contain the SHA-1 hashes of their children, thus forming a hash tree. The hash of the B+-tree root is the i-handle, as shown in the diagram for a user and a group.
A client can fetch and verify any block of any file in the user’s i-table by recursively requesting the appropriate intermediary blocks.
Protocol
The i-handles are stored in digitally signed messages known as version structures. They are shown in the diagram below:
A particular user signs each version structure. It can have three things:
It must always contain the user’s i-handle.
It may contain one or more i-handles of groups to which the user belongs.
It must have a version vector consisting of a version number for every user and group in the system.
When user u performs a file system operation, u’s client acquires the global lock and downloads the latest version structure for each user and group. This is called the version structure list, or VSL.
The client then computes a new version structure, z, by potentially updating i-handles and setting the version numbers in z to reflect the current state of the file system.
On a fetch, the client copies u’s previous i-handle into z, and nothing is changed. On a modification, the client computes and includes new i-handles for u and for any groups whose i-tables it is modifying.
The client sets z’s version vector to reflect the version number of each VSL entry. Finally, the client bumps version numbers to reflect the i-handles in z.
To check consistency, the client verifies that the VSL contains u’s previous version structure and that the set of all VSL entries combined with z is ordered. If checks are successful, the user signs the new version structure and sends it to the server with a COMMIT RPC.
The server adds the new structure to the VSL and retires the old entries for updated i-handles. At last, the client releases the file system lock.
4.4 Concurrent SUNDR
Serialized SUNDR is too conservative. Each client must wait for the previous client’s version vector before computing and signing its own.
An ideal system would like most operations to proceed concurrently. The only time one client should have to wait for another is when it reads a file the other is writing.
Update certificates
SUNDR solves the concurrent updates by pre-declaring a fetch or modify operation before receiving the VSL from the server.
The user sends signed messages called update certificates.
If Yu is u’s current VSL entry, an updated certificate for u’s next operation contains:
u’s next version number
a hash of u’s VSL entry
a (possibly empty) list of modifications to perform
Each modification (or delta) can be one of four types:
Set file <user, i> to i-hash h.
Set group file <group, i> to <user, i>
Set/delete entry name in directory h
Pre-allocate a range of group i-numbers
The client sends the update certificate to the server in an UPDATE RPC.The server replies with the VSL and a list of all pending operations not yet reflected in the VSL, called the awaiting version list or PVL.
When signing an updated certificate, a client cannot predict the version vector of its following version structure, as the vector may depend on concurrent operations by other clients.
Upon receiving the VSL and PVL, a client ensures that the VSL, the unsigned version structures in the PVL, and its new version structure are ordered.
It checks for conflicts. If none of the operations in the PVL change files the client is currently fetching or group i-tables it is modifying, the client signs a new version structure and sends it to the server for inclusion in the VSL.
Update conflicts
If a client fetches a file and the PVL contains a modification to that file, this signifies a read-after-write conflict.
In this case, the client still commits its version structure as before but then waits for fetched files to be committed to the VSL before returning to the application.
The PVL may contain a modification to a group i-handle that the client also wishes to modify, signifying a write-after-write conflict.
The clients check the PVL for read-after-write conflicts. When a client sees a conflicting modification in the PVL, it will wait for the corresponding VSL entry even if u has already incorporated the change in the group.
The solution is for u to incorporate any modifications in the PVL which not yet been reflected. Also record the current contents of the PVL in a new field of the version structure.
In this way, other clients can detect missing PVL entries when they notice those entries referenced in u’s version structure.
5. Discussion
SUNDR only detects attacks. It does not resolve them.
SUNDR’s protocol leaves considerable opportunities for compression and optimization.
SUNDR’s semantics differ from those of traditional Unix.
One cannot change the owner of a file in SUNDR.
6. File system/ Block store implementation
The one good part of the paper is that it details two implementations of SUNDR.
Read the original paper if you want to build something using SUNDR or a similar system.
7. Related work
Many file systems use cryptographic storage to keep data secret and check integrity. Most of them are non-networked.
Several other network file systems provide varying degrees of integrity checks but reduce integrity on read sharing or are vulnerable to consistency attacks.
The Byzantine fault-tolerant file system(BFS) uses replication to ensure the integrity of a network file system.
Farsite is a P2P file system that spreads across people’s unreliable desktop machines.
CFS is a secure read-only file P2P system.
Ivy is a read-write version of CFS.
Pond relies on a trusted “inner core” of machines for security.
8. Conclusions
SUNDR is a general-purpose, multi-user network file system that never presents applications with incorrect file system states.
SUNDR’s protocol guarantees fork consistency, ensuring that the server behaves correctly or that its failure will be detected after users communicate.
References
My post on PBFT (BFS)
FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment
Wide-area cooperative storage with CFS
Ivy: A Read/Write Peer-to-Peer File System