<h1 style="text-align:center; color:#cb42f5">
PicoCTF Walkthrough: Part 1
</h1>
Đây là lời giải cho một số thử thách của **picoCTF** mà mình cảm thấy thú vị và hữu ích. Hầu hết trong số chúng sẽ liên quan đến việc viết chương trình.
## Pixelated
Thử thách này giống một thử thách của forensics hơn là thử thách cryptography
Về cơ bản, chúng ta cần phải kết hợp hai hình ảnh được cho để khôi phục lại hình ảnh gốc.
Dưới đây sẽ là script lời giải được tạo ra dưới sự trợ giúp của LLM (**chatGPT**)
:::spoiler <b style="color:tomato">combine_images.py</b>
```python=1
from PIL import Image
def combine_images(image1_path, image2_path, output_path):
# Open the images
image1 = Image.open(image1_path)
image2 = Image.open(image2_path)
# Ensure both images have the same size
if image1.size != image2.size:
raise ValueError("Images must have the same size")
# Combine the images using a simple averaging technique
combined_image = Image.blend(image1, image2, alpha=0.5)
# Save the combined image
combined_image.save(output_path)
if __name__ == "__main__":
image1_path = "scrambled1.png"
image2_path = "scrambled2.png"
output_path = "combined_image.png"
combine_images(image1_path, image2_path, output_path)
```
:::
Và chúng ta đã có được một hình ảnh xám.
Tất cả những gì chúng ta cần làm bây giờ là tải bức ảnh lên <a href="https://29a.ch/photo-forensics/#forensic-magnifier">website này</a> và thử các lựa chọn cho đến khi ta nhìn rõ được flag trong bức ảnh thôi.
:::success
**Flag:** <b style="color:#3262a8">picoCTF{d562333d}</b>
:::
## Easy Peasy
:::spoiler <b>otp.py</b>
```python=
#!/usr/bin/python3 -u
import os.path
KEY_FILE = "key"
KEY_LEN = 50000
FLAG_FILE = "flag"
def startup(key_location):
flag = open(FLAG_FILE).read()
kf = open(KEY_FILE, "rb").read()
start = key_location
stop = key_location + len(flag)
key = kf[start:stop]
key_location = stop
result = list(map(lambda p, k: "{:02x}".format(ord(p) ^ k), flag, key))
print("This is the encrypted flag!\n{}\n".format("".join(result)))
return key_location
def encrypt(key_location):
ui = input("What data would you like to encrypt? ").rstrip()
if len(ui) == 0 or len(ui) > KEY_LEN:
return -1
start = key_location
stop = key_location + len(ui)
kf = open(KEY_FILE, "rb").read()
if stop >= KEY_LEN:
stop = stop % KEY_LEN
key = kf[start:] + kf[:stop]
else:
key = kf[start:stop]
key_location = stop
result = list(map(lambda p, k: "{:02x}".format(ord(p) ^ k), ui, key))
print("Here ya go!\n{}\n".format("".join(result)))
return key_location
print("******************Welcome to our OTP implementation!******************")
c = startup(0)
while c >= 0:
c = encrypt(c)
```
:::
Đây là một thử thách được viết vào sau thời kỳ hồng hoang một chút nên nhìn cách viết đề nó hơi lạ.
Bạn sẽ được gửi dữ liệu có độ dài không được vượt quá độ dài khóa trong mỗi lần gửi, và chú ý đoạn mã này của hàm **encrypt** như sau:
```python=
if stop >= KEY_LEN:
stop = stop % KEY_LEN
key = kf[start:] + kf[:stop]
else:
key = kf[start:stop]
key_location = stop
```
Có nghĩa là nếu tổng độ dài trong các lần gửi mà vượt quá độ dài khóa thì ta sẽ quay lại đầu khóa và tiếp tục mã hóa. Như vậy thì ta có thể tận dụng điều này để khôi phục lại đoạn khóa dùng để mã hóa flag.
Dưới đây là script cho bài này:
:::spoiler <b style="color:tomato">solution.py</b>
```python=
from pwn import *
from Crypto.Util.strxor import strxor
KEY_LEN = 50000
HOST = "mercury.picoctf.net"; PORT = 58913
connection = remote(HOST, PORT)
connection.recvuntil(b'This is the encrypted flag!\n')
encrypted_flag = connection.recvline().strip().decode()
encrypted_flag = bytes.fromhex(encrypted_flag)
length = len(encrypted_flag)
connection.recvuntil(b"What data would you like to encrypt? ")
data_send = b"0"*(KEY_LEN - length)
connection.sendline(data_send)
connection.recvuntil(b"What data would you like to encrypt? ")
data_send = b"0"*length
connection.sendline(data_send)
connection.recvuntil(b'Here ya go!\n')
encrypted_data = connection.recvline().strip().decode()
encrypted_data = bytes.fromhex(encrypted_data)
connection.close()
data_send = data_send[-length:]
key = strxor(encrypted_data, data_send)
inside_flag = strxor(encrypted_flag, key).decode()
flag = "picoCTF{" + inside_flag + '}'
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{35ecb423b3b43472c35cc2f41011c6d2}
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{35ecb423b3b43472c35cc2f41011c6d2}</b>
:::
>[!Note] Nói thêm về bài này
>Ban đầu mình gửi thẳng 50000 ký tự rồi lấy 64 ký tự cuối để khôi phục flag, nhưng không hiểu vì một lý do nào đó mà lại ra sai đáp án nên mình mới thả dislike bài này. :-1:
## No Padding, No Problem
Bài này nhìn qua là ta có thể thấy đây là tấn công liên quan đến **Oracle** của RSA. Chúng ta sẽ được cho khóa công khai $(n, e, c)$ và server sẽ tiến hành giải mã theo yêu cầu của chúng ta. Tuy nhiên nếu chúng ta nhập vào $\text{ciphertext}$ mà đề cho để giải mã thì server sẽ từ chối giải mã cho mình. Vì vậy chúng ta phải tìm cách để đánh lừa server, ta có cách như sau:
- Chọn một số nguyên ngẫu nhiên $a \in (0 ,n)$ sao cho $a\cdot m < n$.
- Tính $\text{new_cipher} = a^{e} \cdot c ~~ mod ~ n$.
- Gửi $\text{new_cipher}$ cho server để giải mã, ta thu về được $\text{plaintext}$.
- Ta tìm được $\text{flag} = \frac{\text{plaintext}}{a}$.
Việc chứng minh điều này sẽ được coi như là một bài tập dành cho những người đọc bài viết này. :penguin:
Dưới đây sẽ là script lời giải:
:::spoiler <b style="color:tomato">solution.py</b>
```python=
from pwn import *
from Crypto.Util.number import long_to_bytes
HOST = "mercury.picoctf.net"; PORT = 33780
connection = remote(HOST, PORT)
connection.recvuntil(b"n: ")
n = int(connection.recvline().strip().decode())
connection.recvuntil(b"e: ")
e = int(connection.recvline().strip().decode())
connection.recvuntil(b"ciphertext: ")
ciphertext = int(connection.recvline().strip().decode())
new_cipher = (pow(2, e, n)*ciphertext) % n
connection.recvuntil(b"Give me ciphertext to decrypt: ")
connection.sendline(f"{new_cipher}".encode())
connection.recvuntil(b"Here you go: ")
plaintext = int(connection.recvline().strip().decode())
int_flag = plaintext//2
flag = long_to_bytes(int_flag).decode()
connection.success(f"Got flag: {flag}")
# [+] Got flag: picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_0801973}
connection.close()
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_0801973}</b>
:::
## New Caesar
:::spoiler <b>new_caesar.py</b>
```python=
import string
LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]
def b16_encode(plain):
enc = ""
for c in plain:
binary = "{0:08b}".format(ord(c))
enc += ALPHABET[int(binary[:4], 2)]
enc += ALPHABET[int(binary[4:], 2)]
return enc
def shift(c, k):
t1 = ord(c) - LOWERCASE_OFFSET
t2 = ord(k) - LOWERCASE_OFFSET
return ALPHABET[(t1 + t2) % len(ALPHABET)]
flag = "redacted"
key = "redacted"
assert all([k in ALPHABET for k in key])
assert len(key) == 1
b16 = b16_encode(flag)
enc = ""
for i, c in enumerate(b16):
enc += shift(c, key[i % len(key)])
print(enc)
```
:::
Ta để ý hai dòng này:
```python=
assert all([k in ALPHABET for k in key])
assert len(key) == 1
```
Điều này chứng tỏ khóa chỉ có 16 giá trị có thể có, và trên hết hàm mã hóa đề bài có thể đảo ngược nên ta chỉ cần viết hàm giải mã và thử hết không gian khóa là ra.
:::spoiler <b style="color:tomato">solution.py</b>
```python=
import string
LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]
def decrypt_message(encryted, key):
b16_flag = ""
t2 = ord(key) - LOWERCASE_OFFSET
for char in encryted:
index = ALPHABET.index(char)
t1_1 = index - t2
t1_2 = index + 16 - t2
if(t1_1 < 0): t1 = t1_2
else: t1 = t1_1
b16_flag += chr(t1 + LOWERCASE_OFFSET)
flag = ""
for i in range(0, len(b16_flag), 2):
left_half = ALPHABET.index(b16_flag[i])
right_half = ALPHABET.index(b16_flag[i+1])
binary = format(left_half, "04b") + format(right_half, "04b")
flag += chr(int(binary, 2))
return flag
encrypted_flag = "lkmjkemjmkiekeijiiigljlhilihliikiliginliljimiklligljiflhiniiiniiihlhilimlhijil"
for key in ALPHABET:
print(decrypt_message(encrypted_flag, key))
# ºÉ¤Éʤ¹·¸¸¹»¹···
# ©¸¸¹sxwu¨¦zv§yzu|§¨{yªu¨t¦|w|wv¦z{¦xz
# §§¨bgfdiehidkjhdckfkfeijgi
# qQqVUSXTWXSZYWSRZUZUTXYVX
# v`@`EDBusGCtFGBItuHFwBuAsIDIDCsGHsEG
# et_tu?_431db62c5618cd75f1d0b83832b67b46
# TcNcd.N#" SQ%!R$% 'RS&$U S/Q'"'"!Q%&Q#%
# CR=RS=B@AABDB@@@
# 2A,AB
# ???00131
# !01ûÿý .òþ/ñòýô/ óñ"ý ü.ôÿôÿþ.òó.ðò
# /
# / ê
# ïîìáíàáìãâàìëãîãîíáâïá
# ùÙùÞÝÛ
# ÑßÛÚ
# ÒÝÒÝÜ
# ÐÑ
# ÞÐ
# ÈèÍÌÊýûÏËüÎÏÊÁüýÀÎÿÊýÉûÁÌÁÌËûÏÀûÍÏ
# íü×üý·×¼»¹ì꾺뽾¹°ë쿽î¹ì¸ê°»°»ºê¾¿ê¼¾
# ÜëÆëì¦Æ«ª¨ÛÙ©Ú¬¨¯ÚÛ®¬Ý¨Û§Ù¯ª¯ª©Ù®Ù«
# ËÚµÚÛµÊÈÉÉÊÌÊÈÈÈ
```
:::
Vậy là ta đã có 16 flag tiềm năng, 1 trong số chúng chắc chắn là flag (cụ thể là `et_tu?_431db62c5618cd75f1d0b83832b67b46` vì nhìn nó khả nghi vãi).
:::success
**Flag:** <b style="color:#3262a8">picoCTF{et_tu?_431db62c5618cd75f1d0b83832b67b46}</b>
:::
>[!Tip]
>Hàm format trong python có vẻ tiện lợi khi chuyển về nhị phân so với hàm bin vì mình có thể tùy chọn độ dài của số ở dạng nhị phân.
## spelling-quiz
:::spoiler <b>encrypt.py</b>
```python3=
import random
import os
files = [
os.path.join(path, file)
for path, dirs, files in os.walk('.')
for file in files
if file.split('.')[-1] == 'txt'
]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
random.shuffle(shuffled := alphabet[:])
dictionary = dict(zip(alphabet, shuffled))
for filename in files:
text = open(filename, 'r').read()
encrypted = ''.join([
dictionary[c]
if c in dictionary else c
for c in text
])
open(filename, 'w').write(encrypted)
```
:::
:::spoiler <b>flag.txt</b>
```tex!
brcfxba_vfr_mid_hosbrm_iprc_exa_hoav_vwcrm
```
:::
:::spoiler <b>study-guide.txt</b>
```tex!
gocnfwnwtr
sxlyrxaic
dcrrtfrxcv
uxbvwavcq
lwvicwtiwm
pwtmwnxvicq
avingciisa
ylwtmrcawx
mwaxdcrrxuwlwvq
yciflwnf
mwaxsrtwvq
iovabxcabqwtd
bcrwtnlwtxvwit
srlxtwkwtd
bcriurmwrtv
nflicxlyicsxswmr
titrlrnvcilqvwn
xanrcvxwtxulr
vficxniblxavwra
bwttxnlrv
bxbrcerwdfva
wtnxctxvwit
titborcwlwvq
otbcrywtrm
ucxaalwgr
vcxtabiawvwpr
dlqnrcil
wmilxvcwkrc
fqbrcixcvwx
brcwsrmollxcq
crtmwvwit
sitavcwnwmr
rzvcxabrnvcxl
sitosrtvxllq
nfilrfrsxvwt
iprccrxlwas
mwttrclraa
nxcbrllos
uxccolrr
rzvciprcvrmtraa
trnraaxc
rpwtnwtd
brcabrnvwpwas
blxasilqkxuwlwvq
... (dài quá nên mình không tiện viết ở đây)
```
:::
Nhìn phức tạp vậy thôi chứ bài này chỉ cần lên một website có tên <a href="https://quipqiup.com/">quipqiup</a> để giải mã là ra. Ta sẽ nhập đoạn mã trong file `flag.txt` ở trên cùng và nhập các từ trong file `study-guide.txt` ở bên dưới (nhớ chỉ cần nhập vài chục từ là đủ rồi, nhập quá nhiều sẽ khiến cho website bị đơ).
Sau khi nhập và chạy thì ta sẽ thu được các kết quả bên dưới:
:::success
**Flag:** <b style="color:#3262a8">picoCTF{perhaps_the_dog_jumped_over_was_just_tired}</b>
:::
## Custom encryption
:::spoiler <b>custom_encryption.py</b>
```python=
from random import randint
import sys
def generator(g, x, p):
return pow(g, x) % p
def encrypt(plaintext, key):
cipher = []
for char in plaintext:
cipher.append(((ord(char) * key*311)))
return cipher
def is_prime(p):
v = 0
for i in range(2, p + 1):
if p % i == 0:
v = v + 1
if v > 1:
return False
else:
return True
def dynamic_xor_encrypt(plaintext, text_key):
cipher_text = ""
key_length = len(text_key)
for i, char in enumerate(plaintext[::-1]):
key_char = text_key[i % key_length]
encrypted_char = chr(ord(char) ^ ord(key_char))
cipher_text += encrypted_char
return cipher_text
def test(plain_text, text_key):
p = 97
g = 31
if not is_prime(p) and not is_prime(g):
print("Enter prime numbers")
return
a = randint(p-10, p)
b = randint(g-10, g)
print(f"a = {a}")
print(f"b = {b}")
u = generator(g, a, p)
v = generator(g, b, p)
key = generator(v, a, p)
b_key = generator(u, b, p)
shared_key = None
if key == b_key:
shared_key = key
else:
print("Invalid key")
return
semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
cipher = encrypt(semi_cipher, shared_key)
print(f'cipher is: {cipher}')
if __name__ == "__main__":
message = sys.argv[1]
test(message, "trudeau")
```
:::
:::spoiler <b>enc_flag</b>
```tex!
a = 88
b = 26
cipher is: [97965, 185045, 740180, 946995, 1012305, 21770, 827260, 751065, 718410, 457170, 0, 903455, 228585, 54425, 740180, 0, 239470, 936110, 10885, 674870, 261240, 293895, 65310, 65310, 185045, 65310, 283010, 555135, 348320, 533365, 283010, 76195, 130620, 185045]
```
:::
Bài này nhìn trông phức tạp vậy chứ thực chất cũng chỉ là thử kỹ năng dịch ngược của chúng ta mà thôi. Chúng ta sẽ thấy hàm này sử dụng các phép toán XOR và phép nhân trên miền nguyên $\mathbb{Z}$, vốn có thể dịch ngược được.
Dưới đây sẽ là script lời giải:
:::spoiler <b style="color:tomato">solution.py</b>
```python=
text_key = "trudeau"
def dynamic_xor_encrypt(ciphertext, text_key):
plaintext = ""
key_length = len(text_key)
for i, char in enumerate(ciphertext):
key_char = text_key[i % key_length]
encrypted_char = chr(ord(char) ^ ord(key_char))
plaintext += encrypted_char
return plaintext
def decrypt_message(ciphertext, text_key):
a = 88; b = 26; p = 97; g = 31
shared_key = pow(g, a*b, p)
semi_plaintext = ""
for number in ciphertext:
semi_plaintext += chr(number//(shared_key*311))
plaintext = dynamic_xor_encrypt(semi_plaintext, text_key)
return plaintext[::-1]
text_key = "trudeau"
ciphertext = [97965, 185045, 740180, 946995, 1012305, 21770, 827260, 751065, 718410, 457170, 0, 903455, 228585, 54425, 740180, 0, 239470, 936110, 10885, 674870, 261240, 293895, 65310, 65310, 185045, 65310, 283010, 555135, 348320, 533365, 283010, 76195, 130620, 185045]
flag = decrypt_message(ciphertext, text_key)
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{custom_d2cr0pt6d_019c831c}
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{custom_d2cr0pt6d_019c831c}</b>
:::
## miniRSA
:::spoiler <b>ciphertext</b>
```tex!
N: 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e: 3
ciphertext (c): 2205316413931134031074603746928247799030155221252519872650080519263755075355825243327515211479747536697517688468095325517209911688684309894900992899707504087647575997847717180766377832435022794675332132906451858990782325436498952049751141
```
:::
Ban đầu nhìn thấy $e$ nhỏ làm mình tưởng bài này ngon lành dễ ăn lắm chứ (dễ ăn thật nếu mình cẩn thận suy nghĩ một chút). Mình có sử dụng thư viện **gmpy2** của python và làm như sau:
```python=
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
N = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e = 3
c = 2205316413931134031074603746928247799030155221252519872650080519263755075355825243327515211479747536697517688468095325517209911688684309894900992899707504087647575997847717180766377832435022794675332132906451858990782325436498952049751141
k = 1
while(True):
expression = c + k*N
m, exact = iroot(expression, e)
if exact:
flag = long_to_bytes(m).decode()
break
print("[!] Got flag:", flag)
```
Mình nhận ra điều bất thường khi $k$ chạy đến giá trị vài triệu, sau khi kiểm tra và suy nghĩ thì mình nhận ra chân lý như sau: Giá trị của $n$ rất lớn tận 2048 bit, điều này dẫn tới khả năng $m^{e} < n$, tức là $k = 0$. Vì vậy mình đã có sự chỉnh sửa nhỏ và đã ra kết quả.
Dưới đây là các script lời giải của mình, ở trên là lời giải mình nghĩ ra còn ở dưới là lời giải mà mình thấy khá hay nên sưu tầm lại.
:::spoiler <b style="color:tomato">solution1.py</b>
```python=
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
N = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e = 3
c = 2205316413931134031074603746928247799030155221252519872650080519263755075355825243327515211479747536697517688468095325517209911688684309894900992899707504087647575997847717180766377832435022794675332132906451858990782325436498952049751141
k = 0
while(True):
expression = c + k*N
m, exact = iroot(expression, e)
if exact:
flag = long_to_bytes(m).decode()
break
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{n33d_a_lArg3r_e_d0cd6eae}
```
:::
:::spoiler <b style="color:tomato">solution2.py</b>
```python=
from Crypto.Util.number import long_to_bytes
def binary_search_message(e, c):
left = 1; right = c
while(right - left > 1):
middle = (right + left)//2
if(middle**e > c): right = middle
else: left = middle
return left if (left**e == c) else right
N = 29331922499794985782735976045591164936683059380558950386560160105740343201513369939006307531165922708949619162698623675349030430859547825708994708321803705309459438099340427770580064400911431856656901982789948285309956111848686906152664473350940486507451771223435835260168971210087470894448460745593956840586530527915802541450092946574694809584880896601317519794442862977471129319781313161842056501715040555964011899589002863730868679527184420789010551475067862907739054966183120621407246398518098981106431219207697870293412176440482900183550467375190239898455201170831410460483829448603477361305838743852756938687673
e = 3
c = 2205316413931134031074603746928247799030155221252519872650080519263755075355825243327515211479747536697517688468095325517209911688684309894900992899707504087647575997847717180766377832435022794675332132906451858990782325436498952049751141
flag = long_to_bytes(binary_search_message(e, c))
print("[!] Got flag:", flag.decode())
# [!] Got flag: picoCTF{n33d_a_lArg3r_e_d0cd6eae}
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{n33d_a_lArg3r_e_d0cd6eae}</b>
:::
## b00tl3gRSA3
Bài này khi kết nối với server thì sẽ được trả về 3 số $n, e, c$, ngoài ra thì không trả về gì thêm. Để ý gợi ý họ có nói rằng có nhiều hơn số thừa số nguyên tố ngoài $p$ và $q$, vì vậy mình sẽ dùng thuật toán phân tích thừa số nguyên tố bằng đường cong Elliptic của Lenstra (<a href="https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization">elliptic-curve factorization method</a>). May mắn là **Sagemath** đã có sẵn thuật toán này nên mình chỉ việc gọi thôi.
Dưới đây là script lời giải:
:::spoiler <b style="color:tomato">solution.py</b>
```python=
from pwn import *
from sage.all import Integer, prod
from Crypto.Util.number import long_to_bytes
connection = remote("jupiter.challenges.picoctf.org", 51575)
c = int(connection.recvline().strip().decode()[2:])
n = int(connection.recvline().strip().decode()[2:])
e = int(connection.recvline().strip().decode()[2:])
factor_list = Integer(n).factor(algorithm="ecm")
phi = prod([p - 1 for p,e in factor_list])
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
connection.success(f"Got flag: {flag}")
connection.close()
# [+] Got flag: picoCTF{too_many_fact0rs_0731311}
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{too_many_fact0rs_0731311}</b>
:::
## Sum-O-Primes
:::spoiler <b>gen.py</b>
```python=
#!/usr/bin/python
from binascii import hexlify
from gmpy2 import mpz_urandomb, next_prime, random_state
import math
import os
import sys
if sys.version_info < (3, 9):
import gmpy2
math.gcd = gmpy2.gcd
math.lcm = gmpy2.lcm
FLAG = open('flag.txt').read().strip()
FLAG = int(hexlify(FLAG.encode()), 16)
SEED = int(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)
def get_prime(bits):
return next_prime(mpz_urandomb(STATE, bits) | (1 << (bits - 1)))
p = get_prime(1024)
q = get_prime(1024)
x = p + q
n = p * q
e = 65537
m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)
c = pow(FLAG, e, n)
print(f'x = {x:x}')
print(f'n = {n:x}')
print(f'c = {c:x}')
```
:::
:::spoiler <b>output.txt</b>
```tex!
x = 1626a189dcb38ca6b8e9ee26623ab5c3c6cd7e4c7ff6726f4b03831ca48c617a056827c5763458d0aa7172650072b892649cc73f943f156b795ff5dd2fc9a53b140cf9c3ee2cbb8181d17bb0275f404b4090766f798ad156db7e71000e93db65f3e1bc7406532d0f509fbecf095ef215b4ad51f5e8ac765861e5f93808948bf72
n = 720d66204ec312d7f1bc688495d4585ec58520170b86ed3488c3f9c76407b7e9e466b82a282ba90d484698160f2e27f413b07cf8805d560abdffa977547d5fec3190a1ce284dfc8e92193f2f70590bf9c6e6d0ab449e35ef43ed20232b7f8686696125cde1f950230fbc6858392a3715c1b8a4947748b7fadd5cc921716ad5e0129c91ea88fceee140fb1c594606186afacb69143ef8f7b3b1aa2cc3206395c60e71ec0555dd15838d8a8395e8ccf9a4e4c4199ae0ab3f8af7ebc6605edc5ddd480be2d6c41e38618eba5822a1e566080877268802750de71e890ac865ebf87fdc290d9151e407dff4c97390c9e7388fd538e2716515cea2240f55963c2e0c21
c = 554b90eb12fbece709d7bf23ab91f9b52d71cd77fbf42f65d68623c2055d99956b9bcf2eaf14771fa5781fae86624e44b452a0f68768849faba1b9695ce353a17238a3e7040ee7aede68b35bf4b51daf0982653910b280ac98aad9a5b3c49d226e10b2e8660effc2cb2a553039bde527e42f1795bc078af6ed2928505be6df1ebe993f2ed8c10477dd5cc9f899d1e69b6512b71c732472dde521f5393c76b2f9fbed668560d4e50ca177dd14b923414549d688b20fab94dba7cad7b5a729941c772dc4a1db79b0e6a111d2d2e8998b4e2a272dc940a9dd4cf856faa5a2ee0cb6f36f0ce6edbb421697e517a4d589cc5a880eecf6fbf65e5f6a1a437b06e5ff9a
```
:::
Đề bài cho chúng ta $e$, $c$ và đặc biệt là hai số $n = p \cdot q$ và $x = p + q$. Theo định lý <a href="https://en.wikipedia.org/wiki/Vieta%27s_formulas">Viète</a> đảo ta có $p$ và $q$ là nghiệm của phương trình $t^{2} - xt + n = 0$. Sau khi giải phương trình tìm lại được $p$, $q$ thì ta sẽ tiến hành giải mã RSA như bình thường.
Chú ý rằng $d = e^{-1} ~\operatorname{mod} m$ với $m = \operatorname{lcm}(a,b)$, công thức này hơi khác so với RSA tiêu chuẩn khi nó dùng hàm <a href="https://en.wikipedia.org/wiki/Carmichael_function"><b>Carmichael</b></a> thay vì phi hàm <a href="https://en.wikipedia.org/wiki/Euler%27s_totient_function"><b>Euler</b></a>.
:::spoiler <b style="color:tomato">solution.py</b>
```python=
from sage.all import var, solve, inverse_mod, lcm
from Crypto.Util.number import long_to_bytes
x = "1626a189dcb38ca6b8e9ee26623ab5c3c6cd7e4c7ff6726f4b03831ca48c617a056827c5763458d0aa7172650072b892649cc73f943f156b795ff5dd2fc9a53b140cf9c3ee2cbb8181d17bb0275f404b4090766f798ad156db7e71000e93db65f3e1bc7406532d0f509fbecf095ef215b4ad51f5e8ac765861e5f93808948bf72"
n = "720d66204ec312d7f1bc688495d4585ec58520170b86ed3488c3f9c76407b7e9e466b82a282ba90d484698160f2e27f413b07cf8805d560abdffa977547d5fec3190a1ce284dfc8e92193f2f70590bf9c6e6d0ab449e35ef43ed20232b7f8686696125cde1f950230fbc6858392a3715c1b8a4947748b7fadd5cc921716ad5e0129c91ea88fceee140fb1c594606186afacb69143ef8f7b3b1aa2cc3206395c60e71ec0555dd15838d8a8395e8ccf9a4e4c4199ae0ab3f8af7ebc6605edc5ddd480be2d6c41e38618eba5822a1e566080877268802750de71e890ac865ebf87fdc290d9151e407dff4c97390c9e7388fd538e2716515cea2240f55963c2e0c21"
c = "554b90eb12fbece709d7bf23ab91f9b52d71cd77fbf42f65d68623c2055d99956b9bcf2eaf14771fa5781fae86624e44b452a0f68768849faba1b9695ce353a17238a3e7040ee7aede68b35bf4b51daf0982653910b280ac98aad9a5b3c49d226e10b2e8660effc2cb2a553039bde527e42f1795bc078af6ed2928505be6df1ebe993f2ed8c10477dd5cc9f899d1e69b6512b71c732472dde521f5393c76b2f9fbed668560d4e50ca177dd14b923414549d688b20fab94dba7cad7b5a729941c772dc4a1db79b0e6a111d2d2e8998b4e2a272dc940a9dd4cf856faa5a2ee0cb6f36f0ce6edbb421697e517a4d589cc5a880eecf6fbf65e5f6a1a437b06e5ff9a"
e = 65537
x = int(x, 16)
n = int(n, 16)
c = int(c, 16)
t = var('t')
solution = solve(t**2 - x*t + n, t)
p = solution[0].rhs()
q = solution[1].rhs()
d = inverse_mod(e, lcm(p - 1, q - 1))
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print("[!] Got flag:", flag)
# [!] Got flag: picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_92fe3557}
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_92fe3557}</b>
:::
## New Vignere
:::spoiler <b>new_vignere.py</b>
```python=
import string
LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]
def b16_encode(plain):
enc = ""
for c in plain:
binary = "{0:08b}".format(ord(c))
enc += ALPHABET[int(binary[:4], 2)]
enc += ALPHABET[int(binary[4:], 2)]
return enc
def shift(c, k):
t1 = ord(c) - LOWERCASE_OFFSET
t2 = ord(k) - LOWERCASE_OFFSET
return ALPHABET[(t1 + t2) % len(ALPHABET)]
flag = "redacted"
assert all([c in "abcdef0123456789" for c in flag])
key = "redacted"
assert all([k in ALPHABET for k in key]) and len(key) < 15
b16 = b16_encode(flag)
enc = ""
for i, c in enumerate(b16):
enc += shift(c, key[i % len(key)])
print(enc)
```
:::
Bài này giống như một bản nâng cấp của [New Caesar](#New-Caesar) khi ta chỉ được cho biết một vài thông tin mơ hồ như sau:
```python=
flag = "redacted"
assert all([c in "abcdef0123456789" for c in flag])
key = "redacted"
assert all([k in ALPHABET for k in key]) and len(key) < 15
```
Bài này chúng ta sẽ tiến hành <a href="https://en.wikipedia.org/wiki/Kasiski_examination">kiểm tra Kasiski</a> để có thể dự đoán độ dài khóa. Nói thêm về kiểm tra Kasiski, ta có các bước chính sau:
1. <b>Tìm chuỗi lặp:</b> Bạn cần tìm tất cả các chuỗi ký tự lặp lại có độ dài được khuyến khích là ít nhất 3 chữ cái trong văn bản mã (vì càng nhiều chữ cái thì độ chính xác càng cao).
2. <b>Tính khoảng cách:</b> Đo khoảng cách giữa các lần xuất hiện của mỗi chuỗi lặp đó.
3. <b>Tìm ước số chung lớn nhất (UCLN):</b> Tính UCLN của tất cả các khoảng cách đã tìm được. UCLN này có khả năng cao là độ dài của khóa.
Ví dụ, nếu một chuỗi "ABC" xuất hiện hai lần trong văn bản mã và khoảng cách giữa chúng là $20$, và một chuỗi khác "XYZ" cũng lặp lại với khoảng cách là $30$, thì $\gcd(20, 30) = 10$ Điều này gợi ý rằng độ dài khóa có thể là $10$.
Để tìm hiểu thêm về bản chất đằng sau và tính đúng đắn của phương pháp này thì bạn có thể lên mạng hoặc dùng LLM để giải thích.
Quay trở lại thử thách, ta thấy chuỗi`epdfglkfnbjbhbpicohidjgkhfnejeecmjfnejddgmhpndmchbmifnepdhdmhbah` có chuỗi con `fn` và khoảng cách giữa các chuỗi con `fn` này lần lượt là $9$ và $18$. Như vậy rất có thể độ dài của khóa sẽ là ước của $\gcd(9, 18) = 9$.
Ta cũng để ý rằng các ký tự trong flag luôn là ký tự hexadecimal nên khi mã hóa Base16 flag thì ta được một chuỗi mà các ký tự ở vị trí chẵn luôn là `h` hoặc `g`.
> [!Note] Giải thích
> Vì flag chỉ chứa các ký tự hexadecial $(0-9, a-f)$, nên khi chuyển sang mã nhị phân 8-bit, 4 bit đầu tiên sẽ có quy luật rất rõ ràng:
> - Các chữ số $(0-9)$ khi chuyển sang mã **ASCII** có 4 bit đầu là `0011`. Giá trị này tương ứng với ký tự thứ 3 trong **ALPHABET** là `d`.
> - Các chữ cái $(a-f)$ khi chuyển sang mã **ASCII** có 4 bit đầu là `0110`. Giá trị này tương ứng với ký tự thứ 6 trong **ALPHABET** là `g`.
> Điều này có nghĩa là chuỗi trung gian sau khi qua **b16_encode** (nhưng trước khi bị mã hóa **Vigenère**) sẽ có một quy luật: các ký tự ở vị trí chẵn (0, 2, 4,...) phải là `d` hoặc `g`. Đây chính là "lỗ hổng" để giải mã.
Vì không gian của mỗi ký tự trong khóa rất nhỏ, chỉ có $16$ khả năng, nên ta sẽ tận dụng điều này và các tính chất đã phân tích ở trên để tiến hành brute-force như sau:
1. <b>Lặp qua từng vị trí của khóa:</b> Tạo một vòng lặp chạy từ `key_pos = 0` đến `len(key)`.
2. <b>Với mỗi vị trí, thử mọi khả năng:</b> Bên trong vòng lặp trên, tạo một vòng lặp nữa để thử từng ký tự trong **ALPHABET** (`a` đến `p`) làm ứng cử viên cho `key[key_pos]`. Gọi đây là `candidate_char`.
3. <b>Kiểm tra ứng cử viên:</b> Giờ, chúng ta cần kiểm tra xem candidate_char có phải là ký tự đúng cho `key[key_pos]` hay không. Cách làm như sau:
a. Lấy tất cả các ký tự trong bản mã (**CIPHERTEXT**) mà `key[key_pos]` đã mã hóa. Đó là các ký tự ở vị trí `key_pos`, `key_pos + len(key)`, `key_pos + 2*len(key)`, ...
b. Với mỗi ký tự bản mã này, hãy **giải mã thử** nó bằng `candidate_char` (dùng hàm `unshift`).
c. Sau khi giải mã thử, chúng ta có một ký tự trung gian giả định. Bây giờ, hãy áp dụng "Quy luật `d` hoặc `g`".
d. **Chỉ khi** vị trí của ký tự bản mã là **chẵn** (ví dụ: 0, 2, 18, 20,...), thì ký tự trung gian giả định mà ta vừa tìm được phải là `d` hoặc `g`.
e. Nếu có bất kỳ một trường hợp nào vi phạm quy luật này, `candidate_char` chắc chắn sai. Chúng ta ngay lập tức loại bỏ nó và chuyển sang thử ký tự tiếp theo trong **ALPHABET**.
4. <b>Tìm ký tự đúng:</b> Nếu một `candidate_char` vượt qua tất cả các bài kiểm tra ở bước 3 cho tất cả các vị trí liên quan, thì đó chính là ký tự đúng cho `key[key_pos]`. Lưu nó lại và chuyển sang tìm ký tự cho vị trí tiếp theo của khóa (`key_pos + 1`).
Nếu bạn nào thấy văn phong giống AI thì đúng rồi đó, mình đã dựa vào AI để viết đoạn phân tích và giải thích trên (vì mình lười :penguin:). Nhân tiện thì dưới đây sẽ là script giải bài cho thử thách này:
:::spoiler <b style="color:tomato">solution.py</b>
```python=
import string
LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]
# Đảo ngược của hàm shift
def unshift(c: str, k: str) -> str:
t1 = ord(c) - LOWERCASE_OFFSET
t2 = ord(k) - LOWERCASE_OFFSET
decrypted_index = (t1 - t2) % len(ALPHABET)
return ALPHABET[decrypted_index]
# Đảo ngược hàm mã hóa b16
def b16_decode(cipher: str) -> str:
plain = ""
for c1, c2 in zip(cipher[0::2], cipher[1::2]):
n1 = "{0:04b}".format(ALPHABET.index(c1))
n2 = "{0:04b}".format(ALPHABET.index(c2))
binary = int(n1 + n2, 2)
plain += chr(binary)
return plain
# Đảo ngược mã hóa đề bài
def decrypt(enc: str, key: str) -> str:
dec = ""
for i, c in enumerate(enc):
dec += unshift(c, key[i % len(key)])
return b16_decode(dec)
# Sau kiểm tra Kasiski, ta tìm được độ dài khóa tiềm năng là 1, 3 và 9
CIPHERTEXT = "epdfglkfnbjbhbpicohidjgkhfnejeecmjfnejddgmhpndmchbmifnepdhdmhbah"
POTENTIAL_KEY_LENGTH = [1, 3, 9]
# Chúng ta bắt đầu brute-force thông minh để tìm những ký tự khóa khả quan
for KEY_LENGTH in POTENTIAL_KEY_LENGTH:
possible_key_chars = [[] for _ in range(KEY_LENGTH)]
for key_position in range(KEY_LENGTH):
for key_char in ALPHABET:
is_valid_key_char = True
for cipher_postion in range(key_position, len(CIPHERTEXT), KEY_LENGTH):
decrypted_char = unshift(CIPHERTEXT[cipher_postion], key_char)
if(cipher_postion % 2 == 0):
if(decrypted_char not in ['d', 'g']):
is_valid_key_char = False
break
if is_valid_key_char:
possible_key_chars[key_position].append(key_char)
is_possible_list = True
for key_char in possible_key_chars:
if(key_char == []):
is_possible_list = False
break
if(is_possible_list == False): continue
# Đoạn này dùng quay lui (backtracking) để có thể lấy ra tất cả các khóa khả thi
def backtrack(i: int, n: int, current: string, possible_key_chars: list, possible_key_list: list):
if(i == n):
possible_key_list.append(current)
return
for char in possible_key_chars[i]:
current += char
backtrack(i+1, n, current, possible_key_chars, possible_key_list)
current = current[:-1] # Python lỏ này không xịn như C++, dùng string::pop_back() là xong
possible_key_list = []
backtrack(0, len(possible_key_chars), "", possible_key_chars, possible_key_list)
# Muốn in ra màu mè ở đoạn này một chút mà cũng khó nhỉ 🥺
print("All possible flags and keys:")
for index, possible_key in enumerate(possible_key_list, start=1):
possible_flag = decrypt(CIPHERTEXT, possible_key)
print(f"{index:>{1}}. Key: {possible_key}")
print(" "*(1 + 5) + "Flag: picoCTF{" + f"{possible_flag}" + '}')
# All possible flags and keys:
# 1. Key: bgabajepk
# Flag: picoCTF{94bf01ad4b8a63425c32c02ba4c9632f}
# 2. Key: bgnbajepk
# Flag: picoCTF{9dbf04ad4bha63725c3bc02ea4c9f32f}
```
:::
:::success
**Flag:** <b style="color:#3262a8">picoCTF{94bf01ad4b8a63425c32c02ba4c9632f}</b>
:::
>[!Important] Lưu ý
>Ở flag thứ hai có ký tự `h` kỳ lạ không thuộc ký tự hexadecimal nên ta có thể loại luôn flag thứ hai nhé!
## Summary
Đây là những bài mà mình cảm thấy khá thú vị trong **picoCTF**. Các câu trung bình thì thường không thuần khiết cryptography (cụ thể là lai tạp với forensics) và cũng không khó lắm. Các câu ở mức độ khó thì giống với cryptography và độ khó cũng tăng lên đáng kể làm việc giải nó cũng trở nên thú vị hơn.
Hi vọng bài viết này sẽ giúp ích được phần nào đó cho các bạn đọc. Xin chào và hẹn gặp lại ở các phần tiếp theo :wave:.
Sign in with Wallet
Connect another wallet