When reversing smart-cards, the side-channel attacks are known to be quite effective on hardware. But, what is it, and can it be used in software reverse-engineering and how?
A 'side-channel attack' define any technique that will consider unintended and/or indirect information channels to reach his goal. It has been first defined in smart-card cryptography to describe attacks which are using unintentional information leak from the embedded chip on the card and that can be used in retrieval of keys and data. For example, it may be used by monitoring:
Execution Time (Timing attack): To distinguish which operations has been performed and guess, for example, which branch of the code has been selected (and, thus, the value of the test).
Power Consumption (Power monitoring attack): To distinguish precisely what sequence of instructions has been performed and be able to recompose the values of the variables. Note that there exist several techniques of analysis using the same input but with slightly different way of analyzing it. For example, we can list: Single Power Analysis (SPA), Differential Power Analysis (DPA), High-order Differential Power Analysis (HO-DPA), Template Attacks, ...
Electromagnetic Radiation (Electromagnetic attacks): Closely related to power consumption, but can also provide information that are not found in power consumption especially on RFID or NFC chips.
If you're more interested in learning how to leverage this information then I'd suggest to start by reading Power Analysis Attacks. Don't get 'scared' away by the fact that the book is about smart cards. Most of the information also applies 1-to-1 on 'normal' (SoC) embedded devices.
Forgot to mention there's an open source platform called OpenSCA and some open source hardware called FOBOS (Flexible Open-source BOard for Side-channel) for which I can't seem to find a proper link from home.
Application to Software Reverse-engineering
Speaking about the application of side-channel attacks in software reverse engineering now, it is more or less any attacks that will rely on using unintended or indirect information leakage. The best recent example is this post from Jonathan Salwan describing how he guessed the password of a crackme just by counting the number of instructions executed on various inputs with Pin.
More broadly, this technique has been used since long in software reverse-engineering without naming it, or could have improved many analysis. The basic idea is to first consider that if a piece of software is too obscure to understand it quickly, we can consider it as a black-box and think about using a side-channels technique to guess the enclosed data through a guided trial and error technique.
The list of side-channels available in software reverse-engineering is much longer than the one we have in hardware. Because it enclose the previous list and add some new channels such as (non exhaustive list):
Instruction Count: Allow to identify different behaviors depending on the input.
Read/Write Count: Same as above, with more possibilities to identify patterns because it includes also instruction read.
Raised Interrupt Count: Depending on what type of interrupt is raised, when and how, you might identify different behaviors and be able to determined the good path to your goal.
Accessed Instruction Addresses: Allow to rebuild the parts of the program that are active at a precise moment.
Accessed Memory Addresses: Allow to rebuild data pattern or complex data-structure stored or accessed in memory (eg. in the heap).
This list is far from being exhaustive, but basically tools such as Valgrind VM or others can be used to perform such analysis and quickly deduce information about the behavior of a given program, thus speeding up the reverse-engineering.
Obfuscation and Possible Counter-measures
Trying to build a software which will be resistant to such attacks will borrow also a lot from the smart-card industry. But, not only. Here are a few tricks, I could think of (but far from being complete about all we can find).
Armoring Program Branches
The instruction count is extremely efficient to detect which branch has been taken in code like this:
if (value) ret = foo(); else ret = bar();
bar() having different instruction count.
This can be defeated by executing
value is and deciding afterward what is the value of
tmp_foo = foo(); tmp_bar = bar(); if (value) ret = tmp_foo; else ret = tmp_bar;
This technique render your program much more difficult to guess from a side-channel attack, but also much less efficient. One has to find a proper trade-off.
Countering Timing Attacks
Timing attacks are extremely easy to perform and difficult to workaround because
sleep() cannot be an option (too easy to detect in a code and, anyway you cannot assume a specific speed for the processor). The programmer has to identify the execution time of each branch of his program and to balance each branch with extra non-useful operations which are of the same computational power than the ones from the other branchs. The point being to render each branch indistinguishable from the others only based on the execution time.
Another way to dilute the side-channel is to massively multi-thread your program. Imagine that each branch of your program is executed in a separate thread, and one variable tell in which thread the current program really is (if possible in a cryptic manner). Then side-channel analysis will be much more difficult to perform.
Conclusion and Further Research
Side-channel attacks has been widely under-estimated for software reverse-engineering, it can drastically speed-up the reverse of many programs. But, in the same time, obfuscation techniques exists and have to be developed specifically targeting software reverse-engineering. So, don't be surprised if you see more and more novelties related to this field.