virtual.1

Name: virtual.1

Author: bagolymadar

URL: https://crackmes.one/crackme/5f3a64df33c5d42a7c667d45

Download: here

Difficulty: 3

Quality: 4.5

Goal: write a key generator

Method: static/dynamic analysis

Tools used: Ghidra, edb, emacs+sly+sbcl

Executable format: ELF

Arch: x86-64

MD5: 037f3db331b417fd8794325a0feccafa

SHA256: 11d27395c11bc12595e219116746fbaf89a2cc825321f4db99fea82f17273c09

Tutorial

Run binary with ./virtual1 and you will be presented with

Fire up ghidra, go to function vmstart and interpret so you can infer basic vm parameters:

1. 0x108 - vm code that we need to decode and interpret
2. 0x230 - 64bit operand1
3. 0x238 - 64bit operand2
4. 0x248 - pc (program counter)
5. 0x250 - username pointer
6. 0x258 - password pointer
7. 0x268 - stack (misinterpreted by ghidra as stdin) - grows downwards

undefined8 vmstart(undefined8 username,undefined8 password)

{
  long lVar1;
  undefined1 *result;
  
  result = &DAT_00104230;
  for (lVar1 = 0xc0; lVar1 != 0; lVar1 = lVar1 + -1) {
    *result = 0;
    result = result + 1;
  }
  DAT_00104268 = &stdin;
  result = &DAT_00104230;
  dat_username = username;
  dat_password = password;
  interpret();
  return *(undefined8 *)(result + 0x10);
}

The interpret function is where we going to spend most of our time. It’s a simple dispatch function that checks opcodes and dispatches appropriate vm function. Every VM function is in charge of advancing or defining new PC. Instructions are variable lengths.

Ghidra decompilation was useful for gathering basic facts about the crackme but for deeper understanding I needed a debugger. My debugger of choice is EDB and it’s only Olly-like debugger on Linux I’m aware of and comfortable using.

So, I started it with edb --stdin ./input.txt --run ./virtual.1 where input.txt contains sample username/password to get me going. I spent a lot of time analyzing functions, taking notes, and all that stuff in debugger, til it became inpractical due to high number of iterations and character checks, so I needed better approach.

I reimplemented the VM and all its functions in Common Lisp for this crackme, and put trace - simple format - in dispatch function. You can find full source code with original comments and insights i discovered throughout this process here. It mimics x86 pointer arithmetics and memory semantics to a certain extent - minus little endian stuff. dump-memory would print vm memory at any point i wanted. A step counter allowed me stop/return from dispatch function whenever needed. Putting all of this together: trace, dispatch control, vm memory inspection - allowed me understand username/password generation logic.

Running vm in LISP is very natural process and it’s just matter of using following instructions

(defparameter *vm*
  (make-initial-vm *username* *password*))


(dispatch *vm*)

It looks like this in case username/password pair is correct

Username/password generation details/constraints:

1. Allowed symbols for username/password are hex digits (0-9, A-F capitalized). Every other symbol won’t pass vm checks and will result in vm halt. One exception to this is fifth password symbol that must be ‘-‘.
2. Username length is defined two first password digits
3. Third and fourth password digit represent popcount sum of username chars and it’s a hexnum (so if popcount is 68 third and forth digit will be 44)
4. Fifth password character is ascii symbol ‘-‘
5. After these conditions are satisfied, crackhash - or how i called it - function kicks in. It starts with a constant seed 0xB7E151628AED2A6A (eulers number), and it iterates total number of username chars. Each iteration it ROLs the constant by username-char-popcount, and depending whether the popcount is odd or even, it will also LOGNOT the char/byte value or just use ascii value (in case it’s even), and XORs the rotated number with that value. That’s the crackhash algo in a nutshell.
6. Endstate hash value we get will be compared against last 16 password chars and if it’s equal - we get a goodboy message.

I simplified it so it’s digestable, you can find more details in my workbook lisp file. I left all comments in the file, some of them are incorrect or false conclusions, but it was part of the learning process so I think it’s valuable to have them there.

Keygen source is here and can be run as script with SBCL common lisp implementation:

chmod +x keygen.lisp
./keygen.lisp

Conclusion

I really enjoyed solving this crackme since it’s fair and entertaining. It has no dirty tricks up its sleeves and does not imply certain knowledge besides a basic understanding of assembly and being curious about RE.

I would recommend it to newcomers to RE who want to solve their first VM based crackme.

Great job by the author.