ASISCTF 2022 Quals Crypto Writeup

字数统计: 2.8k字   |   阅读时长≈ 17分

An enjoyable CTF competition！Never Stop Exploiting got the 4th place in the end. We solved all the six crypto challenges and here are the writeups by tl2cents.

 

Binned, 126 solves, 45 pts

 

Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3

from Crypto.Util.number import *
from gensafeprime import *
from flag import flag

def keygen(nbit):
	p, q = [generate(nbit) for _ in range(2)]
	return (p, q)

def encrypt(m, pubkey):
	return pow(pubkey + 1, m, pubkey ** 3)

p, q = keygen(512)
n = p * q

flag = bytes_to_long(flag)
enc = encrypt(flag, n)

print(f'pubkey = {n}')
print(f'enc = {enc}')

 

Solution

The encryption is : where . It seems like a discrete logarithm problem but the solution is far away from that. The order of with modulo is preventing any kind of smooth attack and subgroup attack. The trick is binomial expansion of and the left part is the first three terms in or the first two terms in . Just solve the equation in integer ring!

exp

1
2
3
4
5
6
7
8
9
10
11
12
# sage
from Crypto.Util.number import *
pubkey = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160
def encrypt(m, pubkey):
    return pow(pubkey + 1, m, pubkey ** 3)

P.<x> = PolynomialRing(ZZ)
f =  x*pubkey +1 - (enc%(pubkey^2))
# (n+1)^flag = enc mod n^3
flag = f.roots()[0][0]
print(long_to_bytes(int(flag)))

 

Chaffymasking, 66 solves, 73 pts

Just reverse the chaffy_mask function and find that the keys are given with a reversible encryption（xor） which might not be intended solution after seeing the flag.

exp

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
# python
from pwn import *
import numpy as np
import binascii
import os, sys
def pad(inp, length):
	result = inp + os.urandom(length - len(inp))
	return result

def byte_xor(a, b):
	return bytes(_a ^ _b for _a,_b in zip(a,b)) 
m, n = 512, 64 
IVK = # omit

LTC = np.zeros([n, m], dtype=(int))
LTC[0,:] = IVK

for i in range(1, n):
    for j in range(m // n + 1):
        LTC[i,j*n:(j+1)*n] = np.roll(IVK[j*n:(j+1)*n], i)
salt = os.urandom(m//8).hex().encode()
m, n = 512, 64 
q = n ** 2
half1_salt = salt[:m // 8]
half2_salt = salt[m // 8:]
xor_salts = int.from_bytes(byte_xor(half1_salt, half2_salt), "big")
assert xor_salts != 0
half1_binStr = "{:08b}".format(int(half1_salt.hex(),16))
if(len(half1_binStr) < m):
    half1_binStr = "0" * (m - len(half1_binStr)%m) + half1_binStr
half2_binStr = "{:08b}".format(int(half2_salt.hex(),16))
if(len(half2_binStr) < m):
    half2_binStr = "0" * (m - len(half2_binStr)%m) + half2_binStr

vec_1 = np.array(list(half1_binStr), dtype=int)
vec_1 = np.reshape(vec_1, (m,1))
vec_2 = np.array(list(half2_binStr), dtype=int)
vec_2 = np.reshape(vec_2, (m,1))
out_1 = LTC.dot(vec_1) % q
out_2 = LTC.dot(vec_2) % q

io = remote('65.21.255.31',31377)
io.sendlineafter(b"Give me your salt: ",salt)
io.recvuntil(b"masked_flag = ")
masked_flag= io.recvline().decode().strip()[2:]

enc = []
for i in range(n):
    enc.append(int(masked_flag[2*i:2*i+2],16))
enc_vec = np.reshape(enc,(n,1))

flagV = (enc_vec^out_1^out_2) % 256
print(f"[+] flagV {bytes(list(flagV.reshape(-1)))}")
# ASIS{Lattice_based_hash_collision_it_was_sooooooooooooooo_easY!}

 

Desired curve, 19 solves, 194 pts

 

Source code

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
#!/usr/bin/env sage

import sys
from Crypto.Util.number import *
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def main():
	border = "|"
	pr(border*72)
	pr(border, "Hi all, now it's time to solve a relatively simple challenge about  ", border)
	pr(border, "relatively elliptic curves! We will generate an elliptic curve with ", border)
	pr(border, "your desired parameters, are you ready!?                            ", border)
	pr(border*72)

	nbit = 256
	q = getPrime(nbit)
	F = GF(q)

	while True:
		pr(border, "Send the `y' element of two points in your desired elliptic curve:  ")
		ans = sc()
		try:
			y1, y2 = [int(_) % q for _ in ans.split(b',')]
		except:
			die(border, "Your parameters are not valid! Bye!!")
		A = (y1**2 - y2**2 - 1337**3 + 31337**3) * inverse(-30000, q) % q
		B = (y1**2 - 1337**3 - A * 1337) % q
		E = EllipticCurve(GF(q), [A, B])
		G = E.random_point()

		m = bytes_to_long(flag)
		assert m < q
		C = m * G
		pr(border, f'The parameters and encrypted flag are:')
		pr(border, f'q = {q}')
		pr(border, f'G = ({G.xy()[0]}, {G.xy()[1]})')
		pr(border, f'm * G = ({C.xy()[0]}, {C.xy()[1]})')

		pr(border, f'Now find the flag :P')

if __name__ == '__main__':
	main()

 

Solution

We can choose and to control and , parameters of ecc curve and the flag is encrypted by . Maybe there is a way to obtain a pair of such that is smooth (by brute forcing or something tricky). I simply implemented the subgroup attack. Observe that every time there are small factors of , we can transform and into the subgroup with order by multiplying where is smooth with its prime factors from . Then solve the subgroup discrete logarithm: and obtain . Continue until you fully recover the flag with .

exp

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
# sage
from pwn import *
from Crypto.Util.number import *
io = remote('65.21.255.31', 10101)
io.sendlineafter(b"Send the `y' element of two points in your desired elliptic curve:  ",b"1,1")
io.recvline()
io.recvline()

sub_results = []
sub_mods = []

q = int(io.recvline().decode().split("=")[-1].strip())

def sub_group_cracker():
    y1 = randint(1,q)
    y2 = randint(1,q)
    io.sendlineafter(b"Send the `y' element of two points in your desired elliptic curve:  ",f"{y1},{y2}".encode())
    io.recvline()
    io.recvline()
    
    q_ = int(io.recvline().decode().split("=")[-1].strip())
    assert q_ == q
    print(f"[+] q = {q}")
    G = [int(i.strip().strip("()")) for i in io.recvline().decode().split("=")[-1].split(",")]
    print(f"[+] G = {G}")
    mG = [int(i.strip().strip("()")) for i in io.recvline().decode().split("=")[-1].split(",")]
    print(f"[+] mG = {mG}")
    E = EllipticCurve(GF(q), [A(y1,y2), B(y1,y2)])
    # order_ls = factor(E.order())
    g_order = E(G).order()
    order_ls = factor(g_order)
    print(f"[+] G order {order_ls}")

    sub_group_order = 1
    for p,e in order_ls:
        if p.nbits() <= 40:
            sub_group_order*= (p^e)
    expon = g_order//sub_group_order
    mm = discrete_log(expon*E(mG),expon*E(G),ord = sub_group_order,operation = "+")
    # compute dlp in subgroup 
    print("[+] subgroup dlp (m mod sub_group_order) = ", mm)
    return mm , sub_group_order

# with good luck, it's quick to get flag
for _ in range(20):
    mm,sub_mod = sub_group_cracker()
    sub_results.append(ZZ(mm))
    sub_mods.append(ZZ(sub_mod))
    m = crt(sub_results,sub_mods)
    flag = long_to_bytes(int(m))
    if b"ASIS" in flag:
        print(flag)
        break

 

Disinvolute, 7 solves, 334 pts

Fascinating! Safe primes are not safe this time! I came up with two solutions for this challenge.

Challenge info:

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
test@tl2cents:~$ nc 65.21.255.31 12431
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Welcome to disinvolute challenge, with respet you should solve a    |
|  very hard nested DLP problem! For this I have used safe primes to   |
|  insure that secuirty is MAX! This is an impossible mission! YES!!!  |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Options:
|       [E]ncrypted flag!
|       [F]acts
|       [Q]uit
f
| e = 65537
| g = 19
| G = 7
| n = 148267061058508140521771844336357309638193892680830195994160435155477469086917454039271500259436678115087207606317117102876682845930891594642648585082452526513788285554286522281479430636699137451087982039394834852230409441379845133453897324929887574781827710609261015600756331507149838295821831013983881738389
| x = 4762228865112713933680901686312365438129543465633308131394213429335503949565244481709257174336654854804801415429822876318871430932962637771832260779974221594549081075526225455803075556244759773424025448602402416296738408795507100015745114555257736736093818152570949549787743320873704496070532836113256737166
| y = 1108860751796709331344647906028326950754821659277541482354358602643335344374460647577034423609942879025016135867349727283942882622507736748361346004160798320992095814111122298279112119647096302425446695751072628908811645869472412699194693577438376762025200214230041011993884089216839121719313852986953023723173686
| m = bytes_to_long(flag)
| pow(g, pow(G, x), n) == pow(g, pow(G, y), n)
| Options:
|       [E]ncrypted flag!
|       [F]acts
|       [Q]uit
e
| pow(m, e, n) = 105605841738961983417577860678752974932535437666329804651842025661498876678103379117144657722045837391523737156819410348181082826864098784246794477942656416786047722500499494659365335093851833727146241282145989311890111537596263118905768162627976192397364757993978612885949454870746076488102879019056734690608

 

Solution 1: Safe primes structure (Intended)

We obtain a nested power equation : . The first power of gives : , and the second power of gives where is Euler function. From above equation, we have:

This situation is corresponding to the RSA cycling attack if is deliberately selected such that in is small. I’ll introduce two general attacks with information of or leaked.

  • cycling attack : If is small, we can simply encrypt the ciphertext times and get plaintext ：.
  • recovering from factorization of : this attack can performs well if the factorization of is given (or can be easily obtained by factor , factorDB) and the number of prime factors is small. The core idea is reversing the Euler function and obtain all the possible prime factors of . The detailed process can be found here: Cycling Writeup of Google CTF 2022, writeups.

The scenario of this challenge is similar to the challengeCycling of Google CTF 2022 quals, but in this challenge, we’re not given the exact value of and we can’t factorize either. Notice that : “I have used safe primes to insure that security is MAX“, we focus on the expression of in the safe prime case.

Applying (2) into expression of n and :

Plugging (3) into (4), we obtain an expression of with ：

By (2), we also have and replace in (5):

Hence, if are strong primes, given the exact value of , we can easily recover by (6) and solve the quadratic equation to factor .

In this challenge , and k is small (about ) by analyzing the data samples, so brute-forcing is enough to recover .

remote data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from pwn import *
from Crypto.Util.number import *
from factordb.factordb import FactorDB
from tqdm import tqdm

context.log_level = 'error'

def obtain_new_data():
    io = remote('65.21.255.31', 12431)
    io.sendlineafter(b"[Q]uit\n",b"f")
    e = int(io.recvline().decode().split("=")[-1].strip())
    g = int(io.recvline().decode().split("=")[-1].strip())
    G = int(io.recvline().decode().split("=")[-1].strip())   
    n = int(io.recvline().decode().split("=")[-1].strip())
    x = int(io.recvline().decode().split("=")[-1].strip())
    y = int(io.recvline().decode().split("=")[-1].strip())
    io.sendlineafter(b"[Q]uit\n",b"e")
    enc = int(io.recvline().decode().split("=")[-1].strip())
    io.close()
    print(y-x)
    return enc,n,x,y,e,g,G

Solver

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
# sage
from Crypto.Util.number import *
from tqdm import tqdm
enc,n,x,y,e,g,G = obtain_new_data()
small_factors = factor(ZZ(y-x),limit = 2^30)
factor_list = [ p for p,_ in small_factors]
kphiphin =ZZ(y-x)

PR.<x> = PolynomialRing(ZZ)
all_possible_phi_n_factors = []

print(kphiphin.nbits())
for k in tqdm(range(2,2**24)):
    if kphiphin % k!=0:
        continue
    f = n - 6*x + 3 - 2*(kphiphin//k)
    root = f.roots()
    if len(root)>0 and ZZ(root[0][0]).nbits() < 600:
        print(root)
        break
p_q = root[0][0]
p0q0 = (n-2*p_q-1)//4
f = x^2 - p_q*x + p0q0
r = f.roots()
p0,q0 = r[0][0],r[1][0]
assert is_prime(p0)
assert is_prime(q0)

p = 2*p0+1
q = 2*q0+1
assert is_prime(p)
assert is_prime(q)

phi = (p-1)*(q-1)
print(long_to_bytes(int(pow(enc,inverse(65537,phi),n))))

 

Solution 2: RSA Broadcast Attack (Unintended)

Every time, we connect to server and obtain a new encrypted data sample . At most, we need 65537 data samples to fully recover by RSA Broadcast Attack: collect enough samples until we can calculate the 65537-th root of in integer ring! The connection times : and the time cost is about 6 hours. I guess that’s why the organizers added another server for this challenge halfway through the game.

 

Mariana, 59 solves, 80 pts

Math trick! We need to input x such that:

By the Euler theorem：

 

Mindseat, 33 solves, 128 pts

Factorize RSA modulo and then compute subgroup discrete logarithm.

Source code

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
#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import params, flag

def keygen(nbit, k): # Pubkey function
	_p = 1
	while True:
		p, q = [_p + (getRandomNBitInteger(nbit - k) << k) for _ in '01']
		if isPrime(p) and isPrime(q):
			while True:
				s = getRandomRange(2, p * q)
				if pow(s, (p - 1) // 2, p) * pow(s, (q - 1) // 2, q) == (p - 1) * (q - 1):
					pubkey = p * q, s
					return pubkey

def encrypt(pubkey, m):
	n, s = pubkey
	r = getRandomRange(2, n)
	return pow(s, m, n) * pow(r, 2 ** k, n) % n

flag = flag.lstrip(b'ASIS{').rstrip(b'}')
nbit, k = params
PUBKEYS = [keygen(nbit, k) for _ in range(4)]
flag = [bytes_to_long(flag[i*8:i*8 + 8]) for i in range(4)]
ENCS = [encrypt(PUBKEYS[_], flag[_]) for _ in range(4)]

print(f'PUBKEYS = {PUBKEYS}')
print(f'ENCS = {ENCS}')

 

Factorize RSA modulo

The primes are generated with backdoor : . In this case, if k is more than half of p.nbits(), we can use the coppersmith method to factorize the RSA modulo . How to extract k? Observe that :

Find the max k of each modulo n and choose the smallest one as the final k parameter. I choose k = 134.

Coppersmith cracker

1
2
3
4
5
6
7
8
def small_roots(n,k=134):
    Zn.<x> = PolynomialRing(Zmod(n))
    unknown_bit = n.nbits()//2 - k
    print(f"[+] unknown bit number : {unknown_bit}")
    f = x*2**k + 1
    root = f.monic().small_roots(X = 2^(unknown_bit+1), beta = 0.4)
    print(root)
    return root

 

Discrete Logarithm

The encryption process is :

Notice the the order of contains the prime power factor : because and the the order of doesn’t contain the prime power factor: , we can transform (2) into the following discrete logarithm problem in subgroup with order :

In the previous section, . Now we can fully recover m by computing the discrete logarithm in (3).

exp

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
ns = PUBKEYS
for pub in PUBKEYS:
    ns.append(pub[0])
    ss.append(pub[1])
def small_roots(n,k):
    Zn.<x> = PolynomialRing(Zmod(n))
    unknown_bit = n.nbits()//2 - k
    print(f"[+] unknown bit number : {unknown_bit}")
    f = x*2**k + 1
    root = f.monic().small_roots(X = 2^(unknown_bit+1), beta = 0.4)
    print(root)
    return root

ps,qs = [],[]
k = 134
for n,s in zip(ns,ss):
    ph,qh = small_roots(n,k)
    p = ZZ(ph*2**k+1)
    q = ZZ(qh*2**k+1)
    assert p*q == n
    ps.append(p)
    qs.append(q)
    
for p,q,s,enc in zip(ps,qs,ss,ENCS):
    Gp = GF(p)
    fs = factor(p-1)
    pd = (p-1)//2**134
    flag = int(discrete_log(Gp(enc)^pd,Gp(s)^pd))
    print(long_to_bytes(flag).decode(),end="")
# N3w_CTF_nEW_Joye_Libert_CrYpt0_5

 

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true


Hi, this is tl2cents
Currently Ph.D at IIE of UCAS
Graduated from USTC (2018-2022)

CTFer
Focus on blockchain, crypto and reversing
Team member of NeSE and Nebula

Research
Blockchain | ETH | FHE
PQC | Cryptography | Android

Contact Me
echo Y2F4dWxhc2FlbGFAb3V0bG9vay5jb20K | base64 -d

Thanks for JoeyBling and Litten