0xgame 2024-Crypto-Week 2

[Week 2] Diffie-Hellman

• Diffie-Hellman题目是一个很好的hint，去了解了一下
• 这是一种公钥交换的算法，在A，B两人处各自生成一对密钥（A，a）和（B，b）
• 其中A和B是公钥用来互相间传输的，a和b是私钥，保存在本地
• 然后两人用自己的私钥和对方的公钥就可以生成出S（共享公钥），两人计算出来的S是相同的
• 然后查看题目附件，就是在靶机上生成（A，a），并发送A
• 那本地为了能建立通信，同样也生成（B，b），并发送B。（此处生成过程可以套用附件的函数）
• 此时靶机便会计算出S，继而计算出MD5，并以此用作AES加密的密钥
• 最终输出密文
• 那本地同样用b和A生成S，然后用自带库AES解密密文
• 编写脚本

from string import ascii_letters, digits
from hashlib import sha256
from itertools import product
from Crypto.Cipher import AES
from hashlib import md5
from pwn import *

ip = '118.195.138.159' #要netcat的ip
port = 10000 #端口
io = remote(ip,port)

def proof():
	io.recvuntil(b'XXXX+')
	proof = io.recvuntil(b')')[:-1]
	io.recvuntil(b'== ')
	hash = io.recvuntil(b'\n')[:-1].decode()
	dict = ascii_letters + digits
	for word in product(dict, repeat=4):
		word = ''.join(word).encode()
		if sha256( (word+proof) ).hexdigest() == hash: break
	io.sendlineafter(b'XXXX: ',word)

def MD5(m):return md5( str(m).encode() ).digest()

proof()
q,g = io.recvline().decode()[15:-2].split(", ")
q,g = int(q),int(g)
Bob_PriKey = randint(1, q)
Bob_PubKey = pow(g, Bob_PriKey, q)
Alice_PubKey = int(io.recvline().decode()[15:-1])
print(f"Alice_PubKey={Alice_PubKey}")
io.recvuntil(b"[+] Give me the Bob_PubKey\n>")
io.sendline(str(Bob_PubKey).encode('utf-8'))
io.recvline()
c = io.recvline().decode()[17:-1]
Share_Key = pow(Alice_PubKey,Bob_PriKey,q)
Cipher = AES.new(MD5(Share_Key), AES.MODE_ECB)
m = Cipher.decrypt(bytes.fromhex(c))
print(m.strip(b"\x00"))

• 0xGame{107c7960-d339-48b5-92b9-d59ad5644cf6}

[Week 2] Elgamal

• 本题有关Elgamal数字签名

有关Elgamal数字签名

1. 系统初始化

选择一个大素数$p$p和一个生成元$g$g（通常是$g$g是$p$p的原根）。然后选择一个私钥$x$x，满足 $1<x<p−1$1<x<p−1。公钥由以下元素构成：

• $p$p
• $g$g
• $y = g^xmod\\ p$y=gxmodp

2. 签名生成

要签署消息$m$m，执行以下步骤：

1. 哈希消息：使用安全的哈希函数（如SHA-256）计算消息的哈希值$H(m)$H(m)。
2. 选择随机数：选择一个随机数$k$k，满足$1<k<p−1$1<k<p−1且$k$k与$\\varphi(p) = p-1$varphi(p)=p−1互质。
3. 计算签名：
   • 计算$r = g^k mod\\ p$r=gkmodp。
   • 计算$s = k^{-1} \\cdot (H(m) + x \\cdot r) mod (p-1)$s=k−1cdot(H(m)+xcdotr)mod(p−1)，其中$k^{-1}$k−1是$k$k模$\\varphi(p)$varphi(p)的逆元。

签名为$(r,s)$(r,s)。

3. 签名验证

接受放在接收到消息$m$m和$(r,s)$(r,s)后，可以通过以下步骤验证签名

1. 验证$r$r的有效性：检查$0<r<p$0<r<p和$0<s<p−1$0<s<p−1是否成立。
2. 计算哈希值：计算$H(m)$H(m)
3. 计算验证值：
   • 计算$u\_1=y^rr^smod\\ p$u_1=yrrsmodp。
   • 计算$u\_2=g^mmod\\ p$u_2=gmmodp。
4. 验证签名：如果$u\_1=u\_2\\ mod\\ p$u_1=u_2modp,则签名有效，否则无效。

• 题干有明显提到在验签函数中参数校验出现问题
• 检查发现，$(r,s)$(r,s)是对$q$q取模后的结果
• 然而在验签中并没有校验$r$r和$s$s的大小，也就是说，我可以传入比$q$q大的数
• 这里就存在了伪造签名的可能性
• 然而Elgamal并不是直接对明文加密，而是对其的sha256加密
• 由于目前sha256的不可碰撞性，和无法预知性，并不能推测出伪造明文$m’$m’
• 因而要依据$m$m和$m’$m’的关系进行推算得到$r’$r’和$s’$s’
• 以下为推导过程

$根据验签原理，已知g^mmod\\ p=y^rr^smod\\ p$根据验签原理，已知gmmodp=yrrsmodp

$要构造(m’,r’,s’)满足g^{m’}mod\\ p=y^{r’}r’^{s’}mod\\ p$要构造(m’,r’,s’)满足gm’modp=yr’r’s’modp

$存在关系m’=km\\ mod(p-1)$存在关系m’=kmmod(p−1)

$g^{m’}mod\\ p=g^{km+k'(p-1)}mod\\ p=(g^{km}mod\\ p\\cdot g^{k'(p-1)}mod\\ p)mod\\ p$gm’modp=gkm+k′(p−1)modp=(gkmmodpcdotgk′(p−1)modp)modp

$根据费马小定理a^{\\varphi (p)}mod\\ p=1且gcd(p,1)=1$根据费马小定理avarphi(p)modp=1且gcd(p,1)=1

$\\Rightarrow g^{km}mod\\ p=y^{kr}r^{ks}mod\\ p$Rightarrowgkmmodp=ykrrksmodp

$\\Rightarrow y^{kr+k\_1(p-1)}(r+k\_2p)^{ks}mod\\ p=y^{r’}r’^{s’}mod\\ p$Rightarrowykr+k_1(p−1)(r+k_2p)ksmodp=yr’r’s’modp

$使kr+k\_1(p-1)=r+k\_2p$使kr+k_1(p−1)=r+k_2p

$\\Rightarrow k\_1=(k-1)r\\ mod\\ p$Rightarrowk_1=(k−1)rmodp

\\therefore \\left\\{\\begin{matrix}r’=kr+k\_1(p-1)\\\\s’=ks\\end{matrix}\\right.

• 然后手写脚本，逆元计算k

from string import ascii_letters, digits
from hashlib import sha256
from itertools import product
from Crypto.Util.number import *
from pwn import *

ip = '118.195.138.159' #要netcat的ip
port = 10002 #端口
io = remote(ip,port)

def proof():
	io.recvuntil(b'XXXX+')
	proof = io.recvuntil(b')')[:-1]
	io.recvuntil(b'== ')
	hash = io.recvuntil(b'\n')[:-1].decode()
	dict = ascii_letters + digits
	for word in product(dict, repeat=4):
		word = ''.join(word).encode()
		if sha256( (word+proof) ).hexdigest() == hash: break
	io.sendlineafter(b'XXXX: ',word)

proof()
q,g,y = io.recvline().decode()[23:-2].split(", ")
q,g,y = map(int,[q,g,y])
phi = q-1
msg = bytes.fromhex(io.recvline().decode()[16:-1])
r,s = io.recvline().decode()[28:-2].split(", ")
r,s = map(int,[r,s])
io.recvuntil(b"Now, it's your turn to help me sign something\n[+] Give me your message:\n>")

msg_ = (b'Welcome_to_0xGame2024').hex()
io.sendline(msg_.encode('utf-8'))
msg_ = bytes.fromhex(msg_)
m = int(sha256(msg).hexdigest(),16)
m_ = int(sha256(msg_).hexdigest(),16)
k = m_*inverse(m,(q-1))
s_ = k*s
k1 = (k-1)*r//q+(k-1)*r%q
k2 = (k-1)*r%q
r_ = r+k1*q

io.recvuntil(b"[+] Give me your r:\n>")
io.sendline(str(r_).encode('utf-8'))
io.recvuntil(b"[+] Give me your s:\n>")
io.sendline(str(s_).encode('utf-8'))
io.interactive()

• 0xGame{93e9adb8-8a6d-4517-9c61-13081c413e41}

[Week 2] RC4

• 分析代码发现，在util文件中定义了由密钥KEY生成密钥流keystream
• 以及异或加密
• 用脚本连接靶机通过人机验证

from string import ascii_letters, digits
from hashlib import sha256
from itertools import product
from pwn import *

ip = '118.195.138.159' #要netcat的ip
port = 10001 #端口
io = remote(ip,port)

def proof():
	io.recvuntil(b'XXXX+')
	proof = io.recvuntil(b')')[:-1]
	io.recvuntil(b'== ')
	hash = io.recvuntil(b'\n')[:-1].decode()
	dict = ascii_letters + digits
	for word in product(dict, repeat=4):
		word = ''.join(word).encode()
		if sha256( (word+proof) ).hexdigest() == hash: break
	io.sendlineafter(b'XXXX: ',word)
	
proof()
io.interactive()

• 输入明文获取对应的密文，以及flag的密文
• 注意：因为密钥流是256长度随机生成，所以输入明文必须比flag长，才能计算出加密时使用过的密钥
• 编写脚本计算flag

m = "6162636465666768696a6b6c6d6e6f707172737475767778797a6162636465666768696a6b6c6d6e6f707172737475767778797a"
c = "1c2227967f1f7e60b38d47862cd1bf575075ac29b4108d2a7604e4368cc63b5f8d89d93701d6a26257f97da0952b15a5211d94d9"
enc = "4d380393771c6230ebd114d8728ce70a1730ec6cec5fcb313853e164d992730a8f87d3390cdffe6e59bc6aaf"
KEY = None
def recover_key(plaintext, ciphertext):
    pt_bytes = bytes.fromhex(plaintext)
    ct_bytes = bytes.fromhex(ciphertext)
    keystream = bytes([b1 ^ b2 for b1, b2 in zip(pt_bytes, ct_bytes)])
    return keystream
enc = bytes.fromhex(enc)
keystream = recover_key(m,c)
flag = bytes([b1 ^ b2 for b1, b2 in zip(enc, keystream)])
print(flag)

• 此处的输入我用了[a-zA-Z]
• 最终得到0xGame{81682337-6731-91c7-d060-3efcdfe1ba5f}

[Week 2] RSA-IV

• 都是常见的RSA攻击类型，BUUCTF全刷到过，查看原理以及之前的wp
• 主要不想手动解，便花了点时间用pwntool写了个自动脚本
• challenge1是低加密指数攻击
• challenge2是dp泄露
• challenge3是维纳攻击
• challenge4是共模攻击

from string import ascii_letters, digits
from hashlib import sha256
from itertools import product
from pwn import *
from Crypto.Util.number import *
from RSAwienerHacker import *
import gmpy2

ip = '118.195.138.159' #要netcat的ip
port = 10003 #端口
io = remote(ip,port)

def proof():
	io.recvuntil(b'XXXX+')
	proof = io.recvuntil(b')')[:-1]
	io.recvuntil(b'== ')
	hash = io.recvuntil(b'\n')[:-1].decode()
	dict = ascii_letters + digits
	for word in product(dict, repeat=4):
		word = ''.join(word).encode()
		if sha256( (word+proof) ).hexdigest() == hash: break
	io.sendlineafter(b'XXXX: ',word)

def slove0():
	io.recvuntil(b"[+] input choice:\n>")
	io.sendline(b'0')
	n,e,c = io.recvline().decode()[1:-2].split(', ')
	n,e,c = int(n),int(e),int(c)
	# 低加密指数广播攻击
	io.recvuntil(b">")
	while True:
		if gmpy2.iroot(c,e)[1]:
			m = gmpy2.iroot(c,e)[0]
			print(f"1:{m}")
			break
		c += n
	io.sendline(str(m).encode('utf-8'))
	
def slove1():
	io.recvuntil(b"[+] input choice:\n>")
	io.sendline(b'1')
	n,e,c,dp = io.recvline().decode()[1:-2].split(', ')
	n,e,c,dp = int(n),int(e),int(c),int(dp)
	# dp泄露
	a = dp*e-1
	for x in range(2,e):
		if a%x == 0:
			p = a//x+1
			if n%p == 0:
				q = n//p
				break
	d = inverse(e,(p-1)*(q-1))
	m = pow(c,d,n)
	print(f"2:{m}")
	io.sendline(str(m).encode('utf-8'))

def slove2():
	io.recvuntil(b"[+] input choice:\n>")
	io.sendline(b'2')
	n,e,c = io.recvline().decode()[1:-2].split(', ')
	n,e,c = int(n),int(e),int(c)
	# 维纳攻击
	d = hack_RSA(e,n)
	m = pow(c,d,n)
	print(f"3:{m}")
	io.sendline(str(m).encode('utf-8'))

def slove3():
	io.recvuntil(b"[+] input choice:\n>")
	io.sendline(b'3')
	n,e,c,e_,c_ = io.recvline().decode()[1:-2].split(', ')
	n,e1,c1,e2,c2 = int(n),int(e),int(c),int(e_),int(c_)
	# 共模攻击
	e1_e2=e1-e2
	s1 = inverse(e1_e2,e2)
	s2 = (1-e1*s1)//e2
	m = pow(c1,s1,n)*pow(c2,s2,n)%n
	print(f"4:{m}")
	io.sendline(str(m).encode('utf-8'))
	
proof()
slove0()
slove1()
slove2()
slove3()
io.interactive()

• 最后拿到0xGame{2b5e024a-3c62-4f4a-afe0-b81851d9efc8}

[Week 2] LFSR-baby

• LFSR是指线性(Linear)反馈(Feedback)移位(Shift)寄存器(Register)
• 即有一个可移动的寄存器，通过反馈计算出下一个移动的数值，而其计算方式是线性的
• 分析源码得到存在一个mask固定窗口和state滑动窗口，最初始的state即为seed
• 两个列表中的二进制对应按位与运算，将所有结果异或保存至output
• output即为生成的随机数，存入getrandbits函数中的result末尾
• 将output存入state末尾，使窗口向后滑动一位
• 继续反复操作，不断生成随机数
• 注意到题目给的随机数是生成128位后的结果
• 因此可以判断，一组随机数生成后正好完全将原先128位的seed从state变量中顶出

• 如图，假设这是最后一次生成随机数，计算时的mask是1128，state是0127，上下同列的按位与运算，再异或，存入state的末尾（128）最终红色框内的128位数就是最终输出的随机数
• 也就是说，可以通过脚本算出state中0位置是什么，然后再反复使用这种方式计算出原来完整的128位seed
• 下面编写脚本

from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()

def init_state(seed):
    result = [int(i) for i in bin(seed)[2:]]
    PadLenth = 128 - len(result)
    result += [ 0 ] * PadLenth
    assert len(result) == 128
    return result

def init_random(seed):
    result = [int(i) for i in bin(seed)[2:]]
    PadLenth = 128 - len(result)
    result = [ 0 ] * PadLenth + result
    assert len(result) == 128
    return result

random1 = 103763907686833223776774671653901476306
copy = random1
random2 = 136523407741230013545146835206624093442
Mask_seed = 245818399386224174743537177607796459213
random1,random2 = map(init_random,[random1,random2])
mask = init_state(Mask_seed)

def calc(state):
    for i in range(128):
        output = 0
        for i in range(1,128):
            output += state[i-1]*mask[i]
        output += state[-1]
        output = output%2
        state = [output] + state[:-1]
    return state
result = int(''.join(str(x) for x in calc(random2)),2) == copy
print(f"The calculation is {result}")
print("0xGame{"+MD5(int(''.join(str(x) for x in calc(random1)),2))+"}")

• 代码中要注意随机数的长度并没有128位要手动补零，同时是在开头补，而不是调用源码的方法
• 另外可以用第二个随机数来检验算法是否正确
• 运行得到0xGame{030ec00de18ceb4ddea5f6612d28bf39}

[Week 2] LFSR-easy

• 这题是依据种子和随机数倒推掩码
• mask用$x\_1~x\_128$x_1 x_128表示
• seed用$s\_1~s\_128$s_1 s_128表示
• random用$x\_129~x\_256$x_129 x_256表示
• 可以得到如下的计算式

\\sum\_{i=1}^{128} s\_{i+n}x\_i\\ mod\\ 2=s\_{129+n}m\\ ,\\ n\\in \[0,128\]

• 因此可以写出在Zmod 2数域下的矩阵

\\begin{bmatrix} s\_{1} & \\dots & s\_{128}\\\\ \\dots & \\dots & \\dots\\\\ s\_{128} & \\dots & s\_{255}\\end{bmatrix}\\begin{bmatrix} s\_{129}\\\\ \\dots\\\\ s\_{256}\\end{bmatrix}

• 用Sage编写脚本计算解

from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()

def init_state(seed):
    result = [int(i) for i in bin(seed)[2:]]
    PadLenth = 128 - len(result)
    result += [ 0 ] * PadLenth
    assert len(result) == 128
    return result

def init_random(seed):
    result = [int(i) for i in bin(seed)[2:]]
    PadLenth = 128 - len(result)
    result = [ 0 ] * PadLenth + result
    assert len(result) == 128
    return result

random1 = 299913606793279087601607783679841106505
random2 = 192457791072277356149547266972735354901
seed = 165943427582675380464843619836793254673
random1,random2 = map(init_random,[random1,random2])
seed = init_state(seed)

def solve_GF2_linear_system(A, b):
    """
    使用 SageMath 在 GF(2) 上求解线性方程组 Ax = b
    :param A: 系数矩阵
    :param b: 结果向量
    :return: 解向量 x
    """
    F = GF(2)
    A_GF2 = Matrix(F, A)
    b_GF2 = vector(F, b)

    try:
        x = A_GF2.solve_right(b_GF2)
        return x
    except ValueError:
        return None

def solution(m):
    a,b = m[0],m[1]
    solution = solve_GF2_linear_system(a, b)
    if solution:
        print(f"解向量为: {solution}")
        return solution
    else:
        print("无解")
        return None

def change(seed,random):
    All = seed + random
    a = [[0]*128 for _ in range(128)]
    b = random
    for i in range(128):
        a[i] = All[i:i+128]
    return (a,b)

ans1 = solution(change(seed,random1))
ans2 = solution(change(random1,random2))
print("The calculation is ",ans1 == ans2)
if ans1 == ans2:
    print("0xGame{"+MD5(int("".join(str(i) for i in ans1),2))+"}")

• 解出0xGame{d56821feacab64cdb87c754ad06823a2}