20210828-WMCTF-CryptoSecPartWriteUp

  • 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中最小的那个,题目没有说清楚,给各位师傅添麻烦了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
<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会得到

image-20210828113817600

1
2
3
4
5
6
7
8
9
10
11
12
13
<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!<!-- so why not try to post 'flag' as rp? -->

  • flag

    1
    2
    3
    4
    5
    Your rp value:1620418829165478

    What happend to my bot?????

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

第一次写post脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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佬博客比较好懂

首先背包问题

image-20210903154901333

  • 私钥生成

    选择一个超递增集${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

有了这个可以求出密度

1
2
3
4
from math import log

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

说是低密度($d<0.9408$)可以直接搞,不太懂原理,抄个脚本

抄自论文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#!/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的高位,但也不知道拿来怎么用

保存了一组数据下来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# 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

image-20210903140354348

构造$B$这样的格

image-20210903141338898

$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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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出不来,往大一点的地方取

1
2
3
4
5
6
7
8
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次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

有限域开方也可以

1
2
3
4
5
6
7
8
9
10
11
12
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))

ocb(not solve)

ezl1near(not solve)