Brute (Solved After Event)

No need fancy crypto trick just brute, and btw you have to spin up to 20 vms with multi-thread to make it fast enough

Kita diberikan beberapa file, yakni chall.py dan out.txt. Pada chall.py, terdapat kode sumber dari soal.

chall.py

from Crypto.Util.number import getStrongPrime
m = int.from_bytes("IFEST13{???}".encode())
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
print(f'{pow(m, 0x10001, n)}\n{n}\n{p >> 40}')

Intinya, ini adalah RSA biasa yang nilai p nya di-leak kecuali untuk 40-bit terakhirnya. Kita perlu me-recover 40-bit terakhir ini. Ini adalah textbook case dari Coppersmith Attack. Saya sebenarnya baru mempelajari ini dari write-up milik tim Peserta, maka dari itu saya ucapkan terima kasih sebanyak-banyaknya atas ilmunya :).

Langsung saja ke kode solvernya. Challenge ini membutuhkan fungsi small_roots yang ada di SageMath. Oleh karena itu, kita bisa gunakan website SageCell untuk menjalankan kode Sage, atau menggunakan library Sage di dalam Python seperti yang saya praktekkan di bawah ini. Penjelasan pada kode saya terakan pada komentar-komentar yang ada.

solve.py

from sage.all import *
from Crypto.Util.number import *

# Remember when you have to use Python's int, Sage's Integer, and Sage PolynomialRing's IntegerMod as datatype

c = 10190308328132298810370792830407498649727116694895887482897571470790876671909417379902577324803848850655954471082089060952194185721425541632970106409477409460179454591137511596832421737353754768175974443794887211632429320728354925107321000890255988379005072889707213292319847199584075893238735146835736979402380614028245390503793552296747076984394930725251632591625471426901314091323869057780461687871597918704838734422002502048443745431116004254026457663052173884656414629831184831431248595040967979335625485086150017379359647307566607127100190320972594606082853976569219798608787775461446205014804326191379628416459
n = 22052867210059985056723988324723437469643935229284382742545572507193384098102119262228001598529023654073757846310755124262636633869347982051002191511240379141051585596043583392443536537486511985566413114358501620593150325155980714427378089922768898334419054390129931556129883835862579370606862267536439488040273973837168042166190169509259514869605813849934412879327376082076832835805173922914432614662509276644729233158638994237998916272949330215708015931366306430206836771702005645140291164351968902134211930508335582704492675362575695821618037439189132191250206861088835015459823510074661891457866577589023776648751
p_hi = 138398228938242977290956349154712526327465608129677172002562239407676097284597892604642541735116262199110899389173013415023231356739796256927576905061498760222434453315905920861684849512303589509164929424151033355318032546176479325956586655296074717479220347079941178337950508153135271887365359007
e = 65537
k_unknown_bits = 40
p_bit_length = 1024

# Get approximate value of p (with zero's on the last 40 bits)
p_approx = p_hi << k_unknown_bits
print(f"[*] 40 LSB bits of p_approx: {bin(p_approx)[2:][-40:]}")

# Define Ring mod n
R = PolynomialRing(Zmod(n), 'x_var')
x_var = R.gen()
poly = p_approx + x_var

# Upper bound for x_var is p_lo length (40 bits)
X_bound = 2**k_unknown_bits
beta = 0.5

# Find small roots
potential_p_lo_val = poly.small_roots(X=X_bound, beta=beta)
print(f"[*] Found {len(potential_p_lo_val)} small_roots values")
print(f"[*] small_roots = {potential_p_lo_val}")

# Go through all potential small roots
if not potential_p_lo_val:
	print("[-] No small_roots found. Exiting...")
else:
	for pos_p_lo in potential_p_lo_val:
		pos_p_lo = Integer(pos_p_lo)	# Change datatype from IntegerMod to Integer

		print(f"[*] Trying p_lo = {pos_p_lo}")
		
		# [1] Check if the candidate is within the boundary
		if not (0 <= pos_p_lo and pos_p_lo < X_bound):
			print("[-] Value of p_lo is out of bound")
			continue

		# [2] Check if the candidate calculates to the correct p
		pos_p = p_approx + pos_p_lo
		if (pos_p == 0) or (n % pos_p != 0):
			print("[-] Value of p_lo is incorrect")
			continue

		# [3] Decrypt the FLAG
		try:
			pos_q = n // pos_p
			print(f"[+] Found p = {pos_p}")
			print(f"[+] Found q = {pos_q}")
			phi = (pos_p-1)*(pos_q-1)
			d = pow(e,-1,phi)
			m = pow(c, d, n)
			print(f"[+] Found FLAG = {long_to_bytes(m)}")
		except Exception as e:
			print(e)

$ sage solve.py 
[*] 40 LSB bits of p_approx: 0000000000000000000000000000000000000000
[*] Found 1 small_roots values
[*] small_roots = [307143335585]
[*] Trying p_lo = 307143335585
[+] Found p = 152170461981203044138580018222860171483648966011319086281925541493885759794755162431349753477795696871153242407332984090443277761904418330933031999427592715238374825598836399798707345437190519440709648421600461011378200951012246668647337881673386523838896883273245813392691473455180122270797417610128336314017
[+] Found q = 144922128269440884691193969052877601732271046027622462528828552456155401850440263363345392437840052541235167051587359051054314257198207968414263143150653184708601934583747143373284586518556647550413291191561975196911578481725624854131586335162113599967650646081359560140388118421436124444909155273819195665103
[+] Found FLAG = b'happy_brute__as_long_as_possible_lol_it_wont_be_the_flag_isnt_it?'

Flag: IFEST13{happy_brute__as_long_as_possible_lol_it_wont_be_the_flag_isnt_it?}