强网杯
Crypto300：
这题其实是改了2017年国赛mailbox的，相当mailbox2吧，只是绕过ElGamal的方式不一样吧，mailbox i春秋上有复现，官方也有WP
首先分析程序:
class HandleCheckin(SocketServer.StreamRequestHandler):
def handle(self):
Random.atfork()
req = self.request
proof = b64.b64encode(os.urandom(12)) #产生12位的随机字符
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''')
我们需要生成一个以proof开头的长度为proof长度加5的字符串，并且其sha1的值以16比特的0结束。
这里我们直接使用如下的方式来绕过。
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，这是一个利用给定字符集合以及指定长度进行多线程爆破的函数。其中，第一个参数为爆破函数，这里是sha1，第二个参数是字符集，第三个参数是字节数，第四个参数指的是我们只尝试字节数为第三个参数指定字节数的排列，即长度是固定的。更加具体的信息请参考pwntools。
绕过之后，我们继续分析程序，简单看下generate_keys函数，可以知道该函数是ElGamal生成公钥的过程，然后看了看verify函数，就是验证签名的过程。
继续分析
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会自动生成p,g,pk，我们需要输入一串base64加密的信息，然后再输入数字签名，程序通过验证函数verify判断是否满足条件，如果满足的话就输出flag，不满足就不行
根据条件可以知道的是:
- 自己提供msg和数字签名
- 输入的msg需要先用base64编码
- msg的长度大于6，msg的比特位<10的5次方，小于MSGLENGTH = 40000
- 数字签名需要用,隔开
接下来看验证函数：
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
这里我后来查了一下，是一种ElGamal签名的验证方法
ElGamal签名
验证算法
可以看到这里的验证方法跟题目中的verify函数几乎是一致的，给出的p,g,pk也就是上图中的p,g,y,验证(pow(pk, r, p) * pow(r, s, p)) % p == pow(g, m, p)也就是上面的验证方法
那么知道题目的验证是什么方法，我们应该怎么绕过呢，这里与国赛的mailbox就不一样了，国赛的是给了签名的，所以是选择签名伪造，但是这里是自己提供message和签名的，有一种攻击ElGamal的方法叫做通用伪造签名
大概意思就是自己通过伪造能通过验证的message和签名，那么根据上面写脚本（图中j的-1这里表示求j关于p-1的乘法逆元）
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): #使m长度为偶数，不然编码十六进制的时候会出现错误
return len(m) % 2 == 1 and '0' + m or m
e = getRandomRange(2,p-1) #获得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)
msg_base64=base64.b64encode(makeodd(hex(msg)[2:].rstrip('L').decode('hex')))
这样我们就得到了能绕过验证的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会出现错误，使得username无法输入
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
