{%hackmd @abc90/temp3 %}
# KMACTF 2023
# Simple encode
chall.py

import string
from hashlib import md5
import random

def encode(m):
    return ''.join(bin(ord(c))[2:] for c in m)


flag = "KMA{" + "".join(random.choices(string.printable[:-6], k=27)) + "}"
print(f'{flag = }')

flag_hash = md5(flag.encode()).hexdigest()
print(f'{flag_hash = }')

flag_encode = encode(flag)
print(f'{flag_encode = }')

'''
flag_hash = '16ab78b0c0654e663d7e2e22ac0a9b7a'
flag_encode = '10010111001101100000111110111010001011000111000101010110110001101101001011100101110000111010110101111000101111001111110100000010001111000111011011011110101011111110011000111110111101001001000100011010001101111101'
'''

Đọc source code mình thấy ,flag được random lấy 27 kí tự ngẫu nhiên trong `string.printable[:-6]` trừ những kí tự điều khiển , với không gian mẫu là 94 random lấy chuỗi 27 kí tự sẽ có $94^{27}$ cách chọn nên việc brute force không khả thi .

Khi encode thử các kí tự có thể xuất hiện bằng hàm `encode()` mình thấy các kí tự sẽ chỉ encode thành chuỗi binary có độ dài 6 hoặc 7 bit .
Vì vậy, ý tưởng của bài này là sẽ tìm các chuỗi random khi encode thỏa mãn chuỗi binary .
Nếu kí tự thứ `i` với độ dài bin là 6, hoặc 7 bit có thể in được , thì thêm vào chuỗi , tiếp tục tìm các kí tự tiếp theo . Đến khi tìm được chuỗi có len là 27
Ban đầu mình thử 1 vài kí tự bằng tay thì có thể tìm được
1 vài kí tự chính xác ví dụ chuỗi đúng sẽ bắt đầu bằng `(X8UX` và sẽ kết thúc bằng `HFF` . Nếu may mắn thử tay có thể tìm đc flag, nhưng mất rất nhiều thời gian và chưa tối ưu.

Dưới đây là solution mình dùng đệ quy để tìm các chuỗi thỏa mãn chuỗi `bin_enc`. Khi kí tự thứ `i` có thể in ra màn hình thì tiếp tục tìm các kí tự kế tiếp .
Có 4 trường hợp xảy ra:
- chuỗi 6 bit là kí tự thỏa mãn và và 7 bit thì không
- chuỗi 6 bit là kí tự không thỏa mãn và và 7 bit thì có
- cả 2 chuỗi 6 và 7 bit đều là kí tự thỏa mãn thì tìm tiếp cả 2 trường hợp
- cả 2 không thỏa mãn thì return dừng tìm
Khi tìm được chuỗi có độ dài 27 kí tự thì lưu vào mảng .Để check hash tìm flag

Tìm được càng nhiều kí tự chính xác thì việc tính toán càng đơn giản hơn

sol.py

import string
from hashlib import md5
flag = "KMA{"
hash_str = "16ab78b0c0654e663d7e2e22ac0a9b7a"
flag_hash = md5(flag.encode()).hexdigest()
bin_enc = "10010111001101100000111110111010001011000111000101010110110001101101001011100101110000111010110101111000101111001111110100000010001111000111011011011110101011111110011000111110111101001001000100011010001101111101"
mid = "101000101100011100010101011011000110110100101110010111000011101011010111100010111100111111010000001000111100011101101101111010101111111001100011111011110100100100010001101000110"
def encode(m):
    return ''.join(bin(ord(c))[2:] for c in m)

print(len(mid))
def binary_to_letter(binary_str):
    decimal_value = int(binary_str, 2)

    character = chr(decimal_value)

    return character


res = "(X8" 
end = "HFF"
mid_part = mid[len(encode(res)):]
def indc(c):
    if c in string.printable[:-6]:
        return True
    return False


all_flag = []
def findres(end):
    mid_part = mid[len(encode(end)):]
    if len(end) == 27:
        all_flag.append(end)
        return
    last6 = binary_to_letter(mid_part[:6])
    last7 = binary_to_letter(mid_part[:7])

    if indc(last6) and not indc(last7) :
        end = end + last6 
        findres(end)
    elif not indc(last6) and  indc(last7) :
        end = end + last7 
        findres(end)
    elif indc(last6) and indc(last7):
        end1 = end +last6 
        findres(end1)
        end2 = end + last7 
        findres(end2)
    else :
        return
findres(res)
print(all_flag)
print("---------------------------------")
for x in all_flag:
    flag = "KMA{" + x + "}"
    flag_hash = md5(flag.encode()).hexdigest()
    if flag_hash == hash_str:
        print(flag)

Flag: `KMA{(X8UX6K%0uWE9>@#1m^W<1=tHFF}`

# Similar But ...

chall.py

from Crypto.Util.number import *

p = getPrime(2048)
q = getPrime(2048)
n = p*q
e = 2

print(f'{n = }')

flag = "KMA{anh che roi!!!!!!!}"
l = len(flag)
print(f'{l = }')

msg = f'''
Gửi đến những người em thân yêu của anh, hôm nay anh muốn chia sẻ với các em một câu chuyện về kho báu. 
Trong câu chuyện này, kho báu được chia thành hai nửa, và mỗi nửa mang trong mình một ý nghĩa đặc biệt.
Nửa đầu tiên anh giấu ở đây: {flag[:l//2]}
Còn đây là nửa thứ hai: {flag[l//2:]}
Hãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.
Chúc các em may mắn !!!
'''

c = pow(bytes_to_long(msg.encode()), e,n)
print(f'{c = }')

'''
n = 284195696721751741542976970377246384163200746062783759329661617188815436776424189078521874168074640320924439097731870753354899953210403298438375686437215681238598996375382536537768278254146374135440697791835320902172928838535170207920563260188268857178412014945665843067884706362429213081345697201062048319151146709862154724701120787598264599428501030945241764332469820283330386978451487308358496070493019375227430237712951734594609189071738774562063639368050519599690219339371888693892756654714125742546793650545564645761412676393745546867317157950660276413454704121923686068169935524575099441009254762051678974615084672006274688302115077734407074204036930371634952480748870905140950407665202776686680232626404222734370828402377048157739018826752500816695651244608931659579045297636939347065142654266415418100162785201594053030962306454285243690682313810711305540434910861763618201288903763117959626276874769295456013747611282355250494278056557319959998777444026981083893016148032869660521587008308779834135343779295437340050873017686606894792594175473683376016830206421076702465312246840917660142641545140295983913838540847955749716541937276104901379735588334581049297927341758018775135576856481243743641314705618868934645861372761
l = 46
c = 197348052174145638785229215457497516691585910055835441125583073645980013777032065006627024581136020897300252228534006100306209234223154204281916399887451961006595700453576912583653484661863741375270305419615721406198781214515934675523007505165820308082654403780811498250984535336719680589351485735567955825720119048693747519278867766555710216038040229689357846375187513096350835998852728799656866437148777620905204000517049701112204778019184506339386241329691058153055354968087261832501249138236077313408204182929051641521267083356295624561257562991234261668632037087231724232716833294744291699334965334803826200727633700589654688863746449952492047286765973034494755978048670534899135052018421945310658805856492088479095070115314198579191182336314746398558742288499341372595578846975164079893641205584309595266932028754927985671375042116891444819656916960144209962788439147210122667753145683940192069926363191913583924164601419393905729897192079336412469978182139715148777895764888053578167383521367586833983484951931519842177634434322107919818397921097644416813823140565831649561406124639176188646350960425853516784830094432718779747088309513889971075211757981041043652016970888838329334179083984287540371718185534696012444989603691
'''

Bài này tuy e = 2 nhưng msg rất dài nên không thể dùng low exponent attack
len(msg) = 395

$$m^e = 2^{395*8*2} = 2^{6320} > n $$

Chúng ta có thể sử dụng phương pháp của Coppersmith
$$x < N^{(1/{degree(f(x)}) - epsilon}$$
epsilon là độ chính xác, epsilon càng nhỏ độ chính xác càng cao, nhưng tính lâu hơn ,epsilon thường là 1/7 hoặc 1/8

$$f(x) = ((msg + x)^e - c )mod n $$

$msg + x$ sẽ bằng plaintext khi $f(x)$ = 0

Thay các kí tự của flag = X ta được

msg = f'''
Gửi đến những người em thân yêu của anh, hôm nay anh muốn chia sẻ với các em một câu chuyện về kho báu. 
Trong câu chuyện này, kho báu được chia thành hai nửa, và mỗi nửa mang trong mình một ý nghĩa đặc biệt.
Nửa đầu tiên anh giấu ở đây: XXXXXXXXXXXXXXXXXXXXXXX
Còn đây là nửa thứ hai: XXXXXXXXXXXXXXXXXXXXXXX
Hãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.
Chúc các em may mắn !!!
'''

Đoạn
`"XXXXXXXXXXXXXXXXXXXXXXX\nCòn đây là nửa thứ hai: XXXXXXXXXXXXXXXXXXXXXXX\nHãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.\nChúc các em may mắn !!!\n"` dài 156 kí tự ,
Suy ra $$max(x): x < 2^{8*156} = 2^{1248} $$
$$ x^e = x^2 < 2^{2496} $$
Thay các kí tự `X` bằng byte null `\x00`
trong đó 46 là flag còn lại là 2 đoạn text
`\nCòn đây là nửa thứ hai: ` len = 25
`\nHãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.\nChúc các em may mắn !!!\n"` len = 85

Nếu một số kết thúc bằng byte null, điều đó có nghĩa là nó chia hết cho 256. Do đó, nó phải là bội số của 256$${2^8}^{25} = 256^{25} = 2^{200} $$

Tương tự với chuỗi thứ 2
$${2^8}^{85} = 256^{85} = 2^{680} $$

$$ g(x) = (msg + 2^{200}*x + 2^{680})^e - c$$

Do đó $$ x*2^{200} + 2^{680} < 2^{1248} $$
$$=> x < 2^{1048} $$
$$=> x^e < 2^{2096} < n$$

Thử epsilon = 1/7

$$ \frac{1}{degree(g(x))} - epsilon = \frac{1}{2} - \frac{1}{7} = \frac{5}{14} $$

$$ 2^{4096*\frac{5}{14}} = 2^{1462.8} > x $$
nên Coppersmith sẽ hoạt động

sol.sage

from Crypto.Util.number import *
from Crypto.Util.number import *
msg = f'''
Gửi đến những người em thân yêu của anh, hôm nay anh muốn chia sẻ với các em một câu chuyện về kho báu. 
Trong câu chuyện này, kho báu được chia thành hai nửa, và mỗi nửa mang trong mình một ý nghĩa đặc biệt.
Nửa đầu tiên anh giấu ở đây: XXXXXXXXXXXXXXXXXXXXXXX
Còn đây là nửa thứ hai: XXXXXXXXXXXXXXXXXXXXXXX
Hãy tìm ra kho báu của anh đi, anh để hết trong msg rồi đó.
Chúc các em may mắn !!!
'''
print(len(msg))
msg = msg.encode()
msg = msg.replace(b"X",b"\x00")
msg = bytes_to_long(msg)
n = 284195696721751741542976970377246384163200746062783759329661617188815436776424189078521874168074640320924439097731870753354899953210403298438375686437215681238598996375382536537768278254146374135440697791835320902172928838535170207920563260188268857178412014945665843067884706362429213081345697201062048319151146709862154724701120787598264599428501030945241764332469820283330386978451487308358496070493019375227430237712951734594609189071738774562063639368050519599690219339371888693892756654714125742546793650545564645761412676393745546867317157950660276413454704121923686068169935524575099441009254762051678974615084672006274688302115077734407074204036930371634952480748870905140950407665202776686680232626404222734370828402377048157739018826752500816695651244608931659579045297636939347065142654266415418100162785201594053030962306454285243690682313810711305540434910861763618201288903763117959626276874769295456013747611282355250494278056557319959998777444026981083893016148032869660521587008308779834135343779295437340050873017686606894792594175473683376016830206421076702465312246840917660142641545140295983913838540847955749716541937276104901379735588334581049297927341758018775135576856481243743641314705618868934645861372761
l = 46
e = 2
c = 197348052174145638785229215457497516691585910055835441125583073645980013777032065006627024581136020897300252228534006100306209234223154204281916399887451961006595700453576912583653484661863741375270305419615721406198781214515934675523007505165820308082654403780811498250984535336719680589351485735567955825720119048693747519278867766555710216038040229689357846375187513096350835998852728799656866437148777620905204000517049701112204778019184506339386241329691058153055354968087261832501249138236077313408204182929051641521267083356295624561257562991234261668632037087231724232716833294744291699334965334803826200727633700589654688863746449952492047286765973034494755978048670534899135052018421945310658805856492088479095070115314198579191182336314746398558742288499341372595578846975164079893641205584309595266932028754927985671375042116891444819656916960144209962788439147210122667753145683940192069926363191913583924164601419393905729897192079336412469978182139715148777895764888053578167383521367586833983484951931519842177634434322107919818397921097644416813823140565831649561406124639176188646350960425853516784830094432718779747088309513889971075211757981041043652016970888838329334179083984287540371718185534696012444989603691

P.<x> = PolynomialRing(Zmod(n))
pol = (msg + (2^200)*x + (2^680))^e - c
pol = pol.monic()
flag  = pol.small_roots(epsilon=1/7)[0]
print(long_to_bytes(int(flag)).replace(b'\x00',b'').rstrip(b'\xff'))

Flag: `KMA{So_litttt_c0pp33r_Sm1th_Savageeeee!!!!!!!|`

# Bazoka

chall.py

from hashlib import md5

def encrypt(plaintext, key):
    key = md5(key).digest()
    msg = plaintext + b'|' + key
    # print(msg)
    encrypted = b'K'
    for i in range(len(msg)):
        encrypted += bytes([(msg[i] + key[i%len(key)]  + encrypted[i]) & 0xff])
    return encrypted.hex()

flag = b"KMA{anh xoa di roi}"
key = b"anh xoa di roi"
ciphertext = encrypt(flag, key)
print(ciphertext)
# 4b851cc4cdd1c7a3b7a3d83095a46a320e6b21e9e5afab7b8869d930c9cd981a0523a037faca8425f9a921c6ebca8f7087f8aab5bc53fe9cd5acfa9e

Do biết 4 kí tự đầu là `KMA{` nên có thể tìm đc key[:4] = `\xefJg\x8e`

msg[41] = b"}"
msg[42] = b"|"

Tìm được key[9] = `\xfb` và key[10] = `)`
Theo cách tương tự khôi phục được key = `\xefJg\x8e\x9c\x82h\xa4y\xfb)6\x95^S{`

Khi có Key rồi thì có thể brute force flag dễ dàng

sol.py

from hashlib import md5
def encrypt(plaintext, key):
    key = md5(key).digest()
    msg = plaintext + b'|' + key
    # print(msg)
    encrypted = b'K'
    for i in range(len(msg)):
        encrypted += bytes([(msg[i] + key[i%len(key)]  + encrypted[i]) & 0xff])
    return encrypted.hex()



flag = b""
ciphertext = "4b851cc4cdd1c7a3b7a3d83095a46a320e6b21e9e5afab7b8869d930c9cd981a0523a037faca8425f9a921c6ebca8f7087f8aab5bc53fe9cd5acfa9e"
ct_bytes = bytes.fromhex(ciphertext)
print(ct_bytes)
key = b'\xefJg\x8e\x9c\x82h\xa4y\xfb)6\x95^S{'
# print(len(key))

#msg[42] = b'|'


encrypted=b'K'
for i in range(59):
    for x in range(256):
        tmp = bytes([(x + key[i%len(key)]  + encrypted[i]) & 0xff])
        if tmp == bytes([ct_bytes[i+1]]):
            encrypted += tmp
            flag += bytes([x])
        
print(flag)
# print(key)
        

Flag: `KMA{https://zhuanlan.zhihu.com/p/30548907}|\xefJg\x8e\x9c\x82h\xa4y\xfb)6\x95^S{`