> Chan de
## Source and Output
Source:

#!/usr/bin/env sage
# Problem by rec, with nothing.

# type: ignore

import os
import secret
import hashlib
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad

LEN = 32

def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))]) 
def challenge(m: bytes, pbits: int, level: int=0):
    p = getPrime(pbits)
    M = random_matrix(GF(p), LEN).matrix_from_rows_and_columns(range(LEN), range(LEN-level))
    c = vector(GF(p), m) * M
    return {"p": p, "M": M.list(), "c": c.list()}

args = {
    "chall1": {
        "m": os.urandom(LEN),
        "pbits": 512,
        "level": 0x00
    },
    "chall2": {
        "m": os.urandom(LEN),
        "pbits": 10,
        "level": 0x01
    },
    "chall3": {
        "m": os.urandom(LEN),
        "pbits": 256,
        "level": 0x10
    }
}

out = dict()
enc = pad(secret.flag, LEN)
for i in range(3):
    out[f"chall{i+1}"] = challenge(**args[f"chall{i+1}"])
    enc = xor(enc, hashlib.sha512(args[f"chall{i+1}"]["m"]).digest())
out["enc"] = enc.hex()
with open('output.txt', 'w') as f:
    f.write(f"{out = }")

Output ([sieu dai nen tai ve o day nhe!!!](https://actvneduvn-my.sharepoint.com/:t:/g/personal/at210413_actvn_edu_vn/EQKTvDiIUbVDtIdQjFuDI9oBGo0FVDvuEh1MuErOIVq6gg?e=hjTMq7))
## Analysing
Chall của anh Minh thì luôn là một file nhưng nhiều chall nhiều tầng :penguin:, và bài này thì không ngoại lệ. Dù là 3 chall nhưng về cách triển khai là giống nhau, chỉ khác về thông số cũng như là độ khó cũng sẽ tăng dần. Vì thế mình sẽ đi phân tích cách triển khai mã hóa trước khi đi chi tiết vào độ khó của từng chall.
Đầu tiên là hàm `xor`:

def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])

Hàm xor này khác thông thường ở chỗ nó được dùng để xor hai chuỗi byte có thể có độ dài khác nhau. Nếu hai chuỗi có độ dài khác nhau, hàm lặp lại chuỗi ngắn hơn để khớp với độ dài của chuỗi dài hơn.
Hàm `challenge`:

def challenge(m: bytes, pbits: int, level: int=0):
    p = getPrime(pbits)
    M = random_matrix(GF(p), LEN).matrix_from_rows_and_columns(range(LEN), range(LEN-level))
    c = vector(GF(p), m) * M

    return {"p": p, "M": M.list(), "c": c.list()}

Hàm sử dụng các tham số `m`, `p` (số nguyên tố được tạo ngẫu nhiên với độ dài `pbits`), và `level` (cái này dùng để điều chỉnh kích thước của ma trận, cũng như quyết định độ khó của từng chall).
`p` được chọn ngẫu nhiên theo độ dài được định ở từng chal. Matrix `M` cũng được tạo random với kích thước hàng cột là `LEN = 32`, các phần tử thuộc $GF(p)$. Tuy nhiên, như đề cập ở trên, sử dụng thêm `level` để điều chỉnh kích thước của ma trận. Số cột sẽ luôn là 32, tuy nhiên thì số hàng sẽ được điều chỉnh theo tham số `level` với `matrix_from_rows_and_columns(range(LEN), range(LEN-level))` hay tổng quát hơn thì kích thước cuối của Matrix `M` sẽ là 32 hàng và (32 - `level`) cột, cũng chính là 32 - `level` cột đầu tiên. Vector `c` là kết quả của việc chuyển bản rõ `m` thành vector trong trường $GF(p)$ rồi nhân với matrix `M`. Vector này sẽ gồm `32 - level phần tử`.
Hàm trả về các giá trị `p`, ma trận `M` và vector `c`.
Chi tiết các thông số ở 3 chall (các bản rõ luôn có độ dài là 32):

args = {
    "chall1": {
        "m": os.urandom(LEN),
        "pbits": 512,
        "level": 0x00 #=0 => ma trận có kích thước 32x32
    },
    "chall2": {
        "m": os.urandom(LEN),
        "pbits": 10,
        "level": 0x01 #=1 ma trận có kích thước 32x31
    },
    "chall3": {
        "m": os.urandom(LEN),
        "pbits": 256,
        "level": 0x10 #=16 => ma trận có kích thước 32x16
    }
}

Mã hóa:

enc = pad(secret.flag, LEN)
for i in range(3):
    out[f"chall{i+1}"] = challenge(**args[f"chall{i+1}"])
    enc = xor(enc, hashlib.sha512(args[f"chall{i+1}"]["m"]).digest())
out["enc"] = enc.hex()

Flag được pad sao cho đủ độ dài 32. Qua mỗi challenge thì m được mã hóa từng lượt thông qua hàm `challenge` với các thông số lần lượt từ `chall1`, `chall2` và `chall3`. Giá trị `enc` được cập nhật bằng cách xor giá trị thu được trước đó với giá trị mới có được từ mỗi hàm challenge đã qua hàm băm. `flag` đi qua từng lớp mã hóa có thể viết như sau:
\begin{gather}
enc = xor(xor(xor(pad(secret.flag, 32),SHA512(m1)),SHA512(m2)),SHA512(m3))
\end{gather}Trong đó, các giá trị $m1, m2, m3$ chính là các giá trị `m` ở các chall. Nhiệm vụ của ta là cần tìm các giá trị `m` này để khôi phục lại được flag.
## Exploiting
### chall1:
Thông số ở đây là dễ xử lí nhất:

"chall1": {
        "m": os.urandom(LEN),
        "pbits": 512,
        "level": 0x00 #=0 => ma trận có kích thước 32x32

Dễ là bởi nó là level 0, ma trận không bị cắt bớt cột, tức là ta có được toàn bộ ma trận A 32x32. Rõ ràng ta sẽ có theo như hàm `challenge` thì $m1 * M = c$, với m1 là một vector có 32 phần tử, M là ma trận 32x32 và cho ra c.

\begin{gather*}
\begin{bmatrix}
m_1 & m_2 &\dots &m_{32}
\end{bmatrix} \times
\begin{bmatrix}
M_{1,1} & M_{1,2} & \cdots & M_{1,32} \\
M_{2,1} & M_{2,2} & \cdots & M_{2,32} \\
\vdots & \vdots & \ddots & \vdots \\
M_{32,1} & M_{32,2} & \cdots & M_{32,32}
\end{bmatrix} =
\begin{bmatrix}
c_{1} & c_2 & \cdots & c_{32}
\end{bmatrix}
\end{gather*}
Rõ ràng thì ta có thể sử dụng ma trận nghịch đảo của M để tính được m1 : $m1 = c . M^{-1}$.

from sage.all import Matrix, GF, vector
LEN = 32
with open("output.txt", "r") as f:
    data = f.read()

exec(data) 

def solve(challenge_data):
    p = challenge_data["p"]
    M_list = challenge_data["M"]
    c_list = challenge_data["c"]
    M = Matrix(GF(p), LEN, LEN, M_list)
    c = vector(GF(p), c_list)
    try:
        M_inv = M.inverse()
        m = c * M_inv
        return bytes(int(x) for x in m)
    except:
        return None

m_recovered = solve(out["chall1"])
print(m_recovered)
#Recovered m1: b'Z\x12\xeb\xc3\xec\x13y\x8d`d\xab\x81<8\xbd\x1f\x9f\x98V\xff\x16\x84\xbd4r\xef\xe2\xb9--\xb9F'

### chall2:
Khi sang đến chall này, level từ 0 đã nâng lên 1. Kích thước của ma trận M đã giảm, cũng như là độ khó cũng đã tăng lên.

 "chall2": {
        "m": os.urandom(LEN),
        "pbits": 10,
        "level": 0x01 #=1 ma trận có kích thước 32x31
    },

Ở chall này, không chỉ có `level` thay đổi, chỉ số `pbits` cũng đã thay đổi theo. Với giá trị `level = 1`, số cột của ma trận M sẽ bị giảm xuống thành `LEN - 1 = 31` nhưng giữ nguyên số hàng là 32. Phép tính sẽ như sau:
\begin{gather*}
\begin{bmatrix}
m_1 & m_2 &\dots &m_{32}
\end{bmatrix} \times
\begin{bmatrix}
M_{1,1} & M_{1,2} & \cdots & M_{1,31} \\
M_{2,1} & M_{2,2} & \cdots & M_{2,31} \\
\vdots & \vdots & \ddots & \vdots \\
M_{32,1} & M_{32,2} & \cdots & M_{32,31}
\end{bmatrix} =
\begin{bmatrix}
c_{1} & c_2 & \cdots & c_{31}
\end{bmatrix}
\end{gather*}
Mình thử khai triển từng phần tử của vector theo hướng nhân ma trận:
\begin{gather}
c_i=\sum_{j=1}^{32}m_j.M_{j,i}
\end{gather}Có 31 phần tử trong vector c, tức ta có một hệ gồm 31 phương trình nhưng có đến 32 ẩn $m_j$ cần tìm. Khác với lần trước, chỉ cần lập ma trận nghịch đảo của ma trận $M$ là có thể tìm lại được vector m, nhưng lần này thì ma trận không vuông vì thế nên làm như ở `chall1` là không khả thi.
Tuy nhiên, nhận thấy rằng vì `m` là chuỗi bytes, nên các giá trị của các phần tử của m chỉ có thể dao động trong khoảng 0 đến 256. Cùng với đó, việc chỉ nhiều hơn 1 biến so với điều kiện bình thường để giải hệ phương trình thì mình nhận ra có thể bruteforce để tìm ra vector m.
Mình sẽ lấy giá trị đầu tiên `m1` thử bruteforce. Khi này thì với mỗi giá trị thử của `m1`, vector m sẽ thu gọn chỉ còn 31 giá trị cần tìm. Hàng ngang đầu của `M` cũng sẽ được gọt bỏ, tạo ra ma trận vuông 31x31 có thể nghịch đảo được, và từ đây có thể tìm được 31 giá trị tương ứng trong vector m, với yêu cầu là các tất cả các giá trị phần tử phải thuộc trong khoảng 0 đến 256. Thử thêm 1 lần nữa với các giá trị gốc `p`, `M` và `c`, nếu thỏa mãn thì với công nhận đó là 1 nghiệm hợp lệ.

from sage.all import *
LEN = 32

def verify_m2(m2: bytes, p2: int, M2_list: list, c2_list: list) -> bool:
    m2_vec = vector(GF(p2), [b for b in m2])
    M2 = matrix(GF(p2), LEN, LEN - 1, M2_list)  # LEN=32, LEN - level=31
    c2_calculated = m2_vec * M2
    c2_expected = vector(GF(p2), c2_list)
    return c2_calculated == c2_expected

p2 = 547
M2_list = [34, 380, 317, 35, 149, 164, 326, 503, 247, 19, 422, 302, 541, 192, 430, 1, 210, 438, 290, 104, 371, 451, 425, 337, 448, 452, 299, 170, 269, 370, 385, 389, 204, 184, 495, 246, 146, 398, 250, 309, 436, 65, 474, 104, 539, 120, 484, 337, 420, 380, 286, 440, 391, 367, 285, 57, 217, 73, 137, 285, 339, 72, 238, 219, 33, 3, 505, 378, 136, 467, 502, 126, 504, 50, 337, 252, 143, 351, 54, 64, 354, 517, 475, 533, 167, 289, 81, 71, 421, 288, 262, 437, 331, 368, 423, 189, 543, 426, 90, 167, 41, 326, 369, 206, 498, 459, 3, 112, 475, 483, 205, 418, 278, 359, 235, 99, 385, 25, 123, 457, 503, 72, 22, 147, 509, 434, 72, 363, 71, 211, 496, 373, 527, 415, 338, 127, 319, 41, 308, 335, 431, 431, 141, 380, 499, 277, 86, 263, 235, 135, 43, 420, 6, 110, 354, 495, 319, 76, 410, 322, 61, 183, 123, 324, 39, 164, 181, 142, 144, 290, 418, 233, 351, 292, 24, 211, 56, 332, 270, 263, 403, 403, 388, 491, 130, 489, 421, 284, 73, 456, 297, 20, 144, 542, 195, 392, 73, 218, 35, 206, 459, 221, 252, 434, 533, 44, 73, 361, 319, 186, 249, 459, 28, 315, 266, 443, 517, 501, 79, 104, 544, 451, 477, 281, 351, 20, 455, 543, 264, 173, 438, 426, 440, 320, 92, 297, 28, 280, 438, 204, 104, 126, 95, 147, 10, 76, 441, 20, 265, 79, 206, 267, 5, 236, 104, 312, 295, 512, 320, 461, 27, 425, 152, 295, 388, 84, 369, 190, 133, 188, 402, 519, 338, 7, 425, 324, 365, 211, 458, 441, 7, 123, 449, 535, 338, 273, 68, 362, 506, 206, 243, 380, 293, 480, 472, 445, 255, 67, 178, 136, 443, 169, 541, 509, 368, 356, 136, 90, 379, 67, 435, 312, 464, 474, 91, 148, 99, 538, 80, 210, 482, 9, 472, 200, 68, 461, 519, 74, 300, 533, 290, 66, 386, 350, 260, 429, 355, 75, 472, 418, 41, 450, 18, 6, 0, 459, 220, 518, 136, 281, 322, 475, 535, 213, 514, 459, 382, 353, 276, 121, 284, 155, 214, 448, 446, 182, 308, 319, 387, 205, 21, 204, 463, 504, 282, 336, 120, 213, 494, 447, 342, 216, 438, 100, 44, 244, 539, 82, 539, 420, 455, 59, 364, 500, 205, 67, 168, 155, 157, 502, 382, 409, 454, 281, 286, 273, 179, 143, 55, 194, 515, 231, 494, 16, 335, 188, 470, 301, 295, 85, 409, 156, 143, 308, 493, 267, 326, 240, 30, 479, 247, 178, 339, 397, 200, 352, 308, 74, 533, 127, 244, 501, 330, 135, 266, 330, 263, 494, 357, 496, 469, 388, 113, 453, 466, 6, 181, 449, 477, 466, 215, 56, 216, 101, 28, 288, 319, 33, 294, 390, 36, 156, 243, 283, 142, 485, 494, 316, 86, 388, 18, 117, 359, 498, 441, 199, 2, 485, 85, 21, 245, 360, 36, 222, 342, 450, 164, 501, 366, 303, 335, 438, 132, 404, 95, 285, 477, 41, 74, 293, 248, 46, 417, 20, 460, 7, 373, 82, 6, 279, 36, 369, 330, 2, 411, 393, 182, 277, 442, 215, 432, 231, 453, 524, 28, 418, 512, 438, 88, 369, 137, 430, 105, 219, 126, 398, 334, 75, 168, 363, 452, 434, 469, 357, 397, 133, 472, 337, 296, 61, 138, 126, 530, 477, 327, 527, 161, 486, 214, 240, 89, 502, 435, 253, 466, 158, 444, 91, 538, 429, 69, 371, 220, 480, 413, 17, 340, 351, 170, 224, 524, 188, 338, 421, 413, 467, 534, 246, 126, 198, 68, 522, 497, 465, 205, 255, 205, 426, 111, 410, 294, 184, 30, 318, 166, 542, 324, 530, 460, 302, 274, 310, 168, 484, 521, 301, 511, 199, 308, 315, 161, 354, 433, 342, 101, 279, 321, 92, 168, 46, 384, 40, 131, 508, 64, 124, 377, 39, 185, 133, 295, 188, 432, 242, 123, 505, 64, 314, 175, 489, 426, 324, 258, 359, 460, 482, 412, 380, 191, 274, 35, 328, 237, 454, 438, 530, 387, 36, 70, 257, 199, 179, 351, 19, 276, 182, 381, 300, 312, 255, 14, 145, 521, 321, 26, 496, 459, 292, 363, 517, 120, 189, 127, 211, 318, 482, 359, 212, 33, 325, 239, 320, 13, 465, 215, 506, 276, 69, 310, 456, 417, 156, 262, 507, 100, 373, 395, 291, 432, 202, 534, 465, 97, 90, 400, 255, 42, 397, 519, 36, 260, 56, 110, 307, 411, 40, 318, 184, 412, 81, 64, 457, 135, 300, 424, 19, 522, 296, 228, 491, 344, 58, 540, 519, 190, 54, 438, 448, 472, 503, 195, 522, 450, 38, 52, 7, 444, 390, 121, 185, 490, 533, 279, 344, 145, 346, 34, 431, 502, 319, 418, 152, 30, 408, 511, 56, 230, 496, 112, 131, 430, 278, 335, 406, 540, 317, 370, 68, 324, 389, 297, 131, 392, 361, 66, 39, 408, 240, 430, 224, 211, 396, 59, 409, 528, 309, 88, 3, 26, 336, 493, 0, 113, 464, 396, 246, 535, 20, 315, 392, 149, 513, 146, 237, 177, 384, 49, 138, 466, 117, 458, 99, 356, 44, 459, 75, 188, 49, 36, 243, 456, 198, 251, 207, 261, 362, 195, 323, 342, 77, 512, 458, 324, 319, 302, 312, 120, 272, 24, 512, 454, 123, 163, 8, 503, 94, 148, 223, 27, 438, 436, 232, 48, 172, 475, 185, 18, 371, 360, 404, 56, 250, 114, 413, 223, 519, 84, 220, 158, 418, 64, 308, 197, 2, 400, 489, 66, 139, 488, 386, 109, 466, 68, 373, 10, 129, 447, 28, 24, 181, 377, 6, 437, 311, 66, 263, 178, 27, 355, 19, 343, 49, 224, 336, 341, 385, 431, 330, 533, 58, 170, 464, 101, 410, 430, 361, 444, 160, 494, 263, 310, 164, 403, 470, 211, 524, 488, 434, 233, 381, 459, 387, 272, 62, 353, 202, 418, 172, 257, 253, 363, 87, 546, 545, 44, 258, 23, 426, 105, 431, 95, 289]
c2_list = [260, 252, 264, 289, 177, 159, 360, 47, 314, 457, 243, 281, 122, 193, 481, 46, 481, 375, 32, 415, 172, 522, 125, 140, 332, 311, 185, 147, 383, 203, 399]
M2 = matrix(GF(p2), LEN, LEN-1, M2_list)
c2 = vector(GF(p2), c2_list)
possible = []
found = False
for x in range(256):
    try:
        target = c2 - x * M2[0]
        M_sub = M2[1:LEN, 0:LEN-1]
        M_sub_inv = M_sub.inverse()
        m_rest = target * M_sub_inv
        valid = True
        m = [x]
        for val in m_rest:
            v = int(val)
            if v < 0 or v > 256:
                valid = False
                break
            m.append(v)
        if valid:
            m2 = bytes(m)
            if verify_m2(m2, p2, M2_list, c2_list) == True:
                print("Valid")
                possible.append(m2)
                print(m2)
                found = True
            continue
    except:
        continue
if not found:
    print("Failed")
#b'\x1a\x91QA\xdb\xe6\xd3:_\x9ai\x00\x7f\x99\xb7b\xc4\xd8\x1e\xadT\x97\xce\x1c\x8e\x9b\x05\x18\xcd\xfc\x98\xc1'

### chall3
Độ khó ở chall này đã được nhân lên nhiều lần:

"chall3": {
        "m": os.urandom(LEN),
        "pbits": 256,
        "level": 0x10

Level lần này đã được nâng lên 16, tức khi này ma trận `M` sẽ chỉ còn là 32x16. Cần hiểu rằng:

Ta muốn tìm m, nhưng hệ phương trình này có nhiều nghiệm vì M có 16 cột (< 32 hàng), tức là không đủ ràng buộc để xác định được nghiệm duy nhất. Vậy nên ta đi dựng lattice.
Tuy nhiên, được anh Minh cho con hàng cực vjp, nên xài thử nha ae :penguin::

tmp = out["chall3"]
p = tmp["p"]
M = matrix(LEN, LEN - 0x10, tmp["M"])
c = tmp["c"]

load('https://raw.githubusercontent.com/TheBlupper/linineq/main/linineq.py')
lb = [0] * LEN
ub = [256] * LEN

for cc in solve_bounded_mod_gen(M.T, c, lb, ub, p):
    m3 = cc
print(bytes(m3))
#b' \xb1\xd3\x98\x89\x97\xab\xfcL\xa4R\xf1&\x87\xe1\x1cX\xb2\x8d\xc5\x0bK\xf3\xc7\x9f\x1f\xb9\xf0F\nX\xac'

Hoặc một cách khác, với phương trình cẩn giải trong trường $GF(p)$, lập lattice như sau:

\begin{gather}
B =
\begin{bmatrix}
M & I \\
p.I & 0 \\
c & 0\\
\end{bmatrix}
\end{gather}

Cụ thể thì:
* Hàng đầu tiên, gồm M (32x16) và I (32x32). Các hàng này tạo ra không gian sinh bởi M và các cơ sở đơn vị, cho phép biểu diễn m trong tổ hợp tuyến tính.
* Hàng thứ 2 gồm p.I (16x16), 0 (16x32), các hàng này thêm các bội của p vào lattice, mô phỏng phép tính modulo p để giới hạn số nghiệm.
* Hàng thứ 3 là c,0; Đây là vector c=mM trong hệ phương trình.

Thực hiện LLL, ta thu được vector [c, -m] nằm trong lattice này. Code giải:

a = out["chall3"]
p = a["p"]
M = matrix(LEN, LEN - 0x10, a["M"])
c = a["c"]

M = matrix(ZZ, 32, 16, M)
c = matrix(ZZ, 1, 16, c)

A = block_matrix([
    [M, identity_matrix(32)],
    [p * identity_matrix(16), zero_matrix(16, 32)],
    [c, zero_matrix(1, 32)]
])

m = A.LLL()
m3 = bytes(map(abs, m[1][16:]))
print(m3)
#b'\x1a\x91QA\xdb\xe6\xd3:_\x9ai\x00\x7f\x99\xb7b\xc4\xd8\x1e\xadT\x97\xce\x1c\x8e\x9b\x05\x18\xcd\xfc\x98\xc1'

Đến đây đã có đủ các giá trị m. Đem đảo ngược lại quá trình xor ban đầu thoai:

from Crypto.Util.number import *
import hashlib
import tqdm
m1 = b'Z\x12\xeb\xc3\xec\x13y\x8d`d\xab\x81<8\xbd\x1f\x9f\x98V\xff\x16\x84\xbd4r\xef\xe2\xb9--\xb9F'
m2 = b'\x1a\x91QA\xdb\xe6\xd3:_\x9ai\x00\x7f\x99\xb7b\xc4\xd8\x1e\xadT\x97\xce\x1c\x8e\x9b\x05\x18\xcd\xfc\x98\xc1'
m3 = b' \xb1\xd3\x98\x89\x97\xab\xfcL\xa4R\xf1&\x87\xe1\x1cX\xb2\x8d\xc5\x0bK\xf3\xc7\x9f\x1f\xb9\xf0F\nX\xac'
enc = bytes.fromhex('dd8516e6df32ee2452eaea890b199aeea4809244e11c49f62e1bf5aeafa7038f2cb365b626aa15b4f7d10976e3499b5158ab30d790a13aefae3791814bea368a')

cs = [
    hashlib.sha512(m1).digest(),
    hashlib.sha512(m2).digest(),
    hashlib.sha512(m3).digest()
]
flag = bytes([cs[0][i] ^ cs[1][i] ^ cs[2][i] ^ enc[i] for i in tqdm.tqdm(range(len(enc)))])
print(flag)
#b'flag{toi_la_lolicon_thi_sao_?}\x02\x02flag{toi_la_lolicon_thi_sao_?}\x02\x02'