crypto400.py

crypto400.py

from sympy import *
from sympy import pdiv, prem
from sympy.abc import x
from random import random, choice, randint
from string import ascii_letters, digits
import sys
import os
import binascii
import threading
import Queue
import struct                                                                   
import socket                                                                   
import telnetlib                                                                
import sys, time                                                           
import string
import re
from threading import Lock

FLAG_FILE = "flag"
FLAG_PATH = os.path.join(os.path.dirname(__file__), FLAG_FILE)
THREAD_COUNT = 10
MIN_COEFFICIENT = 1
MAX_COEFFICIENT = 999999999999
RANDOM_INDEX = 0.5
CHALLENGE_COUNT = 5
MESSAGE_LENGTH = 16

mylock = Lock()

class Crypter:
    def __init__(self, k):
        self._k = k
        self._n = 2 * k + 1
        self._domain = GF(2)
        #self._sk = Poly(x**21 + x**19 + x**18 + x**13 + x**12 + x**11 + x**8 + x**7 + x**4 + x**3 + 1, x, domain = self._domain)
        self._sk = self._multithreading(self._secret_key)
        self.pk = self._public_key()
        self.sol = self.solve_secret_key(self.pk, self._n)
        print self.sol

    def _poly(self, expr):
        return Poly(expr, x, domain=self._domain)

    def _random_poly(self, n):
        rp = random_poly(x, n, MIN_COEFFICIENT, MAX_COEFFICIENT)
        return self._poly(rp)

    def _secret_key(self, result_queue):
        while result_queue.empty():
            secret_key = self._random_poly(self._n)
            if secret_key.is_irreducible and degree(secret_key) == self._n:
                result_queue.put(secret_key)
        sys.exit()

    def _public_key(self):
        public_key = []

        poly0 = self._random_poly(self._n)
        if degree(poly0) < self._n:
            tmp = self._poly(x ** self._n)
            poly0 += tmp

        poly1 = self._random_poly(self._k - 1)
        poly2 = poly0 * self._sk + self._poly(x) * poly1
        public_key.append(poly2)
        
        #a0*x+b0
        
        for i in range(1, self._k):
            poly0_i = self._random_poly(self._k)
            poly1_i = self._random_poly(self._k - 1)
            poly2_i = poly0_i * self._sk + self._poly(x) * poly1_i
            poly2_i = poly2_i % poly2
            #ai*x+bi = (a0*x+b0)*k
            public_key.append(poly2_i)

        return public_key
    
    def solve_secret_key(self, pkeys, n):
        pol = [0]*(n+2)
        pol[n+1]=pol[0]=1
        while True:
            j = 2
            while (j<n+1) and (pol[j]==1):
                pol[j]=0
                j += 1
            pol[j] = 1
            xpol = Poly(pol,x,domain=self._domain)
            if all([ (pkeys[j] % xpol).nth(0)==0 for j in range(1,len(pkeys))]):
                return xpol
        raise Exception("Not found")
    
    @staticmethod
    def _multithreading(func):
        result_queue = Queue.Queue()
        threads = [threading.Thread(target=func, args=[result_queue]) for i in range(THREAD_COUNT)]
        for th in threads:
            th.start()
        result = result_queue.get()
        result_queue.put(result)
        return result

    def encrypt(self, msg):
        temp = []
        for i in range(1, len(self.pk)):
            if random() <= RANDOM_INDEX:
                temp.append(i)

        cipher = self._poly(msg % 2)
        
        for i in temp:
            e = self._random_poly(self._k - 1)
            cipher += self.pk[i] + self._poly(x) * e
                
        return cipher % self.pk[0]

    def decrypt(self, cipher):
        return (cipher % self._sk) % self._poly(x)


class Challenge:
    def __init__(self):
        self._challenge_count = CHALLENGE_COUNT
        self._message_length = MESSAGE_LENGTH

    @staticmethod
    def _win():
        print open(FLAG_PATH).read()

    def _generator(self):
        msg = ''.join(choice(ascii_letters + digits) for _ in range(self._message_length))
        n = 10#randint(5, 10)
        return msg, n

    def _magic(self):
        msg, n = self._generator()
        crypter = Crypter(n)
        msg_bin = bin(int(binascii.hexlify(msg), 16))[2:]
        #print crypter.pk
        print map(lambda z: z.all_terms(), crypter.pk)
        ciphers = []
        for i in msg_bin:
            cipher = crypter.encrypt(int(i))
            ciphers.append(cipher.all_terms())
        print ciphers
        return msg
    
    def play(self):
        success = 0
        while True:
            if success == self._challenge_count:
                self._win()
                return
            print 'Here is your challenge:'
            print '\nPlease wait, this may take awhile:'
            print '------------------------------------------------------------------'
            my_msg = self._magic()
            print '------------------------------------------------------------------'
            your_msg = raw_input('> Enter your answer: ')
            if your_msg != my_msg:
                print 'Bye!'
                return
            success += 1

class Solve:
    def __init__(self,ip,id):
        self.id = id
        self._challenge_count = CHALLENGE_COUNT
        self._message_length = MESSAGE_LENGTH
        self.s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)  
        self.s.connect((ip, 7500)) 
        self.re = re.compile('------------------------------------------------------------------\s*'
                        +'(.*)------------------------------------------------------------------', re.MULTILINE|re.DOTALL)
    def mkpoly(self, lst):
        r = Poly(0,x,domain=GF(2))
        for (n,), a in lst:
            r+=Poly(a*x**n,x,domain=GF(2))
        return r
    def solve_secret_key(self, pkeys, n):
        pol = [0]*(n+2)
        pol[n+1]=pol[0]=1
        while True:
            j = 2
            while (j<n+1) and (pol[j]==1):
                pol[j]=0
                j += 1
            if j==n+1: break
            pol[j] = 1
            xpol = Poly(pol,x,domain=GF(2))
            if all([ (pkeys[j] % xpol).nth(0)==0 for j in range(1,len(pkeys))]):
                return xpol
        with mylock:
            print "no solution ",self.id
        return None
    def solveCase(self,prob):
        prob = self.re.search(prob)
        prob = prob.groups(0)[0]
        prob=re.sub(r"\s+",'',prob)
        pp = prob.index("[[")
        prob = prob[pp:]
        pp = prob.index("]][[")
        prob = [prob[:pp+2],prob[pp+2:]]
        prob = [eval(s.strip("\r\n\t ").replace("\t","")) for s in prob]
        pk = [self.mkpoly(_pk) for _pk in prob[0]]
        n = degree(pk[0])/2-1
        sol = self.solve_secret_key(pk,n)
        if sol is None:
            return False
        bb = ""
        for p in prob[1]:
            p = self.mkpoly(p)
            bb+=str((p % sol).nth(0))
        r=hex(int(bb,2))[2:-1].decode("hex")
        with mylock:
            print "###", r, len(r)
        self.s.send(r+"\n")
        return true
        
    def solve(self):
        self.s.recv(10)
        self.s.send("\n")
        for i in range(CHALLENGE_COUNT):
            with mylock:
                print >> sys.stderr, "# Reading #",self.id,i
            s = ""
            m = None
            while True:
                ss = self.s.recv(4096)
                #print >> sys.stderr,ss
                s+=ss
                if "Bye" in s:
                    return False
                if "> Enter your answer:" in s:
                    break
            with mylock:
                print >> sys.stderr,"# Solving #",self.id,i
            if not(self.solveCase(s)):
                return False
        flag =  self.s.recv(4096).strip()
        with mylock:
            print "./submit.py crypto400 "+flag+" "+str(self.id)
        return True
        
HOSTS = [
("10.10.10.19",9,"snatchtheroot.whitehatvn.com"),
("10.10.10.14",3,"samurai.whitehatvn.com"),
#("10.10.10.13",4,"babyphd.whitehatvn.com"),
#("10.10.10.15",5,"217.whitehatvn.com"),
("10.10.10.11",10,"shellphish.whitehatvn.com"),
#("10.10.10.10",11,"ppp.whitehatvn.com"),
("10.10.10.16",8,"dragonsector.whitehatvn.com"),
("10.10.10.17",7,"mslc.whitehatvn.com"),
#("10.10.10.18",2,"dcua.whitehatvn.com"),
]
def attack(h):
    while True:
        try:
            with mylock:
                print >> sys.stderr, "# Attacking ",h[2]
            s = Solve(h[0],h[1])
            if s.solve():
                break
        except:
            pass
        
threads = [threading.Thread(target=attack, args=[h]) for h in HOSTS]
for th in threads:
    th.start()