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警告)