Category: Analysis-Offensive
Points: 200
Description:
Figure out the 8 possible numeric passwords. The password with the highest value is your flag.
Download the file(https://s3-ap-northeast-1.amazonaws.com/trendmicro-ctf-2017/KLgUiDGO6ObXwmG7FAfR/files2.enc)
Decrypt the downloaded file by the following command.
> openssl enc -d -aes-256-cbc -k nMl8REk39qxaHdQbjRPv -in files2.enc -out files2.zip
> unzip files2.zip
UPDATE: If you have issues decrypting, please try the following command instead.
> openssl enc -d -aes-256-cbc -k nMl8REk39qxaHdQbjRPv -in files2.enc -out files2.zip -md md5
> unzip files2.zip
The zip contained 1 file, called cracktheflag.exe. I ran the command, file cracktheflag.exe to get some additional information about the file.
$ file cracktheflag.exe
cracktheflag.exe: PE32 executable (console) Intel 80386, for MS Windows
Ok, so we have a 32-bit Windows PE executable. Next I loaded it into IDA Pro for further analysis.
The first thing I observed was that towards the end of start, or more preciselly @ 0x00401145, there is a block of code that gets executed when we enter a correct value. In all other cases, the program jumps straight to loc_401195, which executes call ExitProcess.
So now I went back towards the top of start to try and figure out how we can avoid the execution path to loc_401195.
So the program pushes the string “Validate Flag:” to the stack and executes call sub_401184. This function will likely print that string to the console. Next I observed that the program pushes two variables onto the stack, nNumberOfBytesToRead and lpBuffer. Then it executes call sub_4011EC folowed by a cmp eax, 6. I could reasonably guess that this function would read 8 bytes from the console, and return the number of bytes that it read. The cmp eax, 6 would then be used to verify that 6 bytes were entered at the console. I used the Win32 debugger to verify this suspicion.
Yup, I entered 4 bytes and eax was set to 4. So now we can note down our first constraint for the password, it must be 6 characters long.
Next I noticed that StrToIntA gets called 4 times. Additionally, the same method gets executed 3 times, sub_40100. But since this method didn’t appear to be affecting the control flow yet, I decided to ignore it for now. However, I was curious as to why StrToIntA was getting executed so many times, so using the debugger, I checked the stack each time before it was executed to see what parameters the program was using.
The test string I used was ‘123456’. Below is some Python pseudocode to better illustrate what is happening.
numbstr = '123456'
val1 = int(numbstr)
sub_401000(val1)
val2 = int(numbstr[:2]) #int('12')
sub_401000(val2)
val3 = int(numbstr[2:4]) #int('34')
sub_401000(val3)
val4 = int(numbstr[4:]) #int('56')
Next, I observed the code immediately following the StrToIntA calls. It looks like we want to avoid the jump that could occur as a result of ‘js loc_401195’. I didn’t immediately recognize the js instruction, so I had to quickly search online for more information. Apparently, this jump occurs when the SF flag is set to 1. And the SF flag will be set to 1 if a previous arithmetic operation results in a negative value. Or more specifically, if ‘sub eax, ecx’ results in eax becoming negative. The result from the previous StrToIntA gets stored in eax, so this is a value we can control using the last 2 digits of the string we enter. When this loop is first entered, we know the value of ecx will be 1, because of the 2 previous operations, xor ecx, ecx (which sets ecx to 0), and inc ecx which increments ecx by 1. If eax is 0, the loop is exited and the program continues executing. After the check for eax being negative, ecx is increased by 2, and the loop continues.
To confirm my analysis, I decided to implement this code in Python, and then bruteforce numbers from 0-99 to find which values will result in program execution continuing to loc_4010F7.
def try_numb_part1(last2):
ecx = 0x1
while last2 > 0:
last2 = last2 - ecx
ecx += 2
if last2 != 0:
return False
return True
def brute_part1():
possible_vals = []
for i in range(0, 100)[::-1]:
if try_numb_part1(i):
print('Last 2 digits may be... %02d' % i)
possible_vals.append(i)
return possible_vals
brute_part1()
The result of executing this script is…
$ python brute1.py
Last 2 digits may be... 81
Last 2 digits may be... 64
Last 2 digits may be... 49
Last 2 digits may be... 36
Last 2 digits may be... 25
Last 2 digits may be... 16
Last 2 digits may be... 09
Last 2 digits may be... 04
Last 2 digits may be... 01
Last 2 digits may be... 00
Next, I again ran the application with my debugger attached and used the string, ‘123481’ to verify that my script was correct. I indeed exited the loop without jumping to loc_401195.
So lets update our list of constraints:
- The string must be 6 characters long
- The last 2 digits must be one of the following: [81, 64, 49, 36, 25, 16, 09, 04, 01, 00]
- It’s likely that all characers should be decimal numbers, but this hasn’t been confirmed yet
Now, lets investigate loc_4010F7, as it also contains a conditional jump to loc_401195.
loc_4010F7:
mov eax, edi
mul edi
mov ecx, dword_40301B
mov dword_403042, ecx
mov ebx, eax
push offset dword_403042
call StrToIntA
xor eax, ebx
shr eax, 8
jnz short loc_401195
Before the previous loop was executed, the result of the last StrToIntA was stored in edi. So first edi is stored in eax, which is followed by the instruction mul edi. This will multiply edi by eax and store the result in eax. Or in other words, it is simply squaring the edi and storing the result in eax. Then there is an instruction for mov ebx, eax. So the result of the squaring is finally stored in ebx.
Then using the debugger, I observed that StrToIntA is once again being called, but this time on the first 4 characters entered by the user. The result of this call, is stored in eax and then an xor is perfomed with ebx, the result being stored in eax. Finally, shr eax, 8 is executed. For those unaware, ‘shr’ stands for Shift Right. So it is shifting the value of eax, right by 8 bits and then storing the result in eax. This must result in eax = 0 or otherwise the program will end.
Again, I will implement this in Python. Additionally, I will combine it with the previous bruteforce for part1, and implement a bruteforce for part2.
def try_numb_part2(first_4, last2):
ebx = last2*last2
eax = first_4
result = (eax ^ ebx) >> 8
if result == 0:
return True
else:
return False
def brute_part2():
solutions = []
possible_vals = brute_part1()
for i in range(0,10000)[::-1]:
for last in possible_vals:
if try_numb_part2(i,last):
solutions.append((i,last))
#print(solutions)
print('# of possible solutions: %d' % len(solutions))
print('First possible solution: %04d%02d' % solutions[0])
return solutions
brute_part2()
The output for this script is now…
$ ./cracktheflag.py
Last 2 digits may be... 81
Last 2 digits may be... 64
Last 2 digits may be... 49
Last 2 digits may be... 36
Last 2 digits may be... 25
Last 2 digits may be... 16
Last 2 digits may be... 09
Last 2 digits may be... 04
Last 2 digits may be... 01
Last 2 digits may be... 00
# of possible solutions: 2560
First possible solution: 665581
And now we will once again update our list of constraints:
- The string must be 6 characters long
- The last 2 digits must be one of the following: [81, 64, 49, 36, 25, 16, 09, 04, 01, 00]
- The first 4 digits must also be numbers
- When the first 4 digits, and the last 2 digits are passed to try_numb_part2(), the function must return True.
So now lets use ‘665581’ as the next test string and begin reversing the last conditional jump to loc_401195.
Hmm, there is that function we previously ignored, sub_401000. After that call, the program moves the value stored at dword_403005 into eax, and checks if eax is set to 0. I have not so far seen any references to dword_403005, so perhaps it’s time to reverse the sub_401000 function.
Sure enough, this is where dword_403005 gets modified. There are two possible places where this function will return. One of them will execute or dword_403005, 80000000h causing dword_403005 to no longer be set to 0.
After stepping through this function quite a few times, I discovered that it starts by dividing the number stored at dword_40300D by 2. If the remainder of this division is 0, the function exits and sets dword_403005 to 80000000h. Then the denominator is then increased by 1 and then calculated for a remainder once again. This loop continues until the denominator is equal to the numerator. In otherwords, this function is testing for prime numbers! Rather than attempt to implement the assembly in Python, I googled for one already implemented online and found the following on StackOverflow.
#https://stackoverflow.com/a/15285588/5948112
def isprime(n):
if n==2 or n==3: return True
if n%2==0 or n<2: return False
for i in range(3,int(n**0.5)+1,2): # only odd numbers
if n%i==0:
return False
return True
Lets go back to that previous block of code that executed the prime function a few times, we’ll use the Python psuedocode for readability:
numbstr = '123456'
val1 = int(numbstr)
sub_401000(val1)
val2 = int(numbstr[:2]) #int('12')
sub_401000(val2)
val3 = int(numbstr[2:4]) #int('34')
sub_401000(val3)
val4 = int(numbstr[4:]) #int('56')
Now that we know sub_401000() checks if the number is prime, we can update our list of constraints:
- The string must be 6 characters long
- The last 2 digits must be one of the following: [81, 64, 49, 36, 25, 16, 09, 04, 01, 00]
- The first 4 digits must also be numbers
- When the first 4 digits, and the last 2 digits are passed to try_numb_part2(), the function must return True.
- The entire number must be prime
- The number from the first 2 digits must be prime
- The number from the middle 2 digits must be prime
I still had not checked what values were being passed to the last call to the prime number function, but I decided to implement what I have so far in Python to see if the # of possible solutions is small enough to manually brute force.
First I hacked up a function to brute force the values that would satisfy the prime number requirements.
def brute_prime_numbs():
primes = []
for i in range(0,999999+1):
numb = '%06d' % i
if not isprime(int(numb)):
continue
if not isprime(int(numb[:2])):
continue
if not isprime(int(numb[2:4])):
continue
primes.append(numb)
return primes
And finally, to tie everything together I have the following code:
possible_vals = brute_part2()
primes = brute_prime_numbs()
prime_solutions = []
for vals in possible_vals:
val = '%04d%02d' % vals
if val not in primes:
continue
prime_solutions.append(val)
print('Calculated %d possible solutions.' % len(prime_solutions))
print(prime_solutions)
Executing the final script results in the following output:
$ ./cracktheflag.py
Last 2 digits may be... 81
Last 2 digits may be... 64
Last 2 digits may be... 49
Last 2 digits may be... 36
Last 2 digits may be... 25
Last 2 digits may be... 16
Last 2 digits may be... 09
Last 2 digits may be... 04
Last 2 digits may be... 01
Last 2 digits may be... 00
# of possible solutions: 2560
First possible solution: 665581
Calculated 15 possible solutions.
['238949', '236749', '235349', '234749', '234149', '231349', '025309', '025301', '024709', '024109', '022901', '021701', '021101', '020509', '020201']
While we haven’t found the exact 8 solutions, we have narrowed it down to 15 possible solutions. And since we only need to provide the largest solution as the flag, I figured I would just try each possible solution, starting from the largest. While the first solution was rejected by the binary, the 2nd solution was accepted.
Here you can find the complete implementation for cracktheflag.py
Flag
TMCTF{236749}