Friday, March 16, 2012

Duqu and Time and Space disruption

There has been much talk about Duqu (the worm) these last few days.

I'm not sure what is new here but the classic, foundational security idea: Time and Space disruption.

There is only one single pillar in optimization, and probably in everything we do in life too. It is called locality: Temporal locality and Spatial locality.

Temporal locality says that a program usually favors instructions that it has just recently executed. Think of a loop. A program runs through the same bunch of instructions again and again in that loop.

Spatial locality says that a program usually favors data that are close to each other. A loop, for example, will often iterate through data in the same array, one after another one in a sequential manner.

Locality of time and space are what make our habits and create order from chaos in this life. We wake up in the morning, eat breakfast and go to work every week day. That is locality of time. We usually go to the restaurant around the corner, the cinema a few blocks away, the toilet a few steps away.

Temporal and spatial localities help us understand and predict how a program or even a person would behave. So naturally, the best way, and may I so brazenly declare the one principle, to confuse all reverse engineering attempts and analysis is to disrupt this pattern. The more you can do that, the less predictable and understandable you become. As a figurative example, chasing after a crazy person is way more difficult than a sane one.

Duqu actively aimed for that. From what I can gather from public write ups, Duqu aggressively employs dynamic calls. This is certainly a great way to break spatial locality. Normally, you would have code similar to:

push 2
push 1
call func

Instead, in Duqu, you have:

push 2
push 1
call [mem_location]

What is the function being called? You can only find out at runtime. This makes static analysis virtually impossible. It breaks spatial locality.

Unsurprisingly, this is nothing new. This is exactly how virtual functions are implemented in C++. So, here's a tip for software writers in the battle against crackers: Use more virtual functions to better confuse crackers! That also suggests some object orientation implementation in the case of Duqu.

Beside using function pointers, Duqu employs event driven model. This disrupts temporal locality in architecture. Regular application follows a sequential model where we do everything step by step. Duqu does some small part, then moves on to do some other tiny unrelated part, then gets back to the previous work. It breaks the flow of analysis and requires great patience to trace the worm.

I may have missed many discussion but to me that's about it. I have not seen any active attempt to randomly place different code blocks at different locations, garbage control flows, and other techniques to actively disrupt localities.

But if with just this one technique (probably a result from some discipline way of writing code), Duqu has greatly confused security experts, you know that time and space disruption is at the core of all obfuscations.

PS: On a side note, I used to make a tool that follows exactly this simple principle.

No comments:

Post a Comment