UTCTF 2020 - IR
category: Reverse Engineering
We found this snippet of code on our employee’s laptop. It looks really scary. Can you figure out what it does?
Challenge file: chal.e
This challenge is about reading LLVM IR (intermediate representation) language, let’s first get some knowledge about LLVM and then dive into the challenge.
LLVM in simple words:
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations (IR) and converts it into object files (machine code).
Each language has a frontend which is the actual compiler that generates the LLVM IR, some of them are:
clang (C / C++), llgo (Go), …
LLVM IR is a low-level programming language (much like assembly) and it provides type safety, low-level operations, flexibility, and the capability of representing “all” high-level languages cleanly and efficiently, one language to rule them all :)
For more about LLVM, see this video: https://www.youtube.com/watch?v=a5-WaD8VV38
Back to the challenge:
I will split the code into multiple sections to understand it more easily, I’ve removed some of the metadata like the “aligns” and “dbgs” for cleaner code.
@check = dso_local global [64 x i8] c"\03\12\1A\17\0A\EC\F2\14\0E\05\03\1D\19\0E\02\0A\1F\07\0C\01\17\06\0C\0A\19\13\0A\16\1C\18\08\07\1A\03\1D\1C\11\0B\F3\87\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\05"
@MAX_SIZE = dso_local global i32 64
First we see two global variables, check which is an array of 64 bytes with constant values (used for comparing with the input later) and MAX_SIZE which is a 32 bit integer (i32) and its value is set to 64.
define dso_local i32 @_Z7reversePc(i8*) #0 {
%2 = alloca i32 ! define %2 as int
%3 = alloca i8* ! define %3 as char*
%4 = alloca i32 ! define %4 as int
%5 = alloca i32 ! define %5 as int
%6 = alloca i32 ! define %6 as int
store i8* %0, i8** %3 ! %3 = %0 ==> input
store i32 0, i32* %4 ! %4 = 0
br label %7 ! jmp to %7
Next there is a function definition with the name _Z7reversePc which takes one argument of type char* (i8*) “which acts as the input” and it’s stored in variable %0.
Then five local variables are defined (%2 to %6), the input argument is stored in %3 and 0 is stored in %4, then we branch to label %7.
- Variables in LLVM IR start with %.
- LLVM IR has an infinite number of variables.
- Data types are very similar to high level languages: i32 for 32 bit integer, i8* for 8 bit array (char array), and so on.
7:
%8 = load i32, i32* %4 ! %8 = %4 ==> counter
%9 = load i32, i32* @MAX_SIZE ! %9 = 64 ==> MAX_SIZE
%10 = icmp slt i32 %8, %9 ! if(%8 < %9):
br i1 %10, label %11, label %23 ! jmp to %11 else: jmp to %23 ==> end loop
11:
! get input[i]
%12 = load i8*, i8** %3 ! %12 = %3 ==> input
%13 = load i32, i32* %4 ! %13 = %4 ==> counter
%14 = sext i32 %13 to i64 ! %14 = sign_extend(%13) ==> compiler stuff
%15 = getelementptr inbounds i8, i8* %12, i64 %14 ! %15 = get_memory(%12[%14])
%16 = load i8, i8* %15 ! %16 = *(%15) ==> dereference
%17 = sext i8 %16 to i32 ! 17 = sign_extend(%16) ==> compiler stuff
%18 = add nsw i32 %17, 5 ! %18 += %17 + 5
%19 = trunc i32 %18 to i8 ! %19 = truncate(%18) ==> compiler stuff
store i8 %19, i8* %15 ! %15 = %19 ==> store the result back
br label %20 ! %jmp to %20
20:
%21 = load i32, i32* %4 ! %21 = %4 ==> counter
%22 = add nsw i32 %21, 1 ! %22 = %21 + 1
store i32 %22, i32* %4 ! %4 = %22
br label %7 ! jmp back to %7
This section loops through the input stored at %3 with a counter stored at %4 from 0 to MAX_SIZE. At each iteration, it gets the character at input[counter] using getelementptr and adds 5 to it.
- Some keywords like sext and trunc are just compiler generated code (may be for optimization) so ignore them here.
- LLVM IR variables are immutable (can’t be changed), that’s why there is many variables for such simple operations.
The C equivalent to this is:
for(int i=0; i<MAX_SIZE; i++)
input[i] += 5
23:
store i32 0, i32* %5 ! %5 = 0 ==> counter
br label %24 ! jmp to %24
24:
%25 = load i32, i32* %5 ! %25 = %5 ==> counter
%26 = load i32, i32* @MAX_SIZE ! %26 = 64 ==> MAX_SIZE
%27 = sub nsw i32 %26, 1 ! %27 = %26 - 1 ==> MAX_SIZE-1
%28 = icmp slt i32 %25, %27 ! if(%25 < %27)
br i1 %28, label %29, label %48 ! jmp to %29 else: jmp to %48 ==> end loop
29:
! get input[i+1]
%30 = load i8*, i8** %3 ! %30 = %i3 ==> input
%31 = load i32, i32* %5 ! %31 = %5 ==> counter
%32 = add nsw i32 %31, 1 ! %32 = %31 + 1 ==> counter+1
%33 = sext i32 %32 to i64 ! %33 = sign_extend(%32) ==> compiler stuff
%34 = getelementptr inbounds i8, i8* %30, i64 %33 !%34 = get_memory(%30[%33])
%35 = load i8, i8* %34 ! %35 = *(%34) ==> dereference
%36 = sext i8 %35 to i32 ! %36 = sign_extend(%35) ==> compiler stuff
! get input[i]
%37 = load i8*, i8** %3 ! %37 = %i3 ==> input
%38 = load i32, i32* %5 ! %38 = %5 ==> counter
%39 = sext i32 %38 to i64 ! %39 = sign_extend(%38) ==> compiler stuff
%40 = getelementptr inbounds i8, i8* %37, i64 %39 ! %40 = get_memory(%37[%39])
%41 = load i8, i8* %40 ! %41 = *(%40) ==> dereference
%42 = sext i8 %41 to i32 ! %42 = sign_extend(%41) ==> compiler stuff
%43 = xor i32 %42, %36 ! %43 = %42 ^ %36 ==> input[i] ^ input[i+1]
%44 = trunc i32 %43 to i8 ! %44 = truncate(%43) ==> compiler stuff
store i8 %44, i8* %40 ! %40 = %44 ==> store the result back
br label %45 ! jmp to %45
45:
%46 = load i32, i32* %5 ! %46 = %5 ==> counter
%47 = add nsw i32 %46, 1 ! %47 = %46 + 1
store i32 %47, i32* %5 ! %5 = %47
br label %24 ! jmp back to %24
Here we can see another loop through the input which XORs each byte of the input with it’s adjacent one.
The C equivalent to this is:
for(int i=0; i<MAX_SIZE-1; i++)
input[i] ^= input[i+1]
48:
store i32 0, i32* %6 ! %6 = 0 ==> counter
br label %49 ! jmp to %49
49:
%50 = load i32, i32* %6 ! %50 = %6 ==> counter
%51 = load i32, i32* @MAX_SIZE ! %51 = 64 ==> MAX_SIZE
%52 = icmp slt i32 %50, %51 ! if(%50 < %51)
br i1 %52, label %53, label %71 ! jmp to %53 else: jmp to %71 ==> end loop
53:
! get check[i]
%54 = load i32, i32* %6 ! %54 = %6 ==> counter
%55 = sext i32 %54 to i64 ! %55 = sign_extend(%54) ==> compiler stuff
%56 = getelementptr inbounds [64 x i8], [64 x i8]* @check, i64 0, i64 %55 ! get_memory(%check[%55])
%57 = load i8, i8* %56 ! %57 = *(%56) ==> dereference
%58 = zext i8 %57 to i32 ! %58 = zero_extend(%57) ==> compiler stuff
! get input[i]
%59 = load i8*, i8** %3 ! %59 = %i3 ==> input
%60 = load i32, i32* %6 ! %60 = %6 ==> counter
%61 = sext i32 %60 to i64 ! %61 = sign_extend(%60) ==> compiler stuff
%62 = getelementptr inbounds i8, i8* %59, i64 %61 ! %62 = get_memory(%59[%61])
%63 = load i8, i8* %62 ! %63 = *(%62) ==> dereference
%64 = zext i8 %63 to i32 ! %64 = zero_extend(%63) ==> compiler stuff
%65 = icmp ne i32 %58, %64 ! if(%58 != %64) ==> check[i] != input[i]
br i1 %65, label %66, label %67 ! jmp to %66 ==> end loop else: jmp to %67
66:
store i32 0, i32* %2 ! %2 = 0 ==> return value
br label %72 ! jmp to %72
67:
br label %68 ! jmp to %68
68:
%69 = load i32, i32* %6 ! %69 = %6 ==> counter
%70 = add nsw i32 %69, 1 ! %70 = %69 + 1
store i32 %70, i32* %6 ! %6 = %70
br label %49 ! jmp back to %49
71:
store i32 1, i32* %2 ! %2 = 1 ==> return value
br label %72 ! jmp to %72
72:
%73 = load i32, i32* %2 ! %73 = %2
ret i32 %73 ! return %73
}
The final block just compares the modified input array with the check array to test for equality.
The C equivalent to this is:
for(int i=0; i<MAX_SIZE; i++)
if(check[i] != input[i])
return 0;
return 1;
Solution:
As you can see the final algorithm is so simple, we can reverse it and eventually get the flag :)
check = "\x03\x12\x1A\x17\x0A\xEC\xF2\x14\x0E\x05\x03\x1D\x19\x0E\x02\x0A\x1F\x07\x0C\x01\x17\x06\x0C\x0A\x19\x13\x0A\x16\x1C\x18\x08\x07\x1A\x03\x1D\x1C\x11\x0B\xF3\x87\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x05"
lcheck = [ord(i) for i in check]
for i in range(len(lcheck)-1, 0, -1):
lcheck[i-1] = lcheck[i-1] ^ lcheck[i]
flag = "".join([chr(i-5) for i in lcheck])
print(flag)
The flag is: utflag{machine_agnostic_ir_is_wonderful}