GitS CTF 2013 write-up

Hint: flag is not a frag: once you've got it, you can get one more...

At these weekend we've participated in the Ghost in the Shellcode CTF event.
As usual, there were few of us, and nobody has been solving tasks constantly.
Actually, there were NO reverse-engineers among us, and tasks were full of binary stuff.
Nevertheless, as usual, again, we've managed to get some points and finished 16-th.
Thanks to ont, overxor, blackfan.

Here's a write-up on the task I liked ('cause I like Web, PPC and Crypto categories, and there was only Crypto out of them):

Crypto 250

We're given:
Цитата:
Question 12 - RabinsBitch
Points: 250

Extract the key! Answers in sha256("p=0x...,q=0x...".lower()) (File running at rabinsbitch.2013.ghostintheshellcode.com)
You can find the source code in the attachment.

At first, the service asks to solve a SHA-1 puzzle:
Код:
...
		req.sendall("You must first solve a puzzle, a sha1 sum ending in 26 bit's set to 1, it must be of length %s bytes, starting with %s"%(len(proof)+5,proof))
		test=req.recv(21)
		ha=hashlib.sha1()
		ha.update(test)
		if (test[0:16]!=proof or ord(ha.digest()[-1])!=0xff or 
            ord(ha.digest()[-2])!=0xff or
			ord(ha.digest()[-3])!=0xff or
			ord(ha.digest()[-4])&3!=3 
			):
			req.sendall("NOPE")
...
Such puzzle can be solved by the brute force. I used itertools.combinations for this purpose.
Also, there's implemented a ciphering algorithm:
Код:
...
def encrypt(m,n):
    c=pow(m,2,n)
    return c
...
The decryption is not fully correct, though it does return the correct answers (due to the Fermat's little theorem):
Код:
...
def decrypt(c,p,q):
    mp=pow(c,(p+1)/4,p)
    mq=pow(c,(q+1)/4,q)
    r1 = pow(c, (p+1)/4, p)
    r2 = pow(c, (q+1)/4, q)

    return (reste_chinois([r1, r2], [p, q]), \
                reste_chinois([-r1, r2], [p, q]), \
                reste_chinois([r1, -r2], [p, q]), \
                reste_chinois([-r1, -r2], [p, q]))
...
decrypt() returns a tuple of 4 solutions of Chinese Remainder Theorem.

So, we should obtain and factorize the modulo. First, I've used an obvious solution -- took the received tuple decrypt( 1, p, q ), say, (a,b,c,d).
Square of each of these numbers is congruent to 1 modulo n. Thus, we can obtain the modulo itself by computing the GCD of all the numbers:

Код:
...
norm = lambda x: pow( x, 2 ) - 1
r = [ norm( int( x ) ) for x in r ] #r = (a,b,c,d)
print 'GCD of the tuple is %s' % gcd( gcd( gcd( r[ 0 ], r[ 1 ] ), r[ 2 ] ), r[ 3 ] )
FactorDB.com didn't know the factors of the obtained modulo at that moment, so, I decided to perfom these actions on the decrypt( 2, p, q ).
The GCD of the new tuple turned out to be exactly p. So, the challenge was solved.

But after I've passed this task, hellman from MoreSmokedLeetChicken told me about the right way to solve this task.
Since the decrypt() functions returns the following tuple:

Код:
(reste_chinois([r1, r2], [p, q]), reste_chinois([-r1, r2], [p, q]), reste_chinois([r1, -r2], [p, q]), reste_chinois([-r1, -r2], [p, q])),
the modulo n can be computed as follows:

Код:
decrypt( 1, p, q )[ 0 ] + decrypt( 1, p, q )[ 3 ] = decrypt( 1, p, q )[ 1 ] + decrypt( 1, p, q )[ 2 ] = 
reste_chinois([r1, r2], [p, q]) + reste_chinois([-r1, -r2], [p, q]) = reste_chinois([-r1, r2], [p, q]) + reste_chinois([r1, -r2], [p, q]) = n
Then, the factors can be computing by taking GCD:

Код:
p = GCD( decrypt( 1, p, q )[ 0 ] + decrypt( 1, p, q )[ 1 ], n)
q = GCD( decrypt( 1, p, q )[ 0 ] + decrypt( 1, p, q )[ 3 ], n) = n / p
So, the final exploit looks like this (my initial solution is commented):

Код:
import hashlib, socket, re, itertools, struct
from fractions import gcd

s = socket.socket()
s.connect( ('54.235.155.218', 9955) )
tmp = s.recv( 256 )
proof = re.search( 'with (\S+)', tmp ).group( 1 )

print 'Ok, got salt: %s\nStarting brute force' % proof
charset = ''.join( [ chr( x ) for x in xrange( 0, 128 ) ] )
found = False

for comb in itertools.combinations( charset, 5 ):
    test = proof + ''.join( comb )
    ha=hashlib.sha1()
    ha.update( test )
    if ( ord( ha.digest()[ -1 ] ) == 0xff and
            ord( ha.digest()[ -2 ] ) == 0xff and
			ord( ha.digest()[ -3 ] ) == 0xff and
			ord( ha.digest()[ -4 ] ) & 3 == 3 
			):
        print 'Found %s' % test
        found = True
        break

if not found:
    print 'Could not find string =('
    quit()

s.send( test )
s.send( struct.pack( 'H', 1 ) )
s.send( chr( 1 ) )
r = ''
while 1:
    t = s.recv( 256 )
    if t == '':
        break
    r += t

#print 'Ok, decrypt( 1, p, q ) == (%s)' % r
#norm = lambda x: pow( x, 2 ) - 1
r = r.split( ',' )
#r = [ norm( int( x ) ) for x in r ]
r = [ int( x ) for x in r ]
#print 'GCD of the tuple is %s' % gcd( gcd( gcd( r[ 0 ], r[ 1 ] ), r[ 2 ] ), r[ 3 ] )
n = r[ 0 ] + r[ 3 ]
p = gcd( r[ 0 ] + r[ 1 ], n )
q = n / p
ans = 'p=%s,q=%s' % (hex( p ).rstrip( 'L' ), hex( q ).rstrip( 'L' ))
print 'W00t, the flag is %s' % hashlib.sha256( ans ).hexdigest()

s.close()
Now it's time to launch it:

Цитата:
$ python crypto250.py
Ok, got salt: U/0VkklASh1aiZsd
Starting brute force
Found U/0VkklASh1aiZsd(H`|
W00t, the flag is 98ebb2bffe5b0eb2872e395f7b504162a7c2a6fda6820c0e03 9d85ebece7bde2

P.S. Some guy (ius) in the IRC pointed that all this staff is described at wikipedia: https://en.wikipedia.org/wiki/Rabin_cryptosystem#Decryption
I just haven't thought about the name of the task and treated it as some unknown cipher algorithm.