# Symmetry Cryptography
## ECB Oracle

Description
> ECB is the most simple mode, with each plaintext block encrypted entirely independently. In this case, your input is prepended to the secret flag and encrypted and that's it. We don't even provide a decrypt function. Perhaps you don't need a padding oracle when you have an "ECB oracle"?


* Tư tưởng chính là mã hóa từng block 16 byte thành 32 hex tương ứng

VD: ABCDEFGHIKJLMNOP (16 byte) -> zxcvbnmasdfghjklqwertyuiopqscfgh (32 hex)

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad


KEY = ?
FLAG = ?


@chal.route('/ecb_oracle/encrypt/<plaintext>/')
def encrypt(plaintext):
    plaintext = bytes.fromhex(plaintext)

    padded = pad(plaintext + FLAG.encode(), 16)
    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        encrypted = cipher.encrypt(padded)
    except ValueError as e:
        return {"error": str(e)}

    return {"ciphertext": encrypted.hex()}

* Ở đây đoạn code chỉ cho hàm để mã hóa, chứ không cho hàm để giải mã

**Giải thích code**

padded = pad(plaintext + FLAG.encode(), 16)

* Hàm **pad(data_btye, block_size)** để mở rộng (hiểu đơn giản là nhét chữ) data để đạt độ dài block_size (byte). Mục đích để đảm bảo độ dài data luôn là bội số của 16

VD:
> pad(b'ab', 6) ---> b'ab **\x04\x04\x04\x04**'

* Nếu độ dài của data đã là bội của 16, hàm này sẽ tự động thêm vào 16 kí tự nữa (kí tự 'o')

VD:
> XXXXXXXcrypto{te
> xkhdghakhdkajdt}
> **oooooooooooooooo** (0) <-- padding 16

**Tìm độ dài của flag**
* Thử 'AAAAAAAAAAAA' (6 byte) và cipher text sẽ là:
> 855bf10aab428df16de163f39d9b665b
> 702bab69dc1be9665a9807fad88ad3d5
>

* Và khi thử 'AAAAAAAAAAAAAAAA' (7 byte) sẽ ra thêm 1 dòng 32 hex nữa, chứng tỏ khi nhập plaintext có độ dài là 7 byte, thì độ dài của plaintext + flag sẽ là bội của 16 (byte), và 1 dòng thêm kia chính là 1 dòng pad thêm vào

Plaintext + flag (P + F):
> XXXXXXXcrypto{aa
> dahduiadhuiadh}
> ooooooooooooooo <-- padding 16

=> Ciphertext ( C ):
> 61e2e16d2b2f76d7cb68bc8511d0d934
> ec103207cd9ee73c84ab8819ebff4505
> 3150f4d79d7cc6c1d4b574b1fce84247 <--- padding of 16

* 2 dòng đầu chính là plaintext + flag được mã hóa dưới dạng hex, 64 hex tương đương 32 byte (1 hex = 2 byte). Mà ta vừa thêm vào 7 byte plaintext nên độ dài của flag suy ra là 32 - 7 = 25 byte

**Brute Force các kí tự trong flag**
* Format sẽ là 'crypto{text}' nên ta chỉ cần đoán xem text là gì.
* Nếu thêm 'AA' (khi đó độ dài plaintext là 8 byte)
P + F:
> XXXXXXXXcrypto{
> adahduiadhuiadh
> }oooooooooooooo

C:
> 9290467e38b839889c380e6ea83745ef
> cddbe6872f3fcc58b0cc14cfa547d423
> b260ae79e941ddf896fa63b3d82a184b <-- }ooooooooooooooo

* Giờ check xem kí tự đầu của dòng cuối có phải đúng là '}' không. Trong bảng ASCII, '}' tương ứng '7d'. Sau khi pad, dòng cuối sẽ có dạng '7d0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f' (hex). Nên chúng ta sẽ nhập cái này vào để encrypt, ta sẽ có đoạn hex

P + F:
}\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f **(16 byte)**
crypto{asdaasdas
dasdasda}ooooooo
C:

> b260ae79e941ddf896fa63b3d82a184b <-- }ooooooooooooooo
> 4a324f27e8fde012631ac310cce8d626
> 5c4e884ba0ecc2141c276d06247f6b2f

* Và quả nhiên dự đoán ban đầu của chúng ta đã đúng. Nếu cứ thêm kí tự 'AA' vào đằng trước, rồi brute force từng kí tự, ta sẽ thu được flag.

* Ta sẽ target vào kí tự đầu tiên của dòng 3

> XXXXXXXcrypto{te (7 byte plaintext)
> xkhdghakhdkajdt}
> ooooooooooooooo (0)
>

---

> XXXXXXXXcrypto{t (8 byte plaintext)
> exkhdghakhdkajdt
> }oooooooooooooo (1)
>

---

> XXXXXXXXXcrypto{ (9 byte plaintext)
> texkhdghakhdkajd
> t}oooooooooooooo (2)

* Khi đó ta sẽ brute force **xx**7d0e0e0e0e0e0e0e0e0e0e0e0e0e0e với **xx** sẽ là các số hex
* Khi tìm được 16 byte cuối của flag, ta sẽ brute force **xx** + 30 hex đầu của flag để tìm nốt 2 kí tự còn lại

> XXXXXXXXXXXXXXXX (25 byte plaintext)
> XXXXXXXcrypto{te
> **xkhdghakhdkajdt}** <-- 16 kí tự cuối của flag
> oooooooooooooooo (3)

Ta chạy nốt 2 vòng để tìm ra 2 kí tự còn lại

> XXXXXXXXXXXXXXXX (26 byte plaintext)
> XXXXXXXXcrypto{t
> e**xkhdghakhdkajdt** <-- chỉ giữ lại 15 kí tự đầu của flag và brute force
**}** ooooooooooooooo (4)

---
> XXXXXXXXXXXXXXXX (27 byte plaintext)
> XXXXXXXXXcrypto{
> te**xkhdghakhdkajd** <-- chỉ giữ lại 14 kí tự đầu của flag và brute force
> **t}** oooooooooooooo (5)

Sau đây là script

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import requests

# Request encryted from web
def get_request(param):
    r = requests.get('https://aes.cryptohack.org/ecb_oracle/encrypt/' + param)
    data = r.json()['ciphertext']
    return data

# Generate the rest of the third block (padding)
def padding(number):
    time = number
    number = hex(number)[2:]
    if len(number) == 1:
        number = '0' + number
    return number * time

# Find the first character of the third block
def extract(i):
    for w in word_list:
        if len(flag) < 32:
            inp = w + flag + padding(i) # String 32 hex
            first_block = get_request(inp)[:32]
            print('testing', inp)
            if first_block == block:
                return w
        else:
            inp = w + flag[:30]
            first_block = get_request(inp)[:32]
            print('testing', inp)
            if first_block == block:
                return w

# Generate word list        
word_list = []
for i in range(32, 127):
    word = hex(i)[2:]
    if len(word) == 1:
        word = '0' + word
    word_list.append(word)

flag = ''

# Find the last 16 byte of flag
for i in range(15, -1, -1):
    offset = 16 - i
    added = 'AA' * 7 + 'AA' * offset
    block = get_request(added)[64:96] # Check on the third block 
    flag = extract(i) + flag

flag = '6e3675316e355f683437335f3363627d'

# Check the first 2 characters of the text
for i in range(2):
    offset = 17 + i
    added = 'AA' * 7 + 'AA' * offset
    block = get_request(added)[64:96] # Check on the third block 
    flag = extract(i) + flag

flag = '70336e3675316e355f683437335f3363627d' # hex
# p3n6u1n5_h473_3cb} in byte
# flag = crypto{p3n6u1n5_h473_3cb}

## ECB CBC WTF
> Here you can encrypt in CBC but only decrypt in ECB. That shouldn't be a weakness because they're different modes... right?


Source

from Crypto.Cipher import AES


KEY = ?
FLAG = ?


@chal.route('/ecbcbcwtf/decrypt/<ciphertext>/')
def decrypt(ciphertext):
    ciphertext = bytes.fromhex(ciphertext)

    cipher = AES.new(KEY, AES.MODE_ECB)
    try:
        decrypted = cipher.decrypt(ciphertext)
    except ValueError as e:
        return {"error": str(e)}

    return {"plaintext": decrypted.hex()}


@chal.route('/ecbcbcwtf/encrypt_flag/')
def encrypt_flag():
    iv = os.urandom(16)

    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    encrypted = cipher.encrypt(FLAG.encode())
    ciphertext = iv.hex() + encrypted.hex()

    return {"ciphertext": ciphertext}

* Ciphertext = mã hóa (iv + plaintext1 + plaintext2)

import requests
from Crypto.Util.number import long_to_bytes, bytes_to_long

# len(iv) = 16, len(flag) = 32, p1 = 16, p2 = 16 in bytes
def encrypted():
    url = 'https://aes.cryptohack.org/ecbcbcwtf/encrypt_flag/'
    ciphertext = requests.get(url)
    return bytes.fromhex(ciphertext.json()['ciphertext'])

def decrypted(ciphertext):
    ciphertext =  ciphertext.hex()
    url = 'https://aes.cryptohack.org/ecbcbcwtf/decrypt/' + ciphertext
    plaintext = requests.get(url)
    return bytes.fromhex(plaintext.json()['plaintext'])

def xor(text1, text2):
    return long_to_bytes(bytes_to_long(text1) ^ bytes_to_long(text2))

ciphertext = encrypted()

iv = ciphertext[:16]
ciphertext1 = ciphertext[16:32]
ciphertext2 = ciphertext[32:]

# dn = pn ^ c(n-1) (c0 = iv)
decrypted1_xor = decrypted(ciphertext1)
decrypted2_xor = decrypted(ciphertext2)

p2 = xor(decrypted2_xor, ciphertext1)
p1 = xor(iv, decrypted1_xor)
plaintext = p1 + p2
print(plaintext.decode())

# flag = crypto{3cb_5uck5_4v01d_17_!!!!!}

## Flipping Cookie

> Description
> You can get a cookie for my website, but it won't help you read the flag... I think.


Source

from Crypto.Cipher import AES
import os
from Crypto.Util.Padding import pad, unpad
from datetime import datetime, timedelta


KEY = ?
FLAG = ?


@chal.route('/flipping_cookie/check_admin/<cookie>/<iv>/')
def check_admin(cookie, iv):
    cookie = bytes.fromhex(cookie)
    iv = bytes.fromhex(iv)

    try:
        cipher = AES.new(KEY, AES.MODE_CBC, iv)
        decrypted = cipher.decrypt(cookie)
        unpadded = unpad(decrypted, 16)
    except ValueError as e:
        return {"error": str(e)}

    if b"admin=True" in unpadded.split(b";"):
        return {"flag": FLAG}
    else:
        return {"error": "Only admin can read the flag"}


@chal.route('/flipping_cookie/get_cookie/')
def get_cookie():
    expires_at = (datetime.today() + timedelta(days=1)).strftime("%s")
    cookie = f"admin=False;expiry={expires_at}".encode()

    iv = os.urandom(16)
    padded = pad(cookie, 16)
    cipher = AES.new(KEY, AES.MODE_CBC, iv)
    encrypted = cipher.encrypt(padded)
    ciphertext = iv.hex() + encrypted.hex()

    return {"cookie": ciphertext}

Trong hàm **check_admin()**, cookie phải có "admin=True" thì ta mới thu được FLAG. Vậy ta chỉ cần biến đổi cookie từ **get_cookie()** từ "admin=False" thành cái ta cần bằng phép xor

Pt = b'admin=False;expi'
Pf = b'admin=True;\x05\x05\x05\x05\x05'
Pm = xor(Pt, Pf)
new_iv = xor(bytes.fromhex(iv), Pm)


Code

from Crypto.Cipher import AES
import requests
from Crypto.Util.Padding import pad, unpad
from datetime import datetime, timedelta
from Crypto.Util.number import long_to_bytes, bytes_to_long

def get_cookie():
    url = 'https://aes.cryptohack.org/flipping_cookie/get_cookie/'
    iv_cookie = requests.get(url).json()['cookie']
    iv = iv_cookie[:32]
    cookie = iv_cookie[32:]
    return cookie, iv

def decrypted(cookie, iv):
    url = 'https://aes.cryptohack.org/flipping_cookie/check_admin/' + cookie + '/' + iv
    decrypted = requests.get(url)
    return decrypted.json()

def xor(byte1, byte2):
    return long_to_bytes(bytes_to_long(byte1) ^ bytes_to_long(byte2))

cookie, iv = get_cookie()
block1 = bytes.fromhex(cookie[:32])
block2 = cookie[32:]


Pt = b'admin=False;expi'
Pf = b'admin=True;\x05\x05\x05\x05\x05'
Pm = xor(Pt, Pf)
new_iv = xor(bytes.fromhex(iv), Pm)

print(decrypted(block1.hex(), new_iv.hex()))

# flag = crypto{4u7h3n71c4710n_15_3553n714l}

## Symmetry

> Some block cipher modes, such as OFB, CTR, or CFB, turn a block cipher into a stream cipher. The idea behind stream ciphers is to produce a pseudorandom keystream which is then XORed with the plaintext. One advantage of stream ciphers is that they can work of plaintext of arbitrary length, with no padding required.
OFB is an obscure cipher mode, with no real benefits these days over using CTR. This challenge introduces an unusual property of OFB.


Source

from Crypto.Cipher import AES


KEY = ?
FLAG = ?


@chal.route('/symmetry/encrypt/<plaintext>/<iv>/')
def encrypt(plaintext, iv):
    plaintext = bytes.fromhex(plaintext)
    iv = bytes.fromhex(iv)
    if len(iv) != 16:
        return {"error": "IV length must be 16"}

    cipher = AES.new(KEY, AES.MODE_OFB, iv)
    encrypted = cipher.encrypt(plaintext)
    ciphertext = encrypted.hex()

    return {"ciphertext": ciphertext}


@chal.route('/symmetry/encrypt_flag/')
def encrypt_flag():
    iv = os.urandom(16)

    cipher = AES.new(KEY, AES.MODE_OFB, iv)
    encrypted = cipher.encrypt(FLAG.encode())
    ciphertext = iv.hex() + encrypted.hex()

    return {"ciphertext": ciphertext}

* Ở đây đề bài cho 2 hàm **encrypt()** và **encrypt_flag()**, ta nghĩ đến việc đánh vào lỗ hổng đầu vào


* Ta sẽ khéo léo chọn plaintext (Pk) bất kì rồi cho vào hàm **encrypt()**, sau đó lấy kết quả xor với ciphertext của flag, ta sẽ thu được kết quả (khi đó sẽ mất hết cái đống e(iv)).

* Ta chọn Pk = '00' * 33 trùng với độ dài của ciphertext flag, mục đích là khi cho vào phép xor, '00' sẽ không làm thay đổi các bits. Có thể chọn các kí tự khác, nhưng sẽ phải xor tiếp với chính Pk thì mới thu được kết quả.

from Crypto.Cipher import AES
import os
import requests
from Crypto.Util.number import long_to_bytes, bytes_to_long

def encrypt_flag():
    url = 'https://aes.cryptohack.org/symmetry/encrypt_flag/'
    ciphertext = requests.get(url)
    return ciphertext.json()['ciphertext']

def encrypt(plaintext, iv):
    url = url = f'https://aes.cryptohack.org/symmetry/encrypt/{plaintext}/{iv}/'
    ciphertext = requests.get(url)
    return ciphertext.json()['ciphertext']

def xor(text1, text2):
    return bytes(a ^ b for a, b in zip(text1, text2))

# flag = 2 block 16 + 1 block 1

flag_ciphertext = encrypt_flag()
iv = flag_ciphertext[:32]  
ciphertext = flag_ciphertext[32:]

known_plaintext = '00' * (len(ciphertext) // 2)
known_ciphertext = bytes.fromhex(encrypt(known_plaintext, iv))

ciphertext = bytes.fromhex(ciphertext)
plaintext = xor(ciphertext, known_ciphertext)
print(plaintext.decode())

# flag = crypto{0fb_15_5ymm37r1c4l_!!!11!}

## Bean Counter

> I've struggled to get PyCrypto's counter mode doing what I want, so I've turned ECB mode into CTR myself. My counter can go both upwards and downwards to throw off cryptanalysts! There's no chance they'll be able to read my picture.


Source

from Crypto.Cipher import AES


KEY = ?


class StepUpCounter(object):
    def __init__(self, step_up=False):
        self.value = os.urandom(16).hex()
        self.step = 1
        self.stup = step_up

    def increment(self):
        if self.stup:
            self.newIV = hex(int(self.value, 16) + self.step)
        else:
            self.newIV = hex(int(self.value, 16) - self.stup)
        self.value = self.newIV[2:len(self.newIV)]
        return bytes.fromhex(self.value.zfill(32))

    def __repr__(self):
        self.increment()
        return self.value



@chal.route('/bean_counter/encrypt/')
def encrypt():
    cipher = AES.new(KEY, AES.MODE_ECB)
    ctr = StepUpCounter()

    out = []
    with open("challenge_files/bean_flag.png", 'rb') as f:
        block = f.read(16)
        while block:
            keystream = cipher.encrypt(ctr.increment())
            xored = [a^b for a, b in zip(block, keystream)]
            out.append(bytes(xored).hex())
            block = f.read(16)

    return {"encrypted": ''.join(out)}

* Đại loại là thay vì encrypt một giá trị iv cố định, thì với mode này ta sẽ encrypt những giá trị thay đổi
* Nhưng ở hàm **increment** trong class **StepUpCounter**, ở phần else (if False), giá trị của newIV là hex(int(self.value, 16) - self.stup), nhưng self.stup không đổi (luôn là False) và bằng 0, nên coi như newIV sẽ luôn giữ giá trị cố định.
* 32 hex (16 bytes) đầu của một file png (signature bytes) luôn là '89504E470D0A1A0A0000000D49484452'.
* Ta sẽ xor signature bytes với 16 bytes đầu của ciphertext để thu được newIV, sau đó ta sẽ mở rộng độ dài newIV bằng độ dài ciphertext, và xor với ciphertext

Code

import requests
import os
import webbrowser

def encrypt():
    url = 'https://aes.cryptohack.org/bean_counter/encrypt/'
    response = requests.get(url)
    return bytes.fromhex(response.json()['encrypted'])

def xor(text1, text2):
    return bytes(a^b for a,b in zip(text1, text2))

ciphertext = encrypt()
image_header = bytes.fromhex('89504E470D0A1A0A0000000D49484452')
first_16_byte = ciphertext[:16]
encrypted_iv = xor(image_header, first_16_byte)
repeat_count = len(ciphertext) // 16 + 1  # +1 để đảm bảo đủ dài
encrypted_iv = (encrypted_iv * repeat_count)[:len(ciphertext)]
decrypted_data = xor(encrypted_iv, ciphertext)
print(decrypted_data[:50])

with open("decrypted.png", "wb") as f:
    f.write(decrypted_data)

os.system("decrypted.png")

# flag = crypto{hex_bytes_beans}

## Oh SNAP
Description
> Here's the start of my fast network authentication protocol, so far I've only implemented the "Ping" command so there shouldn't be any way to recover the key.

Source

from Crypto.Cipher import ARC4


FLAG = ?


@chal.route('/oh_snap/send_cmd/<ciphertext>/<nonce>/')
def send_cmd(ciphertext, nonce):
    if not ciphertext:
        return {"error": "You must specify a ciphertext"}
    if not nonce:
        return {"error": "You must specify a nonce"}

    ciphertext = bytes.fromhex(ciphertext)
    nonce = bytes.fromhex(nonce)

    cipher = ARC4.new(nonce + FLAG.encode())
    cmd = cipher.decrypt(ciphertext)
    if cmd == b"ping":
        return {"msg": "Pong!"}
    else:
        return {"error": f"Unknown command: {cmd.hex()}"}

* RC4 Cipher: Tạo ra keystream từ key và S_box, gồm có 2 bước
**Key-scheduling algorithm (KSA) và Pseudo-random generation algorithm (PRGA)**

def ksa(k: bytes, rounds: int = N) -> list[int]:
    S = list(range(N)) # identity permutation
    j = 0
    for i in range(rounds):
        j = (j + S[i] + k[i % len(k)]) % N
        S[i], S[j] = S[j], S[i] # swap

    return j, S

def prga(S: list[int]):
    i = j = 0
    while 1:
        i = (i + 1) % N
        j = (j + S[i]) % N
        S[i], S[j] = S[j], S[i]

        z = S[(S[i] + S[j]) % N]
        yield z
        
def decrypt(ct: bytes, key: bytes):
    _, S = ksa(key)
    stream = prga(S)
    return bytes(a ^ b for a, b in zip(ct, stream))

* **FMS Attack:**
Chúng ta sẽ đánh vào điểm yếu của RC4 về sự phân bổ không đồng đều của S_box. Cụ thể là khi chọn nonce trong key = nonce || secret yếu, có dạng (A + 3, n - 1, x), trong đó A là index của byte cần tìm của secret, n là 256 để j ít thay đổi, x là giá trị bất kì trong [0, 255]

Và ta sẽ khai thác từ công thức j(i+1) = j(i) + S[i] + K[i % len(K)], trong đó KS[i] là keystream tại index i, K[i] là key = nonce || secret tại vị trí i

**=> K[i] = j(i+1) - j(i) - S[i]**

Giả sử nonce = [3, 255, 1]
khi đó key = [3, 255, 1, x,...]

S_box = [0, 1, 2, 3,..., 255]

- i = 0, j = 0 + 0 + 3
S_box = [3, 1, 2, 0,.., 255]

- i = 1, j = (1 + 255 + 3) % 256 = 3
S_box = [3, 0, 2, 1,..., 255]

- i = 2, j = 1 + 3 + 2 = 6
S_box = [3, 0, 6, 1, 4, 5, 2, 7,..., 255]

- i = 3, j = x + 1 + 6 = x', S[x'] = x'
S_box = [3, 0, 6, x', 4, 5, 2, 7,..., 1,..., 255]

Khi đi qua **prga**, ta sẽ thu được KS[0] = S[S[0] + S[1]] = S[3] = x' (đây chính là j(i+1))

**=> K[i] = KS[0] - j(i) - S[i]**

Mà keystream = ciphertext ^ plaintext, nên ý tưởng sẽ là khôi phục lại key từ keystream và các chỉ số, và trạng thái của S_box

* Tại sao lại làm theo cách này được ?
Đây cũng chính là điểm yếu của RC4, tỉ lệ S[0], S[1] và S[3] vẫn ở nguyên index sau 252 vòng lặp nữa sẽ là 5%
* j di chuyển ngẫu nhiên nên xác suất để vào 1 thằng trong 3 S[0], S[1], S[3] là 1/256

Trong bài cho phép chúng ta gửi giá trị nonce và ciphertext bất kì. Ta sẽ chọn ciphertext = b'\x00' là 00 trong hex để xor với plaintext sẽ ra keystream[0].

Với mỗi byte của flag, ta sẽ cho x chạy từ 0 - 255, byte nào có tần suất xuất hiện nhiều nhất sẽ là byte của flag (thử nhập nonce có độ dài 222 thì server vẫn trả về kết quả, nhưng 223 thì server báo lỗi, có thể độ dài của flag sẽ là 256 - 222 = 34)

Code:

import requests
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Cipher import ARC4
from collections import Counter

def send_cmd(ciphertext, nonce):
    url = 'https://aes.cryptohack.org/oh_snap/send_cmd/' + ciphertext + '/' + nonce
    response = requests.get(url)
    return response.json()['error'][17:]

def xor(byteA, byteB):
    return long_to_bytes(bytes_to_long(byteA) ^ bytes_to_long(byteB))

def simulate_S_box(key, A):
    key = [int(key.hex()[i * 2: i * 2 + 2], 16) for i in range(len(key))] # Convert nonce into list
    S = [i for i in range(256)]
    j = 0
    for i in range(A + 3):
        j = (j + S[i % 256] + key[i % len(key)]) % 256
        S[i], S[j] = S[j], S[i]
    i = A + 2
    return S[i+1], j # Return S[i] and j of last KSA round

ciphertext = b'\x00'.hex()
length_key = 34
nonce = bytes([3, 255, 1])
plaintext = send_cmd(ciphertext, nonce.hex())
keystream = xor(bytes.fromhex(plaintext), bytes.fromhex(ciphertext))
known = b'crypto{'

for A in range(7, length_key):
    possible_key = [] # Store all possible value of key, pick the most frequent item
    for v in range(256):
        nonce = bytes([A + 3, 255, v])
        key = nonce + known
        plaintext = send_cmd(ciphertext, nonce.hex())
        keystream = xor(bytes.fromhex(plaintext), bytes.fromhex(ciphertext))
        s_i, j = simulate_S_box(key, A)
        possible_key_fragment = (keystream[0] - s_i - j) % 256
        print(v, chr(possible_key_fragment))
        possible_key.append(possible_key_fragment)
    counter = Counter(possible_key)
    key_fragment = chr(counter.most_common(1)[0][0])
    known += key_fragment.encode()
    print(key_fragment, known)


# flag = crypto{w1R3d_equ1v4l3nt_pr1v4cy?!}

## Pad Thai
> Sometimes the classic challenges can be the most delicious
>
> Connect at socket.cryptohack.org 13421
>
> Challenge files:
> - 13421.py
>

13221.py

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from os import urandom

from utils import listener

FLAG = 'crypto{?????????????????????????????????????????????????????}'

class Challenge:
    def __init__(self):
        self.before_input = "Let's practice padding oracle attacks! Recover my message and I'll send you a flag.\n"
        self.message = urandom(16).hex()
        self.key = urandom(16)

    def get_ct(self):
        iv = urandom(16)
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        ct = cipher.encrypt(self.message.encode("ascii"))
        return {"ct": (iv+ct).hex()}

    def check_padding(self, ct):
        ct = bytes.fromhex(ct)
        iv, ct = ct[:16], ct[16:]
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        pt = cipher.decrypt(ct)  # does not remove padding
        try:
            unpad(pt, 16)
        except ValueError:
            good = False
        else:
            good = True
        return {"result": good}

    def check_message(self, message):
        if message != self.message:
            self.exit = True
            return {"error": "incorrect message"}
        return {"flag": FLAG}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, msg):
        if "option" not in msg or msg["option"] not in ("encrypt", "unpad", "check"):
            return {"error": "Option must be one of: encrypt, unpad, check"}

        if msg["option"] == "encrypt": return self.get_ct()
        elif msg["option"] == "unpad": return self.check_padding(msg["ct"])
        elif msg["option"] == "check": return self.check_message(msg["message"])

import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13421)

* Nói qua một chút về đoạn code của đề bài, mỗi lần khởi động challenge sẽ sinh ra đoạn message 32 hex, sau đó message đó sẽ được chuyển thành 32 byte và được mã hóa, nhiệm vụ của ta sẽ phải khôi phục đoạn message đó
* Hàm **unpad(message, byte)** sẽ loại bỏ đi các pad dư thừa ở các khối plaintext. Ta có thể lợi dụng hàm này để khôi phục lại đoạn message


CBC mode operation


* Ta có thể tự do điều chỉnh iv và ciphertext (input) ta sẽ chọn iv sao cho P1[15] = b'\x01' để unpad valid

* Và khi đó ta sẽ khôi phục lại d(C1)[15] (trong đó d(C1) là ciphertext sau khi đi qua hàm decrypt), làm lần lượt với các kí tự còn lại. Sau khi thu được d(C1) hoàn chỉnh thì ta cho xor với iv ban đầu để ra P1. Sau đó làm tương tự với C2, chỉ khác bước cuối thay vì xor với iv thì ta sẽ cho xor với C1.

Code:

    from pwn import *
    import json

    def oracle(iv, ct):
        ct = (iv + ct).hex()
        conn.sendline(json.dumps({"option": "unpad", "ct": ct}).encode())
        res = json.loads(conn.recvline().decode())
        print(len(iv), iv, res)
        return res['result']

    def attack_block(iv, ciphertext):
        known_dct = b''
        for i in range(16): # For each character in a block
            padding = (i+1).to_bytes(1, 'big') * (i+1)
            for guess in range(256): 
                known_fake = xor(bytes([guess]) + known_dct, padding)
                fake_iv = bytes(15 - i) + known_fake
                if oracle(fake_iv, ciphertext):
                    known_dct = bytes([guess]) + known_dct
                    print("FOUND", known_dct)
                    break
        return xor(iv, known_dct)

    def attack(iv, c1, c2):
        p = attack_block(iv, c1)
        p += attack_block(c1, c2)
        return p

    conn = remote('socket.cryptohack.org', 13421)
    print(conn.recvline().decode())

    # Take ciphertext
    payload1 = {"option": "encrypt"}
    conn.sendline(json.dumps(payload1).encode())
    line = conn.recvline(timeout=5)
    data = json.loads(line.decode())['ct']
    data = bytes.fromhex(data)
    iv = data[:16]
    ct = data[16:]
    c1 = ct[:16]
    c2 = ct[-16:]

    plaintext = attack(iv, c1, c2)
    conn.sendline(json.dumps({"option":"check", "message": plaintext.decode()}).encode())
    print(conn.recvline())

## The good, the pad, the ugly

> The first twist of the classic challenge, how can you handle an oracle with errors?
>
> Connect at socket.cryptohack.org 13422
>
> Challenge files:
> - 13422.py

13422.py

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from os import urandom
from random import SystemRandom

from utils import listener

FLAG = 'crypto{??????????????????????????????????????????}'
rng = SystemRandom()


class Challenge:
    def __init__(self):
        self.before_input = "That last challenge was pretty easy, but I'm positive that this one will be harder!\n"
        self.message = urandom(16).hex()
        self.key = urandom(16)
        self.query_count = 0
        self.max_queries = 12_000

    def update_query_count(self):
        self.query_count += 1
        if self.query_count >= self.max_queries:
            self.exit = True

    def get_ct(self):
        iv = urandom(16)
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        ct = cipher.encrypt(self.message.encode("ascii"))
        return {"ct": (iv+ct).hex()}

    def check_padding(self, ct):
        ct = bytes.fromhex(ct)
        iv, ct = ct[:16], ct[16:]
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        pt = cipher.decrypt(ct)  # does not remove padding
        try:
            unpad(pt, 16)
        except ValueError:
            good = False
        else:
            good = True
        self.update_query_count()
        return {"result": good | (rng.random() > 0.4)}

    def check_message(self, message):
        if message != self.message:
            self.exit = True
            return {"error": "incorrect message"}
        return {"flag": FLAG}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, msg):
        if "option" not in msg or msg["option"] not in ("encrypt", "unpad", "check"):
            return {"error": "Option must be one of: encrypt, unpad, check"}

        if msg["option"] == "encrypt": return self.get_ct()
        elif msg["option"] == "unpad": return self.check_padding(msg["ct"])
        elif msg["option"] == "check": return self.check_message(msg["message"])


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13422)

Đây là một bài toán về tấn công thống kê

* Bài này giống Pad Thai, có điều khi ta nhìn vào hàm **check_padding()** thì kết quả trả về là return {"result": good l (rng.random() > 0.4)} (And operation)
Tỉ lệ trả về True của rng là 0,6 trong khi False là 0,4

* Nếu kết quả trả về False, thì chắn chắn sai (False | False)
* Còn nếu kết quả True thì sẽ có các khả năng (True | False), (True | True) là các trường hợp đúng và (False | True) là trường hợp dương tính giả, khi kết quả trả về True thì ta phải check xem có đúng không bằng cách thử lại nhiều lần, nhưng bao nhiêu là đủ ?

* Xác suất sai khi rng trả về True là P = $0,6^n$
Max ping đề cho chạy 12000 queries, mà có 32 byte => Tối đa mỗi byte có thể chạy 120000 / 32 = 375 queries, hãy nhìn vào message, nó ở dưới dạng hex (0123...f), tức ta chỉ cần thử 16 giá trị => Max ping ta có thể thử để trả về 375 / 16 = 23 lần True để chắc chắn rằng đó là byte đúng, và xác suất sai sẽ là $0,6^{23}$ = 7.89730223053602e-06 rất rất nhỏ

Code:

from pwn import *
import json
from Crypto.Util.strxor import strxor

def oracle(prev, ct):
    ct = (prev + ct).hex()
    conn.sendline(json.dumps({"option": "unpad", "ct": ct}).encode())
    res = json.loads(conn.recvline().decode())
    print(len(prev), prev, res)
    return res['result']

def check(prev, ct):
    for i in range(23):
        if not oracle(prev, ct):
            return False
    return True

def attack_block(prev, ciphertext):
    possible_guess = b'0123456789abcdef'
    known_dct = bytearray(16)
    plaintext = bytearray(16)
    for i in range(15, -1, -1):
        pad_val = 16 - i
        for char in possible_guess:
            guess = char ^ pad_val ^ prev[i]
            prefix = bytes(i)
            middle = bytes([guess])
            suffix = bytes([known_dct[j] ^ pad_val for j in range(i + 1, 16)])
            fake_prev = prefix + middle + suffix
            if check(fake_prev, ciphertext):
                known_dct[i] = guess ^ pad_val
                plaintext[i] = known_dct[i] ^ prev[i]
                print("FOUND", known_dct)
                break
    return bytes(plaintext)

def attack(iv, c1, c2):
    p = attack_block(iv, c1)
    p += attack_block(c1, c2)
    return p

conn = remote('socket.cryptohack.org', 13422)
print(conn.recvline().decode())

# Take ciphertext
payload1 = {"option": "encrypt"}
conn.sendline(json.dumps(payload1).encode())
line = conn.recvline(timeout=5)
data = json.loads(line.decode())['ct']
data = bytes.fromhex(data)
iv = data[:16]
ct = data[16:]
c1 = ct[:16]
c2 = ct[-16:]

plaintext = attack(iv, c1, c2)
conn.sendline(json.dumps({"option":"check", "message": plaintext.decode()}).encode())
print(conn.recvline())



iv(f) là prev_fake
iv(r) là prev
p là char

# Mathematics
## Successive Powers
* Dãy trên là dãy của c0 = $x^a$ mod p, c1 = $x^{a+1}$ mod p,...
* Biến đổi thì ta thấy c1 = $x^a$ * x mod p = c0 * x mod p <=> x = ${c0}^{-1}$ * c1 mod p
* Tương tự x = ${c1}^{-1}$ * c2 mod p. Ta có thể tính x dựa vào c0, c1 rồi kiểm tra xem x có bằng biểu thức trên hay không (c1, c2). Đề cũng cho p là số có 3 chữ số nên ta brute force các số từ 100-999

Code:

from Crypto.Util.number import inverse

x_mod = [588,665,216,113,642,4,836,114,851,492,819,237]

for p in range(100, 1000):
    try:
        x1 = x_mod[1] * inverse(x_mod[0], p) % p
        x2 = x_mod[3] * inverse(x_mod[2], p) % p
        if x1 == x2:
            print(p, x1)
    except ValueError as e:
        pass

## Broken RSA
> I tried to send you an important message with RSA, however I messed up my RSA implementation really badly. Can you still recover the flag?
>
> If you think you're doing the right thing but getting garbage, be sure to check all possible solutions.

# Lattices
## Find the lattice
> As we've seen, lattices contain hard problems which can form trapdoor functions for cryptosystems. We also find that in cryptanalysis, lattices can break cryptographic protocols which seem at first to be unrelated to lattices.
>
> This challenge uses modular arithmetic to encrypt the flag, but hidden within the protocol is a two-dimensional lattice. We highly recommend spending time with this challenge and finding how you can break it with a lattice. This is a famous example with plenty of resources available, but knowing how to spot the lattice within a system is often the key to breaking it.
>
> As a hint, you will be able to break this challenge using the Gaussian reduction from the previous challenge.
>
> Challenge files:
> - source.py
> - output.txt

source

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'crypto{?????????????????????}'


def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')

* Đề gợi ý ta sử dụng Gaussian Reduction ở bài trước, vậy đầu tiên ta sẽ xây dựng lattice với ma trận 2x2

* Ta có h = $f^{-1}$ * g mod q
<=> hf = g mod q
<=> hf = g + kq (k thuộc Z)
<=> f(h, 1) = (g, f) + k(q, 0)
<=> (g, f) = k(q, 0) - f(h, 1)
* Từ đó ta đã tạo được một ma trận cơ sở gồm 2 vector là u = (q, 0) và v = (h, 1). Lí do khá đơn giản, thứ nhất vì đề bài đã cho hai số q, h và thứ hai, việc bây giờ của ta là tìm g và f. Tìm 2 số này thông qua thuật toán Gaussian Reduction, sẽ tạo ra 2 vector cơ sở mới ngắn nhất, và (gần) trực giao (vuông góc).
* Điều này xảy ra vì vector (f, g) sẽ có độ dài ngắn nhất và xấp xỉ $\sqrt{p}$ nhờ vào điều kiện ban đầu, và ngắn hơn so với các vector khác.

Code:

sage:
Public_key = (7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257, 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800)
Encrypted_Flag = 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523
q, h = Public_key
q = vector((q, 0))
h = vector((h, 1))

def Gauss(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1 * v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m * v1

v1, v2 = Gauss(q, h)

from Crypto.Util.number import inverse, long_to_bytes

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m

print(long_to_bytes(decrypt(q, h, v1[1], v2[0], Encrypted_Flag)))
flag: crypto{Gauss_lattice_attack!}

## Backpack Cryptography
> I love this cryptosystem so much, I carry it everywhere in my backpack. To lighten the load, I make sure I don't pack anything with high densities.
>
> Challenge files:
> - source.py
> - output.txt

source.py

import random
from collections import namedtuple
import gmpy2
from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes

FLAG = b'crypto{??????????????????????????}'
PrivateKey = namedtuple("PrivateKey", ['b', 'r', 'q'])

def gen_private_key(size):
    s = 10000
    b = []
    for _ in range(size):
        ai = random.randint(s + 1, 2 * s)
        assert ai > sum(b)
        b.append(ai)
        s += ai
    while True:
        q = random.randint(2 * s, 32 * s)
        if isPrime(q):
            break
    r = random.randint(s, q)
    assert q > sum(b)
    assert gmpy2.gcd(q,r) == 1
    return PrivateKey(b, r, q)


def gen_public_key(private_key: PrivateKey):
    a = []
    for x in private_key.b:
        a.append((private_key.r * x) % private_key.q)
    return a


def encrypt(msg, public_key):
    assert len(msg) * 8 <= len(public_key)
    ct = 0
    msg = bytes_to_long(msg)
    for bi in public_key:
        ct += (msg & 1) * bi
        msg >>= 1
    return ct


def decrypt(ct, private_key: PrivateKey):
    ct = inverse(private_key.r, private_key.q) * ct % private_key.q
    msg = 0
    for i in range(len(private_key.b) - 1, -1, -1):
         if ct >= private_key.b[i]:
             msg |= 1 << i
             ct -= private_key.b[i]
    return long_to_bytes(msg)


private_key = gen_private_key(len(FLAG) * 8)
public_key = gen_public_key(private_key)
encrypted = encrypt(FLAG, public_key)
decrypted = decrypt(encrypted, private_key)
assert decrypted == FLAG

print(f'Public key: {public_key}')
print(f'Encrypted Flag: {encrypted}')

Đoạn code trên là cài đặt đơn giản của hệ mã Merkle-Hellman Knapsack (superincreasing knapsack cryptosystem)

* Đề cho public key và encrypted flag, và dựa vào đoạn code trong block encrypt

ct = 0
msg = bytes_to_long(msg)
for bi in public_key:
    ct += (msg & 1) * bi
    msg >>= 1

tức là chuyển msg sang hệ byte/binary, nếu vị trí nào bằng 1 thì ct sẽ cộng public key tương ứng ở vị trí đó
* Ví dụ: pub_key = [1, 5, 16, 70, 200] và msg = 10001
thì ct = 1 * 1 + 0 * 5 + 0 * 16 + 0 * 70 + 1 * 200 = 201
* Từ đây thì ta có thể hình dung bài toán là cho một tập hợp {a1, a2,...,an} (public key), tìm hệ số (0/1) các số đó sao cho tổng bằng S (flag)


* Bước đầu ta sẽ dựng lattice sao cho thỏa mãn yêu cầu trên
\begin{bmatrix}
{\bf I} & {\bf a}\\
{\bf 0} & -S
\end{bmatrix}hay
\begin{bmatrix}
b_1:=&(1 & 0 & \ldots & 0 & a_1)\\
b_2:=&(0 & 1 & \ldots & 0 & a_2)\\
& & \ldots &\\
b_n:=&(0 & 0 & \ldots & 1 & a_n)\\
b_{n+1}:=&(0 & 0 & \ldots & 0 & -S)
\end{bmatrix}
khi đó lattice của ta là `L {m1 * b1 + m2 * b2 + ... + mn * bn}` với $mi \in \{0,1\}$ và ai là giá trị các phần tử trong public key, khi đó vector u cần tìm sẽ chỉ chứa toàn 0, và 1 kết thúc bằng số 0 (cộng tất cả các vector lại với nhau). Nhưng điều này không đảm bảo u sẽ là vecto nhỏ nhất, có hai lí do, một là nếu các giá trị a1, a2 gần sát nhau và hiệu của a1, a2 nhỏ thì sau khi thực hiện thuật toán LLL thì có thể bốc ra vector không mong muốn

* Cải tiến 1:
\begin{bmatrix}
{\bf I} & N{\bf a}\\
{\bf 0} & -NS
\end{bmatrix}hay
\begin{bmatrix}
1 & 0 & \ldots & 0 & Na_1\\
0 & 1 & \ldots & 0 & Na_2\\
& & \ldots &\\
0 & 0 & \ldots & 1 & Na_n\\
0 & 0 & \ldots & 0 & -NS
\end{bmatrix}
* Giờ ta scale các giá trị ai bằng cách nhân thêm N ($N \ge n)$, vấn đề liên quan đến ai, hay hiệu của chúng nhỏ không còn là vấn đề. Nhưng lại có một vấn đề hơi bựa
* Ví dụ vector cần tìm x = [1,1,0,1,1,0] và vector bất kì u = [2,0,0,1,0,0]. Hai vector có độ dài bằng nhau, và thuật toán LLL có thể chọn nhầm vector u

* Giải pháp

\begin{bmatrix}
{\bf I} & N{\bf a}\\
{\bf 1/2} & NS
\end{bmatrix}hay
\begin{bmatrix}
1 & 0 & \ldots & 0 & Na_1\\
0 & 1 & \ldots & 0 & Na_2\\
& & \ldots &\\
0 & 0 & \ldots & 1 & Na_n\\
1/2 & 1/2 & \ldots & 1/2 & NS
\end{bmatrix}

* Khi này vector x có dạng x = (x1 - 1/2, x2 - 1/2,..., xn - 1/2) với $xi \in \{0,1\}$, độ dài x khi đó đúng bằng $\sqrt(n)/2$, đảm bảo là vector nhỏ nhất. Vì các vector khác một là có thành phần cuối khác 0, hoặc sẽ có một thành phần nào đó trị tuyệt đối > 1/2 kiểu như thế này.


Code:

sage:
import math

I = identity_matrix(QQ, 272)
I = I.stack(matrix(QQ, 1, 272, [QQ(1)/2 for _ in range(272)]))  # thêm hàng


N = math.ceil(272 ** 1.5)
L = [[N * x] for x in Public_key]
L.append([N * Encrypted_Flag])
L = matrix(L)
I = I.augment(L)
res = I.LLL()
shit = []
for i in res:
    if len(set(i[:-1])) == 2:
        F = i
print(F)

python
F = (-1/2, 1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, 1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, -1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, 1/2, -1/2, -1/2, -1/2, 1/2, 1/2, 1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, -1/2, 1/2, 1/2, -1/2, 1/2, 1/2, -1/2, -1/2, -1/2, 1/2, -1/2, -1/2, 1/2, 1/2, 1/2, -1/2, -1/2, 1/2, 0)

from Crypto.Util.number import long_to_bytes
F_shit = ''
for i in F:
    if i == -1/2:
        F_shit += '1'
    elif i == 1/2:
        F_shit += '0'
Flag = long_to_bytes(int(F_shit[::-1], 2))
print(Flag)
Flag: crypto{my_kn4ps4ck_1s_l1ghtw31ght}

## Everything is still big (Lattice solution)
Code:

Sage:
import math

N = '0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b'
e = '0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f'
c = '0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5'
N = int(N, 16)
e = int(e, 16)
c = int(c, 16)

x = math.isqrt(N)
u = vector([e, x])
v = vector([N, 0])
M = matrix([u, v])
L = M.LLL()
m, n = L
print(m[1]//x)

python:
from Crypto.Util.number import long_to_bytes

N = '0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b'
e = '0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f'
c = '0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5'
N = int(N, 16)
e = int(e, 16)
c = int(c, 16)

d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007
print(long_to_bytes(pow(c, d, N)))
FLAG: crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}