Tuesday, June 5, 2012

Defcon 20 CTF qualifiers: urandom 300

On this challenge we need to connect to a service that will give us 100000 unsigned integers (uint16_t), and we need to send the required steps to sort this huge list. However, is not going to be an easy task, as there are 2 restrictions:
  1. You only have 10 seconds for reading the numbers, sorting them and sending back the answer to the server 
  2. The anser needs to be "optimal" (or close enough). "[...] If you correctly sort the array in sufficiently few moves I will give you a key!" 

You can solve the first restriction with a good server with good network connection. However, you won't get the answer if you don't meet the second requirement.

As speed is one of our concerns, our sorting algorithm will be Quicksort. It's fast, but... it'll take a huge amount of "swap moves" or "steps" to sort the numbers. It'll take around ~1M moves to sort a random array of 100000 elements, so we'll need to improve that (sending that amount of data might require a really fast internet connection, and for sure it won't be the optimal solution).

Thinking about the problem I realize that the "swaps" moves can be reduced. Imagine that you need to order a deck of cards. Basically you'll search the lowest card from left to right, moving it to the left (first position) once you've found it. Afterwards, you'll search the next-lowest card, and so on. This algorithm that most people use is called Insertion sort. Of course, that process is quite slow, but if you think about that, it can be optimal regarding the number of "swap moves".

The idea behind is that you will sort your deck in the usual way, but using a "cheat-sheet/oracle" that will tell you exactly which is the sorted position for each of your cards. In that case, you'll need only one "swap move" per card, using a maximum of N swap moves and it'll run very quickly.

Therefore, we'll use 2 lists: the first one will be the original (unordered) list. The next one will be the sorted one (using quicksort). Using the sorted list will allow us to get the optimal? number of "swaps moves".Here you go the quick and dirty algorithm:

  1. Grab the unsorted list of integers
  2. Sort them using Quicksort
  3. For each number in the sorted list:
  1. Get the number's position in the sorted list (Sth)
  2. Get the number's position in the unsorted list (Uth)
  3. Send to the server one "swap move", using the previous information (Uth:Sth)
  4. Update the unsorted list with the move that we have sent (that's because the same number might need to be used or moved more than once until it's been "ordered").

Implementing this solution solved only one part of the problem. Issues like bad coding practices, the 5 minutes cooldown and the overall speed of the Python/network code made it difficult to get the solution. In fact, the most difficult part was troubleshooting the apparently "flawless" code, as the server was rejecting any solution... In the end, I found out that it was a little/big endian issue :'(.

After fixing all the previous issues, and running again the script, we got the solution:
Congratulations, your final array is sorted correctly.

Here is your key: a7482ddfb82601fdc392b67836883dcc

I've added here the code that generates the "swap moves" from some sample "datadumps" that were obtained during the CTF. Be careful, as it's a really low quality code :(.

Finally, I'd like to say thanks to my team, as they give me a hand that allowed me to solve this challenge :).

Defcon 20 CTF qualifiers: b200

On the second binary challenge, we have a copy of the server that is listening in one DDTEK servers. We need to find a way to get the key from it.

Basically, the program makes some sanity checks and starts a listener on port 18703, creating a fork process for each request to the server. On little problem here is that GDB on FreeBSD is not handling properly forking process, so you'll need to patch the binary to make easier the debugging proccess.

As you can see below, the main loop that handles the requests will create a fork'd process that will call the function "ptrCheckSolution" (0x08049460)
.text:08049344 mov     [esp], ebx      ; fd
.text:08049347 mov     dword ptr [esp+4], offset ptrCheckSolution ; int
.text:0804934F call    mainRecvLoop

Click me to expand

It seems that we need to analyze that function (0x8049460). Basically it's divided in the folllowing steps:
  1. Check if some "magic" values were sent
  2. Get the length of 2 variables (maximum of 400bytes each). After that, the application will read the 2 variables with the size that we specified before
  3. Do some calculations and if everything is ok, the "key" file will be sent. Otherwise. a "sorry\n" message will appear on our console :(

Step 1) Check that valid "tokens" were sent

We'll need to send 4 words that the server is expecting. As you can see below, it's easy to spot the values from the assembly code:

.text:080494F6 mov     ecx, [ebp+fd]
.text:080494F9 mov     dword ptr [esp+8], 4 ; int (bytes to read)
.text:08049501 mov     [esp+4], eax    ; int
.text:08049505 mov     [esp], ecx      ; fd
.text:08049508 call    recvData        ; Read 4 bytes that we sent
.text:08049533 cmp     ebx, 0FE732D6Fh ; "Magic value #1"
.text:08049539 jnz     short loc_8049  ; "EXIT if magic value doesn't match

The "magic" values are the following: 0x94A4C265h, 0xFE732D6F,0xEEF814CB,0x6EC8A126

Step 2) Read our variables

The server will proceed to read the size of the 2 values that we are going to be sent, checking that each value doesn't exceed 400 bytes

.text:0804960E call    recvData
.text:08049613 cmp     eax, 4
.text:08049616 jnz     loc_80
.text:0804961C mov     eax, [ebp+size]
.text:0804961F cmp     eax, 400h
.text:08049624 ja      loc_8
After that, both values will be read, checking that both of them has the same length, but with different values.
.text:0804969C cld
.text:0804969D cmp     eax, eax
.text:0804969F mov     esi, ebx
.text:080496A1 mov     ecx, eax
.text:080496A3 repe cmpsb
.text:080496A5 jz      loc_80494CD     ; "Are different the values? If not, go to error"

Step 3) Mathematical calculations

If the previous checks were ok, the server will proceed to do some complex calculations on each variable that we sent. After that, it'll check that the result of the calculations were the same for both values.

.text:080496DB call    tangleHASH  ; <= "Complex calculations here"
.text:08049715 call    tangleHASH  ; <= "Complex calculations here"
.text:08049722 mov     esi, [ebp+var_124]
.text:08049728 mov     ecx, 20h
.text:0804972D mov     edi, ebx
.text:0804972F cld
.text:08049730 repe cmpsb   ; 
.text:08049732 jnz invalidValues ; "Exit if both values are identical"
If you take a look on the function that is doing the complex calculations, you'll see plenty of "hardcoded" values.

.text:0804A24B mov     [ebp+var_498], 14B62D86h
.text:0804A255 mov     [ebp+var_494], 31CF379Ch
.text:0804A25F mov     [ebp+var_490], 1BC6382Ah
.text:0804A269 mov     [ebp+var_48C], 752E03B3h
.text:0804A273 mov     [ebp+var_488], 0D0346A2Ah
.text:0804A27D mov     [ebp+var_484], 0A1DC5B93h
.text:0804A287 mov     [ebp+var_480], 0F9BB11D2h
.text:0804A291 mov     [ebp+var_47C], 0EB6A9A40h


If you search some of this "hardcoded values" on Google, you'll discover that it seems to be the assembly code of "the Tangle Hash function". So it seems that we need to find two different strings that have the same value. In other words... we need to find a collision on this algorithm... That might need some time :(.

However, doing a bit of research you'll find out that "Tangle" is a hash algorithm that was sent to the open competition that is searching for the next generation SHA-3 algorithm. As you can see here, it didn't pass the second round as it was vulnerable to collisiion attacks... exactly what we need :)

You can read the paper and try to implement the algorith OR you can do a quick search on Google in order to get an already implemented attack :p. Grab the code here. Take in account that you'll also require the reference implementation of Tangle (here).

After executing the files, you'll get a potential collision: Collision found in Tangle-256
Message 1:
Hash of message 1:
Message 2:
Hash of message 2:

Let's give it a try!...
$ perl -e 'print "\x94\xa4\xc2\x65\xfe\x73\x2d\x6f\xee\xf8\x14\xcb\x6e\xc8\xa1\x26\x28\x00\x00\x00\xc8\x19\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xc8\x19\x00\x80\x00\x00\x00\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x80"' | ncat 18703
437f085141d357c5d28850d5119aacb5   <== Solution!
Got it!. The solution to this challenge is 437f085141d357c5d28850d5119aacb5
Note: Copy of the Tangle implementation + collision program added here

Defcon 20 CTF qualifiers: b100

On this challenge, we face a zip archive with 3 files (mac.h, ssh and sshd). The file "mac.h" seems to be encrypted, but if you take a look carefully you'll be able to see some patterns. The other 2 files seems to be the client/server executables for SSH.

Anyway, analyzing the files will give us a clue about the "encryption" algorithm. So, we'll choose the client executable ("ssh"). A quick win is always search for text references to the "mac.h" file. We were lucky, as there were 6 references to that string in different locations:

try_password_authentication+13D  mov edi, offset aUsrIncludeMac_; "/usr/include/mac.h"
try_password_authentication+17D  mov edi, offset aUsrIncludeMac_; "/usr/include/mac.h"
input_userauth_info_req+1AA  mov edi, offset aUsrIncludeMac_; "/usr/include/mac.h"
input_userauth_info_req+1EA  mov edi, offset aUsrIncludeMac_; "/usr/include/mac.h"
userauth_passwd+170   mov edi, offset aUsrIncludeMac_; "/usr/include/mac.h"
userauth_passwd+1B0   mov edi, offset aUsrIncludeMac_; "/usr/include/mac.h"

Taking a deeper look on the "input_userauth_info_req" function we'll see the following string: "SSH2_OUT: %s \tuser: %s \tpass: %s \t(%s)\n"

Googling for the string "SSH2_OUT" will hint us that we are facing a backdoored executables that writes to a log file all the usernames/passwords. Now it's easier to understand the code:

Step 1) Do not store login attempts for user "abrazi":
ssh:004111AB mov     eax, 6
ssh:004111B0 mov     rsi, rbx
ssh:004111B3 mov     edi, offset aAbrazi ; "abrazi"
ssh:004111B8 cld
ssh:004111B9 mov     rcx, rax
ssh:004111BC repe cmpsb
ssh:004111BE jnz     loc_4112    ;"Do not log if user is 'abrazi'"

Step 2) Save the credentials details (IP, username,password) in the buffer 'abuff'

ssh:004112D8 loc_4112D8:
ssh:004112D8 mov     r12, qword ptr cs:options+0C0h
ssh:004112DF mov     rbx, [r8]
ssh:004112E2 call    get_remote_ipaddr
ssh:004112E7 mov     r9, rbp
ssh:004112EA mov     rcx, rax
ssh:004112ED mov     edx, offset aSSH2_out ; "SSH2_OUT: %s \tuser: %s \tpass: %s \t(%s)\n"...
ssh:004112F2 mov     r8, r12
ssh:004112F5 mov     esi, 400h       ; maxlen
ssh:004112FA mov     edi, offset abuff ; s
ssh:004112FF xor     eax, eax
ssh:00411301 mov     [rsp+38h+var_38], rbx
ssh:00411305 call    _snprintf
ssh:0041130A jmp     loc_4111C4

Step 3) Encode the previous string using "NOT" operator, that basically is the same than XOR'ing the string with 0xff

ssh:004111F0 loc_4111F0:                             ; CODE XREF: input_userauth_info_req+19D j
ssh:004111F0                 not     ds:abuff[rdx] ; "chr = ¬chr" or "chr = chr ^ 0xff"
ssh:004111F6                 add     rdx, 1
ssh:004111FA                 cmp     rdx, rax
ssh:004111FD jnz     short loc_4111F0

Step 4) Write the encrypted string to the "log" file (mac.h)
ssh:00411205 loc_411205:                             
ssh:00411205 mov     esi, (offset a_sshId_dsa+0Ah) ; modes
ssh:0041120A mov     edi, offset aUsrIncludeMac_ ; "/usr/include/mac.h"
ssh:0041120F call    _fopen
ssh:00411214 test    rax, rax
ssh:00411217 mov     cs:alog, rax
ssh:0041121E jz short loc_411245
ssh:00411220 movsxd  rsi, cs:alen    ; size
ssh:00411227 mov     edi, offset abuff ; ptr
ssh:0041122C mov     rcx, rax        ; s
ssh:0041122F mov     edx, 1          ; n
ssh:00411234 call    _fwrite
ssh:00411239 mov     rdi, cs:alog    ; stream
ssh:00411240 call    _fclose

So, with the following script, it'll be possible to decrypt the original (mac.h) file:

for i in cifrado:
    #val=256+~ord(i) <- NOT operation
    val=ord(i) ^ 0xff  # NOT == XOR(0xff)

print output
Unencrypted output:
SSH2_OUT:  user: root  pass: foobar  (ddtek.biz)
SSH2_OUT:  user: root  pass: f00bar  (ddtek.biz)
SSH2_OUT:  user: root  pass: mypassw0rd  (ddtek.biz)
SSH2_OUT:  user: root  pass: supr3m3p0w3r  (defcon.org)
pass_from:  user: root  pass: supr3m3p0w3r  (defcon.org)
SSH2_OUT:  user: emily  pass: l0v3ly
SSH2_OUT:  user: emily  pass: w0nd3rful
SSH2_OUT:  user: emily  pass: n0pa$$w0rd
pass_from:  user: emily  pass: l0v3ly  (hackeruniversity.edu)
pass_from:  user: feather  pass: l1ght3rthand1rt  (ddtek.biz)
pass_from:  user: feather  pass: wh@tsmypa$$  (ddtek.biz)
pass_from:  user: feather  pass: justw@it  (ddtek.biz)
pass_from:  user: feather  pass: ohmygoD  (ddtek.biz)
pass_from:  user: feather  pass: l1ght3rthand1rt  (ddtek.biz)
pass_from:  user: emily  pass: l0v3ly  (ddtek.biz)

After some tries (and discovering that the UI was buggy) you'll get the right solution: supr3m3p0w3r

One last side note: the SSH daemon (sshd), it's also back-doored, and it'll give you access to any account if a "secret" password is entered. However, it seems that the password is not easy to be crack, so if you want to spend some CPU cycles, give it a try :p.
sshd:004092B7 loc_4092B7:             ; salt
sshd:004092B7 mov     esi, offset salty
sshd:004092BC mov     rdi, r12        ; key
sshd:004092BF call    _crypt          
sshd:004092C4 cld
sshd:004092C5 mov     rsi, rax
sshd:004092C8 mov     edi, offset encryptedPWD ; "xzoQHjF6pMZlY"
sshd:004092CD mov     ecx, 0Dh
sshd:004092D2 repe cmpsb   ; Check if crypt(entered_password)  == "xzoQHjF6pMZlY"
sshd:004092D4 jnz     short loc_409303