Caches and Merkle Trees for Efficient Memory Authentication
Blaise Gassend, Dwaine Clarke, Marten van Dijk, Srinivas Devadas, Ed Suh, G. Edward Suh · DSpace@MIT (Massachusetts Institute of Technology) · 2002
We describe a hardware scheme to authenticate all or a part of untrusted external memory using trusted on-chip storage. Our scheme uses Merkle trees and caches to efficiently authenticate memory. Proper placement of Merkle tree checking and generation is critical to ensure good performance. Naïve schemes where the Merkle tree machinery is placed between caches can result in a large increase in memory bandwidth usage. We integrate the Merkle tree machinery with one of the cache levels to significantly reduce memory bandwidth requirements. We present an evaluation of the area and performance costs of various schemes using simulation. For most benchmarks, the performance overhead of authentication using our integrated Merkle tree/caching scheme is less than 25%, whereas the overhead of authentication for a naïve scheme can be as large as 10×. We explore tradeoffs between external memory overhead and processor performance.