Practical Integrity Protection with Oblivious Hashing

Oblivious hashing (OH) is an integrity protection technique that checks the (side) effects resulting from the executed code, as opposed 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 potentially large subset of program instructions 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 for the masses by proposing i) a technique for automatic segregation of deterministic instructions, and ii) a novel extension, i.e., 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 imposes an overhead of 66% on non-CPU intensive programs, which makes it a practical protection measure.