強(qiáng)網(wǎng)杯

Crypto300：

這題其實(shí)是改了2017年國(guó)賽mailbox的，相當(dāng)mailbox2吧，只是繞過(guò)ElGamal的方式不一樣吧，mailbox i春秋上有復(fù)現(xiàn)，官方也有WP

首先分析程序:

class HandleCheckin(SocketServer.StreamRequestHandler):
    def handle(self):
        Random.atfork()
        req = self.request
        proof = b64.b64encode(os.urandom(12))  #產(chǎn)生12位的隨機(jī)字符

        req.sendall(
            "Please provide your proof of work, a sha1 sum ending in 16 bit's set to 0, it must be of length %d bytes, starting with %s\n" % (
            len(proof) + 5, proof))

        test = req.recv(21)  #輸入的字符
        ha = hashlib.sha1()
        ha.update(test)

        if (test[0:16] != proof or ord(ha.digest()[-1]) != 0 or ord(ha.digest()[-2]) != 0): # or ord(ha.digest()[-3]) != 0 or ord(ha.digest()[-4]) != 0):
            req.sendall("Check failed")
            req.close()
            return
        req.sendall('''=== Welcome to Overwatch Mailbox Login Portal v2.0 ===
                        [Notice] As pointed out recently by Dr. Winston, username/password style authentication apparently becomes old-fashioned.
                        We've introduced new signature-based auth system. To login in, please input your username and your signature.

                        [Notice] You have only one chance to log-in.\n\n''')

我們需要生成一個(gè)以proof開(kāi)頭的長(zhǎng)度為proof長(zhǎng)度加5的字符串，并且其sha1的值以16比特的0結(jié)束。

這里我們直接使用如下的方式來(lái)繞過(guò)。

def f(x):
    return sha1(prefix + x).digest()[-2:] == '\0\0'


sh = remote('117.50.6.36', 20014)
# bypass proof
sh.recvuntil('starting with ')
prefix = sh.recvuntil('\n', drop=True)
print string.ascii_letters
s = util.iters.mbruteforce(f, string.ascii_letters + string.digits, 5, 'fixed')
test = prefix + s
sh.send(test)

這里使用了pwntools中的util.iters.mbruteforce，這是一個(gè)利用給定字符集合以及指定長(zhǎng)度進(jìn)行多線(xiàn)程爆破的函數(shù)。其中，第一個(gè)參數(shù)為爆破函數(shù)，這里是sha1，第二個(gè)參數(shù)是字符集，第三個(gè)參數(shù)是字節(jié)數(shù)，第四個(gè)參數(shù)指的是我們只嘗試字節(jié)數(shù)為第三個(gè)參數(shù)指定字節(jié)數(shù)的排列，即長(zhǎng)度是固定的。更加具體的信息請(qǐng)參考pwntools。

繞過(guò)之后，我們繼續(xù)分析程序，簡(jiǎn)單看下generate_keys函數(shù)，可以知道該函數(shù)是ElGamal生成公鑰的過(guò)程，然后看了看verify函數(shù)，就是驗(yàn)證簽名的過(guò)程。

繼續(xù)分析

        req.sendall("Generating keys...\nDispatching keys to corresponding owners...\n")
        pk, sk, g, p = generate_keys()
        req.sendall("Current PK we are using: %s\n" % repr([p, g, pk]))
        print sk, pk, g, p

        for it in range(1):
            req.sendall("Username:")
            msg = self.rfile.readline().strip().decode('base64')
            print 'we got', repr(msg), digitalize(msg)

            if len(msg) < 6 or digitalize(msg) < 1e5 or len(msg) > MSGLENGTH:
                req.sendall("what r u do'in?")
                req.close()
                return
            req.sendall("Signature:")
            sig = self.rfile.readline().strip() #簽名
            print 'we got', repr(sig)
            if len(sig) > MSGLENGTH:
                    req.sendall("what r u do'in?")
                    req.close()
                    return
            sig_rs = sig.split(",")
            if len(sig_rs) < 2:
                    req.sendall("yo what?")
                    req.close()
                    return

            # print "Got sig", sig_rs
            if verify(digitalize(msg), int(sig_rs[0]), int(sig_rs[1]), pk, p, g):
                    req.sendall("Login Success.\nDr. Ziegler has a message for you: " + FLAG)
                    print "shipped flag"
                    req.close()
                    return
             else:
                    req.sendall("You are not the Genji I knew!\n")

這里大概的意思就是generate_keys會(huì)自動(dòng)生成p,g,pk，我們需要輸入一串base64加密的信息，然后再輸入數(shù)字簽名，程序通過(guò)驗(yàn)證函數(shù)verify判斷是否滿(mǎn)足條件，如果滿(mǎn)足的話(huà)就輸出flag，不滿(mǎn)足就不行
根據(jù)條件可以知道的是:

• 自己提供msg和數(shù)字簽名
• 輸入的msg需要先用base64編碼
• msg的長(zhǎng)度大于6，msg的比特位<10的5次方，小于MSGLENGTH = 40000
• 數(shù)字簽名需要用,隔開(kāi)

接下來(lái)看驗(yàn)證函數(shù)：

    def verify(m, r, s, pk, p, g):
        if r < 1 or r >= p or s < 1 or s >= p-1: return False
        if (r + s) % (p-1) == 0: return False  # Simple forgery won't work!
        if (pow(pk, r, p) * pow(r, s, p)) % p == pow(g, m, p):
            return True
        return False

這里我后來(lái)查了一下，是一種ElGamal簽名的驗(yàn)證方法

ElGamal簽名

驗(yàn)證算法

可以看到這里的驗(yàn)證方法跟題目中的verify函數(shù)幾乎是一致的，給出的p,g,pk也就是上圖中的p,g,y,驗(yàn)證(pow(pk, r, p) * pow(r, s, p)) % p == pow(g, m, p)也就是上面的驗(yàn)證方法

那么知道題目的驗(yàn)證是什么方法，我們應(yīng)該怎么繞過(guò)呢，這里與國(guó)賽的mailbox就不一樣了，國(guó)賽的是給了簽名的，所以是選擇簽名偽造，但是這里是自己提供message和簽名的，有一種攻擊ElGamal的方法叫做通用偽造簽名

大概意思就是自己通過(guò)偽造能通過(guò)驗(yàn)證的message和簽名，那么根據(jù)上面寫(xiě)腳本（圖中j的-1這里表示求j關(guān)于p-1的乘法逆元）

def mul_inv(a,b):  #用擴(kuò)展歐幾里得求乘法逆元
    b0 = b
    x0,x1=0,1
    if b ==1:return 1
    while a> 1:
        q =a / b
        a,b = b, a% b
        x0,x1 = x1 - q * x0,x0
    if x1 < 0 : x1 += b0
    return x1

def makeodd(m):   #使m長(zhǎng)度為偶數(shù)，不然編碼十六進(jìn)制的時(shí)候會(huì)出現(xiàn)錯(cuò)誤
    return len(m) % 2 == 1 and '0' + m or m

e = getRandomRange(2,p-1)  #獲得2，p-1之間的隨機(jī)整數(shù)
v = getRandomRange(2,p-1)
while gmpy2.gcd(v,p-1) != 1 :
    v = getRandomRange(2,p-1)
r = gmpy2.powmod(g,e,p) * gmpy2.powmod(pk,v,p) % p
s = (-r * mul_inv(v,p-1)) % (p-1)
if s <0:
    s += p-1
msg=e * s % (p-1)
msg_base64=base64.b64encode(makeodd(hex(msg)[2:].rstrip('L').decode('hex')))

這樣我們就得到了能繞過(guò)驗(yàn)證的message和簽名

最終腳本：

from pwn import *
from hashlib import sha1
import string
from Crypto import Random
from Crypto.Util.number import *
import gmpy2
import base64
def f(x):
    return sha1(prefix + x).digest()[-2:] == '\0\0'


sh = remote('117.50.6.36', 20014)
# bypass proof
sh.recvuntil('starting with ')
prefix = sh.recvuntil('\n', drop=True)
print string.ascii_letters
s = util.iters.mbruteforce(f, string.ascii_letters + string.digits, 5, 'fixed')
test = prefix + s
sh.send(test)  #這里用sendline會(huì)出現(xiàn)錯(cuò)誤，使得username無(wú)法輸入

print sh.recv()
print sh.recv()
PK= sh.recv() #PK
#print PK
p=int(PK.split()[5][1:-2])
g=int(PK.split()[6][:-2])
pk=int(PK.split()[7][:-2])


def mul_inv(a,b):
    b0 = b
    x0,x1=0,1
    if b ==1:return 1
    while a> 1:
        q =a / b
        a,b = b, a% b
        x0,x1 = x1 - q * x0,x0
    if x1 < 0 : x1 += b0
    return x1

def makeodd(m):
    return len(m) % 2 == 1 and '0' + m or m
e = getRandomRange(2,p-1)
v = getRandomRange(2,p-1)
while gmpy2.gcd(v,p-1) != 1 :
    v = getRandomRange(2,p-1)
r = gmpy2.powmod(g,e,p) * gmpy2.powmod(pk,v,p) % p
s = (-r * mul_inv(v,p-1)) % (p-1)
if s <0:
    s += p-1
msg=e * s % (p-1)
#print "msg : ",msg
#print makeodd(hex(msg)[2:].rstrip('L').decode('hex'))
msg_base64=base64.b64encode(makeodd(hex(msg)[2:].rstrip('L').decode('hex')))


print sh.recvuntil('Username:')
sh.sendline(msg_base64)
print sh.recvuntil('Signature:')
#print str(r)+","+str(s)
sh.sendline(str(r)+","+str(s))
print sh.recv()
# sh.close()

得到flag