I’ve just returned from the 2012 International Summer School on Information Security and Protection (ISSISP2012) held at the University of Arizona. This annual summer school brings together a mix of academic researchers and industry practitioners in the field of software protection where the main philosophy, and indeed the only viable approach available, can be summed up as “Security through Obscurity”. The goal here is to impede reverse engineering and to hide algorithms and data in the presence of disassemblers, decompilers, debuggers as well as side-channel analysis – this is the Man-at-the-End (MATE) attack. White box cryptography, I’ve learnt, is the term used to describe the protection of cryptographic primitives and keys against this kind of attack. This week I wish to highlight 3 talks/papers which I found memorable – the first 2 describe techniques to address code injection and timing side-channel attacks; the last one discusses formally verified program obfuscators.

Secure and Practical Defense Against Code-injection Attacks using Software Dynamic Translation

Hu et al. 2006 International Conference on Virtual Execution Environments (VEE’06)

Software dynamic translation (SDT), or dynamic binary translation, is the process of converting sequences of instructions from a source instruction set to a target instruction set at run-time. This is useful for retargeting legacy code on a new platform, but it is also useful for Instruction Set Randomization (ISR). The premise of ISR is simple – only allow code from the original program to execute by randomizing the target instruction set at run-time. The attacker doing the injection has to guess what the instruction set is in order to run his code. If the randomization is protected by a 128-bit AES key, then there is a low probability of correctly guessing the instruction set and an injection successfully executing.

However, code injection attacks aside, SDT is an interesting technique for anti-reverse engineering because it rules out static analysis of the program if the source instruction set is now randomized. An attacker is now forced to analyse the program dynamically and piece together the original if he/she wants to use a static analysis tool such as a disassembler.

Compiler Mitigations for Time Attacks on Modern x86 Processors

Van Cleemput et al. ACM Transactions on Architecture and Code Optimization 2012

Timing side-channels, which can reveal correlations between cryptographic keys and execution time, are non-trivial to remove, as this paper illustrates. It was observed that on various Core 2, Xeon and Atom processors, the timing of a 32-bit unsigned division was dependent on the upper bits of the divisor and dividend. Another undocumented timing channel discovered was the timing behaviour of consecutive memory accesses, which depended on the byte alignment of the store addresses and the displacement between the addresses accessed. The solution adopted takes a purely software approach, and to address the first channel the idea was to duplicate computation in a latency invariant way by adding compensation code, then choosing the correct value using conditional moves. To address the second channel, the authors added no-ops to de-couple memory accesses. The timing overhead of removing these channels is quite high – about 400%. However, the mitigations seem to be highly effective and not the whole program needs to be protected in this manner.

Obfuscation by Partial Evaluation of Distorted Interpreters

Giacobazzi et al. ACM SIGPLAN Partial Evaluation and Program Manipulation (PEPM’12)

The main idea is that an attacker can be modeled as an abstract interpreter of the concrete semantics of a program P. The aim is then to construct a distorted but correct interpreter, interp+, to transform P to P’ so as to make the abstraction imprecise. A simple example is to consider the sign abstraction O = {+,0,-}. This abstraction is complete for integer multiplication because one can precisely derive the sign of x = a*b given the sign of a and b. It is, however, incomplete for addition. So by replacing all multiplications to an equivalent series of additions, the sign abstraction is made imprecise. The authors then showed how to design obfuscating compilers for control-flow flattening, opaque predicate insertion and data-type refinement. In practice real attacks use multiple tools. This can be formalized as an attack having more than one interpreter, and in theory a defender can compose multiple distorting interpreters to create more robust obfuscators.