20210828-WMCTF-CryptoSecPartWriteUp

Posted on 2021-10-08 Edited on 2022-09-10 In CTF-Crypto , WriteUp Views: Symbols count in article: 21k Reading time ≈ 19 mins.

checkin：10 solves：格，背包
easylsb：12 solves：RSA AGCD
baby_ocb：7 solves
ezl1near：8 solves
4xwi11：0 solves

全a了的大师傅的博客

checkin

众所周知，L1near是一个著名大黑客，他为W&M编写了一个全自动的水群机器人，我们偷到了L1near在开发时的简易版本，并且获得了交互的接口，你能帮我们找到L1near偷偷藏起来的flag吗？

http://47.104.243.99:10000/

第二天上了update

请提交合法的secret中最小的那个，题目没有说清楚，给各位师傅添麻烦了～

<title>W&M exclusive robot</title>

<style>
    h1 {text-align:center}
    p {text-align:center}
    form {text-align:center}
</style>

<head>
    <body>
        <h1>Fully automatic rp system</h1>
        <p>Come and get your rp value today!</p>
        <hr></hr>
        <form action="show.php" method="post">
        <input type="hidden" id="rp" name="rp" value="rp">
        <input type="submit" value="Get today's rp!">
        </form>
    </body>
</head>

<script>
    function ran(){
        var rp = Math.floor( Math.random() * 100);
        document.getElementById("rp").setAttribute('value',rp);
    }
    ran();
</script>

<!--
-------------------------------------------------------
Maybe there are some Easter eggs?
So where are them?
-->

rp是0到99的整数，但是post100会得到

<title>W&M exclusive robot</title>

<style>
    h1 {text-align:center}
    p {text-align:center}
</style>

<h1>Fully automatic rp system</h1>
<p>Come and get your rp value today!</p>
<hr></hr>

<p>Your rp value:100</p>
<p>Wow! Golden legend!<!-- so why not try to post 'flag' as rp? --></p>

没有分析出什么东西，稍微梳理一下

0~19

Ah-ha! There is a idiot!
20~39

Gee, this is too miserable.
40~59

Oh, you almost passed it!
60~79

Fortunately, you passed 60.
80~99

You are Koi! Congratulations!
100

Wow! Golden legend!

flag

Your rp value:1620418829165478

What happend to my bot?????

Let me find something in my backpack which can fix this bug!

第一次写post脚本

from Crypto.Util.number import *
import requests


def exDigit(String):
    d = 0
    for j in String:
        if '0' <= j <= '9':
            d = d * 10 + int(j)
    return d

x = 999999999999999999999999999999999
url = "http://47.104.243.99:10000/show.php"
r = requests.post(url, {"rp": 2017515922459700})
for i in range(65537):
    if 'flag' in r.text or 'WMCTF' in r.text or 'wmctf' in r.text or '1620418829165478' in r.text:
        print(r.text)
        print(x)
    line = r.text[205:][:37]
    t = exDigit(line)
    if t < x:
        x = t
    print(t)
    payload = {
        "rp": t
    }
    r = requests.post(url, payload)

到此为止，总之上面搜集的信息都没什么用

wp说看到backpack应该能想到背包（就我想到备份吗），背包加密可以参考CTF Wiki，了解超递增，Merkle–Hellman背包加密，构造01格破解的概念

Knackpack Encryption

简单介绍下背包加密，看la佬博客比较好懂

首先背包问题

私钥生成

选择一个超递增集${s_1, s_2, \cdots, s_n}$

所谓的超递增集就是满足第i个数大于前面所有数的和
公钥生成
1. 选取模数m，确保$m>\sum\limits_{i=1}^n s_i$
2. 选取乘数w，确保$(w,\ m)=1$，这里又说w也是私钥
3. 生成公钥集$t_i$，$t_i\equiv ws_i\ (mod\ m)$
加密

明文b的每一位的二进制为$b_i$
$$
c=\sum\limits_{i=1}^nt_ib_i\ (mod\ m)\notag
$$
解密

先求$w^{-1}$，则
$$
b=\sum\limits_{i=1}^nw^{-1}t_ib_i\ (mod\ m)=\sum\limits_{i=1}^ns_ib_i\ (mod\ m)\notag
$$

该密码系统有一个密度，为$d=\frac{n}{log_2(max{t_i})}$

Striving师傅说春哥说每次post$2^i$，会发现周期是32，得到的值也就公钥集里面的值。借下数据，相当于知道公钥集和密文，要求明文

1
2

t = [97005071980911, 32652300906411, 73356817713575, 108707065719744, 103728503304990, 49534310783118, 53330718889073, 2121345207564, 46184783396167, 115771983454147, 64261597617025, 2311575715655, 56368973049223, 84737125416797, 24316288533033, 82963866264519, 101019837363048, 25996629336722, 41785472478854, 68598110798404, 40392871001665, 94404798756171, 54290928637774, 112742212150946, 91051110026378, 124542182410773, 40388473698647, 22059564851978, 57353373067776, 80692115733908, 84559172686971, 28186390895657]
c = 1620418829165478

有了这个可以求出密度

from math import log

d = len(t) / log(max(t), 2)
# d = 0.6834156494834176

说是低密度（$d<0.9408$）可以直接搞，不太懂原理，抄个脚本

抄自论文

t = [97005071980911, 32652300906411, 73356817713575, 108707065719744, 103728503304990, 49534310783118, 53330718889073, 2121345207564, 46184783396167, 115771983454147, 64261597617025, 2311575715655, 56368973049223, 84737125416797, 24316288533033, 82963866264519, 101019837363048, 25996629336722, 41785472478854, 68598110798404, 40392871001665, 94404798756171, 54290928637774, 112742212150946, 91051110026378, 124542182410773, 40388473698647, 22059564851978, 57353373067776, 80692115733908, 84559172686971, 28186390895657]
ct = 1620418829165478
n = len(t)
M = Matrix.identity(n)

last_row = [0 for x in t]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = t[:]
last_col.append(ct)
M_last_col = Matrix(ZZ, len(last_col), 1, last_col)

M = M.stack(M_last_row)
M = M.augment(M_last_col)

X = M.LLL()
target = X[-1][:-1]
ans = [abs(k) for k in target]
flag = int(''.join([str(i) for i in ans])[::-1], 2)
# 4159506287

听说把解密得到的flag这串数字post过去就得到flag了

easylsb

#!/usr/bin/python3
# encoding: utf-8
import random
import string
import sys
import os
from hashlib import sha256
import uuid
from Crypto.Util.number import *

password = # Hidden
flag = ('flag{' + str(uuid.uuid4()) + '}').encode()

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]).encode()
    digest = sha256(proof).hexdigest()
    printf("sha256(XXXX+%s) == %s" % (proof[4:].decode(),digest))
    printf('Give me XXXX:')
    x = read_str()
    if len(x) != 4 or sha256(x.encode()+proof[4:]).hexdigest() != digest: 
        return False
    return True

def printf(message):
    sys.stdout.write('{0}\n'.format(message))
    sys.stdout.flush()
    sys.stderr.flush()

def read_str():
    return sys.stdin.readline().strip()

def read_int():
    return int(sys.stdin.readline().strip())

def next_prime(a):
    while not isPrime(a):
        a += 2
    return a

def get_prime(a):
    suffix = getPrime(368)
    return next_prime(a ** 2 + suffix + 1)

def generate_pubkey(key):
    p, q = get_prime(getPrime(512)), get_prime(key)
    n = p * q
    return n

def airdrop(a):
    n = generate_pubkey(a)
    printf('gift: {}'.format(n))
    return

def hint(n, e, c):
    printf('n = {}'.format(n))
    printf('e = {}'.format(e))
    printf('c = {}'.format(c))
    return

def leak():
    p = get_prime(getPrime(512))
    e = 0x1000
    c = pow(bytes_to_long(flag), e, p)
    
    hint(p, e, c)
    return

def backdoor():
    printf('Input your password:')
    user_input = read_str()
    if user_input.encode() == password:
        leak()
    else:
        printf('Wrong')
        exit(0)

if __name__ == '__main__':
    if not proof_of_work():
        exit(0)
    
    a = getPrime(512)
    p = get_prime(a)
    q = get_prime(getPrime(512))
    n = p * q
    e = 0x10001
    max_time = 5
    password_enc = pow(bytes_to_long(password), e, n)
    
    printf('====================================',)
    printf('1. Airdrop                          ',)
    printf('2. Backdoor                         ',)
    printf('3. Hint                             ',)
    printf('4. Exit                             ',)
    printf('====================================',)
    
    try:
        while True:
            printf('Your choice:')
            choice = read_int()
            if choice == 1:
                if max_time > 1:
                    airdrop(a)
                    max_time -= 1
                    printf('Done!')
                else:
                    printf('Greed will destroy you!')
                continue
            elif choice == 2:
                backdoor()
                printf('Done!')
                continue
            elif choice == 3:
                hint(n, e, password_enc)
                printf('Done!')
                continue
            elif choice == 4:
                printf('bye~')
                exit(0)
                continue
            else:
                printf('Invalid!')
                continue
    except:
        exit(-1)

流程比较简单，通过4组gift和1个n求得a和p$\rightarrow$解密password$\rightarrow$在e=4096，模数是素数下解密flag

通过尚师傅提醒，尝试之后发现，q开根后取整的结果是和a一样的
$$
\lfloor \sqrt{q} \rfloor=a\notag
$$
然后假设$q=next\_prime(a^2+suffix_1+1),\ p=next\_prime(b^2+suffix_2+1)$

那么n=pq，给n开根号可以得到ab的高位，但也不知道拿来怎么用

保存了一组数据下来

# nc 47.104.243.99 9999
import random
import string
import sys
import os
from hashlib import sha256
import uuid
from Crypto.Util.number import *
from pwn import *
from itertools import product


# flag = ('flag{' + str(uuid.uuid4()) + '}').encode()
# print(flag)
# flag{cb8365b5-a825-4c65-9251-b6827f0792ad}


def proof_of_work():
    # sha256(XXXX+cgDUNjezTPNSj91D) == 30fc93b19ef81e8755f3ee0e3df72722f66556b7636b5037f34d1beb981235b0
    proof = sh.recvline()
    tail = proof[12:28].decode()
    HASH = proof[23:97]
    for i in product(string.ascii_letters + string.digits, repeat=4):
        head = ''.join(i)
        t = hashlib.sha256((head + tail).encode()).hexdigest()
        if t == HASH:
            sh.sendline(head.encode())
            break


def proof_of_work2():
    # sha256(XXXX+cgDUNjezTPNSj91D) == 30fc93b19ef81e8755f3ee0e3df72722f66556b7636b5037f34d1beb981235b0
    proof = sh.recvline()
    tail = 'eqbj8j6Z9xvz3YiV'
    HASH = 'b5808aff39327c9ac49d209d10fe3e27c898d49faffc956bbf1d73523c44ce77'
    for i in product(string.ascii_letters + string.digits, repeat=4):
        head = ''.join(i)
        t = hashlib.sha256((head + tail).encode()).hexdigest()
        if t == HASH:
            sh.sendline(head.encode())
            break


context.log_level = 'debug'
sh = remote("47.104.243.99", 9999)
proof_of_work2()

e = 0x10001
n = 124478026101165354098037876421627662624056206605515177686194103211430464934743129994417330643128683345849733014275487857184516763016301408033382676283620282332485581507315430690690813831282519976585364463744017296315372258981215919387679949709396064987889800074036410663927631478105899096723790945928412829187822284593750473740315866322998068351563015099367643886154042581191841533888375305195743073059105310700318861167337672659772641786687582718180589854118978820530842381081568922213227168617789474006973152602334271699398178963791154954792676067153150646411025449463253194489657095241613282942586704728903727611399
c = 90647155870804971113806442051901226002120015769259333554192477899450971338831255790857101662710560234954831825416787459228033373486077151217415092360097814474283515220281223555587026056325099266316005605716929634353603643319859645167427538563242884591102004934790399528462112789803351851769047685792159647390050985871679243422993775721776244067168064933786611606433105514418429089777322132633028815660525070271128628044386434106685643657668695364607215033856398608992051550288297119711825866170869469834444973857013360900452988222767960318998636640763573797297203544581343736625672669946528644260077687270041162148579
gift1 = 430643544402084432319325961880416327356872029175895120742910502784460696485981655831364057771978842374920289740546998744096646780935886278222230684528731470188637076148307527311922452490801045278988434801896164340653915198079023711297016090027381126073802620204314765869166624636941907534206046998568042400815444697126334029985946496452932477337335924863188276040631646131204436116708742280199903183210826719901897273260766069768314579353548171372586771188839003301749872795307598319516051259672117483195538538878148292313730887085591272354625175614366936749367007177827223031514498275753340915542939818624965339274541
gift2 = 279643881521430665779764628210196159031443254319916096260435206316116655701344325784134050728686231352816394212502789612947929220430466611004330150352137570405484127780364316335386736272544877793446702006665399064591475517610575894857804921152265901610537191780251376268112843688812459951190257679817490601282013470378644045696567456486059374094892490322848884260103728441765221196492288890565220765116737467020984854284776188063793107604665880577892150257025900438921323929874583349697921571156857890185078774883450481945134786456867498237937223992977125106207044050316201931335150865420643200300919950666792333800421
gift3 = 237902069859826089956710602458488697197969935460375469157966706791637991891038954423106099106663742928616105443683571279895168734280020803510641968762322744746722455831059684745613465616901995570874116303439549541932451281441959514629564655972962203744852006794160278105621063202850402448076034174743227230202591123961117876362833492478366233652816443873213201410433457033307944305406209168085355438156499669719905462067847881209129983251184647052314353242784174374088582263983943733709287614092898665984536781786084591414804290805713181580225096207601673326693693442261927044483426965621699507399608913104482509541829
gift4 = 131184496439376311814751172869309509301398236134030748081290782986296909958428702969677021306310259793511587606469385852829507392096577310273567455635233040499932518933927338330158300947934921792366825549482737059128276134653805578959896357503546949681198843822945160611138388841031519307824760189249466171835761078895545203381195921789823129815826662876576368032722825159838976137103324588326186884693453137115752294499574361951327089081432442184727065530788376603390307277709197418051468405219378610308912749832078805547917787498228816440083434077213552664217150489211767711038795362880479839885325109115335568243823

参考论文Approximate GCD

构造$B$这样的格

$x_i$显然就是五组$n_i$开根号得到的，这个上面也证实了；$\lambda$就是368，因为论文里的$r_i$就是题目中的$suffix_i+1$

这样对矩阵B进行LLL()得到的是$q_0\cdot 2^{\lambda +1}$，除以$2^{\lambda +1}$就是论文里的$q_0$了，也就是与$x_0$对应的那个

到此为止还少了一步，接着题目中的$n=pq$推导
$$
n=pq=(a^2+suffix_1+1)(b^2+suffix_2+1)\notag
$$
设$\beta =\sqrt {b^2+suffix_2+1},\ \delta$为p开根后的低位，$r=\delta \beta$

给n开根
$$
\sqrt n=(a+\delta)\beta =a\beta +r\notag
$$
这就和论文里给的形式一样了，而我们刚求出来的$q_0$就是这里的$\beta$，最后$\lfloor\sqrt n/\beta \rfloor =\lfloor (a\beta +r)/\beta\rfloor$，显然$r/\beta$已经是小数部分了，取整就完全舍去了，所以结果就是a

求出来的ans应该是上文的b，先用抄来的脚本得到a

from sympy import root

e = 0x10001
n = 124478026101165354098037876421627662624056206605515177686194103211430464934743129994417330643128683345849733014275487857184516763016301408033382676283620282332485581507315430690690813831282519976585364463744017296315372258981215919387679949709396064987889800074036410663927631478105899096723790945928412829187822284593750473740315866322998068351563015099367643886154042581191841533888375305195743073059105310700318861167337672659772641786687582718180589854118978820530842381081568922213227168617789474006973152602334271699398178963791154954792676067153150646411025449463253194489657095241613282942586704728903727611399
c = 90647155870804971113806442051901226002120015769259333554192477899450971338831255790857101662710560234954831825416787459228033373486077151217415092360097814474283515220281223555587026056325099266316005605716929634353603643319859645167427538563242884591102004934790399528462112789803351851769047685792159647390050985871679243422993775721776244067168064933786611606433105514418429089777322132633028815660525070271128628044386434106685643657668695364607215033856398608992051550288297119711825866170869469834444973857013360900452988222767960318998636640763573797297203544581343736625672669946528644260077687270041162148579
gift1 = 430643544402084432319325961880416327356872029175895120742910502784460696485981655831364057771978842374920289740546998744096646780935886278222230684528731470188637076148307527311922452490801045278988434801896164340653915198079023711297016090027381126073802620204314765869166624636941907534206046998568042400815444697126334029985946496452932477337335924863188276040631646131204436116708742280199903183210826719901897273260766069768314579353548171372586771188839003301749872795307598319516051259672117483195538538878148292313730887085591272354625175614366936749367007177827223031514498275753340915542939818624965339274541
gift2 = 279643881521430665779764628210196159031443254319916096260435206316116655701344325784134050728686231352816394212502789612947929220430466611004330150352137570405484127780364316335386736272544877793446702006665399064591475517610575894857804921152265901610537191780251376268112843688812459951190257679817490601282013470378644045696567456486059374094892490322848884260103728441765221196492288890565220765116737467020984854284776188063793107604665880577892150257025900438921323929874583349697921571156857890185078774883450481945134786456867498237937223992977125106207044050316201931335150865420643200300919950666792333800421
gift3 = 237902069859826089956710602458488697197969935460375469157966706791637991891038954423106099106663742928616105443683571279895168734280020803510641968762322744746722455831059684745613465616901995570874116303439549541932451281441959514629564655972962203744852006794160278105621063202850402448076034174743227230202591123961117876362833492478366233652816443873213201410433457033307944305406209168085355438156499669719905462067847881209129983251184647052314353242784174374088582263983943733709287614092898665984536781786084591414804290805713181580225096207601673326693693442261927044483426965621699507399608913104482509541829
gift4 = 131184496439376311814751172869309509301398236134030748081290782986296909958428702969677021306310259793511587606469385852829507392096577310273567455635233040499932518933927338330158300947934921792366825549482737059128276134653805578959896357503546949681198843822945160611138388841031519307824760189249466171835761078895545203381195921789823129815826662876576368032722825159838976137103324588326186884693453137115752294499574361951327089081432442184727065530788376603390307277709197418051468405219378610308912749832078805547917787498228816440083434077213552664217150489211767711038795362880479839885325109115335568243823

f = lambda a: int(root(a, 2))
x0, x1, x2, x3, x4 = f(n), f(gift1), f(gift2), f(gift3), f(gift4)

B = matrix(ZZ, [[2 ^ 368, x1, x2, x3, x4], [0, -x0, 0, 0, 0], [0, 0, -x0, 0, 0], [0, 0, 0, -x0, 0], [0, 0, 0, 0, -x0]])
L = B.LLL()
ans = L[0][0] // 2 ^ 368

p0 = abs(ans)
a = x0 // p0

print(a)
# a = 25582847577564670038612582668140373129129959651036453923605273284793860890291221263498753328353767798264241675861426056503889321642277844202986695039010291

然后是熟悉的节奏，但和一般的已知p的高位攻击不一样，显然$a^2$已经和p的位数差不多了，只是不知道368位的suffix是多少，所以本质一样，用CopperSmith求小根的算法求出suffix；这里取kbits为369，因为368出不来，往大一点的地方取

a = 25582847577564670038612582668140373129129959651036453923605273284793860890291221263498753328353767798264241675861426056503889321642277844202986695039010291
n = 124478026101165354098037876421627662624056206605515177686194103211430464934743129994417330643128683345849733014275487857184516763016301408033382676283620282332485581507315430690690813831282519976585364463744017296315372258981215919387679949709396064987889800074036410663927631478105899096723790945928412829187822284593750473740315866322998068351563015099367643886154042581191841533888375305195743073059105310700318861167337672659772641786687582718180589854118978820530842381081568922213227168617789474006973152602334271699398178963791154954792676067153150646411025449463253194489657095241613282942586704728903727611399
pbar = a ** 2
kbits = 369
PR.<x> = PolynomialRing(Zmod(n))
f = pbar + x
roots = f.small_roots(X=2^kbits, beta=0.4)
# 967901962469872165537856438801710756065070673694594801499396171114255660549746759504438698205658088002955084386

接下来RSA的常规步奏得到password

Cou1d_I_get_Th3_passw03d_then_captu7e_the_fla9?

正如一开始所说的e是偶数，还是$2^{12}$，与$\varphi(p)=p-1$不互素

可以尝试平方根，有限域开方，12次Rabin

由于p % 4 = 3符合rabin最基本的条件，所以直接开12次方

from Crypto.Util.number import long_to_bytes

p = 496584754781581997154645314415051021632937719346451955222548277806458479939882609131615548616817732786901123585586203791585231652481101508165523306207307511005218236201069837205145881515297396218450658339325435517394532697652694250302927324547950654199907918057947165277944713164863611463887879016367147027651
e = 4096
c = 202821697585498721190880385651888326819052363235092021514522019296117832067188656931773131985516119359273814956340533509702817980744398402155886334655033938474295749168241550740096583920405311629354495691732306096266636370938656838375279086916114964255411601403125984312042419408682006688199111243135798564394

mi = []

for i in range(12):
    mi.append(pow(c, (p + 1) // 4, p))
    mi.append(p - pow(c, (p + 1) // 4, p))
    c = pow(c, (p + 1) // 4, p)

for i in mi:
    t = long_to_bytes(i)
    if b'WMCTF' in t:
        print(t)
        break

有限域开方也可以

from Crypto.Util.number import *
p = 496584754781581997154645314415051021632937719346451955222548277806458479939882609131615548616817732786901123585586203791585231652481101508165523306207307511005218236201069837205145881515297396218450658339325435517394532697652694250302927324547950654199907918057947165277944713164863611463887879016367147027651
e = 4096
c = 202821697585498721190880385651888326819052363235092021514522019296117832067188656931773131985516119359273814956340533509702817980744398402155886334655033938474295749168241550740096583920405311629354495691732306096266636370938656838375279086916114964255411601403125984312042419408682006688199111243135798564394
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
print(res1)
# res1 = [(496584754781581997154645314415051021632937719346451955222548277806458479939882609131615548616817732786901123585586203791585231652481101508165523306207307511005218236201069837205145881515297396218450658339313214656968189495352306293673615992017103882095004555948437432049586089024300970437646867574391499674950, 1), (12220860426343202300387956629311332530846772104903362109509733228358624140562641026241011441975647352701, 1)]
c = 12220860426343202300387956629311332530846772104903362109509733228358624140562641026241011441975647352701
print(long_to_bytes(c))

4XWi11's Blog

20210828-WMCTF-CryptoSecPartWriteUp

checkin

Knackpack Encryption

easylsb

ocb（not solve）

ezl1near（not solve）