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

[*] 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

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

#!/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 GMTThe n value was extracted from authorized key as

0xbe2bac35ca87627aacabc899d4607c3f66ec9c69b4f4121c20e1716a6587e1fdeb84e102173c9db7c22757254288abc1aac22e4cfcf6beeff8003de55cadc17ae6952478861e6415e801e0e3d04aa917188775207f2b53afb7f948166046de1cbe31524b61fcfa9414714308fe089464157d977ffe49c995922b95305ce961d3Below 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 += 1After sometime we got the following values:

p = 10196183246368760603869192593971202143897281417220455881063414616103901438182656326076501376638806928762094749150020638960102206987607293047096627515275223 q = 13097286606179453667665592444299109782484218865253457545521978739889248320232481682880143106432871469494586765663594908396375009598486558938138835723794021 SEED = 1373038672Now 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_thisFlag 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

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.

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

Thanks for the information :)

Delete