Monday, July 8, 2013

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:

system("ssh-keygen -m PKCS8 -i -f 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
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)
    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
challenge@ubuntu:~$ cat flag.txt 
Flag for the challenge is SIGINT_some_people_pay_100_euro_for_this


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)
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)
>>> hex(0x15a4e35 * 2)
>>> hex(0x15a4e35 * (2**32+1))
>>> hex(0x15a4e35 * (2**32+2))
>>> hex(0x15a4e35 * (2**32+1) & 0xffffffff)
>>> hex(0x15a4e35 * (2**32+2) & 0xffffffff)
[*] 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


  1. This can be massively sped up by exploiting a congruence in the RNG -- the large multiplicative constant can be trimmed to 25 bits, and the seed can be trimmed to 25 bits at every iteration too.

    Also, there is no need to generate the full key - just generating a single prime and checking if it divides n is enough.