WriteUp du crackme “Efficiency”

Par S01den
([email protected])
07/10/2019


Aujourd’hui on se penche sur l’un des challenges de qualification pour la SIGSEGv2, un événement sur la sécurité informatique, malheureusement interdit aux mineurs, organisé par l’association RTFM (https://rtfm.re/).

“Efficiency”, écrit par SIben, est le seul challenge de reverse disponible dans la phase de qualification; il s’agit d’un ELF 64-bit demandant un mot de passe, le but étant bien évidement de trouver ce flag (dont on sait qu’il se présente sous la forme “sigsegv{…}”).

Étape 1: Static analysis is awesome…

Lorsqu’on lance le binaire, il nous indique “Please enter the password:”, sans aucun output après avoir entré un mot de passe.
Regardons cela de plus près, en le désassemblant avec IDA.

En observant la forme du graphe du code desassemblé et du pseudo-code, on peut remarquer qu’on a probablement affaire à une VM à reverser.
Voilà les parties les plus intéressantes (avec les variables nommées par votre serviteur !):

void main(__int64 a1, char **a2, char **a3)
{
  __int64 password; // [sp+0h] [bp-20h]@1
  password = 0LL;
  puts("Please enter the password: ");
  read(0, &password, 0x14uLL);
  VM((__int64)&password);
}

Le read() récuperant notre input nous permet de savoir que le flag fait 20 caractères.

_DWORD sub_12C6(_DWORD *a1, unsigned int *a2)
{
  _DWORD *result; // [email protected]
  unsigned __int64 v3; // [sp+18h] [bp-18h]@1
  unsigned __int64 v4; // [sp+20h] [bp-10h]@1
  unsigned __int64 v5; // [sp+28h] [bp-8h]@1

  v5 = 1LL;
  v4 = dword_4074;
  v3 = *a1;
  while ( v4 )
  {
    if ( v4 & 1 )
      v5 = v3 * v5 % (signed int)*a2;
    v4 >>= 1;
    v3 = v3 * v3 % (signed int)*a2;
  }
  result = a1;
  *a1 = v5;
  return result;

Une fonction qui va nous intéresser beaucoup…

void VM(__int64 password)
{
  signed int instructionOpcode;
  int opcodesList[97]; 
  int register1;
  int register2;
  int i; 

  for ( i = 0; i <= 4; ++i )
    array[i + 16LL] = sub_1355(*(_DWORD *)(4LL * i + password));
  qmemcpy(opcodesList, &unk_2020, 0x180uLL);
  while ( 1 )
  {
    register2 = opcodesList[instructionPointeur + 1];
    register1 = opcodesList[instructionPointeur + 2];
    instructionOpcode = opcodesList[instructionPointeur];
    if ( instructionOpcode == 0x789ABCDE )
    {
      cmp_pass(&array[register2], &array[register1]);
    }
    else if ( instructionOpcode <= 0x789ABCDE )
    {
      if ( instructionOpcode == 0x6789ABCD )
      {
        sub_1243(3 * (register2 - 1));
      }
      else if ( instructionOpcode <= 0x6789ABCD )
      {
        if ( instructionOpcode == 0x56789ABC )
        {
          continueIfCheckBad(3 * (register2 - 1));
        }
        else if ( instructionOpcode <= 0x56789ABC )
        {
          if ( instructionOpcode == 0x456789AB )
          {
            add(&array[register2], &array[register1]);
          }
          else if ( instructionOpcode <= 0x456789AB )
          {
            if ( instructionOpcode == 0x3456789A )
            {
              xor(&array[register2], &array[register1]);
            }
            else if ( instructionOpcode <= 0x3456789A )
            {
              if ( instructionOpcode == 0x23456789 )
              {
                sub_1170(&array[register2], register1);
              }
              else if ( instructionOpcode <= 0x23456789 )
              {
                if ( instructionOpcode == 0x12345678 )
                {
                  sub_1155(&array[register2], &array[register1]);
                }
                else if ( instructionOpcode <= 0x12345678 )
                {
                  if ( instructionOpcode == 0xEF012345 )
                  {
                    minus(&array[register2], &array[register1]);
                  }
                  else if ( instructionOpcode <= (signed int)0xEF012345 )
                  {
                    if ( instructionOpcode == 0xDEF01234 )
                    {
                      ContinueIfcheck(3 * (register2 - 1));
                    }
                    else if ( instructionOpcode <= (signed int)0xDEF01234 )
                    {
                      if ( instructionOpcode == 0xCDEF0123 )
                      {
                        sub_12C6(&array[register2], &array[register1]);
                      }
                      else if ( instructionOpcode <= (signed int)0xCDEF0123 )
                      {
                        if ( instructionOpcode == 0xBCDEF012 )
                        {
                          toUint(&array[register2]);
                        }
                        else if ( instructionOpcode <= (signed int)0xBCDEF012 )
                        {
                          if ( instructionOpcode == 0xABCDEF01 )
                            exit(status);
                          if ( instructionOpcode <= (signed int)0xABCDEF01 )
                          {
                            if ( instructionOpcode == 0x89ABCDEF )
                            {
                              lShift(&array[register2], register1);
                            }
                            else if ( instructionOpcode == 0x9ABCDEF0 )
                            {
                              Rshift(&array[register2], register1);
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    instructionPointeur += 3;
  }
}

Et la fonction de la VM, la partie du code la plus importante.

Étape 2: But dynamic analysis can help !

Bon, l’analyse statique c’est sympa (surtout grace au pseudocode généré par IDA) mais pour gagner du temps on ne va pas s’embêter à réimplémenter toute la VM.

Le truc, c’est de poser des breakpoints à des endroits stratégiques pour récuperer des infos utiles.
Pour commencer, on pose un breakpoint en 0x555555555445
(**cmp eax,0x789abcde**),
ce qui correspond à l’adresse de la première instruction de comparaison des opcodes de la VM.
En breakant à cet endroit, on récuperera donc dans le registre EAX l’opcode qui sera executé.

Une fois cela fait, on lance le binaire dans le debugger en entrant d’abord un mot de passe random (“AAAA” dans notre exemple) et on relève les opcodes executés.
On obtient ceci:

**[0x23456789,0x6789abcd,0x23456789,0x23456789,0x23456789,0x23456789,
0x23456789,0x23456789,0x23456789,0x23456789,0x23456789,0x23456789,
0x23456789,0xcdef0123,0x789abcde,0xdef01234,0xbcdef012,0xabcdef01]** 

Maintenant en entrant comme mot de passe la partie connue du flag (“sigsegv{”), on obtient ceci:

**[0x23456789,0x6789abcd,0x23456789,0x23456789,0x23456789,0x23456789,
0x23456789,0x23456789,0x23456789,0x23456789,0x23456789,0x23456789,
0x23456789,0xcdef0123,0x789abcde,0xdef01234,0xcdef0123,0x789abcde,
0xdef01234,0xcdef0123,0x789abcde,0xdef01234,0xbcdef012,0xabcdef01]**

On peut voir que plus d’instructions ont été executé, ce qui nous indique que nous sommes sur la bonne voie.
En ayant réimplémenté la VM on aurait pu écrire un bruteforcer “intelligent” qui utilise le nombre d’instructions executées par la machine virtuelle, mais là on va faire autrement.

On peut observer que les deux séries d’opcodes se terminent par les opcodes
**[0xbcdef012,0xabcdef01]**, précédées par un (dans le cas du ‘AAAA’) ou plusieurs (dans le cas du ‘sigsegv{’) groupe d’opcode suivant **[0xcdef0123,0x789abcde,0xdef01234]**

En se référant au pseudo code d’IDA, on repère que ces opcodes correspondent respectivement aux instructions:

 - sub_12C6(&passwordArray[register2], &passwordArray[register1]);
 - cmp_pass(&passwordArray[register2], &passwordArray[register1]);
 -  ContinueIfcheck(3 * (register2 - 1));

Nous avons donc une transformation opérée sur une partie du pass (4 octets par 4 octets) par la fonction sub_12C6().

Cette partie ainsi transformée est alors comparée via la fonction que j’ai nommé “cmp_pass” et qui agit sur “byte_5068”.

Enfin, la fonction ContinueIfCheck est appelée et va checker le “byte_5068” pour savoir si la comparaison effectuée précédement est correcte ou non et continuer ou arreter l’execution du binaire selon le résultat.
Si la comparaison est fausse, la VM execute les opcodes de fin, à savoir **[0xbcdef012,0xabcdef01]** .

Cependant dans notre fonction de traitement du pass, sub_12C6(), il y des instructions “**div rcx**” en 0x555555555317 et 0x555555555338.
Or, en debuggant un peu, on s’apperçoit que la valeur de RCX change à chaque nouvelle partie du pass traitée.
En breakant et en les relevant on obtient les valeurs suivantes:

**[0x77c7742d, 0x7d61e32d, 0x7b4dbc19, 0x62c26e5f, 0x686493f7]**

Maintenant, on veut récupérer les valeurs auxquelles nos parties de pass transformées sont comparées.
Pour cela nous allons simplement placer un breakpoint en 0x55555555526e
(**cmp edx,eax**), executer en relever le contenu de EAX.
Pour continuer l’execution de la VM et ainsi executer les comparaisons des autres parties du flag malgré un pass totalement faux, il suffit d’entrer la commande “set $rdx = $rax” dans gdb à chaque fois que l’on break ici.

On finit par obtenir ces valeurs:

 **[0x31420fa, 0x2b74da6b, 0x638682bf, 0x5941d721, 0x5ced41bb]**

Nous avons maintenant tout ce qu’il faut pour écrire un script qui nous donnera gentiment le flag ;)

Étape 3: Get the flag !

On connait déjà la première partie du flag: sigsegv{
De plus on sait grace aux arguments passés à read() dans la fonction main() que le pass fait 20 caractères, on a donc finalement un flag de la forme: sigsegv{ABCDEFGHIJK}.

Juste avant on avait vu que l’input est traité par groupes de 4 octets (appelés dans mon script “codon”, #bac_S_SVT_rpz) par la fonction sub_12C6(), executé dans la VM par l’opcode 0xCDEF0123.

L’idée, c’est de réécrire la fonction sub_12c6() grace aux informations obtenues par l’analyse dynamique (les valeurs comparées et les diviseurs) pour bruteforcer les codons du flag dont on ne dispose pas.
En effet, on possède déjà les deux premiers codons (‘sigs’ et ‘egv{’) et le caractère final du dernier codon (’}’), on doit donc bruteforcer 2 groupes de 4 octets + 1 groupe
de 3 octets.
Ainsi, le bruteforce ne devrait pas être trop long ;)

----------------------------------- CUT HERE -----------------------------------

#flag = sigsegv{VM3d_stuff!}

def convert_to_ascii(text):
    return sum(ord(text[byte])<<8*(len(text)-byte-1) for byte in range(len(text)))

def bruteforce(password,codon):
	arrayMod = [0x77c7742d, 0x7d61e32d, 0x7b4dbc19, 0x62c26e5f, 0x686493f7]
	arrayFlag = [0x31420fa, 0x2b74da6b, 0x638682bf, 0x5941d721, 0x5ced41bb]
	v5 = 1
	v4 = 0x10001 # trouvée également grace à l'analyse dynamique
					
	a1 = 1
	passHex = ""

	for i in range(4*a1):
		passHex += password[i]
	v3 = convert_to_ascii(passHex)
	
	while(v4):
		if(v4 & 1):
			v5 = (v3 * v5) % arrayMod[codon]
		v4 >>= 1
		v3 = v3 * v3 % arrayMod[codon]
		if(v5 == arrayFlag[codon]):
			print("FOUND ! "+str(password))
			return 1
	return 0

def main():

	found = 0
	codon = 2

	while codon < 5:
		for a in range(0x20,0x7f):
			for b in range(0x20,0x7f):
				for c in range(0x20,0x7f):
					if(codon == 4):
						password = chr(a)+chr(b)+chr(c)+'}'
						#print(password)
						found = bruteforce(password,codon)
						if(found):
							return 1
					else:
						for d in range(0x20,0x7f):
							password = chr(a)+chr(b)+chr(c)+chr(d)
							#print(password)
							found = bruteforce(password,codon)
							if(found):
								return 1							  
		codon+=1

	return 0

main()

----------------------------------- CUT HERE -----------------------------------

En executant ce petit script, nous obtenons comme flag final: “sigsegv{VM3d_stuff!}”, ce qui nous rapporte 1337 points sur le site des qualifications !
Merci à SIben pour ce challenge très amusant ;)