Composable and Robust Outsourced Storage
Christian Badertscher and Ueli Maurer
The security of data outsourcing mechanisms has become a crucial aspect of today's IT infrastructures. Security goals range from ensuring storage integrity, confidentiality, and access pattern hiding, to proofs of storage, proofs of ownership, and secure deduplication techniques. Despite sharing a common setting, previous security analyses of these tasks are often performed in different models and in a stand-alone fashion, which makes it hard to assess the overall security of a protocol or application involving several security schemes. In this work, we fill this gap and provide a composable model to capture the above security goals. We instantiate the basic client-server setting in this model, where the goal of the honest client is to retain security in the presence of a malicious server. Three specific contributions of the paper, which may be of independent interest, are:
1.) We present a novel and composable definition for secure and robust outsourcing schemes. Our definition is stronger than previous definitions for oblivious RAM or software protection, and assures strong security guarantees against active attacks. It not only assures that an attacker cannot learn the access pattern, but moreover assures resilience to errors and the prevention of targeted attacks to specific locations. We provide a protocol based on the well-known Path ORAM scheme achieving this strong security goal. We justify the need for such a strong notion in practice and show that several existing schemes cannot achieve this level of security.
2.) We present a novel and composable definition for proofs of retrievability capturing the guarantee that a successful audit implies that the current server state allows the client to retrieve his data. As part of our study, we develop an audit mechanism, based on secure and robust outsourcing schemes, that is similar to the construction by Cash et al. (Eurocrpyt 2013), but is universally composable and fault-tolerant.
3.) We assess the security of the standard challenge-response audit mechanism, in which the server has to compute a hash $H(F||c)$ on the file $F$ concatenated with a uniformly random challenge $c$ chosen by the client. Being concerned with composable security, we prove that this audit mechanism is not secure, even in the random oracle model, without assuming additional restrictions on the server behavior. The security of this basic audit scheme was implicitly assumed in Ristenpart et al. (Eurocrypt 2011). To complete the picture, we state the additional assumptions for this audit mechanism to be provably secure and investigate the (in)applicability of hash-function constructions in this setting.