Friday, March 16, 2012

Python is going to have randomized hash function

Barry Warsaw committed a fix for "Randomize hashes of xml atributes in the hash table internal to the pyexpat module" to 2.6 on March 14. The patch was written by David Malcolm based on work by Victor Stinner and with modifications by the Expat project.

This is a collateral damage resulting from the much publicized hash function collision exploit. Expat is an XML parsing library that Python has a wrapper around. It was known to be vulnerable to the same O(N2) bug when one parses an XML element with many same-hash attributes such as wzzgDM51, ezzDlT7W, hzzfbyVV and so on.

Starting from Python 2.6.8rc2, there is a new switch -R, and an environment variable PYTHONHASHSEED that control this randomization.

The bottom line is: if you use Python 32-bit, do think of upgrading to 2.6.8 at the earliest convenience.

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.

Wednesday, March 7, 2012

SELECT COUNT(*) and WHEN

I observed this very interesting MySQL issue. Basically, I have a huge tables with millions of rows in it. It has an ID column which is an auto-incremented integer primary key.

It took me 20 seconds to do SELECT COUNT(*) FROM tbl yet it only took me 4 seconds to do SELECT COUNT(*) FROM tbl WHEN id > 0.

Basically, these two queries return the same value. One would have expected the later to run a bit slower but the experiment proved otherwise. It seems quite counterintuitive. Why?

Tuesday, March 6, 2012

AMD CPU bug!

Does anyone remember Intel Pentium bug? Well, now we have one other CPU bug from AMD.

The description:
http://permalink.gmane.org/gmane.os.dragonfly-bsd.kernel/14471

And the confirmation from AMD:
http://permalink.gmane.org/gmane.os.dragonfly-bsd.kernel/14518

Basically, under very special conditions, the processor will incorrectly update the stack pointer. The most common symptom is a spurious segmentation fault.

This is too hot. Will there be recalls?