WP for *ctf2021

第一次和V&N的师傅们打比赛就冲到了第六，好耶！

最后没AK，不好（悲）

Web

lottery again

看源码，找关键代码

加密部分

29.png

解密部分

30.png

兑换彩票部分

31.png

分析函数可以发现在兑换彩票的时候，会对彩票密文进行解码，通过解码得到的彩票lottery内容从数据库中找到对应数据，取得可兑换的coin数量，并把coin加到解码得到的user账号的硬币中。

分析代码可知，从密文中取得的user账号没有与在数据库中的信息进行验证，故如果我们可以篡改密文中对应的user信息，那么就可以让a用户购买的彩票，给b用户使用，从而让b用户达到白嫖的目的。

我们发现加密方式为MCRYPT_RIJNDAEL_256，ECB模式，通过手动测试发现该算法的分组方式为32字节为一组，在这样的前提下，我们可以尝试替换储存在其中的user数据。

以下来逐步分析如何替换全部user-uuid信息

我们已有的密文数据是：

1
2
3
4
{"lottery":"b52d5239-24a5-4627-b
a46-58a00645c3e4","user":"111111
11-1111-1111-1111-111111111111",
"coin":1}

和

1
2
3
4
{"lottery":"demodemo-demo-demo-d
emo-demodemodemo","user":"222222
22-2222-2222-2222-222222222222",
"coin":1}

如下为一个加密数据的明文内容，每一行的长度为0x20（除最后一行外

1
2
3
4
{"lottery":"b52d5239-24a5-4627-b
a46-58a00645c3e4","user":"111111
11-1111-1111-1111-111111111111",
"coin":1}

我们想要把其替换为

1
2
3
4
{"lottery":"b52d5239-24a5-4627-b
a46-58a00645c3e4","user":"222222
22-2222-2222-2222-222222222222",
"coin":1}

也就是把user信息都从1替换成2 但是我们只可以替换其中的任何一个一行的内容，才不会造成解密错误。于是我们自然可以考虑替换第三行的内容，其标志着该彩票购买者的部分uuid信息。但是由于只是部分uuid信息，所以即使替换了也是如下情况：

1
2
3
4
{"lottery":"b52d5239-24a5-4627-b
a46-58a00645c3e4","user":"111111
22-2222-2222-2222-222222222222",
"coin":1}

其user信息中的前六个字节无法被替换，由于六字节内容过长，不适合用爆破的方法来绕过。 但是如果我们考虑要把前六字节的信息也要替换的话，那么必须同时替换那一行的全部内容，也就是就会变成以下情况：

1
2
3
4
{"lottery":"b52d5239-24a5-4627-b
emo-demodemodemo","user":"222222
22-2222-2222-2222-222222222222",
"coin":1}

也就是会造成lottery信息被替换，这会造成该彩票无法从数据库中读取到，直接报错。 最终考虑到以下构造：

1
2
3
4
5
{"lottery":"b52d5239-24a5-4627-b
a46-58a00645c3e4","user":"111111
emo-demodemodemo","user":"222222
22-2222-2222-2222-222222222222",
"coin":1}

由于在php在json_decode的时候，后面的user会覆盖前面的user，也就是正确的user可以覆盖错误的user，成功修改user信息。

其他部分就是，需要注册、登录、购买、彩票、兑换彩票，可以写个脚本使其自动化。代码中的target为最终要用于购买flag的账号的一个彩票密文数据。

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
import requests
import json
import base64
url = "http://52.149.144.45:8080"
req = requests.session()

def getheaders():
    return {"Cookie" : "api_token=" + token}

def reg(user, pwd):
    text = req.post(url + "/user/register", data={"username": user, "password": pwd}).text
    data = json.loads(text)
    return data

def login(user, pwd):
    text = req.post(url + "/user/login", data={"username": user, "password": pwd}).text
    data = json.loads(text)
    return data

def buy(token):
    text = req.post(url + "/lottery/buy", data={"api_token": token}).text
    data = json.loads(text)
    return data

def hijack(enc, enc2):
    enc = base64.b64decode(enc)
    enc2 = base64.b64decode(enc2)
    return enc[:0x40] + enc2[0x20:0x60] + enc[0x60:]

def getInfo(enc):
    text = req.post(url + "/lottery/info", data={"enc": enc}).text
    data = json.loads(text)
    return data

def charge(user, coin, enc):
    text = req.post(url + "/lottery/charge", data={"user": user, "enc" : enc, "coin" : coin}).text
    data = json.loads(text)
    return data

target = '***************jjXj40HxYWzD7/wbbu6LB8hKIgHzspmlNP0zCwC07w6uK7rCLP2MvVoq8P2oXt+OoD1NY2Ba5J5Hs1AiZkdxBRIrTSq9H8y2BmPiCmO6fH2d9eJW+rk8BfTg14RVjLwF1pW5cSqW2FXVyWb0j5c8edRkKKGE='
uuid = getInfo(target)['info']['user']
for i in range(1000):
    reg_data = reg('wjhflag' + str(i), '123456')
    login_data = login('wjhflag' + str(i), '123456')
    token = login_data['user']['api_token']
    for i in range(3):
        buy_data = buy(token)
        enc = buy_data['enc']
        fake_enc = base64.b64encode(hijack(enc, target))
        data = charge(uuid, 0, fake_enc)
        print(data)

Crypto

GuessKey

憨憨出题人把key给出来了，猜（复制）数字

GuessKey2

GuessKey_fix 其实就是不给key了

先分析题目，看起来是要让我们去猜这个key，但显然不可能成功

接着看下面发现我们每次可以给服务器发送一个mask，来对这个key进行改变，而改变的位置是key中0所在的位置随机选两个的区间来与mask异或，那么也就是说，每次选取的起止位置都是0，那么也就是说每一次的mask都会影响到这两个0

我们选择mask每一次都打1，这样每次的这两个0都会被异或成1（虽然有些地方也变成了0），但是相较于上一个状态，0的区间是被缩小了的，也就是说，在有限次的mask处理过后，key会变成0b1111111111111111111111111111111111111111111111111111111111111111，所以我们每次的guess就可以作为检测，当我们得到Nice.时，也就可以得知此时的key是0b1111111111111111111111111111111111111111111111111111111111111111，相当于key已知，和GuessKey就变成了一道题

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
from Crypto.Util.number import *
from hashlib import sha256
from gmpy2 import *
from pwn import *

r = remote("52.163.228.53", "8082")
turn = 0

while True:
    turn += 1
    r.recvuntil("mask:")
    r.sendline('1')
    r.recvuntil("guess:")
    r.sendline('18446744073709551615')
    back = r.recvline(False)
    print(turn,back)
    if(back == b'Nice.'):
        break

for i in range(2):
    r.recvuntil("mask:")
    r.sendline('0')
    r.recvuntil("guess:")
    r.sendline('18446744073709551615')
    back = r.recvline(False)
    print(turn,back)

flag = r.recvline(False)
print(flag)

MyEnc

这个题把flag当成key，对于我们给出的每个数字根据key的接下来6位对iv进行操作，因为我们已知flag的格式为*CTF{...}，所以我们对于key的前几十位是已知的，所以可以通过前几次操作来得到我们想要的东西

因为返回的值是 $iv+(m ⊕ q)^{i^{i^i}}$ ，我们简记为 $iv+(m⊕q)^{x}$ ，那么我们可以两次令m为0，得到数的即为 $iv+q^x$ 与 $iv+q^y$ ，可知 $q = gcd(n,(iv+q^x)-(iv+q^y))$ ，那么n就可以被轻松分解

接着我们可以令m等于q，这样就可以得到iv

接下来再令m等于0（其实等于几都能算，等于0方便点而已），由于iv、q全部已知，而且状态不超过 $2^7$ ，即可爆破状态，即为此时的6位key

手动补全前几位的key，然后不断通过爆破得到接下来的6位key，当key的长度达到120时，前120位即为flag

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
from Crypto.Util.number import *
from hashlib import sha256
from gmpy2 import *
from pwn import *

table = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
r = remote("52.163.228.53", "8081")

def passpow():
	rev = r.recvuntil("sha256(xxxx+")
	suffix = r.recv(16).decode()
	r.recvuntil(" == ")
	res = r.recv(64).decode()
	def f(x):
		hashresult = hashlib.sha256((x+suffix).encode()).hexdigest()
		if hashresult == res:
			return 1
		else:
			return 0
	prefix = util.iters.mbruteforce(f,table,4,'upto')
	r.recvuntil("Give me xxxx:")
	r.sendline(str(prefix))

def talk(x):
	r.recvuntil("give me a number:\n")
	r.sendline(str(x))
	r.recvuntil("done: ")
	return int(r.recvline(False).strip().decode())

passpow()
print('Successfully pass the pow!')

r.recvuntil("n: ")
n = int(r.recvline(False).strip().decode())
print(n)

a = talk(0)
b = talk(0)
delta = b+n-a

q = gcd(delta,n)
assert q != 1
p = n // q
assert p * q == n

iv = talk(q)

phi = (p-1) * (q-1)
elist = []
for i in range(1,8):
	elist.append(pow(i,pow(i,i,phi),phi))

flag = '001010100100001101010'

while (len(flag)<120):
	delta = talk(0) - iv
	for i in range(128):
		tmp = bin(i)[2:].rjust(7,'0')
		res = 0
		for j in range(len(tmp)):
			if(tmp[j] == '1'):
				res += pow(q,elist[j],n)
				res %= n
		if(delta%n == res):
			flag += bin(i)[2:].rjust(7,'0')
			print(bin(i)[2:].rjust(7,'0'))
			break

flag = flag[:120]
print(flag)
flag = long_to_bytes(int(flag,2))
print(flag)

little case

题目分为两部分，一个是little_trick，一个是real_trick

阅读代码后发现little_trick就是RSA的wiener attack，最后即可分解n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from gmpy2 import *

n1 = 21669699875387343975765484834175962461348837371447024695458479154615348697330944566714587217852888702291368306637977095490953192701450127798670425959768118384915082017373951315699899009631834471691811815393784748930880954114446745814058132752897827717077886547911476575751254872623927783670252969995075629255541621917767501261249192653546875104532649043219697616464205772025267019328364349763854659490144531087349974469079255236823096415094552037488277752927579909539401311624671444833332618177513356173537573280352724384376372955100031534236816681805396608147647003653628203258681097552049114308367967967184116839561
p1 = 125457275769068125757485908164006976153846494199951055956773829512867658202991509882220598391130551501414264867302691498062034690987771420463818096949614464177297177742292221196272475473441901790650971196178740160270878352307469807794533558079725928555246759355468676092854618354193968504322694550607414849887
q1 = 172725732665160218766764654273481422951178250693790825716359642314019315013321867434849375780994146440118500992456863730311444752367847389052666095324149584230474450693683416636565463345342017830651196454735159385924736453857045827989347928771104006978412412405607299616293396656259291378061505961429915687703
e1 = 20717541468269984768938524534679430706714860712589983300712432366828367981392533792814384884126053081363266457682162675931547901815985830455612301105504518353600255693451085179954519939635263372257973143178677586338992274607959326361412487748088349413448526455377296931144384663805056580662706419414607407821761761574754611275621927387380065975844282519447660467416826579669726178901884060454994606177784839804528666823956703141147239309978420776148158425922031573513062568162012505209805669623841355103885621402814626329355281853436655713194649170570579414480803671531927080535374958180810697826214794117466378050607
d1 = 36167461773898995192586226632578677184913220227461899855497899052924496298787

c1 = 17653913822265292046140436077352027388518012934178497059850703004839268622175666123728756590505344279395546682262531546841391088108347695091027910544112830270722179480786859703225421972669021406495452107007154426730798752912163553332446929049057464612267870012438268458914652129391150217932076946886301294155031704279222594842585123671871118879574946424138391703308869753154497665630799300138651304835205755177940116680821142858923842124294529640719629497853598914963074656319325664210104788201957945801990296604585721820046391439235286951088086966253038989586737352467905401107613763487302070546247282406664431777475
p = pow(c1,d1,n1) + 1
n = 22346087036331379968192118389403047568445805414881948978518580277027027486284293415097623011228506968071753709256352246733181304513713003096615266613365080909760605498017330085960699607777361429562376124376340215426398797920168016137830563564636922257215066266075494625782943973857490781916694118187094786034792437781964601089843549995939887939410763350338658901108020658475956489391300528691289604149598720803012371765770928211044755626045817053870803040863722458554924076011151695567147976903053993914859714631837755435592006986598006207692599019026644753575853382810261910332197447386727419606073948645238377595719
q = n // p
assert p * q == n

cipher = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406
phi = (p-1) * (q-1)
print(p)
print(q)

real_tirck中给出了e的下界，以及告诉e和phi并不互素，所以我们猜测 $e\mid\varphi(n)$ （这里其实应该有证明的，有时间了再回来证），所以我们从下界爆破e，并使用AMM测试，能够跑出flag的即为正确的e

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
import random
import time

# About 3 seconds to run
def AMM(o, r, q):
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            j = - discrete_log(d, a)
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    return result

def findAllPRoot(p, e):
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    return proot

def findAllSolutions(mp, proot, cp, p):
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    return all_mp


c = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print(mps, mqs)

def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if bytes.fromhex(h).startswith(b'*CTF') or bytes.fromhex(h).startswith(b'*ctf'):
        print(bytes.fromhex(h))
        return True
    else:
        return False


qwq = []

start = time.time()
print('Start')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
            qwq.append(solution)
    print(time.time() - start)

print(qwq)
end = time.time()
print("{} s.".format(end - start))
# 1061.3823564052582 s.
# b'*CTF{S0_Y0u_ARE_REA11Y_GOOd_At_Pla1_This}Ifyoumissthetrainimonyouwillknowthatiamgoneyoucanheartheflagfluwwwwwwwwww'
# 5715792447162584004830995621288196364667316788985719423575200593843082226610550301623816157835166569193582787431644910982754181340491582409788340367828925355394884518044538804653367543125682677650052644197537897019515168750419392615178911318381369421233129629180441067485047

MyCurve

先放个神仙的sol和资料，有时间回来复现

binary edwards curve
这个曲线和正常的ecc有一个一一对应的映射
映射回去的曲线的阶光滑
容易算dlp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
name binary Edwards curves
parameter d1
parameter d2
coordinate x
coordinate y
satisfying d1(x+y)+d2(x^2+y^2) = (x+x^2)(y+y^2)
addition x = (d1(x1+x2)+d2(x1+y1)(x2+y2)+(x1+x1^2)(x2(y1+y2+1)+y1 y2)) / (d1+(x1+x1^2)(x2+y2))
addition y = (d1(y1+y2)+d2(x1+y1)(x2+y2)+(y1+y1^2)(y2(x1+x2+1)+x1 x2)) / (d1+(y1+y1^2)(x2+y2))
doubling x = (d1(x1+x1)+d2(x1+y1)(x1+y1)+(x1+x1^2)(x1(y1+y1+1)+y1 y1)) / (d1+(x1+x1^2)(x1+y1))
doubling y = (d1(y1+y1)+d2(x1+y1)(x1+y1)+(y1+y1^2)(y1(x1+x1+1)+x1 x1)) / (d1+(y1+y1^2)(x1+y1))
negation x = y1
negation y = x1
toweierstrass u = d1(d1^2+d1+d2)(x+y)/(x y+d1(x+y))
toweierstrass v = d1(d1^2+d1+d2)(x/(x y+d1(x+y))+d1+1)
a0 = 1
a1 = 1
a2 = d1^2+d2
a3 = 0
a4 = 0
a6 = d1^4(d1^4+d1^2+d2^2)
fromweierstrass x = d1(u+d1^2+d1+d2)/(u+v+(d1^2+d1)(d1^2+d1+d2))
fromweierstrass y = d1(u+d1^2+d1+d2)/(v+(d1^2+d1)(d1^2+d1+d2))

Summary

最后摸了好久的鱼，不然就能AK了，呜呜，爬了