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!
 
= open("chal.py","rb").read() # I'll encrypt myself!
print("len:",len(f))
= getStrongPrime(1024)
= getStrongPrime(1024)
 
= p * q
= 0x10001
print("n =",n)
print("e =",e)
print("# flag length:",len(m))
= pad(m, 255)
= 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
= 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453
= 65537
 
= open("chal.py","rb")
inp = f.read()
f.close()
 
= open("chal.enc""rb")
outp = f.read()
f.close()
 
data = []
= 65537
 
for i in range(0768256):
    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)
 
= inverse(6553765539)
= (65537 * u - 1// 65539
 
= (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
= 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(6416-16):
    for j in range(016):
        for k in tqdm(range(0256)):
            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
 
= 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())
'''
 
 
= 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
= 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
= 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
 
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
 
val = [(77010936765396008495452337756562661240243939011172848439081109615157875784261411855101635290874907070056020901709674867604250353250799895482424825163459961), (76777851164357276866499644465822802006538678473475083296658234236620122517398166826857547693953466022605068489266979760977164067377818930943400499575041621), (34181000969577773296415223858746017079573787698084416369226958825797414030997931351865933178274427186538927904848533932096678438894461559467254427322554481)]
 
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
 
= getStrongPrime(512)
= getStrongPrime(512)
= p * q
= getStrongPrime(512)
 
= 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!
 
= 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
= 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
= 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
c1 = 47149257341850631803344907793040624016460864394802627848277699824692112650262968210121452299581667376809654259561510658416826163949830223407035750286554940980726936799838074413937433800942520987785496915219844827204556044437125649495753599550708106983195864758161432571740109614959841908745488347057154186396
c2 = 38096143360064857625836039270668052307251843760085437365614169441559213241186400206703536344838144000472263634954875924378598171294646491844012132284477949793329427432803416979432652621257006572714223359085436237334735438682570204741205174909769464683299442221434350777366303691294099640097749346031264625862
 
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
 
= PolynomialRing(Zmod(n), 'x')
= P.gen()
 
 
= x * (x + B) - c1
mul = (1 << (8 * (128 - flag1_len)))
cc = bytes_to_long(b"\x1e" * 30)
 
= (mul * x + cc) * (mul * x + cc + B) - c2
= g.monic()
 
= f - g 
cc = h.coefficients()
 
= (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)
 
 
= 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
= 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)//2len(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(01648)
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
 
= 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 NoneNone 
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return NoneNone 
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return NoneNone 
 
    if num_var != num_ineq:
        print("Fail: This time, we require num_var = num_ineq")
        return NoneNone
    
    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 NoneNone
    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 NoneNone
    
    return fin_result, applied_weights
 
 
 
# r = remote('share-the-flag.chal.acsc.asia', 37896)
# r.interactive()
 
= 251
= bytes.fromhex("02d4623be12c8f01cb2ebe5f837c1d")
= 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")
 
= Matrix(GF(p), 105128)
vec = []
for i in range(105):
    x, y = 00
    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))
= M.solve_right(vec)
 
# v + bas -> all in 97 ~ 122
 
= Matrix(ZZ, 151151)
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
ACSC Crypto Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
Lattice Attacks Introductory Survey  (0) 2021.07.22
GoogleCTF Quals 2021 Crypto Writeups  (1) 2021.07.19