Encrypting Files and Not Trusting Cloud Storage Providers

Based on 2003 paper from HP Labs and published in FAST

How can we make full use of cloud storage providers and online file sharing, while also protecting our data when we can't trust the big companies providing the cloud storage? The answer is end-to-end encryption and forced no-knowledge storage. The best part is that you can have your cake and eat it too, since this paper shows ways to incorporate the simple file sharing mechanisms popularised in google docs and drive, and the encryption.

The Problem and the Threat Model

We are using this system primarily due to the lack of trust of the server. More specifically, we do not trust the server to keep the files confidential and not skim over them. However, as the data is still stored on the servers, we must trust they do not simply destroy the data entirely. To get around this, a user could implement multiple server providers and copy the same techniques there.

Trust is required in the client's machine where the encryption and other execution is done. This may lack perfect trust due to viruses and other malware, but this is nessesary and would be for almost any cryptographic and security system. There is also trust placed on the key exchanges and distribution as the client will have full control over the keys. This trust system and threat model is perfect though, since almost all trust is put under the direct control of the user, and away from storage providers.

The Solution

Encrypting files is the first step in the solution, but it would be very inefficient to encrypt every file separately. File groups are used where the entire group has the same symmetric encryption key. These file groups are different to file folders and do not have anything to do with file hierarchy. Files have their file group defined in their meta data which allows a small number of groups that reflect who has access to the files, rather than the location of the files in the hierarchy. A small number of file groups, and therefore keys, is important as key distribution and control is done entirely by the user, meaning less keys is very useful for reducing user side overheads.

To achieve a differentiation between read permissions and writing permissions, asymmetric keys are used. The contents of encrypted files are put through a hash function and signed using a private RSA key. This signing can be verified using the public RSA key. As such, the public RSA key can be given to those for reading, and the private key is kept for writers.

A final major problem is revoking access from users. When the server is trusted, this is easily done using user authentication. This is not feasible when the server is not trusted as the server would, in general, need the ability to access the information in order to give that ability to specific users. The server would also cache information, particularly about the users, which is trusting the server with more information than is ideal. The solution is to use key rotation. Keys will change over time, and given the latest keys, a user can generate all previous key versions. Only the owner can generate the future keys. With these properties, a user can lose access if the owner does not send new keys. This is lazy revocation as the user still has access to the files from the past, but this maintains forward secrecy which is the primary security concern. Accepting this shortcoming avoids a significant amount of computational time as each revocation would require a complete re-encryption of all files. Instead, re-encryption is simply done on the next update of the file.

Revoking read privileges versus write privileges relates to revoking the verification RSA key for readers, and the signing RSA key for writers. A problem is that writers have the ability to sign new files, and would hold the next key in the key rotation. To avoid expensive re-encryption when writers lose their privilege, the meta data of files can be updated immediately as a low cost and mostly effective security measure. Data writes can also be validated by the server using an access control list which is effectively like a shared password for writing. This would blocked most updates from revoked writers, however there still remains some attacks where a revoked writer makes changes that can fool a reader with keys that are out of date. The only way to block these revoked writer problems with with aggressive key changes, but this effort may not be worth it if the users' risk appetite is moderate enough.

Conclusion

The final Plutus file system is quite simple and is cryptographically effective at providing user roles and blocking the server from knowledge of the files. In the paper, the researchers evaluate the performance and showed that it was as good if not better than comparable and popular methods that encrypt the transmission of data to the server and trust the server. Take note that is paper is from 2003. A major update would be to use AES for symmetric encryption instead of triple DES as done in the paper.

A final point that makes the system very practical is the scalability. As cryptographic overhead is performed almost entirely on the client's side, and key distribution is done by the client, the server does not expended extra computational power. As such, this can be implemented and server owners will not see an added cost, which means they should premise this system for use on their servers. This overhead place on the user also allows the size of the storage space used to grow and grow without having a compounding impact of the server and extra space required. The Plutus file system seems to be a very effective and cryptographically secure way to store files and collaborate without trusting the server where the files are stored.

References

Subject Paper: "Plutus: Scalable secure file sharing on untrusted storage", Mahesh Kallahalla, Erik Riedel, Ram Swaminathan, Qian Wang, Kevin Fu,
https://www.usenix.org/legacy/event/fast03/tech/full_papers/kallahalla/kallahalla_html/