Hi folks. This post is about a Efiens challenge, easy-medium RE that my colleague Cothan publish on twitter as a part of a set of them included on Efiens CTF.
As described on his tweet, is an easy ctf that try to catch some talent people. I have spare time to participate as brucel33t kamikaze ninja. Three challenges per category that implies an easy,medium and hard levels. Let’s see our binary and it’s behaviour.
mediumRE: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=274cf5b891f49bf138e9d60a08dce32daf80b3ab, not stripped
Binary ask for a password. We can remote GDB with IDA and start analysis. Has «main» and «check» interesting functions. If we focuse on «check» function binary do a strlen check for a 30 characters password lenght setting a counter to -1 if not.
The second red rectangle is indeed the check loop. Counter must be set to 30 to get the «Good» answer, so the if block need to enter 30 times on that compare. It Compares each element of an array «encoded» with our input multiply by first 30 Fibonacci sequence adding «i» value on each iteration.
What is this encoded array? Reader at this moment will have realized that if we use a simple equation we can solve the problem. We have:
- encoded data: solution of input[i] * fibo[i] + i
- fibo data: first 30 fibonacci sequence
Input is what we want to know. Let’s use a python script to solve this. On each iter we must calculate (enc[i] – i)/fibo[i]. This is char value of our input.
See encoded results on a breakpoint
And Fibonacci sequence
Putting all together on Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python | |
| """ | |
| mediumRE from | |
| compare algorithm | |
| for ( i = 0; strlen(input) > i && i <= 29; ++i ) | |
| { | |
| if ( enc[i] == input[i] * fibo[i] + i ) | |
| ++cnt; | |
| } | |
| if ( cnt == 30 ) | |
| printf(yes); | |
| else | |
| printf(no); | |
| """ | |
| encoded = [0x43, 0x70, 0xDE, 0x138, 0x23E, 0x30D, 0x5EA, 0xA09, 0x46A, 0x12BA, 0x2327, 0x3CCB, 0x6258, 0x8BF4, 0xEE56, 0x1AC04, 0x2AE46, 0x3FB89, 0x21B07, 0x8ABD7, 0x115EE4, 0x1C605C, 0x324959, 0x33A637, 0x83A6BB, 0x81A97F, 0x143AFF2, 0x1D664AE, 0x32830EF, 0x1A2F745] | |
| fibo = [0x01 ,0x01 , 0x02 , 0x03 , 0x05 , 0x08 , 0x0D , 0x15 , 0x22 , 0x37 , 0x59 , 0x90 , 0xE9 , 0x179 , 0x262 , 0x3DB , 0x63D , 0xA18 , 0x1055 , 0x1A6D , 0x2AC2 , 0x452F , 0x6FF1 , 0xB520 , 0x12511 , 0x1DA31 , 0x2FF42 , 0x4D973 , 0x7D8B5 , 0xCB228] | |
| i=-1 | |
| flag ='' | |
| for enc in encoded: | |
| i = i + 1 | |
| flag =''.join(chr((enc – i )/fibo[i])) | |
| print flag |
