apbq II
Challenge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
hints = []
for _ in range(3):
a, b = randint(0, 2**312), randint(0, 2**312)
hints.append(a * p + b * q)
FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')
Phân tích: Challenge cho 3 số là tổ hợp tuyến tính của p và q và tích của chúng, yêu cầu tìm lại p và q để khôi phục mã RSA
Vì có 3 biến nên mình gọi 3 phương trình lần lượt là:
1
2
3
a1q + b1p == h1 (1)
a2q + b2p == h2 (2)
a3q + b3p == h3 (3)
Khử q từ phương trình 1 và phương trình 2 ta được $a_2h_1 - a_1h_2 = (b_1a_2-b_2a_1)~p$ hay là $a_2h_1-a_1h_2 = 0 ~ mod ~ p$
Tương tự $b_2h_1-b_1h_2 = 0 ~ mod ~ q$
Nhân lại với nhau ta được $a_1b_1 h_2^2 - (a_2b_1 +a_1b_2) h_1h_2 + a_2b_2 h_1^2 = 0 ~ mod ~ N (*)$
Cứ nhân như thế ta sẽ được 9 phương trình. Tuy nhiên sau khi end giải, mình có nhìn lại và thực tế chỉ cần 2 hints là đủ để giải
Xây dựng ma trận từ Lattice:
Xét phương trình *, ta có thể coi nó là phương trình 3 ẩn $xh_2^2 - yh_1h_2 + zh_1^2 = 0$
Đây là phương trình tuyến tính, ta có thể giải nó bằng LLL với ma trận
\[\begin{pmatrix} \frac{1}{2^{614}} & & & h_{2}^2 \\ & \frac{1}{2^{615}} & & -h_{1}h_{2} \\ & & \frac{1}{2^{614}} & h_{1}^2 \\ & & & N \\ \end{pmatrix}\]Ma trận này sẽ chứa Vector nhỏ chứa nghiệm phương trình là $(\frac{a_1a_2}{2^{614}}…., 0)$ (mình lười viết)
Ta lại có đẳng thức sau $a_1b_1 a_2^2 + a_2b_2 a_1^2 = (a_2b_1 + a_1b_2)a_1a_2$
Phương trình đẳng cấp bậc 2 mình có thể tìm tỷ số của $a_1/a_2 = t_1/t_2$, lại có $t_1h_2 - t_2h_1$ chia hết cho $p$, do đó ta tính được gcd tìm được p
Solution
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
from Crypto.Util.number import long_to_bytes
n = 19604411241131769363446674414275822275458180476470552084588074159518829172495704100505151090666577360738167275118902368371310303168115405693118232835691333564186301532462296609038929723894816307213749698854885742811071911120730847279568876996811433319487396434622751326281226335521193361938724747445445693062336009352580319440819629260614301234971135026395941954109172567154559773437059174108362692061503832044135079892892132874437669744266153424229215832487832220575345912010076934611701182205068942016022731469408259665250938484104489962832891496953003599692437819685070043991828977623632396604764153766442526750861
c = 16285668872352205553535195410427806596787838055817589230402081772267074935944610262823936480340920868690431897597533868262062616060037808676539290467732178272289192993251540763800683055555842878669862850848141950704501553807462214356142018528608581546359772903806691435935873069006470208826518183488708349814610769150918356795466688732617809664831695402633481224388822180989614886783145141129157248734213457746877012517003702540070132542733288350979858743766340483503277308585752213220454288897741262154622769402029906981612699288206404870733274360554941455758083078106150045394190625280336371690998959720015636304971
hints = [773921762798470573303163880380136299117907456177270598418425239064611119645412840945432294881005107606154919094297188183879147500755682510817840590276985061404198538395146658442221987303866921786284298394947485319583779671756246394491275898343836522004269864718405399287554020900395899143149709408762450693357109188640512875099087677956684946219071353228860650842182953922400081939934842271539450654323, 1506346165967409413422972644306025635334450240732478358292064973873339506571546529986180145578525288707094235933775031106971678278204568310035260899591267480098015553318079460357474533531922997212816264042117005473870580122983241038123126855791876827449194400045937398578284016176289760858365282167537689282643483235235028505475719615108102516557986483184881658418430287064598580231630440534438966422546, 531028473288853560172466570664059891687387973059926255729701774553291285115938502989142318123512885100092638435578692032744904444237266108167428726130739434630511943317357743527053899234918340191006102436386051432760331852295930159729030763033361158582919982579082557775409422474301977588011705535991555292564664521116375190464371518812625647175447427886432255779925378071998411170643507118426289778768]
h1, h2, h3 = hints
m = Matrix.identity(QQ, 4)
m[0,0] = 1 / 2^614
m[1,1] = 1 / 2^615
m[2,2] = 1 / 2^614
m[0,3] = h2^2
m[1,3] = -h1*h2
m[2,3] = h1^2
m[3,3] = n
m = m.LLL()
a1b1 = m[0][0] * 2**614
a2b1_a1b2 = m[0][1] * 2**615
a2b2 = m[0][2] * 2**614
R.<t> = PolynomialRing(QQ)
f = a1b1*t^2 - a2b1_a1b2 * t + a2b2
t1, t2 = f.roots()[0][0].as_integer_ratio()
p = gcd(h1*t1-h2*t2,n)
q = n // p
d = pow(65537, -1, int(p-1) * int(q-1))
m = pow(c,int(d), n)
print(long_to_bytes(int(m)))
Mini DNS Server
Challenge
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
import time
from dnslib.server import DNSServer, BaseResolver
from dnslib import RR, TXT, QTYPE, RCODE
class Resolver(BaseResolver):
def resolve(self, request, handler):
reply = request.reply()
reply.header.rcode = RCODE.reverse['REFUSED']
if len(handler.request[0]) > 72:
return reply
if request.get_q().qtype != QTYPE.TXT:
return reply
qname = request.get_q().get_qname()
if qname == 'free.flag.for.flag.loving.flag.capturers.downunderctf.com':
FLAG = open('flag.txt', 'r').read().strip()
txt_resp = FLAG
else:
txt_resp = 'NOPE'
reply.header.rcode = RCODE.reverse['NOERROR']
reply.add_answer(RR(qname, QTYPE.TXT, rdata=TXT(txt_resp)))
return reply
server = DNSServer(Resolver(), port=8053)
server.start_thread()
while server.isAlive():
time.sleep(1)
Chall yêu cầu mình gửi DNS tới server với yêu cầu domain là free.flag.for.flag.loving.flag.capturers.downunderctf.com, request có độ dài không quá 72, question type == TXT
Trước đó mình cũng đang tìm hiểu dở về DNS nên gặp chall này mình cũng có hứng thú, tiếc là không đủ thời gian để làm :((
Cấu trúc của một query DNS
1
2
3
4
5
6
7
8
import dns.query
import dns.message
import dns.rdatatype
domain = 'free.flag.for.flag.loving.flag.capturers.downunderctf.com'
qname = dns.name.from_text(domain)
dns.message.make_query(qname, dns.rdatatype.TXT).to_wire()
# b'\x13\xec\x01\x00\x00\x01\x00\x00\x00\x00\x00\x00\x04free\x04flag\x03for\x04flag\x06loving\x04flag\tcapturers\x0cdownunderctf\x03com\x00\x00\x10\x00\x01'
Như ta thấy 2 bytes đầu là ID, 2 bytes tiếp theo là flags, 2 bytes số lượng câu hỏi (là 1), 6 bytes answer, authority, additional thì không dùng đến, vậy là 12 bytes header
Mỗi subdomain sẽ có dạng \x??abcde với \x?? là độ dài của subdomain đó
Ví dụ: blog.anhtv.live sẽ ghi là \x04blog\x05anhtv\x04live
\x00 đánh dấu kết thúc tên miền
2 bytes gần cuối ghi QUERYTYPE (\x00\x10 là TXT)
2 bytes cuối ghi QUERYCLASS(\x00\x01 là IN - Internet?)
Như vậy thì là độ dài của nó đã là 75 rồi, vậy thì muốn giảm xuống 72 thì phải làm thế nào?
DNS Pointer and Solution
Để giải quyết tin nhắn dài, người ta sử dụng DNS Pointer để lặp lại tin nhắn
= \xc0 + offset sẽ đưa con trỏ dns tới query đó
Nhận thấy Server không check flag, 2 bytes đầu là ngẫu nhiên, vậy ta có thể dùng được 4 bytes, ta sẽ đưa .com lên đầu
1
2
3
4
5
6
7
8
b = b"\x03com"
# Tận dụng được bytes 00 kết thúc domain
b += \x00\x01\x00\x00\x00\x00\x00\x00
# Domain
b += \x04free\x04flag\x03for\x04flag\x06loving\x04flag\tcapturers\x0cdownunderctf
# Trỏ về vị trí ban đầu
b += \xc0\x00
b += \x00\x10\x00\x01
Vậy ta đầy đủ payload, gửi tới server nào
1
2
3
4
5
6
7
8
9
10
11
import socket
host = "0.0.0.0" # Replace by DNS Server
port = 8053
sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
sock.sendto(b, (host, port))
t = sock.recv(4096)
print(t)
sock.close()