fastflag (150pt)

Reversing

Description: SSE allows you to get flags even faster!

nc fastflag-28659598.challenges.bsidessf.net 9999

Files:

• fastflag

Solution

The binary sets up a buffer as follows:

[32 random printable chars]
[flag data]

Then it allows the user to guess a string (462 times) and it performs a special string comparison function:

                     sub_94f:
                    ; rdi points to password string
0x000055555555494f         mov        rax, rdi
                    ; rsi points to user string
0x0000555555554952         sub        rax, rsi
0x0000555555554955         sub        rsi, 0x10

                     loc_555555554959:
0x0000555555554959         add        rsi, 0x10
0x000055555555495d         movdqu     xmm0, xmmword [rsi]
                    ; wow !
0x0000555555554961         pcmpistri  xmm0, xmmword [rsi+rax], 0x18
0x0000555555554968         ja         loc_555555554959

0x000055555555496a         jb         loc_555555554970

0x000055555555496c         xor        rax, rax
0x000055555555496f         ret

                     loc_555555554970:
0x0000555555554970         add        rax, rsi
0x0000555555554973         movzx      rax, byte [rax+rcx]
0x0000555555554978         movzx      rdx, byte [rsi+rcx]
0x000055555555497d         sub        rax, rdx
0x0000555555554980         sar        rax, 0x3f
0x0000555555554984         or         rax, 0x1
0x0000555555554988         inc        rcx
0x000055555555498b         mul        rcx
0x000055555555498e         ret

The cool part of this subroutine is the pcmpistri instruction. From the intel manual we see that this stands for “Packed Compare Implicit Length Strings, Return Index”.

Essentially what it is doing here is comparing two 16-byte string values at a time and setting ecx equal to the first index of a character not matching.

I found the following presentation to be a good reference during my reversing process: https://novalis.org/talks/thinking-with-pcmpistri/slides/#/29

If there is a character that doesn’t match in a given 16-byte section, we will take the jb branch. This part compares the first unmatched byte in the user string to the one in the password string.

If the user byte was lower in value that the real byte, it returns ecx otherwise it returns -ecx.

Here we have a nice data leak and can perform a binary search character by character to step through the whole string.

I wrote a small script to perform this attack:

from pwn import *

s = remote('fastflag-28659598.challenges.bsidessf.net', 9999)

charset = [chr(x) for x in range(32, 128)]

# test a string and return the comparison value
def do(inp):
    s.recvuntil('>')
    s.sendline(inp)
    b = s.recvline().split('[')[1][:-2]
    return int(b)

# perform a binary search for a single character
def bin_search(initial, va, vb, num):
    c = chr(int(va + vb) // 2)
    x = do(initial + c)

    print((initial + c) + ' :: ' + str(x))

    if abs(x) != num:
        return c
    elif x > 0:
        return bin_search(initial, ord(c), vb, num)
    else:
        return bin_search(initial, va, ord(c), num)

initial = ''
for i in range(0, 32+34):
    initial += bin_search(initial, 32, 128, (i % 16) + 1)
    print(initial)

s.interactive()