0xgame 2024-Crypto-Week 3
|
|
149
|
0
|
CTF

[Week 3] ECC-DH

ECDH 算法的工作流程：

  1. 椭圆曲线选择：
    • 首先，双方需要选定一条公共的椭圆曲线。椭圆曲线可以用方程 $y^2 = x^3 + ax + b \mod p$表示，其中 $a$、$b$ 是曲线参数，$p$ 是素数，用于定义有限域上的曲线。
    • 在这条曲线上，双方还需要选定一个公共点 $G$，称为基点。基点是椭圆曲线上的一个已知点，通信双方将用它来生成密钥。
  2. 密钥生成：
    • Alice 随机生成一个私钥 $a$，这个私钥是一个整数。
      • 她计算对应的公钥 $A = a \cdot G$，这里的点乘是椭圆曲线点的标量乘法（多次加法运算）。
    • Bob 也生成一个随机的私钥 $b$，并计算出对应的公钥 $B = b \cdot G$。
  3. 公钥交换：
    • Alice 将她的公钥 $A$ 发送给 Bob，Bob 将他的公钥 $B$ 发送给 Alice。
  4. 共享密钥计算：
    • Alice 使用她的私钥 $a$ 和 Bob 的公钥 $B$ 计算共享密钥：
      $S = a \cdot B = a \cdot (b \cdot G) = (a \cdot b) \cdot G$
    • Bob 使用他的私钥 $b$ 和 Alice 的公钥 $A$ 计算共享密钥：
      $S = b \cdot A = b \cdot (a \cdot G) = (b \cdot a) \cdot G$
    • 由于点乘是交换的，Alice 和 Bob 最终计算得到相同的共享密钥 $S$。
  • 很好理解啊，不涉及比较难的数学知识，只要搞懂原理就行，也用会算
  • 和[Week 2] Diffie-Hellman逻辑上几乎一样，就是本地生成私钥和公钥，然后与靶机交互确定共享公钥
  • 最终用AES对称加密来传输数据
  • 上代码
from hashlib import md5, sha256
from itertools import product
from string import ascii_letters, digits
from Crypto.Cipher import AES
from pwn import *
from Util import *

addr = "nc 118.195.138.159 10004".split(" ")
io = remote(addr[1],int(addr[2]))

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

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()

a = 10809567548006703521
b = 9981694937346749887
p = 25321837821840919771
E = Curve(a, b, p)
g_x,g_y = map(int,io.recvline().decode()[15:-2].split(","))
a_x,a_y = map(int,io.recvline().decode()[20:-2].split(","))
G = Point(g_x,g_y,E)
A = Point(a_x,a_y,E)
b = randint(1, p)
B = b * G
io.sendlineafter(b"[+] Give me the Bob_PubKey.x\n>",str(B.x).encode('utf-8'))
Share_Key = b * A
Cipher = AES.new(MD5(Share_Key.x), AES.MODE_ECB)
io.recvline()
c = bytes.fromhex(io.recvline().decode()[21:-1])
m = Cipher.decrypt(c)
print(m)
io.interactive()
  • 0xGame{71234da9-baf8-406e-9cc7-d08ceedea945}

[Week 3] ECC-baby

  • ECC加密用来交换对称密钥
  • 可以发现素数p不是太大，于是尝试暴力计算key或k
  • 实测k和key都能爆出来
  • Sage脚本：Baby-step Giant-step 算法求解 ECDLP
# Sage 环境
def baby_step_giant_step(E, G, P, n):
    """
    Baby-step Giant-step 算法求解椭圆曲线离散对数问题
    E: 椭圆曲线
    G: 基点
    P: 已知点 P = k * G
    n: 椭圆曲线的阶
    """
    m = ceil(sqrt(n))
    
    # Step 1: Baby-step, 计算表 {i: i*G} for i = 0, 1, ..., m-1
    baby_steps = {}
    for i in range(m):
        baby_steps[i * G] = i
    
    # Step 2: Giant-step, 计算 j * (-m * G)
    inv_mG = -m * G
    current = P
    
    for j in range(m):
        if current in baby_steps:
            return j * m + baby_steps[current]
        current += inv_mG
    
    # 如果没有找到解，返回None
    return None


# 椭圆曲线参数
p = 4559252311 # 椭圆曲线的素数域
a = 1750153947 # 椭圆曲线参数 a
b = 3464736227 # 椭圆曲线参数 b
E = EllipticCurve(GF(p), [a, b]) # 定义椭圆曲线

# 基点 G 和已知点 P = k * G
G = E(2909007728, 1842489211)
P = E(1923527223,2181389961)

# 椭圆曲线的阶
n = E.order()

# 使用 Baby-step Giant-step 求解 k
key = baby_step_giant_step(E, G, P, n)
if k is not None:
    print(f"Found key: {key}")
else:
    print("No solution found.")
  • 得到key = 1670419487
  • 然后用内置的点乘计算$P = G’ \cdot key$
  • 再进行逆运算$M = C + ( – P’)$
  • 又可以根据定义可以知道$−Q=(x_Q​,−y_Q​mod\ p)$
  • 所以搓脚本
from hashlib import md5
from Crypto.Cipher import AES
from Util import *

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

p = 4559252311
a = 1750153947
b = 3464736227
curve = Curve(a, b, p)
G = Point(2909007728,1842489211,curve)
P = Point(1923527223,2181389961,curve)
G_= Point(1349689070,1217312018,curve)
C = Point( 662346568,2640798701,curve)
enc= bytes.fromhex("29bb47e013bd91760b9750f90630d8ef82130596d56121dc101c631dd5d88201a41eb3baa5aa958a6cd082298fc18418")
key = 1670419487
P_ = G_*key
M = C + Point(P_.x,(-P_.y)%p,curve)
Cipher = AES.new(MD5(M.x), AES.MODE_ECB)
m = Cipher.decrypt(enc)
print(m)
  • 0xGame{0b0e28c2-b36d-d745-c0be-fcf0986f316a}

[Week 3] EzLogin-I

  • 分析源码，要使输入的cookie能被正确解析为{“username”: “admin”, “time”: ……}才能得到flag
  • 分析发现对输入转化为json然后进行了AES.CBC加密，再以Base64输出
  • 可以利用CBC加密特性，字节翻转攻击，定向改变某个解析后的明文
  • 下面引用CBC加密和解密的图示
  • 下面是反转攻击示例
  • 由于C=B⊕A，可以特定改变A，使C变成想要的指定字符C’
  • 推导得A’=A⊕C⊕C’
  • 但要注意的是，虽然C被指定改变，但A的改变会影响到整段第一明文的变化
  • 而json是格式固定的，也就意味着只能修改通过修改IV来修改第一明文，而无法改变第二明文
  • 构造payload
from base64 import b64decode, b64encode
from pwn import *


addr = "nc 118.195.138.159 10005".split(" ")
io = remote(addr[1],int(addr[2]))

io.sendlineafter('''+--------------+
| [R] Regist   |
| [L] Login    |
| [F] Getflag  |
+--------------+

[+] Tell me your choice:
>''',b"R")
io.sendlineafter("[+] username:\n>",b"zdmin")
base64en = io.recvline().decode()[13:]
base64de = bytearray(b64decode(base64en))
base64de[14] = base64de[14] ^ ord("z") ^ ord("a")
fake_cookie = b64encode(bytes(base64de))
io.sendlineafter("[+] Tell me your choice:\n>",b"L")
io.sendlineafter("[+] cookie:\n>",fake_cookie)
io.interactive()
  • 0xGame{ad34acff-a813-4bc3-a44a-c270edf244b7}

[Week 3] EzLogin-II

  • 在CBC加密的基础上，由于是分块处理，所以要对不能成块的部分进行填充
  • 这里填充通常采用的是PKCS#7的标准进行填充，即填充字符个数与填充值相同，并且必须填充
  • 如1234→1234\0x04\0x04\0x04\0x04
  • 或12345678→12345678\0x08\0x08\0x08\0x08\0x08\0x08\0x08\0x08
  • (上述是对于8个字节分块的情况举例)
  • 下面讲述Padding Oracle Attack（或者CTF Wiki会比我更详细）
  • 参考上一题的解密方式能发现
  • 由于Block i在经过key解密后要和Block i-1异或得到Plaintxt
  • 也就是说可以改变Block i-1的值来改变Plaintxt的结果，这都是上一题已知的
  • 这题由于对明文脱padding的方法unpad中有Unpad error的报错
  • 可以通过构造Block i-1的最后一个字节使得Plaintxt中的最后一个字节为\0x01
  • 可以发现这样是不会报错的，而其他不正确的填充则会报错
  • 所以可以通过靶机的回显来判断构造是否正确，从而得到正确明文（已知假明文，假IV可以推出中间值，与真IV异或后得到真明文）
  • 然后再对倒数第二个字节同样方式爆破
  • 注意：这里要保证爆破字节以外的字节满足假明文为\0x02
  • 明白原理后就可以手搓脚本了
from base64 import b64decode, b64encode
from pwn import *

addr = "nc 118.195.138.159 10005".split(" ")
io = remote(addr[1], int(addr[2]))

io.sendlineafter('''+--------------+
| [R] Regist   |
| [L] Login    |
| [F] Getflag  |
+--------------+

[+] Tell me your choice:
>''', b"F")
base = io.recvline().decode()[20:]
enc = b64decode(base)
io.sendlineafter("[+] Tell me your choice:\n>", b"L")

alpha = [4]

for i in "0123456789abcdef-}{xGame":
    alpha += [ord(i)]

def padding_oracle_attack(ciphertext):
    # 分块
    blocks = [ciphertext[i:i + 16] for i in range(0, len(ciphertext), 16)]
    decrypt = []
    for block_index in range(1,len(blocks))[::-1]:
        # 构造IV和密文块
        current_block = blocks[block_index]
        iv = blocks[block_index-1]
        fake_iv = bytearray(iv)
        # 遍历IV块
        for attack_index in range(1,17):
            # 伪造IV块中先前值
            for change_index in range(1,attack_index):
                fake_iv[-change_index] = fake_iv[-change_index] ^ (attack_index-1) ^ attack_index
            # 遍历字节值
            for bytes_value in range(1,256):
                fake_iv[-attack_index] = bytes_value
                print(f"尝试: bytes_value: {bytes_value:3}, fake_iv: {fake_iv.hex()}")
                print(f"已得: {decrypt}\n")
                if sendtest(fake_iv + current_block):
                    if (attack_index ^ bytes_value ^ iv[-attack_index]) in alpha:
                        decrypt += [attack_index ^ bytes_value ^ iv[-attack_index]]
                        break
    return "".join([chr(i) for i in decrypt])

def sendtest(modified_ciphertext):
    # 测试靶机响应
    encoded_ciphertext = b64encode(modified_ciphertext).decode()
    io.sendlineafter("[+] cookie:\n>", encoded_ciphertext)
    resp = io.recvline().decode()
    print("响应:", resp[:-1])
    return resp != "[!] Unkown Wrong\n"

# 执行 padding oracle 攻击
decrypted = padding_oracle_attack(enc)[::-1]
print("解密结果: ", decrypted)
io.close()

注意几个点

  1. 原码在经过unpad之后有decode的处理，所以说不能转化为字符的字节同样会引发Unkown Wrong的报错，所以构造IV的时候不要用随机值或者全0填充
  2. 由于直接认定flag是uuid格式并且是由\0x04填充的，所以可以写入alpha，来避免其他同样可能满足不报错的可能性。（正常来说对于末尾字节会有多种可能，若当前可能无法继续往下爆破的时候，需要代码处理好回退操作。）
  3. 靶机测试响应中，有可能会成功json load从而触发TypeError Wrong报错，因此直接判断是否为Unkown Wrong即可
  • 0xGame{6e02937e-634d-4f6f-8ef6-e5f387006cde}

大佬的解法

速度很快，用了明文攻击，来自三顺七

from pwn import *
from base64 import b64encode, b64decode
from time import time
#context(log_level = 'debug')

s = time()
xor = lambda a, b: bytes([x^y for x, y in zip(a, b)])

io = remote('118.195.138.159', 10005)

io.sendlineafter(b'>', b'R')
io.sendlineafter(b'>', b'Admin')
io.recvuntil(b'[+] cookie : ')
cookie = io.recvline()[:-1]

prefix = b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\x00'
cookie = xor(b64decode(cookie), prefix) + b64decode(cookie)[16:]
io.sendlineafter(b'>', b'L')
io.sendlineafter(b'>', b64encode(cookie))
print(io.recvline().decode())


def Send(payload):
	io.sendlineafter(b'>', b64encode(payload))
	result = io.recvline()
	#print(result)
	if result == b'[!] Unkown Wrong\n':
		return 0
	elif result == b'[!] JSON Wrong\n':
		return 1
	elif result == b'[!] TypeError Wrong\n':
		return 1

def PaddingOracle(before,after):
	d_iv = [0 for _ in range(16)]
	dict = list(b'0123456789abcdef{}xGame-') + [i for i in range(2, 16)]
	print(f'dict = {dict}')
	for i in range(1, 17):
		flag = 1
		Pad = [0 for _ in range(17-i)]
		if i == 1:
			Index = []
		else:
			Index = [i for _ in range(i-1)]
		Prefix = Pad + Index

		for j in dict:
			d_iv[-i] = j ^ i
			IV = bytes(xor(xor(before,d_iv), Prefix))
			payload = IV + after
			result = Send(payload)

			if result == 1:
				d_iv[-i] = j
				flag = 0
				print(i, d_iv)
				break

		if flag == 1:
			for j in dict[::-1]:
				d_iv[-(i-1)] = j ^ i
				IV = bytes(xor(xor(before,d_iv), Prefix))
				payload = IV + after
				result = Send(payload)

				if result == 1:
					d_iv[-(i-1)] = j
					print(i, d_iv)
					break

			for j in dict:
				d_iv[-i] = j ^ i
				IV = bytes(xor(xor(before,d_iv), Prefix))
				payload = IV + after
				result = Send(payload)

				if result == 1:
					d_iv[-i] = j
					flag = 0
					print(i, d_iv)
					break

	return bytes(d_iv)

def Oracle():
	io.sendlineafter(b'>', b'F')
	io.recvuntil(b'[+] Here is flag2 : ')
	enc = io.recvline()
	print(enc)
	msg = b64decode(enc)
	io.sendlineafter(b'>', b'L')
	result = b''
	BlockLength = len(msg)//16
	print(f'[+] BlockLength = {BlockLength}')
	Block = [msg[16 * i: 16 * (i+1)] for i in range(BlockLength)]
	for i in range(0,BlockLength - 1):
		print(f'[x] Procing BlockIndex : {i}')
		result += PaddingOracle(Block[i], Block[i+1])
	return result

flag2 = Oracle()
print(flag2)
io.close()
e = time()
print(f'[+] Cost : {e-s}')

[Week 3] LLL-I

关于格的一些大佬讲解-链接–链接

  • 原理比较难搞（我不会
  • 题干说LLL算法出来就行，所以写如下sage
from sage.all import *

B = Matrix(ZZ, [[1849784703482951012865152264025674575, 2664848085955925754350117767673627932, 2099783527396520151610274180590854166, 1020558595577301617108111920545804527],
                   [1207449566811121614020334020195802372, 1954621976999112878661150903673543232, 1326050406731534201574943690688237338, 1361813208094227445768111591959011963],
                   [888810907577479776819993141014777624 , 1216302736807928240875874427765340645, 1027359437421599069599327712873719567, 238961447144792739830554790892164336 ],
                   [60622164517940943037274386912282     , 82958508138755168576836012717468     , 70072118066826856564329627650828     , 16296740862142507745322242235326     ]])
print(B.LLL())
  • 由于flag混入在第一行，得到矩阵后取第一行，无视正负就是flag
  • （由于LLL算出来的是最短基向量，而正负不会影响最短的特性）
  • 脚本
from Crypto.Util.number import *
c = [ -58596440058654765094286903,  -69377248846131264731819316,  -60910008503494441471652194,  -58497746791226042414948989]
print("".join([(long_to_bytes(abs(i))).decode() for i in c]))
  • 0xGame{04679c42-2bc1-42b2-b836-1b0ca542f36b}

后续补充的原理

  • $CM=S$由于$||M||=1$可以认为$C$与$S$是等价的
  • 而又由于$C$是随机生成的其施密特正交化程度几乎可以认为是最高–随机矩阵正交性的证明
  • 因此对$S$进行LLL算法求其等价正交格基就等于求$C$

[Week 3] LLL-II

参考HNP讲解

  • 基于LCG的生成规律$X_{n+1}=aX_n+b\ mod\ m$
  • 已知如下式子

$$\left\{\begin{align} Cs[0]&=a*seed\ mod\ m\\ Cs[1]&=a*Cs[0]+b_1\ mod\ m\\ Cs[i]&=a*Cs[i-1]+b_i\ mod\ m\\ b_i&=Cs[i]-a*Cs[i-1]+k_i*m\\ \end{align}\right.$$

  • 然后构造格

$$\begin{array}\ (k_1&k_2&k_3&k_4&-a&1) \left[\matrix{ m&0&0&0&0&0\\ 0&m&0&0&0&0\\ 0&0&m&0&0&0\\ 0&0&0&m&0&0\\ Cs[0]&Cs[1]&Cs[2]&Cs[3]&K/n&0\\ Cs[1]&Cs[2]&Cs[3]&Cs[4]&0&K } \right] = (b_1&b_2&b_3&b_4&K\cdot a/m&K) \end{array}$$

  • 其中$K$是$b_i$的估计值令$K=2^{128}$
  • 然后就可以根据构造的格，来用sage求解
from Crypto.Util.number import *

cs = [
    11804527453299586684489593808016317337345238230165321056832279785591503368758306671170625597063579251464905729051049524014502008954170088604924368057540940, 4930922884306486570759661288602557428608315558804950537470100263019228888817481617065454705843164809506859574053884206133344549895853064735361336486560981, 5380263856446165449531647111260010594620416730932539097782399557603420658350407080366132490174060420530708293564252852668431923560882648691392446521188465, 10746696290782998433216934286282230556131938525513632178308443345441147075710552571129957873399395862207656161609046567289600084193860244770966610161184627, 2195032957511830992558961021566904850278796737316238566513837995297394215638259916944087623923636789312134734949452839561765171446217520081402769962517110]
m = 12813864523019740432913161815051292412705285817864701047922722497269479288096574264414061282833203433542813637861620032851255308640850882149603687035724753

M = matrix(QQ,6,6)
for i in range(4):
    M[i,i] = m
    M[-2,i] = cs[i]
    M[-1,i] = cs[i+1]
k=2^254
M[-2,-2]=k/m
M[-1,-1]=k
L=M.LLL()
print(L[0])
print(L[1])
print(L[2])
print(L[3])
print(L[4])
print(L[5])
res=L[1][-2].numerator()/k
a=abs(res)
print(a)
# 不知道为什么下面代码Sage中运行不了，但单独拎出来是可以运行的
from hashlib import md5
def MD5(m):return md5(str(m).encode()).hexdigest()
seed=cs[0]*inverse(a,m)%m
flag = '0xGame{' + MD5(seed) + '}'
print(flag)
  • 0xGame{2db84757dd4197f9b9441be25f35bfd5}

[Week 3] LLL-III

  • 没搞懂LLL但找到了板子
  • 几乎一样，改改数据和移位
from Crypto.Cipher import AES
from Crypto.Util.number import *
from hashlib import md5

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

m = 181261975027495237253637490821967974838107429001673555664278471721008386281743
a = 80470362380817459255864867107210711412685230469402969278321951982944620399953
b = 108319759370236783814626433000766721111334570586873607708322790512240104190351
c = [2466192191260213775762623965067957944241015, 1889892785439654571742121335995798632991977, 1996504406563642240453971359031130059982231, 1368301121255830077201589128570528735229741, 3999315855035985269059282518365581428161659, 3490328920889554119780944952082309497051942, 2702734706305439681672702336041879391921064, 2326204581109089646336478471073693577206507, 3428994964289708222751294105726231092393919, 1323508022833004639996954642684521266184999, 2208533770063829989401955757064784165178629, 1477750588164311737782430929424416735436445, 973459098712495505430270020597437829126313, 1849038140302190287389664531813595944725351, 1172797063262026799163573955315738964605214, 1754102136634863587048191504998276360927339, 113488301052880487370840486361933702579704, 2862768938858887304461616362462448055940670, 3625957906056311712594439963134739423933712, 3922085695888226389856345959634471608310638]

h = [0] + c

length = len(h)
for i in range(length):
    h[i] <<= 115

A = [1]
B = [0]

for i in range(1, len(h)-1):
	A.append(a*A[i-1] % m)
	B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)

A = A[1:]
B = B[1:]

Ge = Matrix(ZZ,length,length)

for i in range(len(A)):
    Ge[i,i] = m
    Ge[-2,i] = A[i]
    Ge[-1,i] = B[i]

K = 2**115
Ge[-2,-2] = 1
Ge[-1,-1] = K

for line in Ge.LLL():
    if abs(line[-1]) == K:
        L1 = line[-2]
        seed1 = h[1] + L1
        seed = (seed1 - b) * inverse(a,m) % m
        print(f"seed = {seed}")
        print('0xGame{' + MD5(seed) + '}')
  • 0xGame{459049e068d93f6d70f1ea0da705264a}

0xGameCryptoWriteUp
暂无评论

发送评论 编辑评论

























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



上一篇
下一篇