ReFormat: Automatic Reverse Engineering of Encrypted Messages

Five researchers, Z. WANG, X. JANG, W. CUI, W. WANG and M. GRACE presented, according to me, a nice piece of work at Esorics 2009.

The objective was to automatically reverse engineer encrypted messages without breaking the algorithms. The basic idea is simple. When a piece of software receives an encrypted message, it performs two steps (regardless of the used cryptographic algorithms and protocols). First, it decrypts the message and then it processes the clear message. This means that the message is during a while in the clear in the memory. if you identify the location of this buffer, and when it is used, then game over.

To succeeed, they used two tricks. The first was to distinguish between decryption routines and normal processing routines. Cryptographic functions use far more bit wise and arithmetic operations than normal software. They measured (on OpenSSL) that more than 80% of the operations were bit wise and arithmetic for cryptographic functions. The rate dropped beneath 25% for normal processing. This heuristic allows to detect the encryption/decryption phases.

The second step is to locate the buffer containing the clear text. They identify all the buffers that are written while in decryption phase. Then, they identify all the buffers that are read during the processing phase. The expected buffer should be in the intersection between the two sets.

Obviously, there are many ways to deter this attack. For instance code obfuscation may change the rate. Dynamic code encryption is of course a must. Nevertheless, I found the approach extremely clever.

Once more, it proves that writing secure implementations is extremely difficult. And it requires clearly a twisted mindset. :Happy:

If you are interested in tamper resistance, you have to read this paper. It is available here.

Leave a Reply

Your email address will not be published. Required fields are marked *