2020安恒五月赛crypto部分wp
2020安恒五月赛crypto部分wp
前言
最近ddl，比较多就简单记录一下。(师傅们手速太快了，一个血也没抢到。。。wtcl
bbcrypto
撒盐加密，明文前4bytesflag{已知,已知明文攻击，可以恢复salt，exp如下：
#!/usr/bin/python3
# @Time : 2020-05-22 11:23：57
# @Author : badmonkey
# @FileName: exp.py
# @Software: PyCharm
from gmpy2 import invert
cipher = '177401504b0125272c122743171e2c250a602e3a7c206e014a012703273a3c0160173a73753d'
c = [int(cipher[i*2:(i+1)*2] ,16) for i in range(len(cipher)//2)]
plaintext = "flag{"
p = [ord(i) for i in plaintext]
# 巧合A正好等于两者差
A = c[3]-c[0]
si = []
for i in range(3):
tmp = c[i]-A*p[i]
si.append(tmp%128)
def decrypt(c,si):
m = ""
inv = invert(A,128)
for i in range(len(c)):
tmp = ((c[i]-si[i%3])*inv)%128
m += chr(tmp)
return m
print(decrypt(c,si))
Encrypt_Img
RC4流密码加密，不过一开始，一直在纠结为啥明文和密文的位数对不上。。（中间还和出题师傅交流了一下。。虽然对解题没有啥影响
有经验的密码选手应该可以注意到同一个png，图片被加密了两次，这是大忌。。(反正我没经验。。并没有直接定位到出题点)。
由于同一图片被加密两次，而且加密的密钥正好错了一位。我们可以异或两次的密文，得到错位的密钥的异或值，爆破其中的一个。我们可以一次还原两个密钥，其中的一个密钥恰好是下一组用于加密png的两个密钥中的一个，我们知道还所有密钥对的异或结果，那么我们可以像多米诺骨牌一样，还原所有密钥。exp如下：
from numpy import array
from PIL import Image
# from secret import Key
Key = list("badmoneky")
Plaintext1 = "RC4IsInteresting"
Plaintext2 = "ThisIsAEasyGame"
cnt = 0
class RC4():
def __init__(self, Key):
self.S = [i for i in range(256)]
self.K = [ord(Key[i % len(Key)])*2 for i in range(256)]
self.I, self.J = 0, 0
self.KSA()
def KSA(self):
for i in range(256):
j = (i+self.K[i]+self.S[i]) % 256
self.S[i], self.S[j] = self.S[j], self.S[i]
def next(self):
self.I = (self.I+1) % 256
self.J = (self.J+self.S[self.I]) % 256
self.S[self.J], self.S[self.I] = self.S[self.I], self.S[self.J]
tmp = (self.S[self.J] + self.S[self.I]) % 256
# print self.S[tmp]
return self.S[tmp]
class Encrypt():
def __init__(self, plain):
global cnt
cnt += 1
self.rc4 = RC4(Key)
self.testRC4(plain)
# flag_file = Image.open(r"flag.png")
# img = array(flag_file)
# self.enc(img)
def testRC4(self, plain):
ciphertext = 0
for i in plain:
ciphertext = (ciphertext << 8)+ord(i) ^ self.rc4.next()
print("ciphertext{} = {}".format(cnt, ciphertext))
# Encrypt(Plaintext1)
# Encrypt(Plaintext2)
# ciphertext1 = 12078640933356268898100798377710191641
# ciphertext2 = 79124196547094980420644350061749775
file1 = Image.open(r"enc1.png")
img1 = array(file1)
file2 = Image.open(r"enc2.png")
img2 = array(file2)
def recover(img1,img2,first,cnt):
a1, b1, _ = img1.shape
a2, b2, _ = img2.shape
for i in range(a1):
for j in range(b1):
pixel1 = img1[i,j]
pixel2 = img2[i,j]
pixel = []
for k in range(3):
origin = pixel2[k]^first
pixel.append(origin)
first = pixel1[k]^origin
pixel.append(255)
img1[i,j] = pixel
enc = Image.fromarray(img1)
enc.save("guess{}.png".format(cnt))
return
for i in range(255):
recover(img1,img2,i,i)
# print(a,b,_)
第一次爆破就出了，还算友好。。
Easy_LCG
简单题，已知state1的高位，爆破低16位，根据state2加以限制，得到5种可能。暴力枚举每种可能即可。exp如下：
#!/usr/bin/python3
# @Time : 2020-05-22 15:00：27
# @Author : badmonkey
# @FileName: exp.py
# @Software: PyCharm
from Crypto.Util.number import *
import gmpy2 as gp
class LCG:
def __init__(self):
self.a = 3844066521
self.b = 3316005024
self.m = 2249804527
# self.seed = getRandomNBitInteger(32)
self.seed = 0
def setSeed(self,s):
self.seed = s
return
def next(self):
self.seed = (self.a*self.seed+self.b) % self.m
return self.seed >> 16
def output(self):
# print("a = {}\nb = {}\nm = {}".format(self.a, self.b, self.m))
self.next()
self.next()
def gen_AB(self):
x = ''
for _ in range(64):
x += '1' if self.lcg.next() % 2 else '0'
return pow(self.g, int(x, 2), self.m), int(x, 2)
g = 183096451267674849541594370111199688704
A = 102248652770540219619953045171664636108622486775480799200725530949685509093530
B = 74913924633988481450801262607456437193056607965094613549273335198280176291445
M = 102752586316294557951738800745394456033378966059875498971396396583576430992701
def gen_AB(lcg):
x = ''
for i in range(64):
x += '1' if lcg.next()%2 else '0'
return pow(g,int(x,2),M),int(x,2)
a = 3844066521
b = 3316005024
m = 2249804527
state1 = 16269
state2 = 4249
# a*s1'+b-s2' =y' - a*x'
left = (a*(state1<<16)+b-(state2<<16))%m
def check(x):
seed = (state1<<16)+x
s = (a*seed+b)%m
# guess = (state2<<16)+y
guess = s>>16
if guess == state2:
return True
return False
def findAll():
all = []
for i in range(1<<16):
if check(i):
all.append((state1<<16)+i)
return all
# s1 = findAll()
# print(s1)
s = [1066209821, 1066229421, 1066249021, 1066268621]
inv = gp.invert(a,m)
seed = [int((inv*(i-b))%m) for i in s]
def brute():
lcg = LCG()
tag = True
for sed in seed:
lcg.setSeed(sed)
lcg.output()
_ga , _a = gen_AB(lcg)
if _ga != A :
tag = False
continue
_gb, _b = gen_AB(lcg)
if _gb != B:
tag = False
continue
if tag:
return _a,_b,pow(_ga,_b,M)
return 0,0,0
_a,_b,key = brute()
Cipher = 13040004482819935755130996285494678592830702618071750116744173145400949521388647864913527703
flag = Cipher^key
print(long_to_bytes(flag))
knapsack
背包密码系统，不过啥变化都没加(加了也没啥用。。一般都是超递增背包，这次居然到过来。看起来有点难受。。正常的背包密码中的A,M应该都是大数，这里的 A非常小只有64bits,直接对key2(公钥)的最后一个item进行分解，可以得到64bits的素数即A。接下来需要找到M，然后可以对key2整体乘A的逆元还原key1，解密flag。我们可以找到最后一个$key1_i$使得$key1_i \cdot A \le M$。我们只需要遍历每一个key2中的元素，判断模A是否为零，如果为0，那么很大概率此时的$key1_i \cdot A \le M$。
幸运的是我们恰好可以找到一个$key1_i$使得$key1_i \cdot A \gt M$且$key1_i \cdot A$为1025位，于是有
$$
key1_i \cdot A -k \cdot M = key2_i
$$
其中的k很小，我们可以很容易的计算出kM，然后分解整数，可以得到1025位的M。得到A，M后就一把梭。exp如下：
#! /bin/bash/env python3
from Crypto.Util.number import *
from gmpy2 import next_prime
# 求解超递增背包
def decrypt(c, seq):
m = ''
# 倒序计算
cnt = 0
for i in reversed(seq):
if c >= i:
c -= i
m += '1'
else:
m += '0'
cnt += 1
return int(m, 2)
f = open("pub.txt", "r").readlines()
seq = []
for i in f:
res = i.strip()
seq.append(int(res))
c = 0x8ab3086a3df540d4652c191951756a6574aca491d933e479330532f0586ce03862f82f36dea8038b8bfb0b394331d7a93050efa2a26e46d9d8ca394600456cd79e02890a2c31b02e920c28a9f27c3943ec68fe5555ff4056358f35869859d67d67702edf44b10a7690acbaeea1f4def46392922069bfb71c173a210e9ab384f7
a = 11243098275181678343
sq = [0]*1015
for i in range(len(seq)):
if seq[i]%a == 0:
sq[i] = seq[i]//a
sq = sq[::-1]
start = 17026833443712394968379283916750564238637461988946070353054984895165978959633272575365788071630247770745419618215248096490672622886632703805895282233652643821337185633014648785953511688866826380386799877490765160165004972083108894532905615585700362884599803496389418488214358707285814230709
cur = (start<<1)
# a*cur-seq[-63]
res = seq[61]
KM = a*cur-res
print(KM)
# 分解整数
M = 335428611041311731398614259824482604248524861615176787429946575184146370361110652887115402376826444538743339055691850202034085349274540292019392290484025358504275054761608502214481606484088807087063751542648223811793597463026662881020647708165593980984857948283181770647446888695205803952635117800114545071259
inv = inverse(a,M)
key = [(i*inv)%M for i in seq][::-1]
flag = decrypt(c,key)
print(long_to_bytes(flag))
backpacker
又是一道背包密码题，正好之前出国LLL攻击背包密码的题，所有就是很常规的东西啦。这里给出一个链接，构建格的方法大同小异。感兴趣的读者可以google一下MH加密系统和对应的LLL攻击。直接甩出exp：
from pwn import *
from sage.all import *
import re
import string
from itertools import product
from hashlib import sha256
add = "183.129.189.60"
port = 10036
# sh = remote(add,port)
context.log_level = "debug"
def login(io):
io.recvuntil("Proof of work")
io.recvline()
rec = io.recvline().decode()
s = string.ascii_letters + string.digits
suffix = re.findall(r'\(XXXX\+(.*?)\)', rec)[0]
digest = re.findall(r'== (.*?)\n', rec)[0]
print(f"suffix: {suffix} \ndigest: {digest}")
print('Calculating hash...')
for i in product(s, repeat=4):
prefix = ''.join(i)
guess = prefix + suffix
if sha256(guess.encode()).hexdigest() == digest:
print(guess)
io.recvuntil('Give me XXXX: ')
io.sendline(prefix.encode())
io.recvline()
# io.sendafter(b'Give me XXXX:', prefix.encode())
break
return
# login(sh)
# sh.interactive()
def decrypt(enc,publickey):
# 维数
n = len(publickey)
# 构造格
d = 2*identity_matrix(QQ,n,n)
col = publickey+[enc]
col = matrix(col).transpose()
last = matrix(ZZ,[[1]*n])
tmp = block_matrix(ZZ,[[d],[last]])
grid = block_matrix(ZZ,[[tmp,col*(1^300)]])
# 格基规约 使用LLL算法，找到最短向量
M = grid.LLL()
# 利用最短向量还原信息，注意又两种可能，这里仅考虑第一种，reverse 函数将当前结果转换为第二种可能
m = ''
for i in M[0]:
if i== -1:
m += '0'
elif i == 1:
m += '1'
return m
# 转化为string
def b2s(a):
res = ''
for i in a:
res += chr(i)
return res
def reverse(m):
res = ''
for i in m:
if i == '0':
res += '1'
else:
res += '0'
return res
def chanllenge_1(sh):
sh.recvline()
sh.recvline()
length = 10
pub = []
for i in range(length):
tmp = b2s(sh.recvline()).strip('\n')
pub.append(int(tmp))
sh.recvuntil("c = ")
c = b2s(sh.recvline()).strip('\n')
c = int(c)
m = decrypt(c,pub)
m = reverse(m)
m = int(m,2)
payload = hex(m)[2:]
sh.recvuntil('[-]m(hex) = ')
print(payload)
sh.sendline(payload)
sh.recvline()
return
def chanllenge_2(sh):
length = 50
sh.recvline()
sh.recvline()
pub = []
for i in range(length):
tmp = b2s(sh.recvline()).strip('\n')
pub.append(int(tmp))
sh.recvuntil("c = ")
c = b2s(sh.recvline()).strip('\n')
c = int(c)
m = ''
# 倒序计算
for i in reversed(pub):
if c>=i:
c -= i
m += '1'
else:
m += '0'
m = m[::-1]
m = int(m,2)
payload = hex(m)[2:]
sh.recvuntil('[-]m(hex) = ')
print(payload)
sh.sendline(payload)
sh.recvline()
return
def chanllenge_3(sh):
length = 100
sh.recvline()
sh.recvline()
pub = []
for i in range(length):
tmp = b2s(sh.recvline()).strip('\n')
pub.append(int(tmp))
sh.recvuntil("c = ")
c = b2s(sh.recvline()).strip('\n')
c = int(c)
m = decrypt(c,pub)
# print("m = {}".format(m))
# m = reverse(m)
m = int(m,2)
payload = hex(m)[2:]
sh.recvuntil('[-]m(hex) = ')
print(payload)
sh.sendline(payload)
sh.recvline()
return
sh = remote(add,port)
login(sh)
chanllenge_1(sh)
chanllenge_2(sh)
chanllenge_3(sh)
sh.interactive()
# DASCTF{f1420ca949025b324a614c1b49571860}
总结
师傅们tql,本弱鸡还要继续学习(ddl警告)