Secure Untrusted Data Repository SUNDR Jinyuan Li Maxwell Krohn David Mazie res and Dennis Shasha NYU Department of Computer Science Abstract versions that open back doors and conceal evidence of the security breach Data security is often viewed as the problem of building a better fence around storage servers limiting the number of people with server access disabling unnecessary daemons that might be remotely exploitable and staying current with security patches to minimize the window of vulnerability to software flaws This approach has two drawbacks First experience has shown in many cases that people do not build high enough fences Second perhaps more important high fences are inconvenient they restrict the ways in which people can manage data An alternative approach is to reduce the security needs of file servers This paper presents SUNDR a secure network file system designed to do exactly this Assuming only the existence of digital signatures and a collisionresistant hash function SUNDR s protocol provably guarantees the integrity and consistency of file system data even when malicious parties entirely control the server Unlike previous Byzantine fault tolerant file systems 3 22 that distribute trust but assume that a threshold fraction of servers are honest SUNDR assumes no on line trusted parties To tamper with a user s files without being detected an attacker must either compromise the user s client while the user is logged in or otherwise produce valid digital signatures under the user s public key In particular the superuser s private signature key can be stored off line when not in use making it extremely difficult for an attacker to gain superuser access to the file system SUNDR does not currently address the issue of storage reliability Of course an attacker can always physically damage a server or wipe its disks However SUNDR stores all long lived data in an append only block log Thus it could use append only storage 27 to gain resilience to network attacks Incremental off site backups are also easily implementable to survive physical compromise Moreover because SUNDR does not trust the file server after a disaster any lost file system data can safely be recovered from other untrusted sources that might have the data such as clients file caches SUNDR s security model gives people more options for managing their data than current systems For instance organizations can outsource data storage without fear of the server operators tampering with data It also offers a vast improvement over current file system security We have implemented a secure network file system called SUNDR that guarantees the integrity of data even when malicious parties control the server SUNDR splits storage functionality between two untrusted components a block store and a consistency server The block store holds all file data and most metadata Without interpreting metadata it presents a simple interface for clients to store variable sized data blocks and later retrieve them by cryptographic hash The consistency server implements a novel protocol that guarantees close to open consistency whenever users see each other s updates The protocol roughly consists of users exchanging version stamped digital signatures of block server metadata though a number of subtleties arise in efficiently supporting concurrent clients and groupwritable files We have proven the protocol s security under basic cryptographic assumptions Without somehow producing signed messages valid under a user s or the superuser s public key an attacker cannot tamper with a user s files even given control of the servers and network Despite this guarantee SUNDR performs within a reasonable factor of existing insecure network file systems 1 Introduction Nobody wants malicious attackers tampering with his files This basic and obvious fact underlies much of the way people manage data Important file systems must be kept on secure servers in machine rooms to which only authorized people have access Only highly trusted administrators can perform mundane tasks such as backup and hardware maintenance Conversely people must address the constant threat of attackers gaining administrative privileges on servers Otherwise a number of readily available rootkits allow attackers who penetrate a system to replace core operating system utilities with altered NYU computer science dept technical report TR2003 841 June 2003 This work was supported by National Science Foundation CAREER award CCR 0093361 and by the Defense Advanced Research Projects Agency DARPA and the Space and Naval Warfare Systems Center San Diego under contract N66001 00 1 8927 1 2 1 An attacker who compromises a SUNDR server cannot tamper with file contents Our prototype implementation gives performance within a reasonable factor of the popular NFS file system making SUNDR practical despite its significantly increased security The next section gives an overview of the SUNDR protocol The following two sections describe SUNDR s implementation and how we tuned the protocol to give acceptable performance Section 5 evaluates the performance of our implementation Section 6 discusses related work and Section 7 concludes Data structures Figure 1 shows the basic SUNDR data structures Every file is identified by a hprincipal i numberi pair where principal is the user or group that owns the file and inumber is a per user or per group inode number Unlike traditional file systems SUNDR allows files owned by different users to have the same i number Directory entries map file names onto hprincipal i numberi pairs A per principal data structure called the i table maps each active i number to a collision resistant SHA 1 7 hash of the file s inode We call this value the file s i hash Inodes themselves contain SHA 1 hashes of file data blocks and indirect blocks an approach taken from the SFSRO 10 read only file system SUNDR forms a cryptographic hash tree 15 from each i table The root of this tree is called the i handle Given an i handle and all appropriate intermediary data structures one can verify any block of any file in the itable Thus securely retrieving file system contents boils down to the problem of first obtaining the latest i handle of each user and group then retrieving any needed data blocks by their SHA 1 hashes The latter functionally is conceptually simple to implement in the block server while the former requires a somewhat complex consistency protocol 2 Protocol The SUNDR protocol