codegate2018 密码学总结

pzhxbz
No comments yet

miro

这道题的难点就是解密tls流量，而要解密tls的话必须拿到证书的私钥，当时看了一下证书用的是RSA1024，感觉没有办法，下来看wp发现居然有方法可以分解这个N了。

方法一

有一个工具叫yafu，可以直接分解。

> yafu factor\(0x01c20bdc017e3caa3c579b40d439e2ecd70f12c4d7f2764784c95a3fddba00981ba9ce5b227ade47b0a7a0a8acaba4541ab95c52f6b6de3df9ec090c6c356445b21be437abe10214d0b4a398a96743bbf70c864687fb2ec929f01d6edab2d987fe09799ad2204a2704f33061dbf9c2e03b332f0ba1a446644c864a06cd586d480b\)


fac: factoring 316033277426326097045474758505704980910037958719395560565571239100878192955228495343184968305477308460190076404967552110644822298179716669689426595435572597197633507818204621591917460417859294285475630901332588545477552125047019022149746524843545923758425353103063134585375275638257720039414711534847429265419
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 1.2601 seconds


***factors found***

P155 = 17777324810733646969488445787976391269105128850805128551409042425916175469483806303918279424710789334026260880628723893508382860291986009694703181381742497
P155 = 17777324810733646969488445787976391269105128850805128551409042425916175469168770593916088768472336728042727873643069063316671869732507795155086000807594027

ans = 1

方法二

import gmpy 

def factor_fermat(N):
    a = gmpy.sqrt(N)
    b2 = a*a - N
    while not gmpy.is_square(gmpy.mpz(b2)):
        b2 += 2*a + 1
        a += 1

    factor1 = a - gmpy.sqrt(b2)
    factor2 = a + gmpy.sqrt(b2)
    return (long(factor1.digits()), long(factor2.digits()))

emmmmm，似乎就是一个优化过的枚举。

分解出这两个质数之后其实就很简单了，可以直接算出证书使用的私钥来解密。

babyrsa

感觉完全就是数学题

首先由题意可知：

g = d ∗ ( p − const )

由已知条件：

ed \equiv 1 \mod N \Rightarrow m^{ed} \equiv m \mod N

所以：

m^{eg} \equiv m^{e*d(p-const)} \equiv m^{p-const}\mod N

而

m^{p-const} * m^{const-1} \equiv m^{p-1} \mod N

根据费马小定理

m^{p-1} \equiv 1 \mod p \Rightarrow m^{p-1}-1=k*p

这时我们再求出k*p和N的公约数，就得到p了。

所以具体求法为：

kp = pow(2,e*g,N) * pow(2,0xdeadbeef-1,N)
p  = gcd(kp-1,N) # N = pq

求出p之后自然就可以求出私钥，直接解密即可。

Useless returnz

一道披着misc外皮的密码学（

给出的生成cookie算法为（输入为 用户名+ip）：

#-*- coding: utf-8 -*-

class Encrypt():

    def __init__(self, iv=None, keystr=None):        
#        self.iv = "useles5@"
#        self.keystr = "SUCK_7h15+4lG0_!"
        self.iv = iv
        self.keystr = keystr
        self.init_matrix = []
        chunk1 = self.keystr[0:8]
        chunk2 = self.keystr[8:16]
        row = []


        for i in range(0, 8):
            for j in range(0, 8):
                row.append(ord(chunk1[i]) ^ ord(chunk2[j]))

            self.init_matrix.append( row[0:8])

            del row[:]



    def split(self, p_txt):

        chunk = []

        if len(p_txt)%8 != 0:
            p_txt += "x" * (8 - len(p_txt)%8)


        for i in range(0, len(p_txt), 8 ):
             chunk.append(p_txt[i:i+8])


        return chunk


    def change(self, p_txt):

        temp = []
        result = []

        p_chunk = self.split(p_txt)

        for i in range(0, len(p_chunk)):
            for j in range(0, 8):
                temp.append(ord(p_chunk[i][j]))

            result.append(temp[0:8])
            del temp[:]


        return result


    def schedule(self, num):

        shift = [1, 2, 3, 2, 2, 1, 2, 3]
        temp = []
        matrix = []


        if num%2 == 0:            
            for i in range(0, 8):
                for j in range(0, 8):
                    temp.append(self.init_matrix[i][(8 - shift[i] + j)%8])

                matrix.append(temp[0:8])
                del temp[:]


        else:
            for i in range(0, 8):
                for j in range(0, 8):
                    temp.append(self.init_matrix[i][(shift[i] + j)%8])

                matrix.append(temp[0:8])
                del temp[:]


        return matrix



    def round0(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] - 10 + k_chunk[0])
        temp.append(p_chunk[1] ^ k_chunk[1])            
        temp.append(p_chunk[2] + k_chunk[2])
        temp.append(p_chunk[3] % (k_chunk[3]+2) + 32)
        temp.append(p_chunk[4] * 2 - k_chunk[3] - 7)
        temp.append(p_chunk[5] - 11 - k_chunk[5]%13)
        temp.append(p_chunk[6] ^ k_chunk[6])            
        temp.append(p_chunk[7] * 5 / (k_chunk[7] + 5))

        return temp



    def round1(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] - 11 + k_chunk[0])
        temp.append(p_chunk[1] ^ (k_chunk[1])%5)
        temp.append(p_chunk[2] ^ k_chunk[2])            
        temp.append(p_chunk[3] % (k_chunk[3]+2) + 34)
        temp.append(p_chunk[4] - k_chunk[3] + 14)
        temp.append(p_chunk[5] ^ k_chunk[5])           
        temp.append(p_chunk[6] + 9 - k_chunk[6])
        temp.append(p_chunk[7] + k_chunk[7])

        return temp



    def round2(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] - 11 + k_chunk[0])
        temp.append(p_chunk[1] ^ (k_chunk[1]) % 13)
        temp.append(p_chunk[2] + k_chunk[2] + 17)
        temp.append(p_chunk[3] ^ k_chunk[3])            
        temp.append(p_chunk[4] ^ k_chunk[4])            
        temp.append(p_chunk[5] - k_chunk[5] + 20)
        temp.append(p_chunk[6] / 3 % (k_chunk[6]+15))
        temp.append(p_chunk[7] + k_chunk[7])

        return temp



    def round3(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] + k_chunk[0])
        temp.append(p_chunk[1] ^ k_chunk[1] - 15)
        temp.append(p_chunk[2] ^ k_chunk[2])            
        temp.append(p_chunk[3] + k_chunk[3])            
        temp.append(p_chunk[4] + k_chunk[3] - 33)
        temp.append(p_chunk[5] ^ k_chunk[5])            
        temp.append(p_chunk[6] + k_chunk[6] - 55)
        temp.append(p_chunk[7] + k_chunk[7])

        return temp



    def round4(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] + k_chunk[0])
        temp.append(p_chunk[1] + k_chunk[1] + 17)
        temp.append(p_chunk[2] ^ k_chunk[2])            
        temp.append(p_chunk[3] - k_chunk[3] + 20)            
        temp.append(p_chunk[4] % (k_chunk[3]+2) - 34)
        temp.append(p_chunk[5] ^ k_chunk[5])            
        temp.append(p_chunk[6] + k_chunk[6])
        temp.append(p_chunk[7] - 11 + k_chunk[7])

        return temp


    def round5(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] / 6 % (k_chunk[0]+1))
        temp.append(p_chunk[1] ^ k_chunk[1])            
        temp.append(p_chunk[2] - k_chunk[2] + 20)            
        temp.append(p_chunk[3] - k_chunk[3] + 20)            
        temp.append(p_chunk[4] % (k_chunk[3]+7) - 34)
        temp.append(p_chunk[5] + k_chunk[5])
        temp.append(p_chunk[6] ^ k_chunk[6])            
        temp.append(p_chunk[7] + k_chunk[7])      

        return temp


    def round6(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] / 6 % (k_chunk[0]+7))
        temp.append(p_chunk[1] + k_chunk[1])
        temp.append(p_chunk[2] ^ k_chunk[2])            
        temp.append(p_chunk[3] - k_chunk[3] % 2 + 55)            
        temp.append(p_chunk[4] % (k_chunk[3]+3) + 127)
        temp.append(p_chunk[5] ^ k_chunk[5])            
        temp.append(p_chunk[6] + k_chunk[6] % 3)
        temp.append(p_chunk[7] + 11 + k_chunk[7])       

        return temp


    def round7(self, p_chunk, k_chunk):

        temp = []

        temp.append(p_chunk[0] + k_chunk[0]%30)
        temp.append(p_chunk[1] / (k_chunk[1]+1))
        temp.append(p_chunk[2] % (k_chunk[2]+4) + 18)            
        temp.append(p_chunk[3] ^ k_chunk[3])            
        temp.append(p_chunk[4] ^ k_chunk[4])            
        temp.append(p_chunk[5] / (k_chunk[5]+10) + 97)
        temp.append(p_chunk[6] + k_chunk[6])            
        temp.append(p_chunk[7] / 11 + k_chunk[7])       

        return temp



    def xor_calc(self, iv, chunk):

        result = []

        for i in range(0, 8):
            result.append(iv[i] ^ chunk[i])

        return result



    def encblock(self, chunk, num):

        rows = self.schedule(num)

        block = []
        result = []

        block.append(self.round0(chunk, rows[0]))
        block.append(self.round1(chunk, rows[1]))
        block.append(self.round2(chunk, rows[2]))
        block.append(self.round3(chunk, rows[3]))
        block.append(self.round4(chunk, rows[4]))
        block.append(self.round5(chunk, rows[5]))
        block.append(self.round6(chunk, rows[6]))
        block.append(self.round7(chunk, rows[7]))


        if num%2 == 0:
            result.append(chunk[0]^block[0][1]^block[1][2]^block[2][3])
            result.append(chunk[1]^block[0][1]^block[1][2]^block[3][2])
            result.append(chunk[2]^block[0][1]^block[2][3]^block[3][2])
            result.append(chunk[3]^block[1][2]^block[2][3]^block[3][2])
            result.append(chunk[4]^block[4][2]^block[5][1]^block[6][2])
            result.append(chunk[5]^block[4][2]^block[5][1]^block[7][3])
            result.append(chunk[6]^block[4][2]^block[6][2]^block[7][3])
            result.append(chunk[7]^block[5][1]^block[6][2]^block[7][3])

        else:
            result.append(chunk[0]^block[0][6]^block[1][5]^block[2][4])
            result.append(chunk[1]^block[0][6]^block[1][5]^block[3][5])
            result.append(chunk[2]^block[0][6]^block[2][4]^block[3][5])
            result.append(chunk[3]^block[1][5]^block[2][4]^block[3][5])
            result.append(chunk[4]^block[4][5]^block[5][6]^block[6][5])
            result.append(chunk[5]^block[4][5]^block[5][6]^block[7][4])
            result.append(chunk[6]^block[4][5]^block[6][5]^block[7][4])
            result.append(chunk[7]^block[5][6]^block[6][5]^block[7][4])


        return result



    def encrypt(self, plaintxt):

        p_chunks = self.change(plaintxt)
        e_chunks = []

        for i in range(0, len(p_chunks)):
            if i == 0:
                xor = (self.change(self.iv)[0])

            temp = self.xor_calc(xor, p_chunks[i])
            e_chunks.append(self.encblock(temp, i))

            del xor[:]
            del temp[:]

            xor.extend(e_chunks[i])  


        enctxt = ""

        for i in range(0, len(e_chunks)):
            for j in range(0, 8):
                enctxt += chr(e_chunks[i][j])


        return enctxt.encode('hex')

这道题的目标是在不知道key和iv的情况下求出“admin127.0.0.1”加密之后的结果。

看上去是一个分块加密，每次加密8个字节，具体的流程是先亦或，在用输入以及key生成另一个表，再进行亦或。然而，如果仔细观察的话，会发现加密时亦或用的block所使用的加密依然是亦或。所以这个加密可以直接化简成：输入之间亦或之后又亦或了一个和key有关的值。

所以最直接的解法，我们可以随便选一组iv和key，来加密“admin127.0.0.1”和另一个长度差距在一个block内的明文。当然题目环境已经不在了，我这里随便取了一组“test222.222.22.2”，之后对他们进行加密。

为了方便测试，我加了一段代码：

if __name__ == "__main__":
    mode = sys.argv[1]
    if mode == 's':
        en = Encrypt("3546255950330000","6e46174d6a4d447c6f00000000000000")
    if mode == 'l':
        en = Encrypt('7'*8,'6'*64)

    print(en.encrypt(sys.argv[2]))

我们现在就能得到三组数据：

pwn@ubuntu:~/Desktop$ python enc.py l test222.222.22.2
160011005750464c4b5a4c4b0d0d0d11
pwn@ubuntu:~/Desktop$ python enc.py s test222.222.22.2
43531051540612131b5b1b1d0b5b584b
pwn@ubuntu:~/Desktop$ python enc.py l admin127.0.0.1
01000d000a515b574813441407070748

我们把第一组和第二组数据亦或得到的结果就是（明文部分都是相等的，被约掉了）

(iv_1 \oplus key_1 ) \oplus(iv_2 \oplus key_2)

当然这里的key1和key2并不是真正的key

而这个值肯定是定值，所以我们让在本地加密的admin127.0.0.1再亦或这个值，就可以得到使用服务器的iv和key加密之后的值了

可以验证一下：

pwn@ubuntu:~/Desktop$ python enc.py s admin127.0.0.1
54530c5109070f081812134201515212

In [24]: xor_calc('160011005750464c4b5a4c4b0d0d0d11'.decode('hex'),'43531051540612131b5b1b1d0b5b584b'.decode('hex'))
Out[24]: 'US\x01Q\x03VT_P\x01WV\x06VUZ'

In [25]: t = xor_calc('160011005750464c4b5a4c4b0d0d0d11'.decode('hex'),'43531051540612131b5b1b1d0b5b584b'.decode('hex')) 

In [26]: xor_calc('160011005750464c4b5a4c4b0d0d0d11'.decode('hex'),t)
Out[26]: 'CS\x10QT\x06\x12\x13\x1b[\x1b\x1d\x0b[XK'

In [27]: xor_calc('01000d000a515b574813441407070748'.decode('hex'),t).encode('hex')
Out[27]: '54530c5109070f081812134201515212'

可以看到与服务器的加密结果是一致的。

但是拿到cookie后登上去，会提示你flag是用服务器的key和iv调用encrpyt(“IT’s_Wh3re_MY_De4M0n5_Hid3_###_”)的结果，看wp发现需要拿到服务器的key和iv，可能是用户名不能过长，不能使用之前的方法吧。

然后wp就用sage直接列了个方程解出来了 ？？？？

看了一下，亦或运算是可以化为GF(2)上的加法的，所以就可以直接得出一个线性方程组，就能直接解出来（。

所以当时做不出来可能是被那一堆除了亦或的运算吓到了，很是丢人QAQ。

发表评论

电子邮件地址不会被公开。 必填项已用*标注