Computer Architecture Today

Informing the broad computing community about current activities, advances and future directions in computer architecture.

This is the first post in a series of posts on different approaches to systems security especially as they apply to hardware and architectural security. In this post, we will consider the use of mathematics/cryptography as an approach to improving systems security.

The class of techniques described in this blog post, which we broadly refer to as applied hardware and architecture cryptography,  apply proven cryptographic techniques to strengthen systems. These techniques have many desirable properties such as the ability to provide strong, provable guarantees against very capable adversaries, often adversaries with unbounded computational power.

Broadly speaking, in all security approaches there is a notion of a trust boundary, and within the trust boundary, the system is assumed to work correctly.  Further, depending on the type of attacks we are concerned with, we typically assume that the adversary normally cannot tamper with or monitor state within the trust boundary. There are two reasons why having a small trust boundary is important.  First, as the trust boundary grows the chance of bugs increases, and a bug within the trust boundary undermines the entire system. Second, as the trust boundary grows, the classes of adversary that can permeate that boundary increases. With this in mind, cryptographic techniques, generally speaking, allow systems to operate with a smaller trust boundary.

For example, consider a database system that is distributed across a data center, or even across data centers. It has been shown how realistic adversaries can easily monitor system behavior, e.g., through tapping on a connection, at that scale.  Naively securing this system would require a large amount of trust; “guns and guards”, trusted personnel, and trusted software and hardware. On the other hand, one can implement this system with encryption/decryption units between the compute and the storage.  This allows the same database to be implemented while removing storage and connections from the trust boundary.

Applications of Cryptography to hardware and architecture:

Any system can be thought of as a composition of storage, transmission and compute elements.  Different cryptographic techniques can reduce the trust boundary of each of these three components with respect to different threats and system requirements.

  • Storage: Probabilistic encryption or Proofs of Retrievability are two examples of cryptographic concepts can be used to reduce trust in storage.  These two techniques serve complementary purposes: Probabilistic encryption hides data stored at rest.  Proofs of retrievability provide a guarantee that data hasn’t been deleted.

  • Transmission: A number of encryption schemes (e.g., probabilistic symmetric encryption, and a number of asymmetric (public-key) schemes, e.g., attribute-based and broadcast encryption) and Oblivious RAM can reduce trust in transmission.  These two also have complementary uses, given different adversarial models.  Encryption schemes hide data during transmission while  Oblivious RAM hides data and the accessed locations.

  • Compute: Finally, order preserving and homomorphic encryption are examples of techniques that can reduce trust in compute.  These two, yet again, are each useful in different circumstances. Order preserving encryption is only useful when simple comparisons such as less than/greater than need to be applied to data and reveals the outcome of these comparisons to an attacker, but is reasonably efficient.  Homomorphic encryption can implement arbitrary computations without revealing any information, but incurs additional overheads.

Importantly, none of the above cryptographic techniques entirely eliminate the trust boundary, but rather reduce the trust boundary to system endpoints.  For example, using encryption in a database system requires the data to be encrypted/decrypted when it reaches the compute.

As they fall within the trust boundary, how these endpoints are implemented is critical for security to hold.  While correct implementation is neither easy nor obvious for crypto systems any more than other systems, it is generally believed that it is easier to formally verify that the implementation matches a specification. In other words, while the the use of crypto does not reduce the trust to zero, it minimizes the chance of erroneous implementations and provides guarantees that can be precisely articulated.

Much remains to be done in this area. The holy grail is to develop systems with the proper balance of crypto and secure HW/SW.  Systems based on pure crypto have high security but high performance overheads. Systems based on no crypto require large trust boundaries, meaning low security and low performance overheads.  By properly designing and implementing hybrid SW/HW/crypto systems we can get the best of both worlds, enabling important applications, such as voting systems, securely sharing sensitive data between organizations for collaborative healthcare, financial transactions, etc. While many applications are realizable right now with pure crypto, they are prohibitively expensive.  The challenge is identifying when particular systems components (storage/transmission/compute) should or should not be placed within the trust boundary, and composing the right systems/crypto techniques to get performance back without compromising security. It is important to remember that when researching how crypto can reduce the trust boundary, performance overhead should be a second order concern.  It is common that once the research community embraces the need for specific cryptographic technique, that technique can be optimized to reduce overheads.

For Further Study:

About the Authors: Chris Fletcher is an assistant professor at the University of Illinois at Urbana-Champaign. His interests lie at the intersections between computer architecture, security and machine learning.  His website is http://cwfletcher.net/Simha Sethumadhavan is an associate professor at Columbia University. His website is http://www.cs.columbia.edu/~simha, and his twitter is https://www.twitter.com/thesimha.