mic

Task:

Flags for free!

nc 109.233.61.11 3120

Source code also provided (file mic_server.py)

Solution:

So, first thing to do: open and read source file (whatever...)

Some interesting things: conversation with server consits of two parts: in the first part we send to server a big prime number (more than 100, but less than 200 binary places), then we send a base ( number, that greater than 1 but less than prime -1); stage two: server sends a flag mixed in our base. Flag is greater than our prime (from sources: assert 1 << 256 < FLAG < 1 << 512), so, in fact we receive only part of flag.

Server mixes flag into our base with following algorithm:

res = pow(g * FLAG, FLAG, p) * FLAG + FLAG

res %= p

So, if we send some different primes, we will get remainders of flag by modulo of sent primes... it looks like Chinese Remainder Theorem . But res = (g^FLAG * FLAG^FLAG)*FLAG + FLAG mod p, and even if get enough remainders, it would be easy, to extract pure FLAG. So we need a special g, to get rid of powered FLAG... maybe not one g...

Let base = p-g (p - our prime)

res2 = ((p-g)^FLAG * FLAG^FLAG)*FLAG + FLAG mod p

if FLAG is odd:  

(p-g)^FLAG mod p = -(g^FLAG), so 

res2 = (-(g^FLAG) * FLAG^FLAG)*FLAG + FLAG mod p

res1 =  (g^FLAG * FLAG^FLAG)*FLAG + FLAG mod p

res1 + res2 = g^FLAG * FLAG^FLAG+1 + FLAG -(g^FLAG) * FLAG^FLAG+1+ FLAG mod p = 2*FLAG mod p

And it is main idea of our attack.

Send a two bases two server, some g, and prime - g, so then we can get a remainder of 2*FLAG by modulo of prime and use CRT to recover flag.. in case of even FLAG we should substract res2 from res1 instead of sum.

Lets wrute some code and pwn task. 

I took six prime numbers from wiki's article abour RSA-numbers (RSA-100,110 and 120=) ). I think 6 numbers will be enough to use CRT. 

Then i used this script to get six remainders:

g = 2
primes = [37975227936943673922808872755445627854565536638199, 40094690950920881030683735292761468389214899724061,
6122421090493547576937037317561418841225758554253106999, 5846418214406154678836553182979162384198610505601062333,
327414555693498015751146303749141488063642403240171463406883, 693342667110830181197325401899700641361965863127336680673013]

remainders = []

print "Receiving remainders..."
for i in xrange(0,6,1):
	conn = create_connection(('109.233.61.11', 3120));

	data = conn.recv(1024);
	conn.send(str(primes[i]) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	conn.send(str(g) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	res1 = data.split()[-1]

	conn = create_connection(('109.233.61.11', 3120));

	data = conn.recv(1024);
	conn.send(str(primes[i]) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	conn.send(str(primes[i]-g) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	res2 = data.split()[-1]

	remainders.append((int(res1)+int(res2))%primes[i])

When i got remainders, i used CRT to recover FLAG:

def extended_euclidean(a, b):	
	x = 0
	lastx = 1
	y = 1
	lasty = 0
	
	while b != 0:
		q = a // b
		a, b = b, a % b		
		x, lastx = (lastx - q * x, x)
		y, lasty = (lasty - q * y, y)
	return (a, lastx, lasty)
	
def inverse(var, module):
	v = extended_euclidean(var,module)
	return (v[0]==1)*(v[1] % module)

def CRT(RemList,ModulList):
	N  = reduce(mul,ModulList)        		# multiply ModulList together
	Ns = [N/mi for mi in ModulList]   		# create list of all N/multiply
	ys = [inverse(Ni, mi) for Ni,mi in zip(Ns,ModulList)] # get inverse elements of Ni by module mi
	return (reduce(add,[ri*Ni*yi for ri,Ni,yi in zip(RemList,Ns,ys)]) % N,N)

result =  CRT(remainders,primes)

And finally we can find flag: we shoud devide result by 2 and then decode it from hex:

f = result[0]/2
encoded_flag = str(hex(f))[2:-1]
flag = encoded_flag.decode("hex")

And the flag is  CTF{cf5246e06b13432b9e1116ddef226455}

And here is full script to perform attack:

#!/usr/bin/env python
from socket import create_connection
from sys import *
from fractions import gcd
from numpy import random
from operator import *
from time import *

def extended_euclidean(a, b):	
	x = 0
	lastx = 1
	y = 1
	lasty = 0
	
	while b != 0:
		q = a // b
		a, b = b, a % b		
		x, lastx = (lastx - q * x, x)
		y, lasty = (lasty - q * y, y)
	return (a, lastx, lasty)
	
def inverse(var, module):
	v = extended_euclidean(var,module)
	return (v[0]==1)*(v[1] % module)

def CRT(RemList,ModulList):
	N  = reduce(mul,ModulList)        		# multiply ModulList together
	Ns = [N/mi for mi in ModulList]   		# create list of all N/multiply
	ys = [inverse(Ni, mi) for Ni,mi in zip(Ns,ModulList)] # get inverse elements of Ni by module mi
	return (reduce(add,[ri*Ni*yi for ri,Ni,yi in zip(RemList,Ns,ys)]) % N,N)

g = 2
primes = [37975227936943673922808872755445627854565536638199, 40094690950920881030683735292761468389214899724061,
6122421090493547576937037317561418841225758554253106999, 5846418214406154678836553182979162384198610505601062333,
327414555693498015751146303749141488063642403240171463406883, 693342667110830181197325401899700641361965863127336680673013]

remainders = []

print "Receiving remainders..."
for i in xrange(0,6,1):
	conn = create_connection(('109.233.61.11', 3120));

	data = conn.recv(1024);
	conn.send(str(primes[i]) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	conn.send(str(g) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	res1 = data.split()[-1]

	conn = create_connection(('109.233.61.11', 3120));

	data = conn.recv(1024);
	conn.send(str(primes[i]) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	conn.send(str(primes[i]-g) + "\n")
	sleep(0.1)

	data = conn.recv(1024);
	res2 = data.split()[-1]

	remainders.append((int(res1)+int(res2))%primes[i])

print "Using Chinese Remainder Theorem to recover flag..."

result =  CRT(remainders,primes)
f = result[0]/2
encoded_flag = str(hex(f))[2:-1]
flag = encoded_flag.decode("hex")
print flag