ACTF2022

2022-06-27

实训了一个月，一直没参加比赛，这次浅浅做了些题，又是被SU的各位哥哥带飞。

MISC

Mahjoong

在线麻将，可以点击自动对局，打一会儿会弹出flag：
ACTF{y@kumAn_1s_incredl3le}，多么朴实无华的签到题。

emoji

🐨🐧🐧🐨🐨🐨🐧🐧🐨🐨🐧🐨🐧🐧🐨🐧🐨🐨🐧🐨🐨🐨🐧🐧🐧🐨🐨🐧🐨🐨🐧🐧🐨🐧🐧🐨🐧🐧🐨🐧🐧🐨🐨🐧🐨🐧🐨🐧🐨🐧🐨🐨🐨🐨🐨🐧🐨🐨🐧🐧🐧🐨🐨🐧🐨🐧🐨🐧🐧🐨🐨🐧🐧🐨🐨🐧🐧🐧🐨🐧🐨🐨🐧🐨🐨🐧🐨

转为二进制:

100111001101001011011100011011001001001001101010101111101100011010100110011000101101101

转为整数:

94794095464206931577745773

转为十六进制:

0x4e696e3649355f6353316d

即为flag:

m1Sc_5I6niN

又一个签到题，给了个hex文件，观察了下发现是bz2格式，解压多次依次发现了zs、gz、lzma格式；那么应该是四个压缩算法循环压缩了n次，写个while循环解压即可。

import zstandard
import pathlib
import gzip
import bz2
import lzma

count = 1
extra_outputfile = "compress/flag" + str(count)
outputfile = "compress/flag" + str(count + 1)

def decompress_lzma_to_folder(input_file):
    with open(outputfile, 'wb') as f:
        print("lzma:" + outputfile)
        f.write(lzma.open(input_file).read())

def decompress_zstandard_to_folder(input_file):
    input_file = pathlib.Path(input_file)
    with open(input_file, 'rb') as compressed:
        decomp = zstandard.ZstdDecompressor()
        print("zst:" + outputfile)
        with open(outputfile, 'wb') as destination:
            decomp.copy_stream(compressed, destination)

def decompress_gzip_to_folder(input_file):
    with gzip.open(input_file, 'rb') as f_in:
        with open(outputfile, 'wb') as f:
            print("lzma:" + outputfile)
            f.write(f_in.read())

def decompress_bzip_to_folder(input_file):
    with open(input_file, 'rb') as f_in:
        with open(outputfile, 'wb') as f:
            print("bzip:" + outputfile)
            f.write(bz2.decompress(f_in.read()))

while True:
    with open(extra_outputfile, 'rb') as f:
        data = f.read()
        print(data[0:4])
        if data[0:4] == b"(\xb5/\xfd":
            decompress_zstandard_to_folder(extra_outputfile)
        elif data[0:4] == b'\x1f\x8b\x08\x08':
            decompress_gzip_to_folder(extra_outputfile)
        elif data[0:4] == b'\xfd7zX' or data[0:4] == b']\x00\x00\x80':
            decompress_lzma_to_folder(extra_outputfile)
        elif data[0:4] == b'BZh9':
            decompress_bzip_to_folder(extra_outputfile)
        else:
            break
        extra_outputfile = outputfile
        print("extra:" + extra_outputfile)
        count = count + 1
        outputfile = "compress/flag" + str(count + 1)
        print("now:" + outputfile)

# ACTF{r0cK_4Nd_rolL_1n_C0mpr33s1ng_aNd_uNCOmrEs5iNg}

Crypto

impossible RSA

给了ssl格式的公钥，先去在线网站解出n、e。
根据题目条件可推导出这样的关系：

$k*p^2+p-e*n=0$

这里直接用求根判别公式去爆破k即可。exp：

from Crypto.Util.number import *
from gmpy2 import *

e = 65537
n = 15987576139341888788648863000534417640300610310400667285095951525208145689364599119023071414036901060746667790322978452082156680245315967027826237720608915093109552001033660867808508307569531484090109429319369422352192782126107818889717133951923616077943884651989622345435505428708807799081267551724239052569147921746342232280621533501263115148844736900422712305937266228809533549134349607212400851092005281865296850991469375578815615235030857047620950536534729591359236290249610371406300791107442098796128895918697534590865459421439398361818591924211607651747970679849262467894774012617335352887745475509155575074809
for i in range(1,100000):
    l = iroot(1 + 4 * i * e * n,2)
    if l[1]:
        if n%((l[0]-1) // (2*i)) == 0:
            p = (l[0]-1) // (2*i)
            q = n//p
            print(i)
            break
assert p*q == n
flag = open('flag','rb').read()
f = bytes_to_long(flag)
d = invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(f,d,n)))
# b'ACTF{F1nD1nG_5pEcia1_n_i5_nOt_eA5y}'

RSA LEAK

这题一共有两个难点：1.类似于中间相遇的攻击思想求rp和rq 2.用已知条件建立一元二次方程求根
首先根据leak函数来求ra和rb，由于这两者都是（0，2^24）的随机数，要爆破很困难，于是采用中间相遇的思想——以空间换时间：

# 中间相遇攻击
dic = {}
for i in tqdm(range(1,2**24)):
    tmp =(out-pow(i,e,n0))%n0
    dic[tmp]=i

for i in tqdm(range(2**24)):
    t = pow(i,e,n0)
    if t in dic.keys():
        print(i,dic[t])

对于n=pp.qq，不难发现a.b就等于n开四次根取整，证明如下（rp和rq对于a和b来说相当于一个很小的量）：

$a*b= \sqrt[4]{(a^4+o(a))} * \sqrt[4]{(b^4+o(b))}$

整理一下所有的已知条件：

$r_{p}=pp-p; r_{q}=qq-q; p*q=(ab)^4; pp*qq=n$

如果我们用$r{p}$乘$r{q}$，会出现$n$,$pp.q$,$qq.p$,$p.q$ ，由于 $pp.q$ 是未知的，所以需要构造这个来相消；因此考虑 $r{p}.q$ ，同理$r{q}.p$，消去以后剩下 $p.q$ 和 $n$ ，都是已知量，最后得到：

$r_{p}*qq+(pq-r_{p}*r_{q}-pp*qq)+r_{q}*pp = 0$

等式两边同乘qq得到关于qq的一元二次方程，解出来就是qq，完整过程：

from gmpy2 import *
from tqdm import tqdm

n0 = 122146249659110799196678177080657779971
out = (90846368443479079691227824315092288065-0xdeadbeef)%n0
sig = 0xdeadbeef
e = 65537

# 中间相遇攻击
dic = {}
for i in tqdm(range(1,2**24)):
    tmp =(out-pow(i,e,n0))%n0
    dic[tmp]=i

for i in tqdm(range(2**24)):
    t = pow(i,e,n0)
    if t in dic.keys():
        print(i,dic[t])

# sage
import gmpy2
r1=11974933
r2=405771
n = 3183573836769699313763043722513486503160533089470716348487649113450828830224151824106050562868640291712433283679799855890306945562430572137128269318944453041825476154913676849658599642113896525291798525533722805116041675462675732995881671359593602584751304602244415149859346875340361740775463623467503186824385780851920136368593725535779854726168687179051303851797111239451264183276544616736820298054063232641359775128753071340474714720534858295660426278356630743758247422916519687362426114443660989774519751234591819547129288719863041972824405872212208118093577184659446552017086531002340663509215501866212294702743
e = 65537
c = 48433948078708266558408900822131846839473472350405274958254566291017137879542806238459456400958349315245447486509633749276746053786868315163583443030289607980449076267295483248068122553237802668045588106193692102901936355277693449867608379899254200590252441986645643511838233803828204450622023993363140246583650322952060860867801081687288233255776380790653361695125971596448862744165007007840033270102756536056501059098523990991260352123691349393725158028931174218091973919457078350257978338294099849690514328273829474324145569140386584429042884336459789499705672633475010234403132893629856284982320249119974872840
t=gmpy2.iroot(n,4)[0]^4
A=r1
B=t-r1*r2-n
C=r2*n
q=(-B+isqrt(B^2-4*A*C))//(2*A)
p=n//q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))
# b'ACTF{lsb_attack_in_RSA|a32d7f}'

复现

safer-telegram-bot-1

审计下sage.js，发现两个比较关键的地方：

对js不太熟，读个大概意思就行。对bot发/login他会马上把uid变为0_login_callback:" + msg.chat.id + ":" + msg.message_id，然后sleep一段随机时间，变为authorizedUids[0].uid + "_login_callback:" + msg.chat.id + ":" + msg.message_id，然后再马上变成-1_login_callback:" + msg.chat.id + ":" + msg.message_id，去查了下js的random，发现它是以当前时间为种子进行随机的，不太好预测，但可以多次发/login，每次间隔不同或相同时间点开，可能会在某个时候恰好碰对时间出flag(我觉得完全不可控，凭运气)，预期解应该不是这样的。