This writeup is long overdue, sorry about that. I participated in ACSC finals, and solved nearly all crypto, as there was a cryptography challenge that was really more about SQL Injection than cryptography. To be more detailed, the exact same cryptogrpahic vulnerability is used in one of the cryptohack challenges (and it has very similar setups as well) so the cryptographic side of the challenge is next to none. I had some fun learning some basic SQL Injection and got close, but ultimately failed to solve the challenge. I did solve all others, including one that was solved only by me. This writeup will be relatively short and concise, as I do not have a lot of time on my hands.
The solutions codes are on the usual github, https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/ACSC
RSA Stream
|
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
|
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse
from Crypto.Util.Padding import pad
from flag import m
#m = b"ACSC{<REDACTED>}" # flag!
f = open("chal.py","rb").read() # I'll encrypt myself!
print("len:",len(f))
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
e = 0x10001
print("n =",n)
print("e =",e)
print("# flag length:",len(m))
m = pad(m, 255)
m = bytes_to_long(m)
assert m < n
stream = pow(m,e,n)
cipher = b""
for a in range(0,len(f),256):
q = f[a:a+256]
if len(q) < 256:q = pad(q, 256)
q = bytes_to_long(q)
c = stream ^ q
cipher += long_to_bytes(c,256)
e = gmpy2.next_prime(e)
stream = pow(m,e,n)
open("chal.enc","wb").write(cipher)
|
cs |
We see that we are encrypting the given python file, so we know the plaintext and the ciphertext.
Since this is an XOR cipher, this implies that we know all the key streams used to encrypt the plaintext.
We note that the key streams are composed of $m^e \pmod{n}$ where $e$ are several primes.
Of course, if we know $m^{e_1} \pmod{n}$ and $m^{e_2} \pmod{n}$ with $\gcd(e_1, e_2) = 1$, we can find $r_1, r_2$ such that $e_1r_1 + e_2r_2 = 1$.
Now we can finish calculating $m$ by simply using $$m \equiv m^{e_1 \cdot r_1} m^{e_2 \cdot r_2} \pmod{n}$$
|
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
|
length = 723
n = 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453
e = 65537
f = open("chal.py","rb")
inp = f.read()
f.close()
f = open("chal.enc", "rb")
outp = f.read()
f.close()
data = []
e = 65537
for i in range(0, 768, 256):
cc = inp[i:i+256]
if len(cc) < 256:
cc = pad(cc, 256)
res = bytes_to_long(cc) ^ bytes_to_long(outp[i:i+256])
data.append([res, e])
e = nextprime(e)
u = inverse(65537, 65539)
v = (65537 * u - 1) // 65539
m = (pow(data[0][0], u, n) * inverse(pow(data[1][0], v, n), n)) % n
print(long_to_bytes(m))
|
cs |
CBCBC
|
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
126
127
128
129
130
131
|
#!/usr/bin/env python3
import base64
import json
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from secret import hidden_username, flag
key = os.urandom(16)
iv1 = os.urandom(16)
iv2 = os.urandom(16)
def encrypt(msg):
aes1 = AES.new(key, AES.MODE_CBC, iv1)
aes2 = AES.new(key, AES.MODE_CBC, iv2)
enc = aes2.encrypt(aes1.encrypt(pad(msg, 16)))
return iv1 + iv2 + enc
def decrypt(msg):
iv1, iv2, enc = msg[:16], msg[16:32], msg[32:]
aes1 = AES.new(key, AES.MODE_CBC, iv1)
aes2 = AES.new(key, AES.MODE_CBC, iv2)
msg = unpad(aes1.decrypt(aes2.decrypt(enc)), 16)
return msg
def create_user():
username = input("Your username: ")
if username:
data = {"username": username, "is_admin": False}
else:
# Default token
data = {"username": hidden_username, "is_admin": True}
token = encrypt(json.dumps(data).encode())
print("Your token: ")
print(base64.b64encode(token).decode())
def login():
username = input("Your username: ")
token = input("Your token: ").encode()
try:
data_raw = decrypt(base64.b64decode(token))
except:
print("Failed to login! Check your token again")
return None
try:
data = json.loads(data_raw.decode())
except:
print("Failed to login! Your token is malformed")
return None
if "username" not in data or data["username"] != username:
print("Failed to login! Check your username again")
return None
return data
def none_menu():
print("1. Create user")
print("2. Log in")
print("3. Exit")
try:
inp = int(input("> "))
except ValueError:
print("Wrong choice!")
return None
if inp == 1:
create_user()
return None
elif inp == 2:
return login()
elif inp == 3:
exit(0)
else:
print("Wrong choice!")
return None
def user_menu(user):
print("1. Show flag")
print("2. Log out")
print("3. Exit")
try:
inp = int(input("> "))
except ValueError:
print("Wrong choice!")
return None
if inp == 1:
if "is_admin" in user and user["is_admin"]:
print(flag)
else:
print("No.")
return user
elif inp == 2:
return None
elif inp == 3:
exit(0)
else:
print("Wrong choice!")
return None
def main():
user = None
print("Welcome to CBCBC flag sharing service!")
print("You can get the flag free!")
print("This is super-duper safe from padding oracle attacks,")
print("because it's using CBC twice!")
print("=====================================================")
while True:
if user:
user = user_menu(user)
else:
user = none_menu()
if __name__ == "__main__":
main()
|
cs |
We have a cipher that uses AES-CBC two times. From line 118 we see that padding oracle attacks still work.
If we write out the entire decryption process, we get that $$P_n = D_k(D_k(C_n) \oplus C_{n-1}) \oplus D_k(C_{n-1}) \oplus C_{n-2}$$ where $C_0 = IV_2$ and $C_{-1} = IV_1$. Note that $P_n$ can be easily controlled by $C_{n-2}$.
Therefore, the whole padding oracle attacks work, it's just that we need to change 2 blocks before the targeted block to perform the attack. The remaining parts are straightforward if you have solid understanding of padding oracle attack.
|
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
|
r = remote('167.99.77.49', 52171)
# r.interactive()
def read_menu(x):
for _ in range(x):
r.recvline()
read_menu(5)
read_menu(3)
r.sendline(b"1")
r.send(b"\n")
r.recvline()
token = r.recvline()
token = b64decode(token)
print(token)
print(len(token))
true_ptxt = [0] * 80
for i in range(64, 16, -16):
for j in range(0, 16):
for k in tqdm(range(0, 256)):
if i == 64 and j == 0 and k == 0:
continue
query_token = token[:i-j-17]
query_token += bytes([token[i-j-17] ^ k])
for u in range(j):
query_token += bytes([token[i-j-16+u] ^ true_ptxt[i-j+16+u] ^ (j+1)])
query_token += token[i-16:i+16]
read_menu(3)
r.sendline(b"2")
r.sendline(b"abc")
r.sendline(b64encode(query_token))
res = r.recvline()
if b"Check your token again" not in res:
true_ptxt[i+15-j] = k ^ (j+1)
break
print(bytes(true_ptxt))
print(bytes(true_ptxt))
|
cs |
Swap on Curve
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
from params import p, a, b, flag, y
x = int.from_bytes(flag, "big")
assert 0 < x < p
assert 0 < y < p
assert x != y
EC = EllipticCurve(GF(p), [a, b])
assert EC(x,y)
assert EC(y,x)
print("p = {}".format(p))
print("a = {}".format(a))
print("b = {}".format(b))
|
cs |
Basically we have to solve $$y^2 = x^3 + ax + b, \quad x^2 = y^3 + ay + b$$ which can be done by doing algebra to change it into a one variable polynomial equation, or using resultants to achieve the same goal. I used the latter option, also using what I learned from joseph (https://twitter.com/josep68_) in CryptoHack discord. Sometimes the resultant function on Sagemath doesn't work for some reason I don't fully understand, but you can get around this by using sylvester matrix trickery.
|
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
|
'''
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
return Matrix.determinant(f1.sylvester_matrix(f2, var))
p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
POL.<x, y> = PolynomialRing(GF(p))
f = y * y - x * x * x - a * x - b
g = x * x - y * y * y - a * y - b
res = resultant(f, g, y)
print(res.roots())
'''
p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
val = [(7701093676539600849545233775656266124024393901117284843908110961515787578426141185510163529087490707005602090170967486760425035325079989548242482516345996, 1), (7677785116435727686649964446582280200653867847347508329665823423662012251739816682685754769395346602260506848926697976097716406737781893094340049957504162, 1), (3418100096957777329641522385874601707957378769808441636922695882579741403099793135186593317827442718653892790484853393209667843889446155946725442732255448, 1)]
for a, b in val:
print(long_to_bytes(a))
|
cs |
Two Rabin
|
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 random
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from flag import flag
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
B = getStrongPrime(512)
m = flag[0:len(flag)//2]
print("flag1_len =",len(m))
m1 = bytes_to_long(m)
m2 = bytes_to_long(pad(m,128))
assert m1 < n
assert m2 < n
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
print("n =",n)
print("B =",B)
print("c1 =",c1)
print("c2 =",c2)
# Harder!
m = flag[len(flag)//2:]
print("flag2_len =",len(m))
m1 = bytes_to_long(m)
m1 <<= ( (128-len(m))*8 )
m1 += random.SystemRandom().getrandbits( (128-len(m))*8 )
m2 = bytes_to_long(m)
m2 <<= ( (128-len(m))*8 )
m2 += random.SystemRandom().getrandbits( (128-len(m))*8 )
assert m1 < n
assert m2 < n
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
print("hard_c1 =",c1)
print("hard_c2 =",c2)
|
cs |
We have two separate problems, each of which needs to be solved to get the flag.
For the first problem, there is a known linear relation between the two messages since the pad is not random. Therefore, the two equations given can both be written as a polynomial equation of a single variable, which means that the system can be solved by polynomial GCD or basic algebra as both equations are only quadratic. I chose the latter option for some reason :P
For the second problem, the padding is small but they are random. Therefore, we can write the first message as $x$ and the second message as $x+y$ where $y$ is some small value. Since we have two quadratic equations on $x, y$, we can use resultants again to make a polynomial equation on $y$ only. Since $y$ is small, this polynomial equation can be solved via coppersmith's attack. After getting $y$, we now have two quadratic equations where $x$ is the only variable, which can be solved similarly as the first problem.
|
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
|
flag1_len = 98
n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
c1 = 47149257341850631803344907793040624016460864394802627848277699824692112650262968210121452299581667376809654259561510658416826163949830223407035750286554940980726936799838074413937433800942520987785496915219844827204556044437125649495753599550708106983195864758161432571740109614959841908745488347057154186396
c2 = 38096143360064857625836039270668052307251843760085437365614169441559213241186400206703536344838144000472263634954875924378598171294646491844012132284477949793329427432803416979432652621257006572714223359085436237334735438682570204741205174909769464683299442221434350777366303691294099640097749346031264625862
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
P = PolynomialRing(Zmod(n), 'x')
x = P.gen()
f = x * (x + B) - c1
mul = (1 << (8 * (128 - flag1_len)))
cc = bytes_to_long(b"\x1e" * 30)
g = (mul * x + cc) * (mul * x + cc + B) - c2
g = g.monic()
h = f - g
cc = h.coefficients()
m = (int(cc[0]) * inverse(int(n - cc[1]), n)) % n
flag1 = long_to_bytes(m)
'''
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
return Matrix.determinant(f1.sylvester_matrix(f2, var))
n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
POL.<x, y> = PolynomialRing(Zmod(n))
f = x * (x + B) - hard_c1
g = (x + y) * (x + y + B) - hard_c2
res = resultant(f, g, x)
print(res)
POL.<y> = PolynomialRing(Zmod(n))
h = y^4 + 79890495413921998317755749042148232336863396932303122279875240130974185840791225375990895444267582903006871773965303045933569843994868097491212523442101173551279596449914721209311144221088483103651821516943100935730831208926818636117783500717523025942791406004609937226219367532136778920138824547343785869589*y^2 + 51092857055466673249380987427595244393604870491102664532822637562859699012127822437087645886784256843354629922356917208150074797607882719481678015312190222601448915412917964775219154717370030324105055787501129672958587186322761301111111401381772704665208028130495822463025972061040003730113313298834567354767
print(h.small_roots(X = (1 << 240), beta = 1.0, epsilon = 0.025))''
y_cands = [1637558660573652475698054766420163959191730746581158985657024969935597275, 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003324807101635213925825667932900258849901826251288979045274120411473033890824]
POL.<x> = PolynomialRing(Zmod(n))
for y in y_cands:
f = x * (x + B) - hard_c1
g = (x + y) * (x + y + B) - hard_c2
h = f - g
print(h)
cc = h.coefficients()
print(cc)
x = - cc[0] / cc[1]
print(h(x))
x = int(x)
print("result", x)
print(int(x * (x + B) - hard_c1) % n)
print(int((x+y)*(x+y+B)-hard_c2) % n)
break
'''
x1 = 37412309942286574006158913496010620267687663146876352767622106656129986496651165862840203148321069273733293624726376167460944865534151793748073347584719705531628535234167400567407324714477822390166015938266208084466510307154956915004073076813624952897284616411776573796324151099101617608303133521659321079317
x1 = n - B - x1
print((x1 * (x1+ B) - hard_c1) % n)
m = x1 >> 240
flag2= long_to_bytes(m)
print(flag2)
print(flag1 + flag2)
|
cs |
Wonderful Hash
|
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
|
import os
import string
from Crypto.Cipher import AES, ARC4, DES
BLOCK = 16
def bxor(a, b):
res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
return bytes(res)
def block_hash(data):
data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
return data[:-2]
def hash(data):
length = len(data)
if length % BLOCK != 0:
pad_len = BLOCK - length % BLOCK
data += bytes([pad_len] * pad_len)
length += pad_len
block_cnt = length // BLOCK
blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
res = b"\x00" * BLOCK
for block in blocks:
res = bxor(res, block_hash(block))
return res
def check(cmd, new_cmd):
if len(cmd) != len(new_cmd):
return False
if hash(cmd) != hash(new_cmd):
return False
for c in new_cmd:
if chr(c) not in string.printable:
return False
return True
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
b"our days, some of them have excelent tasks, but in most cases "
b"they're forgotten just after the CTF finished. We decided to make"
b" some kind of CTF archive and of course, it'll be too boring to "
b"have just an archive, so we made a place, where you can get some "
b"another CTF-related info - current overall Capture The Flag team "
b"rating, per-team statistics etc'")
def menu():
print("[S]tore command")
print("[E]xecute command")
print("[F]iles")
print("[L]eave")
return input("> ")
while True:
choice = menu()
if choice[0] == "S":
new_cmd = input().encode()
if check(cmd, new_cmd):
cmd = new_cmd
else:
print("Oops!")
exit(1)
elif choice[0] == "E":
os.system(cmd)
elif choice[0] == "F":
os.system(b"ls")
elif choice[0] == "L":
break
else:
print("Command Unsupported")
exit(1)
|
cs |
We require some sort of a hash collision. Since the hash is simply XOR of the hash of each blocks, this problem is equivalent to finding $x_1, x_2, \cdots, x_k$ given sets $X_1, X_2, \cdots, X_k$ such that the following holds. $$x_i \in X_i, \quad \oplus_{i=1}^k x_i = 0$$ Of course, if $k=2$ this is the well-known birthday problem.
While I'm not sure if this was required for this challenge, this problem has been studied before. It's in the 2002 CRYPTO paper "A Generalized Birthday Problem", and it has been explained by barkingdog in his blog post https://www.secmem.org/blog/2020/08/19/A-Generalized-Birthday-Problem/. Using this, we can solve the problem in $\mathcal{O}(2^{n/(1+\log_2 k)})$. The basic idea is to make a binary tree and solve the problem "partially" (make LSBs zero) as we go upwards. For more details, consult the blog post above or the 2002 paper.
|
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
126
127
128
129
130
131
132
133
|
r = remote('wonderful-hash.chal.acsc.asia', 10217)
for i in range(5):
print(r.recvline())
ans = b'cat flag DxriPBQeGgXmjlewgmpxnBnWbfoxGirrLUtUlukpPmjqMOlCBmaOIXXqKIGXoFJsdVGypWXGdXcPScZXFQPbnigusUZZdrxpCyMeGgKGqzJQIzbRqThOJXNgPPNXdPjIOtRhGKBXJDlYDGMfcnyAIojYUJaFyUhzjlsSQHZPasglvQOWIyVoYELtFwJQSsBPsNpvcKZYuKWBrEHwDQLkpCYWkbNIHPTHxbPqrzDgcXCnVvJKeIzkiMKqPhUwDRIe '
r.sendline("S")
r.sendline(ans)
for i in range(4):
print(r.recvline())
r.sendline("E")
for i in range(10):
print(r.recvline())
## main sol
BLOCK = 16
def bxor(a, b):
res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
return bytes(res)
def block_hash(data):
data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
return data[:-2]
def hash(data):
length = len(data)
if length % BLOCK != 0:
pad_len = BLOCK - length % BLOCK
data += bytes([pad_len] * pad_len)
length += pad_len
block_cnt = length // BLOCK
blocks = [data[i * BLOCK:(i + 1) * BLOCK] for i in range(block_cnt)]
res = b"\x00" * BLOCK
for block in blocks:
res = bxor(res, block_hash(block))
return res
def get_random_block():
res = "".join([rand.choice(string.ascii_letters) for _ in range(16)])
return res.encode()
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
b"our days, some of them have excelent tasks, but in most cases "
b"they're forgotten just after the CTF finished. We decided to make"
b" some kind of CTF archive and of course, it'll be too boring to "
b"have just an archive, so we made a place, where you can get some "
b"another CTF-related info - current overall Capture The Flag team "
b"rating, per-team statistics etc'")
# 27
print(len(cmd))
target = bytes_to_long(hash(cmd))
fin_blocks = []
block0 = b"cat flag" + b" " * 8
fin_blocks.append(block0)
target ^= bytes_to_long(block_hash(block0))
back_blocks = []
for i in range(9):
back_blocks.append(b" " * 16)
target ^= bytes_to_long(block_hash(b" "*16))
back_blocks.append(b" ")
target ^= bytes_to_long(block_hash(b" " + bytes([15] * 15)))
# now we need 16 blocks
grounds = []
for i in range(16):
cur = []
for j in range(6000):
val = get_random_block()
cc = block_hash(val)
cc = bytes_to_long(cc)
if i == 7:
cc ^= target
cur.append([[val], cc])
grounds.append(cur)
def merger(l, r, tot): # merging [l, r) to have tot zeros
print("WORKING", l, r, tot)
global grounds
if l + 1 == r:
return grounds[l]
cc1 = merger(l, (l+r)//2, tot - 12)
cc2 = merger((l+r) // 2, r, tot - 12)
print(l, (l+r)//2, len(cc1))
print((l+r)//2, r, len(cc2))
LEFT = {}
for i in range(len(cc1)):
res = cc1[i][1] % (1 << tot)
if res in LEFT.keys():
arr = LEFT[res]
arr.append(i)
LEFT[res] = arr
else:
LEFT[res] = [i]
ret = []
for i in range(len(cc2)):
res = cc2[i][1] % (1 << tot)
if res in LEFT.keys():
arr = LEFT[res]
for idx in arr:
xred = cc1[idx][1] ^ cc2[i][1]
vals = cc1[idx][0] + cc2[i][0]
ret.append([vals, xred])
return ret
fin = merger(0, 16, 48)
print(fin[0])
ret = fin[0][0]
sol = fin_blocks + ret + back_blocks
gogo = b""
for block in sol:
gogo += block
print(gogo)
print(len(gogo))
print(hash(gogo))
print(hash(cmd))
|
cs |
Share The 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
|
#!/usr/bin/env python3
import os
import random
import string
with open('flag.txt', 'rb') as f:
FLAG = f.read().strip()
assert FLAG.startswith(b'ACSC{')
assert FLAG.endswith(b'}')
SECRET = FLAG[5:-1]
assert len(SECRET) == 16
p = 251
def random_letters(n):
return ''.join(random.choices(string.ascii_lowercase, k=n)).encode()
print("""\
.----------------.
| Share the flag |
'----------------'
Welcome to our flag-sharing service.
We understand some of you couldn't resist sharing flags with others,
but it is STRICTLY PROHIBITED by the rules.
In order to satisfy your desire...
We made the official flag sharing service for you,
with a new algorithm inspired by Shamir Secret Sharing.
""")
# You'll need at least `threshold` shares to unlock the flag
threshold = 32
# Admin holds `len(SECRET) + 1` shares.
nshares = threshold - (len(SECRET) + 1)
# Splitting the flag
padding = random_letters(threshold - len(SECRET))
coeff = list(SECRET + padding)
xs = bytes(random.sample(range(1, p), k=nshares))
ys = bytes(sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p for x in xs)
print(f'X: {xs.hex()}')
print(f'Y: {ys.hex()}')
|
cs |
This will be explained further later when I upload the CVP repository updates.
|
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
def SVP_oracle(mat):
M = mat.BKZ(block_size = 30)
return M
def solve(mat, lb, ub):
num_var = mat.nrows()
num_ineq = mat.ncols()
max_element = 0
for i in range(num_var):
for j in range(num_ineq):
max_element = max(max_element, abs(mat[i, j]))
# sanity checker
if len(lb) != num_ineq:
print("Fail: len(lb) != num_ineq")
return None, None
if len(ub) != num_ineq:
print("Fail: len(ub) != num_ineq")
return None, None
for i in range(num_ineq):
if lb[i] > ub[i]:
print("Fail: lb[i] > ub[i] at index", i)
return None, None
if num_var != num_ineq:
print("Fail: This time, we require num_var = num_ineq")
return None, None
N = (num_var + num_ineq) // 2
# heuristic for number of solutions
DET = abs(mat.det())
num_sol = 1
for i in range(N):
num_sol *= (ub[i] - lb[i] + 1)
if DET == 0:
print("Fail: Zero Determinant")
return None, None
else:
num_sol //= DET
# + 1 added in for the sake of not making it zero...
print("Expected Number of Solutions : ", num_sol + 1)
# recentering + scaling process begins
max_diff = max([ub[i] - lb[i] for i in range(N)])
applied_weights = []
for i in range(N):
ineq_weight = max_diff // (ub[i] - lb[i])
applied_weights.append(ineq_weight)
for j in range(N):
mat[j, i] *= ineq_weight
lb[i] *= ineq_weight
ub[i] *= ineq_weight
target = vector([(lb[i] + ub[i]) // 2 for i in range(N)])
embedding = 251
Kannan = Matrix(ZZ, N+1, N+1)
for i in range(0, N):
for j in range(0, N):
Kannan[i, j] = mat[i, j]
Kannan[i, N] = 0
for i in range(0, N):
Kannan[N, i] = target[i]
Kannan[N, N] = embedding
# SVP time
result = SVP_oracle(Kannan)
# finding solution
fin_result = None
for i in range(N+1):
isok = True
if abs(result[i, N]) != embedding:
isok = False
result_vector = result[i]
if result[i, N] == embedding:
result_vector = -result_vector
# now result = actual_vector - target
for j in range(N):
if (lb[j] <= result_vector[j] + target[j] <= ub[j]) == False:
isok = False
if isok == False:
continue
print("Found Vector!!")
fin_result = result_vector[:N] + target
if fin_result == None:
print("Fail: could not solve...")
return None, None
return fin_result, applied_weights
# r = remote('share-the-flag.chal.acsc.asia', 37896)
# r.interactive()
p = 251
X = bytes.fromhex("02d4623be12c8f01cb2ebe5f837c1d")
Y = bytes.fromhex("bbdc06ceb34da7b16336b007dc5492")
X2 = bytes.fromhex("2fb9e753b237e68d35e266b0f01c9e")
Y2 = bytes.fromhex("20c0be9140f5a33d71b9e82f8f9409")
X3 = bytes.fromhex("f42e3ee10edeade0a3804a22e86a63")
Y3 = bytes.fromhex("c7224da73d9d96254f94136d9a65f1")
X4 = bytes.fromhex("37c9b07870283dd3f6198c46f027dd")
Y4 = bytes.fromhex("8101a88a365526e8faf417b79599a0")
X5 = bytes.fromhex("b0342cb7b3f5a022d927f9019a1bf3")
Y5 = bytes.fromhex("e2666d892955494775aa3c96c441f5")
X6 = bytes.fromhex("e56bf4f9e746252dbacb93a0a95087")
Y6 = bytes.fromhex("cbb43831857333b2c4663ba2c9189a")
X7 = bytes.fromhex("99ca36b1633cf3d903d8e6291f1bdc")
Y7 = bytes.fromhex("25180068651818171d10422dbdb395")
M = Matrix(GF(p), 105, 128)
vec = []
for i in range(105):
x, y = 0, 0
if i < 15:
x = int(X[i])
y = int(Y[i])
elif i < 30:
x = int(X2[i - 15])
y = int(Y2[i - 15])
elif i < 45:
x = int(X3[i - 30])
y = int(Y3[i - 30])
elif i < 60:
x = int(X4[i - 45])
y = int(Y4[i - 45])
elif i < 75:
x = int(X5[i - 60])
y = int(Y5[i - 60])
elif i < 90:
x = int(X6[i - 75])
y = int(Y6[i - 75])
elif i < 105:
x = int(X6[i - 90])
y = int(Y6[i - 90])
vec.append(y)
for j in range(16):
M[i, j] = (x ** j) % p
if i < 15:
for j in range(16):
M[i, j + 16] = (x ** (j + 16)) % p
elif i < 30:
for j in range(16):
M[i, j + 32] = (x ** (j + 16)) % p
elif i < 45:
for j in range(16):
M[i, j + 48] = (x ** (j + 16)) % p
elif i < 60:
for j in range(16):
M[i, j + 64] = (x ** (j + 16)) % p
elif i < 75:
for j in range(16):
M[i, j + 80] = (x ** (j + 16)) % p
elif i < 90:
for j in range(16):
M[i, j + 96] = (x ** (j + 16)) % p
elif i < 105:
for j in range(16):
M[i, j + 112] = (x ** (j + 16)) % p
vec = vector(GF(p), vec)
bas = M.right_kernel().basis()
print(len(bas))
v = M.solve_right(vec)
# v + bas -> all in 97 ~ 122
M = Matrix(ZZ, 151, 151)
lb = [0] * 151
ub = [0] * 151
for i in range(23):
for j in range(128):
M[i, j] = int(bas[i][j])
M[i, 128 + i] = 1
for i in range(128):
M[23 + i, i] = p
for i in range(128):
if i >= 16:
lb[i] = int(97 - int(v[i]))
ub[i] = int(122 - int(v[i]))
else:
lb[i] = int(32-int(v[i]))
ub[i] = int(128-int(v[i]))
for i in range(23):
lb[i + 128] = 0
ub[i + 128] = p
fin_result, applied_weights = solve(M, lb, ub)
flag = ''
for i in range(16):
flag += chr((fin_result[i] // applied_weights[i] + int(v[i]) + 251 * 30) % 251)
print("ACSC{" + flag + "}")
|
cs |
'CTF' 카테고리의 다른 글
| TSGCTF 2021 Writeups (0) | 2021.10.03 |
|---|---|
| DUCTF 2021 Writeups (0) | 2021.09.26 |
| CryptoCTF Writeups (DoRSA, Polish) (0) | 2021.08.05 |
| GoogleCTF Quals 2021 Crypto Writeups (1) | 2021.07.19 |
| zer0lfsr 2021 Full Writeup (0CTF/TCTF 2021) (2) | 2021.07.05 |