0xgame 2024-Crypto-Week 2
|
|
646
|
0
|
CTF

[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$和一个生成元$g$（通常是$g$是$p$的原根）。然后选择一个私钥$x$，满足 $1<x<p−1$。公钥由以下元素构成：

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

2. 签名生成

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

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

签名为$(r,s)$。

3. 签名验证

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

  1. 验证$r$的有效性：检查$0<r<p$和$0<s<p−1$是否成立。
  2. 计算哈希值：计算$H(m)$
  3. 计算验证值：
    • 计算$u_1=y^rr^smod\ p$。
    • 计算$u_2=g^mmod\ p$。
  4. 验证签名：如果$u_1=u_2\ mod\ p$,则签名有效，否则无效。
  • 题干有明显提到在验签函数中参数校验出现问题
  • 检查发现，$(r,s)$是对$q$取模后的结果
  • 然而在验签中并没有校验$r$和$s$的大小，也就是说，我可以传入比$q$大的数
  • 这里就存在了伪造签名的可能性
  • 然而Elgamal并不是直接对明文加密，而是对其的sha256加密
  • 由于目前sha256的不可碰撞性，和无法预知性，并不能推测出伪造明文$m’$
  • 因而要依据$m$和$m’$的关系进行推算得到$r’$和$s’$
  • 以下为推导过程

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

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

$$存在关系m’=km\ mod(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$$

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

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

$$\Rightarrow y^{kr+k_1(p-1)}(r+k_2p)^{ks}mod\ p=y^{r’}r’^{s’}mod\ p$$

$$使kr+k_1(p-1)=r+k_2p$$

$$\Rightarrow k_1=(k-1)r\ mod\ p$$

$$\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是1~128，state是0~127，上下同列的按位与运算，再异或，存入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$表示
  • seed用$s_1~s_128$表示
  • random用$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}

0xGameCryptoWriteUp
暂无评论

发送评论 编辑评论

























|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!



上一篇
下一篇