Practical Integrity Protection with Oblivious Hashing

Oblivious hashing (OH) is an integrity protection technique that checks the (side) effects resulting from the executed code, in contrast to checking the code itself as done by self-checking (SC). SC introduces atypical behavior in the program logic, like reading the code section loaded in memory. Since such atypical behavior can be detected by attackers, OH is more appealing to be employed in practice than SC. However, OH is incapable of protecting a presumable majority of program instructions, those that depend on nondeterministic (input) data or branches, which have to be manually identified and subsequently skipped. In this paper, we extend OH into a practical protection scheme by proposing i) a technique for automatic segregation of deterministic instructions, and ii) a novel extension, Short Range Oblivious Hashing (SROH), for OH to cover control-flow instructions dependent on nondeterministic data. Our SROH technique increases the range of instructions that OH can protect to nondeterministic branches. Moreover, we intertwine OH with SC to cover (nondeterministic) data dependent instructions and enhance the resilience against tampering attacks. We evaluate the performance overhead as well as the security of our scheme using the MiBench dataset and 3 open source games. Our experiments show that the proposed technique yields a 20-fold increase in the median number of protected instructions and, on non-CPU-intensive programs, imposes an overhead of 52%.