Map and projects (the most frequently updated page of this blog)

2010/02/08

If you want to strike me down in anger

Messing with loops
Do you understand these snippets?
setz ah setnz cl
aad 11 xor eax, eax
add eax,04000f3 mov fs:[eax], esp
jmp eax ror cl, 01
into


the problem

When reversing a program, fast forwarding by skipping loops is important - no one wants to step through each iteration. Also, detecting loop behavior is important in emulators, especially when extra loops are inserted to make them time out.


Let's take a simple example:

If you want to reset ECX and artificially create unneededed computing cycles, you can use
E2FE loop $
which just decrements ECX until it's zero. It might take several seconds (!), even if it's a simple operation altogether. So, it might be critical to detect and fast-forward it (emulate all its cycles at once). For a manual analysis, the skip is trivial.

So, to make either time-constrained emulation or manual analysis harder, you can make your loop harder to detect. Typically, when you analyze loops, you'll find the conditional jump, identify the exit point, and set a breakpoint on it.
Making the conditional jump or the exit point harder to find is what you'd be looking for to make reversing harder.

No Jxx

An easy way to hide the conditional jump and the exit address is to merge both jumps (to loop start and exit) in a single, calculated, unconditional jump, like this:
jmp loop_start + (condition) * (loop_end - loop_start)

So, after your loop condition, which sets some flag
dec cl
turn the flag into a number (0 or 1, then)
setz reg16
multiply by the distance between loop start and end
mov eax, loop_end - loop_start
mul reg16
or, in an unsual way (on AH only)
aad loop_end - loop_start

add the start address
add eax, loop_start
now you can jump inconditionally
jmp eax

Now, you get a standard loop, but with only one jump to both continue and exit, and you have to dig into the code to compute in advance the exit point. Obfuscating the critical information 'end - start' will make it even more difficult to exit from this loop quickly, especially because in this case the loop_exit might not be near the loop body.

a needle in the haystack

Another way is to add several decoy conditional jumps. Make them, as well as the real exit conditional jump, obfuscated (ie, jump on a comparison with 05fb4e3 instead of 0, with the counter hidden somewhere), make them jump to code being decrypted (to prevent software breakpoints), make more than 4 of them (to exhaust hardware breakpoints), and you get a loop that you can't exit of easily, for which you need to check every execution of each of these conditional jumps.
I made a simple example, in which 4 different registers are influenced by a counter (left obvious on purpose here), and compared to odd values, then jumping to different destinations:
cmp ax,0cafb
je 00400130
...
cmp bx,0bf21
je 0040012f
...
cmp dx,0c0d1
je 0040012e
...
cmp si,0bab0
je 00400131
Of course, this example is simplified. Add more junk code and randomization, you'll get what a few packers do.

SEH obfuscation

Peter Ferrie wrote an interesting kind of obfuscated loop:
push 3
pop ecx
call l1
pop eax
pop eax
pop esp
pop ecx
l1:
dec ecx
push ecx
setne cl
xor eax, eax
mov dword ptr fs:[eax], esp
ror cl, 01
into

In this case, the counter is decremented with a
dec ecx
which sets ZF.

the ZF flag is moved to OF by the combination of
setne cl ; cl = ZF ? 0 : 1
ror cl, 01 ; cl = ZF ? 0 (OF cleared) : 80 (OF set)

and the hidden conditional jump is
CE into
which triggers Int4 if OF is set, and nothing otherwise.

In short, this loop works by setting an exception handler, then, depending on ZF then OF, trigger an exception via Int4 (and loop) or just exit the loop.
However the devil is in the details:
the PUSH ecx both saves the counter on the stack, and set the right structure for an SEH (even though the next forwarder is wrong, since it will be the value of the counter and not the next SEH in the chain).
00000002 Pointer to next SEH record
004000F8 SE handler

Also, to restore ESP on each exception iteration, instead of using 4 bytes:
8b642408 mov esp,[esp+8]
It's implemented as 2 discarded pop and a real one, which is 3 bytes
58 pop eax
58 pop eax
5c pop esp



That's 3 examples of obfuscated loops, and the first 2 are used in widespread packers (Waledac, PESpin) already.

Update:
Hiding the counter and exit

Another idea, suggested by Baboon, is to replace the counter increment with something more random-looking, such as a LFSR, to prevent an easy guess of the required amount of iterations, and at the same time, have the loop exit address updated at each iteration, so that it's only correct at the last iteration:
lfsr32 edx, 0d0000001h
xor dword [loop_exit], edx ; exit address is updated blindly

lfsr16 cx, 0b400h
cmp cx, 0eaa2h ; this will be true on the 35th iteration
jnz loop_start

jmp [loop_exit] ; exit address is jumped to blindly

Here, both lfsr are independant. It would be worse if the loop exit also depends on the counter lfsr.

Source and binary

Note that you need to update the last loop_exit variable manually in the source, as YASM doesn't seem to support 'complex' operations such as:
loop_exit dd loop_end ^ Key

[...]

Bidouiller avec les boucles
Vous voyez ce que font ces bouts de code ?
setz ah setnz cl
aad 11 xor eax, eax
add eax,04000f3 mov fs:[eax], esp
jmp eax ror cl, 01
into


Énoncé du problème

Quand on analyse un programme, gagner du temps en sautant les boucles est important - personne ne veut faire du pas à pas sur chaque itération. De même, détecter les boucles est important dans les émulateurs, surtout si on a ajouté des boucles superflues pour les faire abandonner.


Prenons un exemple simple :
Si vous voulez mettre ECX à zéro, et créer des cycles d'exécution supplémentaires, vous pouvez utiliser
E2FE loop $
qui décrémente juste ECX jusqu'a ce qu'il soit nul. Cela peut prendre plusieurs secondes (!), même si c'est au final une opération très simple. On comprend qu'il soit critique de détecter et de l'accélérer (émuler tous les cycles d'un coup). Lors d'une analyse manuelle, la sauter est trivial.


Donc, que ce soit pour rendre plus difficile une émulation en temps limité ou une analyse manuelle, on peut rendre une boucle plus difficile à détecter. D'habitude, quand on analyse une boucle, on trouve le saut conditionnel, on identifie le point de sortie, puis on y met un point d'arrêt.
Rendre le saut conditionnel ou le point de sortie plus difficile à trouver est ce qu'on cherchera pour rendre l'analyse ardue.

pas de Jxx

Un moyen facile de cacher le saut conditionnel et le point de sortie est de fusionner les deux sauts (vers le début et la fin de la boucle) en un seul, calculé, saut inconditionnel, comme ceci:
jmp début + (condition) * (fin - début)

Donc, après la condition de la boucle, qui change les drapeaux
dec cl
on transforme le drapeau en nombre (0 ou 1, dans ce cas)
setz reg16
on multiplie par la distance entre début et fin
mov eax, fin - début
mul reg16
ou, de manière moins répandue, uniquement sur AH
aad fin - début

on ajoute l'adresse de début
add eax, début
maintenant, on peut sauter inconditionnellement
jmp eax

On obtient une boucle standard mais avec un seul saut pour continuer ou sortir, et on doit fouiller dans le code pour savoir à l'avance le point de sortie. Dissimuler l'information cruciale 'fin - début' rendra les choses encore plus difficiles, particulièrement si la sortie est loin du bloc de la boucle.

une aiguille dans une botte de foin

Une autre façon est d'ajouter plusieurs sauts conditionnels factices. On les rendra, de même que le vrai saut de sortie, plus compliqués (par exemple, comparer à une valeur genre 05fb4e3 plutôt que 0, avec le compteur caché quelque part), on les fera sauter vers du code en cours de décryptage (pour éviter les points d'arrêt logiciels), on en mettra plus de 4 (pour être à court de points d'arrêt matériels), et on obtient ainsi une boucle dont on ne peut sortir facilement, à part devoir vérifier à chaque itération chacun de ces sauts conditionnels.
J'ai fait un exemple simple, où 4 registres sont influencés par le compteur (laissé volontairement évident dans ce cas), et comparés à des valeurs bizarres, et qui sauteront vers des adresses différentes:
cmp ax,0cafb
je 00400130
...
cmp bx,0bf21
je 0040012f
...
cmp dx,0c0d1
je 0040012e
...
cmp si,0bab0
je 00400131
Bien sûr, cet exemple est simplifié. Ajoutez du code pourri et aléatoire, et vous aurez ce que font certains packeurs.

une boucle avec SEH

Peter Ferrie a écrit une forme originale de boucle:
push 3
pop ecx
call l1
pop eax
pop eax
pop esp
pop ecx
l1:
dec ecx
push ecx
setne cl
xor eax, eax
mov dword ptr fs:[eax], esp
ror cl, 01
into

Dans ce cas, le compteur est décrémenté via
dec ecx
ce qui modifie ZF.

le drapeau ZF est copié vers OF par la combinaison de
setne cl ; cl = ZF ? 0 : 1
ror cl, 01 ; cl = ZF ? 0 (OF cleared) : 80 (OF set)

et le saut conditionnel caché est
CE into
qui déclenche l'interruption 4 si OF est défini, et rien sinon.

En résumé, cette boucle défini un gestionnaire d'exceptions, puis, en fonction de ZF puis OF, déclenche une exception par Int4 (et boucle) ou sort juste de la boucle.

Cependant, il faut faire attention aux détails :
le PUSH ecx sert à la fois pour sauver le compteur sur la pile, et définir la bonne structure pour le gestionnaire d'exception (même si le gestionnaire suivant sera faux, puisque ça sera le compteur et non le gestionnaire suivant dans la chaîne).
00000002 Pointer to next SEH record
004000F8 SE handler

De même, pour restaurer ESP à chaque itération, au lieu d'utiliser 4 octets:
8b642408 mov esp,[esp+8]
c'est implémenté via 2 pop inutiles et un vrai, ce qui fait 3 octets
58 pop eax
58 pop eax
5c pop esp



Voici donc 3 exemples de boucles cachées, dont les 2 premiers sont utilisés dans des packeurs courants (Waledac, PESpin).

Mise à jour:

cacher le compteur et la sortie

une autre idée, suggérée par Baboon, est de remplacer l'incrément de compteur par quelque chose qui a l'air plus aléatoire, comme un LFSR (registre à décalage à rétroaction linéaire), pour empêcher de deviner facilement le nombre d'itération requis, et en même temps, de modifier l'adresse de sortie de la boucle à chaque itération, pour qu'elle ne soit correcte qu'à la dernière :
lfsr32 edx, 0d0000001h
xor dword [loop_exit], edx ; l'adresse de sortie est modifiée aveuglément

lfsr16 cx, 0b400h
cmp cx, 0eaa2h ; cela sera vrai à la 35ème itération
jnz loop_start

jmp [loop_exit] ; on saute aveuglément à l'adresse de sortie

Ici, les deux lfsr sont indépendants. Ça serait plus compliqué si l'adresse de sortie dépendait aussi du lfsr du compteur.

Source et binaire

Notez que vous devez modifier la dernière variable loop_exit manuellement, car YASM n'accepte pas les opérations complexes telles que :
loop_exit dd loop_end ^ Key

7 comments:

  1. A simple idea I've never seen in packers is to use LFSR as a counter and an other one to decrypt the "end address".

    You couldn't easly get the right "end address" without executing the code ;)

    I've just think about this when I read your post, I'll probably implement this idea in a crackme ... It could be fun :D (but no time for this right now :/ )

    (sorry for my bad english ;) )

    ReplyDelete
  2. You mean replace the usual:
    counter = counter + 1
    and
    until counter =
    with something more complex like
    counter = f(counter, state)
    and
    until counter = ?

    I'm not sure it will make the loop harder to detect, just more difficult to predict its length. But the loop, its condition and exit point will be unchanged.

    I will give it a try later.

    ReplyDelete
  3. No, I mean replace a standard condition :

    mov ecx , 1235
    start:

    do something

    loop start

    by something like that :

    void* t[] = {start_address, end_address ^ K};

    start_address :

    do something

    t[1] ^= LFSR2.next();
    goto(t[(LFSR1.next() == C1)])

    end_address

    you can't found the right end address without executing code and you can't know wich goto(t[(LFSR1.next() == C1)]) is the right one if you set a lot of fake ones with condition satisfied with more execution than the right one

    Here I say LFSR but all pseudo random function with a sufficient period can be used

    ReplyDelete
  4. Updated - I expect that's what you had in mind.

    ReplyDelete
  5. This is the spirit yes ;)

    I've coded a little example wich implement "fake jumps" here is the code and the executable (python to generate GoAsm code) :

    http://baboon.rce.free.fr/download/loopjunk.zip

    I've not only use XOR operations to crypt address (or by inverse the most significant bit for all encrypted address we are sure to raise exception when end address will be reached and it simplify analysis)

    In this example I use a single LFSR and different IV for each fake or real jumps but we can implement my idea with different architectures ...

    (Try to trace the code and find the end address of the loop without "cheating" (by using the messagebox call address for example) it should be hard without develloping tools ;) )

    ReplyDelete
  6. Nice !
    Actually, it's the same problem with 1 or 100 'loops' (can't guess exit point, without guessing the amount of iterations, which is obfuscated).
    Same solution: either reverse the whole logic, or put a conditional breakpoint on each entry. In both cases here, you'd need a script.

    But a very nice result! Thanks for sharing!

    ReplyDelete
  7. The main interest in adding fake loops is to make conditional BP inefficient because of their quantity

    And with a little bit of obfuscation analysis of conditions can become hard :p

    Thanks for writing post too, If I hadn't read your article I would never have this idea

    ReplyDelete