PicoCTF 2018 Writeup: Reversing
Oct 13, 2018 08:56 · 4069 words · 20 minute read
Reversing Warmup 1
Problem
Throughout your journey you will have to run many programs. Can you navigate to /problems/reversing-warmup-1_0_f99f89de33522c93964bdec49fb2b838 on the shell server and run this program to retreive the flag?
Solution
The problem run is known as a ELF binary. It is the most common program format on Linux. Here are the steps to run the program:
alanc@pico-2018-shell-2:~$ cd /problems/reversing-warmup-1_0_f99f89de33522c93964bdec49fb2b838
alanc@pico-2018-shell-2:/problems/reversing-warmup-1_0_f99f89de33522c93964bdec49fb2b838$ ls
run
alanc@pico-2018-shell-2:/problems/reversing-warmup-1_0_f99f89de33522c93964bdec49fb2b838$ ./run
picoCTF{welc0m3_t0_r3VeRs1nG}
flag: picoCTF{welc0m3_t0_r3VeRs1nG}
Reversing Warmup 2
Problem
Can you decode the following string dGg0dF93NHNfczFtcEwz from base64 format to ASCII?
Solution
Base64 is a common encoding format. You can read more about the distinction between encoding and encryption here.
To decoee the string, we can use python, a handy programming language for hackers:
Python 2.7.15 (default, Jun 17 2018, 12:51:03)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 'dGg0dF93NHNfczFtcEwz'.decode('base64')
'th4t_w4s_s1mpL3'
flag: picoCTF{th4t_w4s_s1mpL3}
assembly-0
Problem
What does asm0(0xb6,0xc6) return? Submit the flag as a hexadecimal value (starting with ‘0x’). NOTE: Your submission for this question will NOT be in the normal flag format. Source located in the directory at /problems/assembly-0_0_5a220faedfaf4fbf26e6771960d4a359.
Solution
Read about assembly language or assembly code here. Also, you can watch this youtube series which is helpful.
Let’s take a look at the assembly code:
.intel_syntax noprefix
.bits 32
.global asm0
asm0:
push ebp
mov ebp,esp
mov eax,DWORD PTR [ebp+0x8]
mov ebx,DWORD PTR [ebp+0xc]
mov eax,ebx
mov esp,ebp
pop ebp
ret
As you can see, there’s a function named asm0 that is being exported by the line .global asm0, and the content of the function is right below the asm0: label. We know that the function is called with the argument of 0xb6 and 0xc6 which are at ebp+0x8 and ebp+0xc respectively.
By converting the assembly code to preduo-code, we can the logic of the function:
eax = arg1
ebx = arg2
eax = ebx
Because we know that an assembly function always returns the value than is in the eax register, the asm0 should always return the second argument passed to it; therefore, the return value is 0xc6.
If you find this explanation hard to understand or you want more practice with reading assembly code, take a look at microcorruption which is a great place to get started with reverse engineering. Also, you can find my writeup for microcorruption here
Flag: 0xc6
assembly-1
Problem
What does asm1(0x76) return? Submit the flag as a hexadecimal value (starting with ‘0x’). NOTE: Your submission for this question will NOT be in the normal flag format. Source located in the directory at /problems/assembly-1_0_cfb59ef3b257335ee403035a6e42c2ed.
Solution
This problem is similar to the last one. Let’s take a look at the code:
.intel_syntax noprefix
.bits 32
.global asm1
asm1:
push ebp
mov ebp,esp
cmp DWORD PTR [ebp+0x8],0x98
jg part_a
cmp DWORD PTR [ebp+0x8],0x8
jne part_b
mov eax,DWORD PTR [ebp+0x8]
add eax,0x3
jmp part_d
part_a:
cmp DWORD PTR [ebp+0x8],0x16
jne part_c
mov eax,DWORD PTR [ebp+0x8]
sub eax,0x3
jmp part_d
part_b:
mov eax,DWORD PTR [ebp+0x8]
sub eax,0x3
jmp part_d
cmp DWORD PTR [ebp+0x8],0xbc
jne part_c
mov eax,DWORD PTR [ebp+0x8]
sub eax,0x3
jmp part_d
part_c:
mov eax,DWORD PTR [ebp+0x8]
add eax,0x3
part_d:
pop ebp
ret
For this challenge, control flow is being introduced. We know than [ebp+0x8] is the argument that we passed in (0x76 in this case). Because 0x76 is not larger than 0x98, we will not follow the first jg (jumo greater than) to part_a. For the second comparison, because 0x76 does not equal 0x8, we are going to jump to part_b (jne means jump not equal). In part_b, the argument is loaded into eax and 3 is subtracted from it. After that, the function returns; therefore, we just have to take 0x76 and subtract 0x3 from it to get the flag (0x73).
flag: 0x73
be-quick-or-be-dead-1
Problem
You find this when searching for some music, which leads you to be-quick-or-be-dead-1. Can you run it fast enough? You can also find the executable in /problems/be-quick-or-be-dead-1_3_aeb48854203a88fb1da963f41ae06a1c.
Solution
Playing around with the program, you can see that it will exit after a while before the key is calculated. Now, let’s take a look at the code that competes the key with radare2:
[0x004005a0]> aaaa
[0x00400827]> pdf @ sym.calculate_key
/ (fcn) sym.calculate_key 29
| sym.calculate_key ();
| ; var unsigned int local_4h @ rbp-0x4
| ; CALL XREF from sym.get_key (0x4007a9)
| 0x00400706 55 push rbp
| 0x00400707 4889e5 mov rbp, rsp
| 0x0040070a c745fc3c7ed4. mov dword [local_4h], 0x6fd47e3c
| ; CODE XREF from sym.calculate_key (0x40071c)
| .-> 0x00400711 8345fc01 add dword [local_4h], 1
| : 0x00400715 817dfc78fca8. cmp dword [local_4h], 0xdfa8fc78 ; [0xdfa8fc78:4]=-1
| `=< 0x0040071c 75f3 jne 0x400711
| 0x0040071e 8b45fc mov eax, dword [local_4h]
| 0x00400721 5d pop rbp
\ 0x00400722 c3 ret
As you can see, the function starts witht the value 0x6fd47e3c and decrements it each time until it is equal to 0xdfa8fc78. To speed up this function we can change the initial value to the final value minus 1. Here is how the patching is done in radare2:
[0x00400827]> oo+
[0x00400827]> s 0x0040070a
[0x0040070a]> pd 1
| 0x0040070a c745fc3c7ed4. mov dword [local_4h], 0x6fd47e3c
[0x0040070a]> wa mov dword [rbp-0x4], 0xdfa8fc77
Written 7 byte(s) (mov dword [rbp-0x4], 0xdfa8fc77) = wx c745fc77fca8df
[0x0040070a]> q
Now if you run the program, it will happily print out the flag.
flag: picoCTF{why_bother_doing_unnecessary_computation_27f28e71}
quackme
Problem
Can you deal with the Duck Web? Get us the flag from this program. You can also find the program in /problems/quackme_1_374d85dc071ada50a08b36597288bcfd.
Solution
Let’s first take a look at the core function of the program, do_magic:
int do_magic()
{
int result; // eax
int v1; // [esp+Ch] [ebp-1Ch]
int i; // [esp+10h] [ebp-18h]
char *s; // [esp+14h] [ebp-14h]
signed int v4; // [esp+18h] [ebp-10h]
void *v5; // [esp+1Ch] [ebp-Ch]
s = (char *)read_input();
v4 = strlen(s);
v5 = malloc(v4 + 1);
if ( !v5 )
{
puts("malloc() returned NULL. Out of Memory\n");
exit(-1);
}
memset(v5, 0, v4 + 1);
v1 = 0;
for ( i = 0; ; ++i )
{
result = i;
if ( i >= v4 )
break;
if ( greetingMessage[i] == (*(_BYTE *)(i + 0x8048858) ^ (unsigned __int8)s[i]) )
++v1;
if ( v1 == 25 )
return puts("You are winner!");
}
return result;
}
As you can see, the input when xored with the data at the offset of 0x8048858 should be equal to the greeting message, in order for the program to print out the flag. We can quickly extract the data at that offset and write a python script to solve the challenge:
$ r2 main
-- What has been executed cannot be unexecuted
[0x080484e0]> ps @ 0x8048858
)\x06\x16O+50\x1eQ\x1b[\x14K\x08]+S\x10TQCM\\T]
import string
message = "You have now entered the Duck Web, and you're in for a honkin' good time.\nCan you figure out my trick?"
key = ')\x06\x16O+50\x1eQ\x1b[\x14K\x08]+S\x10TQCM\T]' # data extracted from the binary
output = ''
for i in range(len(key)):
v = chr(ord(key[i])^ord(message[i]))
if v in string.printable:
output += v
else:
output += '_'
print output # picoCTF{qu4ckm3_6b15c941}
flag: picoCTF{qu4ckm3_6b15c941}
assembly-2
Problem
What does asm2(0x8,0x21) return? Submit the flag as a hexadecimal value (starting with ‘0x’). NOTE: Your submission for this question will NOT be in the normal flag format. Source located in the directory at /problems/assembly-2_1_c1900e7d33989b0191c51ef927b24f37.
Solution
This problem is an introduction to loops in assembly.
.intel_syntax noprefix
.bits 32
.global asm2
; asm2(0x8,0x21)
; flag: 0x78
asm2:
push ebp
mov ebp,esp
sub esp,0x10
mov eax,DWORD PTR [ebp+0xc]
mov DWORD PTR [ebp-0x4],eax ; temp = 0x21
mov eax,DWORD PTR [ebp+0x8]
mov DWORD PTR [ebp-0x8],eax ; temp2 = 0x8
jmp part_b
part_a:
add DWORD PTR [ebp-0x4],0x1 ; temp += 1
add DWORD PTR [ebp+0x8],0xa9 ; arg1 += 0xa9
part_b:
cmp DWORD PTR [ebp+0x8],0x3923
jle part_a
mov eax,DWORD PTR [ebp-0x4]
mov esp,ebp
pop ebp
ret
As you can see, arg1 is incremented by 0xa9 each time until it reaches 0x3923 while temp increments by 1 each time; therefore, the flag is 0x21 + ((0x3923-0x8)/0xa9+1) which is 0x78.
flag: 0x78
be-quick-or-be-dead-2
Problem
As you enjoy this music even more, another executable be-quick-or-be-dead-2 shows up. Can you run this fast enough too? You can also find the executable in /problems/be-quick-or-be-dead-2_1_0e5d7acd1fd33f2f0f6e215637a8d3bd.
Solution
This challenge is similar to be-quick-or-be-dead-1 where we have to make the sym.calculate_key function run faster. Let’s take a look at the functions first:
__int64 calculate_key()
{
return fib(1067LL);
}
__int64 __fastcall fib(unsigned int a1)
{
int v1; // ebx
unsigned int v3; // [rsp+1Ch] [rbp-14h]
if ( a1 > 1 )
{
v1 = fib(a1 - 1);
v3 = v1 + (unsigned __int64)fib(a1 - 2);
}
else
{
v3 = a1;
}
return v3;
}
As you can see, it is a fibonacci algorithm in assembly. Now, we can just pre-compute the 1067th value of the fibonacci sequence and substitute in the result at runtime.
Step one, we need to find the 1067th value of the fibonacci sequence while keeping in mind that it is a unsigned int:
a = 1
b = 1
for i in range(1, 0x42b):
a, b = b, a+b
if a >= 4294967296:
a -= 4294967296
if b >= 4294967296:
b -= 4294967296
print hex(a) # 0x2e8e4d99
Now, we have to pass in this value at runtime and skip the computing phase. We can do this by changing both the eax and rip register. Here is the process being done with radare2:
[0x004005a0]> aaaa
[0x004005a0]> ood
[0x7f797b9f1090]> s sym.calculate_key
[0x0040074b]> pdf
/ (fcn) sym.calculate_key 16
| sym.calculate_key ();
| ; CALL XREF from sym.get_key (0x4007e1)
| 0x0040074b 55 push rbp
| 0x0040074c 4889e5 mov rbp, rsp
| 0x0040074f bf2b040000 mov edi, 0x42b ; 1067
| 0x00400754 e8adffffff call sym.fib
| 0x00400759 5d pop rbp
\ 0x0040075a c3 ret
[0x0040074b]> db 0x0040074b
[0x7f5ca266c090]> dc
Be Quick Or Be Dead 2
=====================
Calculating key...
hit breakpoint at: 40074b
[0x0040074b]> dr rip=0x0040075a
0x0040074b ->0x0040075a
[0x0040074b]> dr eax=0x2e8e4d99
0x00000000 ->0x2e8e4d99
[0x0040074b]> dc
child stopped with signal 14
[+] SIGNAL 14 errno=0 addr=0x00000000 code=128 ret=0
Done calculating key
Printing flag:
picoCTF{the_fibonacci_sequence_can_be_done_fast_ec58967b}
[+] signal 14 aka SIGALRM received 0
flag: flag: picoCTF{the_fibonacci_sequence_can_be_done_fast_ec58967b}
be-quick-or-be-dead-3
Problem
As the song draws closer to the end, another executable be-quick-or-be-dead-3 suddenly pops up. This one requires even faster machines. Can you run it fast enough too? You can also find the executable in /problems/be-quick-or-be-dead-3_1_036263621db6b07c874d55f1e0bba59d.
Solution
Following the same theme as the first two problems, we still have to speed up the sym.calculate_key function. Let’s take a look at the function:
__int64 calculate_key()
{
return calc(0x186B5u);
}
__int64 __fastcall calc(unsigned int a1)
{
int v1; // ebx
int v2; // ebx
int v3; // er12
int v4; // ebx
unsigned int v6; // [rsp+1Ch] [rbp-14h]
if ( a1 > 4 )
{
v1 = calc(a1 - 1);
v2 = v1 - (unsigned __int64)calc(a1 - 2);
v3 = calc(a1 - 3);
v4 = v3 - (unsigned __int64)calc(a1 - 4) + v2;
v6 = v4 + 4660 * (unsigned __int64)calc(a1 - 5);
}
else
{
v6 = a1 * a1 + 9029;
}
return v6;
}
As you can see, this time the sym.calculate_key is using a custom algorithm that is also recursive. Let’s try to pre-compute the value again with python. To make the code run faster and prevent stack overflow, we are going to compute and store the return values for calc which is a common tactics in dynamic programming:
import sys
l = 100030
mem = [None]*l
def calc(a1):
if a1 < l and mem[a1] != None:
return mem[a1]
if a1 > 4:
v1 = calc(a1 - 1)
v2 = v1 - calc(a1 - 2)
v3 = calc(a1 - 3)
v4 = v3 - calc(a1 - 4) + v2
v6 = v4 + 4660 * calc(a1 - 5)
else:
v6 = a1 * a1 + 9029
if v6 >= 4294967296:
v6 = v6 % 4294967296
while v6 < 0:
v6 += 4294967296
if a1 < l and mem[a1] == None:
mem[a1] = v6
return v6
for i in range(l):
calc(i)
print calc(0x186B5) # 0x221d8eea
Now with the output value, we can do the same thing as we did for be-quick-or-be-dead-2 and substitute in the values at runtime:
[0x004005a0]> aaaa
[0x004005a0]> pdf @ sym.calculate_key
/ (fcn) sym.calculate_key 16
| sym.calculate_key ();
| ; CALL XREF from sym.get_key (0x400828)
| 0x00400792 55 push rbp
| 0x00400793 4889e5 mov rbp, rsp
| 0x00400796 bfb5860100 mov edi, 0x186b5
| 0x0040079b e866ffffff call sym.calc
| 0x004007a0 5d pop rbp
\ 0x004007a1 c3 ret
[0x004005a0]> ood
[0x7f977ebb1090]> db 0x00400792
[0x7f977ebb1090]> dc
Be Quick Or Be Dead 3
=====================
Calculating key...
hit breakpoint at: 400792
[0x00400792]> dr rip=0x004007a1
0x00400792 ->0x004007a1
[0x00400792]> dr eax=0x221d8eea
0x00000000 ->0x221d8eea
[0x00400792]> dc
child stopped with signal 14
[+] SIGNAL 14 errno=0 addr=0x00000000 code=128 ret=0
Done calculating key
Printing flag:
picoCTF{dynamic_pr0gramming_ftw_a0b0b7f8}
[+] signal 14 aka SIGALRM received 0
flag: picoCTF{dynamic_pr0gramming_ftw_a0b0b7f8}
quackme up
Problem
The duck puns continue. Can you crack, I mean quack this program as well? You can find the program in /problems/quackme-up_4_5cc9019c8499d6d124cd8e8109a0f95b on the shell server.
Solution
For this challenge, you have to reverse the encrypt function and decrypt the flag. Let’s first look at the encrypt function:
int __cdecl encrypt(char *s)
{
char v1; // al
signed int i; // [esp+8h] [ebp-10h]
signed int v4; // [esp+Ch] [ebp-Ch]
v4 = strlen(s);
for ( i = 0; i < v4; ++i )
{
v1 = rol4(s[i]);
s[i] = ror8((char)(v1 ^ 0x16));
}
return v4;
}
As you can see, the function performs two actions: rol4 and ror8. To decrypt it, we just have to go in the reverse order. There is the decrypt method in python:
cipher = '11 80 20 E0 22 53 72 A1 01 41 55 20 A0 C0 25 E3 35 40 55 30 85 55 70 20 C1'.replace(' ', '').decode('hex')
# https://gist.github.com/c633/a7a5cde5ce1b679d3c0a
rol = lambda val, r_bits, max_bits: \
(val << r_bits%max_bits) & (2**max_bits-1) | \
((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))
ror = lambda val, r_bits, max_bits: \
((val & (2**max_bits-1)) >> r_bits%max_bits) | \
(val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))
output = ''
for e in cipher:
output += chr(ror((rol(ord(e), 8, 8) ^ 0x16), 4, 8))
print output
flag: picoCTF{qu4ckm3_2e4b94fc}
Radix’s Terminal
Problem
Can you find the password to Radix’s login? You can also find the executable in /problems/radix-s-terminal_0_b6b476e9952f39511155a2e64fb75248?
Solution
The hint is super helpful for this challenge. By reversing the program, we can see that it’s just an implementation of the base64 encoding in assembly.
Now knowing the encoding algorithm, we can decode the string quite quickly:
>>> 'cGljb0NURntiQXNFXzY0X2VOQ29EaU5nX2lTX0VBc1lfNDE3OTk0NTF9'.decode('base64')
'picoCTF{bAsE_64_eNCoDiNg_iS_EAsY_41799451}'
flag: picoCTF{bAsE_64_eNCoDiNg_iS_EAsY_41799451}
assembly-3
Problem
What does asm3(0xb5e8e971,0xc6b58a95,0xe20737e9) return? Submit the flag as a hexadecimal value (starting with ‘0x’). NOTE: Your submission for this question will NOT be in the normal flag format. Source located in the directory at /problems/assembly-3_3_bfab45ee7af9befc86795220ffa362f4.
Solution
For this challenge, you are suppose to learn about the different size accessors in assembly.
However, because I am tired at this point, I decided to let a computer do this one for me.
I used this assembly emulator for python called unicorn, and here is my code:
from __future__ import print_function
from unicorn import *
from unicorn.x86_const import *
from pwn import *
X86_CODE32 = asm('mov eax, 0x19; xor al, al; mov ah, BYTE PTR [ebp+0xa]; sal ax, 0x10; sub al, BYTE PTR [ebp+0xd]; add ah, BYTE PTR [ebp+0xc]; xor ax, WORD PTR [ebp+0x12]', arch = 'i386', os = 'linux')
ADDRESS = 0x1000000
STACK = 0x2000000
print("Emulate i386 code")
try:
mu = Uc(UC_ARCH_X86, UC_MODE_32)
mu.mem_map(ADDRESS, 2 * 1024 * 1024)
mu.mem_map(STACK, 2 * 1024 * 1024)
mu.mem_write(ADDRESS, X86_CODE32)
mu.mem_write(STACK, '\x0a\x0a\x0a\x0a\x0a\x0a\x0a\x0a'+p32(0xb5e8e971)+p32(0xc6b58a95)+p32(0xe20737e9))
mu.reg_write(UC_X86_REG_EBP, STACK)
mu.emu_start(ADDRESS, ADDRESS + len(X86_CODE32))
print("Emulation done. Below is the CPU context")
r_eax = mu.reg_read(UC_X86_REG_EAX)
r_ebx = mu.reg_read(UC_X86_REG_EBX)
print(">>> EAX = 0x%x" % r_eax) # 0x7771
except UcError as e:
print("ERROR: %s" % e)
flag: 0x7771
keygen-me-1
Problem
Can you generate a valid product key for the validation program in /problems/keygen-me-1_1_8eb35cc7858ff1d2f55d30e5428f30a7
Solution
Let’s start by looking at the main function:
int __cdecl main(int argc, const char **argv, const char **envp)
{
int result; // eax
setvbuf(_bss_start, 0, 2, 0);
if ( argc > 1 )
{
if ( (unsigned __int8)check_valid_key((char *)argv[1]) )// 16 char of uppercase letters or numbers
{
if ( validate_key((char *)argv[1]) )
{
printf("Product Activated Successfully: ");
print_flag(&argc);
result = 0;
}
else
{
puts("INVALID Product Key.");
result = -1;
}
}
else
{
puts("Please Provide a VALID 16 byte Product Key.");
result = -1;
}
}
else
{
puts("Usage: ./activate <PRODUCT_KEY>");
result = -1;
}
return result;
}
As you can see, we need to input a 16 byte key that will make check_valid_key return true. Let’s look at check_valid_key then:
signed int __cdecl check_valid_key(char *a1)
{
signed int result; // eax
char v2; // [esp+Bh] [ebp-5h]
int v3; // [esp+Ch] [ebp-4h]
if ( !a1 )
return 0;
v2 = *a1;
v3 = 0;
while ( v2 )
{
if ( !(unsigned __int8)check_valid_char(v2) )
return 0;
v2 = a1[++v3];
}
if ( v3 == 16 )
result = 16;
else
result = 0;
return result;
}
As you can see, it is a pretty easy algorithm. I then translated the function into python:
def isValid(key):
s = 0
for i in range(len(key)-1):
s += (o(key[i])+1)*(i+1)
print s%0x24
return s % 0x24 == o(key[len(key)-1])
def o(c):
v = ord(c)
if v > 0x2f and v <= 0x39:
return v-0x30
if v <= 0x40 or v > 0x5a:
print 'wrong'
exit()
return v - 0x37
Now it is just about tinkering with the function to get a valid key. In the end, I land on this:
key = 'Z'*14+'A'+'L'
print isValid(key) # True
print key # ZZZZZZZZZZZZZZAL
After this, you just have to input the key to get the flag.
flag: picoCTF{k3yg3n5_4r3_s0_s1mp13_3718231394}
assembly-4
Problem
Can you find the flag using the following assembly source? WARNING: It is VERY long…
Solution
Because the source code is so long this time, it becomes easier to just build and run the code compared to read it.
The .nasm extension reveals that it is a nasm assembly file.
Here are the step to build and run it:
$ nasm -f elf32 comp.nasm
$ gcc -m32 comp.o -o comp
$ ./comp
picoCTF{1_h0p3_y0u_c0mP1l3d_tH15_3205858729}
flag: picoCTF{1_h0p3_y0u_c0mP1l3d_tH15_3205858729}
special-pw
Problem
Can you figure out the right argument to this program to login? We couldn’t manage to get a copy of the binary but we did manage to dump some machine code and memory from the running process.
Solution
Again, it is totally possible to reverse the assembly code by hand; however, I am lazy…
Because I want tools such as radare2 to help me view the code, I need to first build the assembly (remember to remove the memory dump at the end first):
$ gcc -m32 -c original.S -o original.o
$ gcc -m32 ./original.o -o original
$ chmod +x ./original
Now with a proper elf binary, I can load up the binary in any tool that I prefer. Here is the main function:
int __cdecl main(int argc, const char **argv, const char **envp)
{
char *character; // ST0C_4
signed int ref; // [esp+0h] [ebp-10h]
int length; // [esp+4h] [ebp-Ch]
int counter; // [esp+8h] [ebp-8h]
const char *i; // [esp+Ch] [ebp-4h]
const char *input; // [esp+Ch] [ebp-4h]
length = 0;
for ( i = argv[1]; *i; ++i )
++length;
for ( counter = 0; length - 3 > counter; ++counter )
{
character = (char *)&argv[1][counter];
*character ^= 0xDEu;
*(_WORD *)character = __ROR2__(*(_WORD *)character, 13);
*(_DWORD *)character = __ROL4__(*(_DWORD *)character, 15);
}
input = argv[1];
for ( ref = 56212325; *(_BYTE *)ref; ++ref )
{
if ( *input != *(_BYTE *)ref )
return 0;
++input;
}
return argv[1][ref - 0x359BB65] == 0;
}
Much better. Now, I have to implement the decryption algorithm in python:
from struct import unpack, pack
# https://gist.github.com/c633/a7a5cde5ce1b679d3c0a
rol = lambda val, r_bits, max_bits: \
(val << r_bits%max_bits) & (2**max_bits-1) | \
((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))
ror = lambda val, r_bits, max_bits: \
((val & (2**max_bits-1)) >> r_bits%max_bits) | \
(val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))
data = 'b1d3324cfce6ef5eede466cd57f5e17fcd7f55f6e964e7c97f75e954e64df779fcfc5171f93e18d900'.decode('hex')
data = data[:-1]
for i in range(len(data)-3-1, -1, -1):
v, = unpack('<I', data[i:i+4])
data = data[:i] + pack('<I', ror(v, 15, 4*8)) + data[i+4:]
v, = unpack('<H', data[i:i+2])
data = data[:i] + pack('<H', rol(v, 13, 2*8)) + data[i+2:]
v, = unpack('<B', data[i:i+1])
data = data[:i] + pack('<B', v ^ 0xde) + data[i+1:]
print data # picoCTF{gEt_y0Ur_sH1fT5_r1gHt_0cb381c60}
One thing to note in the code above is that the null byte at the end have to be removed. Also, the endianness have to be correct.
flag: picoCTF{gEt_y0Ur_sH1fT5_r1gHt_0cb381c60}
keygen-me-2
Problem
The software has been updated. Can you find us a new product key for the program in /problems/keygen-me-2_0_ac2a45bc27456d666f2bbb6921829203
Solution
This time the validate_key function is a lot more complex:
_BOOL4 __cdecl validate_key(char *key)
{
strlen(key);
return key_constraint_01(key)
&& key_constraint_02((int)key)
&& key_constraint_03((unsigned __int8 *)key)
&& key_constraint_04((unsigned __int8 *)key)
&& key_constraint_05((unsigned __int8 *)key)
&& key_constraint_06((unsigned __int8 *)key)
&& key_constraint_07((unsigned __int8 *)key)
&& key_constraint_08((unsigned __int8 *)key)
&& key_constraint_09((unsigned __int8 *)key)
&& key_constraint_10((unsigned __int8 *)key)
&& key_constraint_11((unsigned __int8 *)key)
&& key_constraint_12((unsigned __int8 *)key);
}
As you can see, 12 different constraints have to be met. This makes the process of generating a valid key by hand basicly impossible. This is when z3 prover comes in. z3 is a SAT solver that outputs possible inputs that meets certain constraints. We can easily use z3 with python:
from z3 import *
def m(a, b):
return If(a % b >= 0,
a % b,
a % b + b)
s = Solver()
v = []
for i in range(16):
e = Int('v'+str(i))
v.append(e)
s.add(e >= 0)
s.add(e <= 35)
s.add(m(v[0] + v[1], 36) == 14)
s.add(m(v[2] + v[3], 36) == 24)
s.add(m(v[2] - v[0], 36) == 6)
s.add(m(v[1] + v[3] + v[5], 36) == 4)
s.add(m(v[2] + v[4] + v[6], 36) == 13)
s.add(m(v[3] + v[4] + v[5], 36) == 22)
s.add(m(v[6] + v[8] + v[10], 36) == 31)
s.add(m(v[1] + v[4] + v[7], 36) == 7)
s.add(m(v[9] + v[12] + v[15], 36) == 20)
s.add(m(v[13] + v[14] + v[15], 36) == 12)
s.add(m(v[8] + v[9] + v[10], 36) == 27)
s.add(m(v[7] + v[12] + v[13], 36) == 23)
# print(s.check())
# m = s.model()
# print m
values = [31, 19, 1, 23, 1, 34, 11, 23, 8, 7, 12, 0, 16, 20, 31, 33]
output = ''
for i in range(0, 16):
v = values[i]
print v
if v < 10:
output += chr(v+0x30)
else:
output += chr(v+0x37)
print output # VJ1N1YBN87C0GKVX
Using this script, we can generate a valid key, and by inputing the key, we are able to obtain the flag.
flag: picoCTF{c0n5tr41nt_50lv1nG_15_W4y_f45t3r_783243818}
circuit123
Problem
Can you crack the key to decrypt map2 for us? The key to map1 is 11443513758266689915.
Solution
Similar to keygen-me-2, we can solve this problem using a SAT solver (z3 in this case).
from z3 import *
s = Solver()
with open('./map2.txt', 'r') as f:
cipher, chalbox = eval(f.read())
length, gates, check = chalbox
v = []
for i in range(length):
e = Bool('v'+str(i))
v.append(e)
for name, args in gates:
if name == 'true':
v.append(True)
else:
u1 = Xor(v[args[0][0]], args[0][1])
u2 = Xor(v[args[1][0]], args[1][1])
if name == 'or':
v.append(Or(u1, u2))
elif name == 'xor':
v.append(Xor(u1, u2))
s.add(Xor(v[check[0]], check[1]) == True)
# print s.check()
# print s.model()
# values = [1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1]
values = [1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1]
values = values[::-1]
output = 0
for i in values:
print i
if i == 1:
output += 1
output <<= 1
print output >> 1 # 219465169949186335766963147192904921805
flag: picoCTF{36cc0cc10d273941c34694abdb21580d__aw350m3_ari7hm37ic__}
Feel free to leave a comment if any of the challenges is not well explained.