[0xGame 2024] week4 完结

到最后总是不能AK，一直遗憾。不会的也记一下感受

Crypto

AES

看了官WP，也没有复现的想法。这种题还是算了，保持不会吧。积分法如果不拿到github的原码是不会的。

DES

差分法也不会。不过自己作的另外一种方法。

在加密的时候只有两轮，每轮L，R只有一侧被加密，这样两轮过后有一侧是只加密过一次的。

P(S_box(EP(R)^key))^L

S_box 将48位密钥分成8块，每块0，5位用来找s_box对应的行，其它4位用来找块里的行列。是个6到4位的映射。因为密文里只出现例里对应的4位值。不能确定行。

当输入的明文为0时，L.R都是0，其实只是加密了key即 P(S_box(key))，对于P可以直接逆过来，S_box比较麻烦，它本身是个6->4的映射，本身是不能完全逆回的。不过也就只差了2位而已。再用一个正常明文来测试一下即可。

前边部分代码是原代码，只加了后边两个函数:r_P,S2

'''
加密只有两轮L                      R 
1:            R               L^P(S_box(EP(R)^sub_key))
2:  L^P(S_box(EP(R)^sub_key))         ...
Out          ...              L^P(S_box(EP(R)^sub_key))#1
所以当输入\0*8时L,R,EP(R)==0, 右侧= P(S_box(sub_key))
通过右侧求key
key通过S_box将6位(05组成行号1-4组成列号,并按轮依次使用box的块取值)转成4位
所以逆向出来每段都有4种情况,8段组合共65536种
#2
输入个普通明文得到密文
用爆破出的key本地加密得到相同密文的为正确的key
'''
from functools import reduce
from operator import add__p = [15,  6, 19, 20, 28, 11, 27, 16,0, 14, 22, 25,  4, 17, 30,  9,1,  7, 23, 13, 31, 26,  2,  8,18, 12, 29,  5, 21, 10,  3, 24]__ep = [31,  0,  1,  2,  3,  4,3,  4,  5,  6,  7,  8,7,  8,  9, 10, 11, 12,11, 12, 13, 14, 15, 16,15, 16, 17, 18, 19, 20,19, 20, 21, 22, 23, 24,23, 24, 25, 26, 27, 28,27, 28, 29, 30, 31,  0
]__s_box = [[[14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7],[ 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8],[ 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0],[15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13]],[[15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10],[ 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5],[ 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15],[13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9]],[[10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8],[13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1],[13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7],[ 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12]],[[ 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15],[13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9],[10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4],[ 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14]],[[ 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9],[14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6],[ 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14],[11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3]],[[12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11],[10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8],[ 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6],[ 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13]],[[ 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1],[13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6],[ 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2],[ 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12]],[[13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7],[ 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2],[ 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8],[ 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11]]
]def EP(data):return [data[x] for x in __ep]def P(data):return [data[x] for x in __p]def S_box(data):output = []for i in range(0, 48, 6):row = data[i] * 2 + data[i + 5]col = reduce(add, [data[i + j] * (2 ** (4 - j)) for j in range(1, 5)])output += [int(x) for x in format(__s_box[i // 6][row][col], '04b')]return outputdef bytes2bin(m):return [int(i) for i in bin( int(m.hex(), 16) )[2:].zfill(8 * len(m))]def bin2bytes(m):return int(''.join([str(i) for i in m]), 2).to_bytes(length = len(m)//8, byteorder='big')def encrypt(plain, key):pt = bytes2bin(plain)sub_key = bytes2bin(key)L, R = pt[:32], pt[32:]for i in range(2):prev_L = LL = Rexpanded_R = EP(R)   #32->48xor_result = [a ^ b for a, b in zip(expanded_R, sub_key)]substituted = S_box(xor_result)permuted = P(substituted)R = [a ^ b for a, b in zip(permuted, prev_L)]cipher = R + Lreturn bin2bytes(cipher)#逆P
def r_P(data):return [data[__p.index(i)] for i in range(32)]def S2(data,i): #通过8个box实现6->4的映射row = data[0] * 2 + data[5]col = int(''.join([str(j) for j in data[1:5]]),2)output = __s_box[i][row][col]return outputfrom pwn import *
context.log_level = 'debug'io = remote('118.195.138.159', 10008)#当plain置0时获取密文
io.sendlineafter(b'[+] choice:\n>', b'E')
io.sendlineafter(b'[+] encrypt:\n>', b'0'*16)
io.recvuntil(b'[+] result: ')
pskey = bytes.fromhex(io.recvline().strip().decode())[4:]#不够简化，懒得改，就是从4行里分别找着列号组回6位
#pskey = b';\xa5:/'
#pskey = P(S_box(sub_key))
skey = r_P(bytes2bin(pskey))
subkey =[]
for i in range(8):r = int(''.join([str(v) for v in skey[i*4:i*4+4]]), 2)tmp = []for j in range(64):data = [int(v) for v in bin(j)[2:].zfill(6)]out = S2(data,i)if out == r:tmp.append(j)subkey.append(tmp)#计算可能提65536个密钥          
allkey = []
def getallkey(tmp, i):#print(tmp,i)if i>=8:key = bytes([int(tmp[j:j+8],2) for j in range(0,48,8)])allkey.append(key)returnfor v in subkey[i]:getallkey(tmp + bin(v)[2:].zfill(6),i+1)getallkey('',0)#加密一个普通密文
plain = '0123456789abcdef'
io.sendlineafter(b'[+] choice:\n>', b'E')
io.sendlineafter(b'[+] encrypt:\n>', plain.encode())
io.recvuntil(b'[+] result: ')
enc2 = bytes.fromhex(io.recvline().strip().decode())#验证key中哪个正确
plain = bytes.fromhex(plain)
for v in allkey:tmp = encrypt(plain, v)if tmp == enc2:print('Found:',v.hex())break io.sendlineafter(b'[+] choice:\n>', b'F')
io.sendlineafter(b'[+] guess:\n>', v.hex().encode())
io.recvline()io.interactive()

Coppersmith-I

h = q >> 253 ，这里q是512位，已知高位但稍有点少，coppersmith极限是249吧，所以需要爆破几位。

hh = h<<253
for i in range(1024):print(i, end= ',')P.<x> = PolynomialRing(Zmod(N))f = hh + x*2^11 + i*2 + 1res = f.monic().small_roots(X=2^242, beta=0.499, epsilon=0.02)if res != []:print(res)p = f(res[0])print(p)breakp = 13295508573884639199620553314279276555713267931632686232046557121192374259545996147310645724590265408681531835562935842452272815109085991754142293560427829
long_to_bytes(int(pow(c, inverse_mod(e,p-1),p)))

RNG

这里说是RNG，实际上看是random的算法MT19937，随便拿个什么现成的软件一弄就行。

不过回溯之后并不能拿到原值。通过第1组state的生成方法，可以很容易通过1恢复0

from pwn import *
from gmpy2 import invert 
from extend_mt19937_predictor import ExtendMT19937Predictor
context.log_level = 'debug'p = remote('118.195.138.159', 10006)#远程通过种子生成624个32位值。求种子
p.recvuntil(b'[+] result:')
v1 = eval(p.recvuntil(b']'))
print(v1)pr = ExtendMT19937Predictor()
#导入已知的624个数据,导入后指向尾部
for i in range(624):pr.setrandbits(v1[i], 32)#向前回溯
for i in range(624):_ = pr.backtrack_getrandbits(32)#取出state
mt3 = []+pr.__dict__['_mt']
#得到的state的mt[0]不正确，通过 mt[1] = 1812433253 * (mt[0] ^ mt[0] >> 30) + 1
yy = (mt3[1]-1)*invert(1812433253, 1<<32)%(1<<32)
# yy = y^y>>30 
y = yy^yy>>30p.sendlineafter(b'[+] seed = ?', str(y).encode())p.interactive()