Vì sao mình không giải ra LoveLinhaLot Revenge

Bài post này sẽ dành để nói về một bài crypto trong kì thi chung khảo jeopardy sinh viên an toàn thông tin vừa qua, quá trình suy nghĩ của mình, tại sao mình không thể giải ra nó cũng như cách sửa để cho solution đúng. Tuy nhiên trước đó thì mình muốn cảm ơn team Veritas đã cùng mình thi đấu đến phút chót xD, đồng thời cũng chúc mừng cho team C2 với giải A&D.

Author: Zayn

Bài này có tên revenge là do bài trước đó đã bị unintended bằng cách send full null bytes cho password. Còn phần Love-Linh-a-Lot thì đến cuối mình sẽ cho các bạn biết sau :v.

Script server

import random
import string
from Crypto.Util.number import isPrime

BLOCK_LEN = 129
CHARSET = string.ascii_uppercase + string.ascii_lowercase + string.digits
users, pwd_hashes = {}, []
allowed_blocks = []

q1 = 57895665874783536962369408363969823887021530656373208299565102620846005563716018275834077962292286213472570266375824572745671541793458387390711613089471407869558363212866932533545785125988453002675479793768261480181947144057144941974626043243654731721303589851520175899531854692118423229594279209070187162279
p1 = 2 * q1 + 1
g1 = 2
assert isPrime(p1)
assert isPrime(q1)
assert pow(g1, q1, p1) == 1
x1 = random.randint(1, 2 ** 256)
y1 = pow(g1, x1, p1)


def block_hash(block, bases, a):
    for x, y in zip(bases, block):
        a = a * pow(x, y, p1) % p1
    
    return a
def secure_hash(data, token, is_login = False):
    assert len(data) + 1 >= BLOCK_LEN, "Invalid Length"
    
    if len(data) % BLOCK_LEN != 0:
        data += b'\x80'
        data += b'\x00' * (BLOCK_LEN - len(data) % BLOCK_LEN - 1)
        
    blocks = [data[i:i + BLOCK_LEN] for i in range(0, len(data), BLOCK_LEN)]
    bases = [pow(g1, x, p1) for x in token] + [g1]
    yu_1 = y1
    
    for block in blocks:
        if all(x == 0 for x in block[:-1]):
            raise ValueError("No cheese this time")
        if is_login:
            if block not in allowed_blocks:
                raise ValueError("Invalid block")
        yu_1 = block_hash(block, bases, yu_1)
        allowed_blocks.append(block)
    
    return yu_1

def register(username, password):
    token = [random.randint(1, q1 - 1) for _ in range(BLOCK_LEN - 1)]
    if username in users:
        print("Username already exists")
        return False
    pwd_hash = secure_hash(password, token)
    users[username] = token
    pwd_hashes.append(pwd_hash)
    return True

    
def login(username, password):  
    if username not in users:
        return False
    token = users[username]
    try:
        password.decode()
    except:
        return False
    pwd_hash = secure_hash(password, token, True)
    return pwd_hash in pwd_hashes

def breach(username):
    if username not in users:
        return None
    return users[username]

def menu():
    print("1. Register")
    print("2. Login")
    print("3. Exit")

def main():
    admin_username = "admin"
    admin_password = ''.join(random.choices(CHARSET, k = BLOCK_LEN - 1)).encode() + b'\x00'
    register(admin_username, admin_password)
    print(f'User {admin_username} registered successfully')
    for _ in range(5):
        try:
            menu()
            choice = int(input("> "))
            if choice == 1:
                username = input("Enter username: ")
                password = bytes.fromhex(input("Enter password: "))
                if register(username, password):
                    print(f'User {username} registered successfully')
            elif choice == 2:
                username = input("Enter username: ")
                password = bytes.fromhex(input("Enter password: "))
                if login(username, password):
                    if username == admin_username:
                        print("Welcome admin, here is your flag: ")
                        print(open("flag.txt").read())
                        exit()
                    else:
                        print(f"Welcome user {username}")
                else:
                    print("Invalid credential")
            elif choice == 3:
                print("Gud bye")
                exit(0)
            elif choice == 1337:
                victim = input("Give me the victim name: ")
                victim_token = breach(victim)
                print("Shhhhh, don't tell anyone about this")
                print(victim_token)
            else:
                print("Invalid choice")
                exit(0)
        except ValueError:
            print("No No No No")
    
if __name__ == "__main__":
    main()

Tóm tắt

Mình cần login dưới danh nghĩa là admin để lấy flag, để làm được điều đó thì phải sử dụng token của admin để hash ra một pwd_hash bằng hàm secure_hash đã được đăng ký trước đó.

Phân tích

def secure_hash(data, token, is_login = False):
    assert len(data) + 1 >= BLOCK_LEN, "Invalid Length"
    
    if len(data) % BLOCK_LEN != 0:
        data += b'\x80'
        data += b'\x00' * (BLOCK_LEN - len(data) % BLOCK_LEN - 1)
        
    blocks = [data[i:i + BLOCK_LEN] for i in range(0, len(data), BLOCK_LEN)]
    bases = [pow(g1, x, p1) for x in token] + [g1]
    yu_1 = y1
    
    for block in blocks:
        if all(x == 0 for x in block[:-1]):
            raise ValueError("No cheese this time")
        if is_login:
            if block not in allowed_blocks:
                raise ValueError("Invalid block")
        yu_1 = block_hash(block, bases, yu_1)
        allowed_blocks.append(block)
    
    return yu_1

Bỏ qua phần kiểm tra độ dài cũng như padding thì mình thấy data của mình sẽ được chia ra thành từng block 129 ký tự, phần token thì được dùng để làm base. Giá trị hash sẽ được tính theo từng block.

Mình sẽ cùng nhìn xem hàm hash xử lý 1 block như thế nào

def block_hash(block, bases, a):
    for x, y in zip(bases, block):
        a = a * pow(x, y, p1) % p1

Viết lại một chút dưới dạng công thức toán thì mình có:

\[\begin{aligned} hash(block) &\equiv y\prod_{0\leq i \leq128}{base_i^{char_i}} &\pmod{p} \\ \\ &\equiv y g^h &\pmod{p} \\ \\ h &\equiv \sum_{0\leq i \leq128}{token_i \cdot char_i} &\pmod{q} \end{aligned}\]

Phương trình cuối của mình mod $q$ là do $g$ có bậc $q$ (assert pow(g1, q1, p1) == 1).

Đến đây thì mình đi xem tài khoản admin được đăng ký như thế nào, trong hàm main:

def main():
    admin_username = "admin"
    admin_password = ''.join(random.choices(CHARSET, k = BLOCK_LEN - 1)).encode() + b'\x00'
    register(admin_username, admin_password)
    print(f'User {admin_username} registered successfully')

Thông tin đáng chú ý ở đây là admin_password gồm 128 ký tự trong CHARSET thêm với 1 byte null ở cuối, vậy là vừa đủ 1 block. Mình sẽ xem tiếp có điều gì thay đổi trong hàm register không:

def register(username, password):
    token = [random.randint(1, q1 - 1) for _ in range(BLOCK_LEN - 1)]
    if username in users:
        print("Username already exists")
        return False
    pwd_hash = secure_hash(password, token)
    users[username] = token
    pwd_hashes.append(pwd_hash)
    return True

Đầu tiên thì đề bài sẽ khởi tạo token cho user, các giá trị của token sẽ nằm trong khoảng $[1, q - 1]$, ở đây hoàn toàn không có gì bất thường vì bậc của $g$ là $q$. Sau đó đã có token thì giá trị hash sẽ được tính cùng với password làm data, lưu lại token của user cũng như giá trị hash. Nếu không có điều gì bất thường trong quá trình tính hash cũng như username chưa từng được đăng ký trước đó (điều này để đảm bảo rằng mình sẽ không đăng ký lại admin và overwrite password cũ) thì hàm sẽ trả về True, báo hiệu rằng đã đăng ký tài khoản thành công.

Oke, tới đây rồi thì câu hỏi tiếp theo là mình cần làm gì để lấy flag.

    for _ in range(5):
        try:
            menu()
            choice = int(input("> "))
            if choice == 1:
                username = input("Enter username: ")
                password = bytes.fromhex(input("Enter password: "))
                if register(username, password):
                    print(f'User {username} registered successfully')
            elif choice == 2:
                username = input("Enter username: ")
                password = bytes.fromhex(input("Enter password: "))
                if login(username, password):
                    if username == admin_username:
                        print("Welcome admin, here is your flag: ")
                        print(open("flag.txt").read())
                        exit()
                    else:
                        print(f"Welcome user {username}")
                else:
                    print("Invalid credential")
            elif choice == 3:
                print("Gud bye")
                exit(0)

Chú ý vào choice = 2, mình sẽ thấy nếu có thể login bằng username là admin thì sẽ có được flag. Vậy thì công việc tiếp theo là đi xem hàm login hoạt động thế nào:

def login(username, password):  
    if username not in users:
        return False
    token = users[username]
    try:
        password.decode()
    except:
        return False
    pwd_hash = secure_hash(password, token, True)
    return pwd_hash in pwd_hashes

Đề bài sẽ lấy token của user (tất nhiên là user phải được đăng ký trước đó) cũng như thử decode password, tới đây thì mình hiểu là các password hợp lệ đều nằm trong khoảng decode được, tức là $char_i \in [0, 127]$. Sau đó thì giá trị hash được tính và kiểm tra xem có được đăng ký trước đó hay không, nếu có thì chúng ta sẽ login thành công.

Một ý nhỏ nhưng cũng ảnh hưởng đến bài mà mình chưa nhắc đến chính là tham số is_login trong hàm secure_hash. Có thể thấy khi ta login thì giá trị is_login sẽ là True, do đó hàm hash sẽ kiểm tra điều kiện:

        if is_login:
            if block not in allowed_blocks:
                raise ValueError("Invalid block")

Điều kiện này sẽ đảm bảo rằng khi mình login, các block password mà mình sử dụng đều là những block được đăng ký qua trước đó.

Vậy tổng kết lại, để lấy flag thì mình cần login với username = admin với giá trị pwd_hash từ password và token đã tồn tại trước đó.

Ý tưởng

Tận dụng choice == 1337, mình sẽ breach(victim) với victim = admin, làm vậy thì mình có được token của admin, công việc còn lại là login với username = admin và một password hợp lệ, cách suy nghĩ đơn giản nhất sẽ là cố gắng tìm lại password của admin, do đây là password được đăng ký trước đó nên chắc chắn là nó sẽ hợp lệ.

Vậy thì bài toán của mình lúc này sẽ là tìm các $char_i$ trong phương trình:

\[h \equiv \sum_{0\leq i \leq128}{token_i \cdot char_i} \pmod{q}\]

Do mình đã biết token cũng như $q$, mình sẽ cố gắng đi tìm $h$ để có thể LLL trên lattice $L$ được tạo bởi basis $M$ như sau:

\[\begin{aligned} M = \left(\begin{array}{cc} token_0 & 1 & 0 & \dots & 0 & 0\\ token_1 & 0 & 1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ token_{128} & 0 & 0 & \dots & 1 & 0\\ h & 0 & 0 & \dots & 0 & 1 \\ q & 0 & 0 & \dots & 0 & 0 \end{array}\right) \end{aligned}\]

Mục tiêu chính là đi tìm vector nhỏ $v = (0, char_0, char_1, \dots, -1)$ được tạo bởi tổ hợp tuyến tính $(char_0, char_1, \dots, char_{128}, 1, k)$.

Tuy nhiên sau một lúc thì mình thấy không có cách nào để kiếm $h$ của admin hết. Vậy nên tiếp theo mình sẽ xét tới ý tưởng là tìm một cái password khác sao cho token với pass đó hash ra được một pwd_hash đã được đăng ký trước (không phải pwd_hash của admin ban đầu).

Vậy thì mình sẽ đi đăng ký một pwd_hash thông qua hàm register với choice = 1.

Mình sẽ gọi token và password cân của mình là $token’$, $char’$. Vậy lúc này bài toán của mình sẽ là, kiếm các $char_i$ sao cho:

\[\sum_{i}{token_i\cdot char_i} \equiv \sum_{i}{token_i'\cdot char_i'} \pmod{q}\]

def get_token(name): 
    io.sendlineafter(b'>', b'1337')
    io.sendlineafter(b'Give me the victim name: ', name)
    io.recvuntil(b"Shhhhh, don't tell anyone about this\n")
    return eval(io.recvline())

def register(name, pw = None): 
    io.sendlineafter(b'>', b'1')
    io.sendlineafter(b"Enter username: ", name)

    if not pw: 
        pw = bytes([122] * (BLOCK_LEN - 1)) + b'\x00'

    io.sendlineafter(b"Enter password: ", pw.hex().encode())
    io.recvline()
    return pw

my_pass = register(b'elita')[:-1]

token_add = get_token(b'admin')
token_eli = get_token(b'elita')

target = sum([a * b for a, b in zip(token_eli, my_pass)]) % q1  

mat = column_matrix(ZZ, token_add + [target])
mat = mat.augment(identity_matrix(BLOCK_LEN))
mat = mat.stack(vector(ZZ, [q1] + [0] * BLOCK_LEN))

lll = mat.LLL()

for r in lll.rows():
    if r[0] == 0: 
        print(r)

Giống như vector $v$ mình nói ở trên, mình chỉ quan tâm những vector có giá trị đầu tiên $v_0 = 0$ (và giá trị cuối bằng $-1$).

Tuy nhiên khi chạy script này thì mình không thấy vector nào thỏa cả, các vector đều trông như thế này:

(223, 285, 147, 285, -129, -132, -291, -76, -104, 211, -46, 161, 7, -377, -61, 78, -456, 123, 141, -399, 114, 722, 572, -31, -129, -41, 51, 49, -78, -521, -88, -608, -474, 474, -18, 40, 393, 6, -85, -107, 125, 332, -358, -200, -323, 133, -458, -158, 83, -284, -457, -49, -222, 128, -324, -93, -212, -565, 111, -131, 547, -1, 86, -269, 245, 77, 371, 378, -364, -16, 528, -272, 245, -329, 259, -432, 75, -64, -71, -388, -327, -269, -421, -15, 397, 186, -152, 146, 360, -101, -218, 405, -393, -276, 620, -86, 214, 424, 543, 228, -99, 273, 141, 301, 130, 173, 82, -70, -105, -288, -193, -146, -76, 284, 68, 261, 469, -199, 148, -51, 46, 82, 75, 75, -34, -14, -2, 0, 0, 0)
(126, -491, -511, -496, 836, -700, -287, -21, 364, 476, 70, -287, 180, 311, -118, -154, -401, 136, -402, 438, -23, 68, -429, -118, -137, -18, 16, -502, -182, 521, -580, -177, -696, 199, 239, -276, -268, 329, 238, 162, 523, 254, 540, -307, 430, -394, -67, 314, 81, -61, 134, -222, 1, 151, 311, -104, -664, -83, 33, 15, 412, 801, -66, -178, -443, 19, -198, -253, 155, -450, 64, -726, -2, -161, -128, 192, 152, -331, 448, 345, -12, -191, -723, 48, 50, -277, 259, -514, 177, -215, 75, -417, -176, 224, -450, 423, 352, 176, 424, 222, 70, 46, -415, 85, -123, -267, -37, 217, 33, 358, 117, 118, -67, -124, 31, 149, 135, -129, 19, -4, 43, -14, -1, 0, 0, 0, 0, 0, 0, 0)
(276, -474, -471, -488, 504, -244, 130, 257, -87, 258, 637, -247, 144, 203, -250, -312, -500, -584, -214, 238, 345, -135, -124, 158, 293, 92, -529, -7, -225, -25, -131, -349, -401, -168, 59, -421, 44, -579, 174, 244, 430, 443, 80, -202, 230, -71, 116, 363, 622, -238, 97, 329, -306, 5, 147, -497, -923, -147, 130, 189, 287, 384, -185, -32, 392, 216, 740, -414, 211, 793, 139, -554, -137, -75, -157, 382, -592, -822, -69, -26, 19, -286, 420, -96, 406, -956, 64, -90, 237, -325, 289, -70, -510, 125, -258, 660, 19, 443, 236, 199, 128, 197, -29, -72, -115, 296, 442, -289, 185, 16, 210, -108, -206, 108, -84, 187, 168, -59, 4, -26, 7, -4, 7, 0, 0, 0, 0, 0, 0, 0)

Giá trị đầu tiên mình cần thì nó khác $0$, trong khi các giá trị cuối thì lại bằng $0$ rất nhiều. Tức là LLL đã chú trọng vào việc reduce độ lớn của các số ở sau thay vì ở trước. Để LLL tập trung vô việc giảm cột đầu tiên, mình sẽ scale cột đầu tiên lên một số $S$ bằng cách nhân thêm một ma trận đường chéo $W = diag(S, 1, \dots, 1)$.

Vậy $M$ của mình sẽ trở thành

\[\begin{aligned} M = \left(\begin{array}{cc} S \cdot token_0 & 1 & 0 & \dots & 0 & 0\\ S \cdot token_1 & 0 & 1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ S \cdot token_{128} & 0 & 0 & \dots & 1 & 0\\ S \cdot h & 0 & 0 & \dots & 0 & 1 \\ S \cdot q & 0 & 0 & \dots & 0 & 0 \end{array}\right) \end{aligned}\]

Nếu như $S$ đủ lớn này giống như đang bảo LLL rằng: “cột đầu tiên rất lớn nè, chú ý vô reduce nó đi”.

Chú ý rằng mục tiêu của mình vẫn không thay đổi, vẫn kiếm $v$ như trên.

\[\begin{aligned} \sum_{i}{token_i \cdot char_i} + kq &= 0 \\ \Rightarrow S \cdot \left(\sum_{i}{token_i \cdot char_i} + kq\right) &= 0 \end{aligned}\]

mat = column_matrix(ZZ, token_add + [target])
mat = mat.augment(identity_matrix(BLOCK_LEN))
mat = mat.stack(vector(ZZ, [q1] + [0] * BLOCK_LEN))

w = identity_matrix(mat.nrows())
w[:1] *= 2 ** 1024 

lll = (mat * w).LLL() / w 

for r in lll.rows()[:10]:
    if r[0] == 0: 
        print(r)

Lúc này thì sẽ có những vector trông như thế này:

(0, -160, -4, -443, -332, 14, -221, 233, 51, -556, 156, -591, 568, -42, 377, 643, 175, -344, -180, -186, -325, 378, 547, 303, -102, 66, -599, 119, -252, -106, 170, -254, -722, 1, -113, 877, -87, 285, -537, 207, -579, -228, 88, -544, -38, -130, -25, 371, 119, 292, -141, -844, 7, 49, 548, -211, 578, -509, -56, -297, 180, 230, 62, 149, 309, 38, 116, -91, -12, -495, -170, 154, 53, 422, -554, 86, -48, 130, -284, 447, -241, 348, -385, 331, -112, -3, 66, 91, 289, -577, -504, 177, 610, -193, 329, 527, 231, 44, 119, 528, 199, 109, -132, -164, 159, 247, -113, 32, -211, -152, 246, 209, 28, 67, 81, -56, -119, -221, -80, -32, -3, -21, 12, 25, -9, 0, 0, 0, 0, 0)
(0, 317, -231, 220, -682, -327, -148, 510, 185, -537, 401, -209, -123, 45, -11, -91, -327, -292, -899, -158, 369, 519, -94, 705, 289, -403, -189, -84, -506, -468, 443, -107, -394, 516, -336, 295, -190, 2, -310, 173, -883, -422, -342, -622, -232, 26, 264, -266, 390, 454, 428, -655, 406, 666, 813, -155, -43, 166, 423, 235, 357, 657, 230, -263, 90, 336, 178, -426, -136, -417, 186, 217, -13, 235, 74, 81, -29, 179, 42, 6, -355, -292, -593, 344, -664, 4, -147, -236, -140, -210, 47, -10, 419, 43, 494, 151, 357, -563, -415, 74, -202, 476, 238, 138, 390, -72, -33, 202, -76, -106, -279, -341, 154, 180, 38, -30, -168, -106, -37, 21, 117, -9, 42, -22, 25, 3, 0, 0, 0, 0)
(0, 29, -330, -130, -184, -340, 29, 236, 636, -131, 395, -189, 16, -23, 397, -50, 512, 45, -697, -492, 422, -83, -128, 345, 311, 144, -94, -454, -915, -69, 762, 421, 148, 360, -72, 234, 76, 67, -913, 55, -494, -194, -101, -436, -172, -222, 249, -929, 269, 565, 350, -540, 406, 326, -206, 255, -129, 70, -150, 357, 207, 305, 282, -320, 261, -229, -266, -83, 43, -690, -32, -162, 150, 0, -41, -587, -61, 653, 127, -306, -105, -517, -263, -29, -83, 297, -393, 31, 470, -65, -533, -139, 78, -7, 212, 66, -335, -213, -589, 29, -500, -186, -5, 146, -21, 284, 70, 356, 154, 81, 16, -151, 197, -108, -27, -61, 23, -71, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Oke, giờ mình chỉ cần thêm điều kiện giá trị cuối = $\pm1$ nữa.

Mình sẽ có những vector

(0, -366, 310, 35, 348, 344, -272, 149, 493, 74, -583, 435, -485, 379, 7, -212, -158, 274, -28, 307, 80, -38, -171, 187, 1045, 132, 241, -955, -617, 254, -271, 116, 820, 151, -92, 379, -104, -220, 321, -113, -344, 11, 682, 323, 130, 131, 245, -46, 413, -28, -170, -24, 304, 42, -403, -130, -787, -566, 447, 930, 510, -189, 292, -305, -557, 252, -387, -34, -622, -320, -293, -5, -40, -143, 484, -67, -32, 36, 255, -227, -509, -462, 470, -319, 141, -367, -190, 196, -228, 91, -190, -239, 202, -364, -99, 44, -277, 117, -585, -164, 243, 857, 192, 1, 277, -551, -218, -7, -72, -772, -211, 343, 221, -188, 209, 95, -492, -164, -20, -245, 27, 256, -123, -16, 191, 101, -158, -51, 34, 1)
(0, -814, 268, 84, 385, -284, -84, 299, -630, 347, 237, -571, 864, -720, -236, -286, 628, -77, -95, -132, -86, 437, 199, -398, -555, 620, 436, 40, -200, -93, -79, -365, 290, 207, 433, 571, -340, 84, 290, -391, 288, -150, -524, 140, 509, -133, -182, 35, -152, -101, 211, 568, -835, -283, -26, 205, -155, 127, 244, -482, 641, -250, 136, 263, 295, -707, 544, 500, -41, -479, -234, -417, 162, 418, -120, -494, -575, -525, -415, 88, -212, -258, -390, 31, -79, 284, -276, 3, -516, 300, -228, -412, 89, 647, 128, 305, 167, -318, -172, -51, 297, 95, -17, -28, -275, -299, 154, -437, 62, 195, -77, -275, 185, -198, 372, 17, -74, -147, 112, 272, 89, 125, 81, 85, -191, 102, 94, 13, 17, -1)
(0, 311, -329, 342, -177, 94, 330, 583, -219, 785, -380, -23, -96, 271, 657, 458, -1, 603, -291, -112, 82, 261, -173, 578, -254, -387, 679, -193, -132, -224, -342, -535, -112, -307, -109, 225, -662, -209, -61, -76, -99, -418, 328, 362, -191, -157, 228, 831, -98, -281, -213, -122, -53, 245, -270, 297, 160, -368, -491, -301, -211, -185, -96, 964, 315, 62, 376, -101, -160, 667, 657, -209, -40, 818, -218, 504, -76, -134, -729, -423, 440, 21, -86, -28, 21, 295, -114, 75, 174, 548, 197, 49, 21, 454, -417, -548, -265, 223, -117, 349, -603, 219, 334, -457, 217, -25, -111, 43, 611, -285, -31, -1, -211, 85, 0, 185, -156, 44, -182, 69, 106, -42, -312, -50, 41, 0, 19, -34, -19, 1)
(0, -361, 239, -168, 67, -243, 124, 646, -343, 624, 0, 288, -585, -380, -12, -85, -339, -126, -175, 507, 103, 80, 207, -94, 248, -661, 4, 67, -415, 78, 609, -527, 669, 131, 262, 986, 9, 111, -320, -339, -253, 73, 306, 244, 124, 76, -25, -97, -190, 427, -448, -324, -169, 406, -188, -90, 15, -478, 261, -117, -89, -252, 116, -345, 263, -150, 541, -85, -20, -371, 620, -448, 251, 242, -65, 400, -117, -229, -236, 498, -115, -59, -164, -325, 92, -14, -91, -427, -273, -432, 35, 434, 265, 577, -173, 752, -89, 280, 444, -717, 315, 773, 148, 471, -172, -941, -167, 749, -213, 88, -184, -64, 50, 78, 97, -764, -10, -22, 149, -40, -263, 129, 105, -128, 96, 6, -69, -62, -6, -1)

Tuy nhiên tới đây thì mình thấy các giá trị $char_i$ mình thu được không như mình mong muốn, nếu như các giá trị $\geq 128$ thì mình chỉ cần làm nhiều block thay vì $1$ nhưng giá trị âm thì hết cứu và đây là lúc thích hợp cho section của tiêu đề…

Vì sao mình không giải được Love-Linh-a-Lot Revenge

Mình quyết định thay đổi hướng đi, thay vì đi kiếm password mới một cách random mình sẽ xây dựng trước một password của mình và xây dựng password cần tìm từ đó.

Ý tưởng như sau:

Mình sẽ cho rằng khoảng cách chênh lệch giữa 2 password $\delta_i = char_i’ - char_i$ là rất nhỏ

Từ đây mình viết lại

\[\begin{aligned} \sum_{i}{token_i\cdot char_i} &\equiv \sum_{i}{token_i'\cdot char_i'} &\pmod{q} \\ \sum_{i}{token_i\cdot (char_i' + \delta_i)} &\equiv \sum_{i}{token_i'\cdot char_i'} &\pmod{q} \\ \sum_{i}{token_i\cdot \delta_i} &\equiv \sum_{i}{\left(token_i'\cdot char_i' - token_i \cdot char_i'\right)} &\pmod{q} \end{aligned}\]

Mình sẽ tạo password $char_i \approx 60$ và mong rằng $\delta_i$ đủ nhỏ để $char_i = char_i’ - \delta_i$ nằm trong byte range.

my_pass = register(b'elita')[:-1]

token_add = get_token(b'admin')
token_eli = get_token(b'elita')

exponent1 = sum([a * b for a, b in zip(token_eli, my_pass)]) % q1  
exponent2 = sum([a * b for a, b in zip(token_add, my_pass)]) % q1  

target = (exponent1 - exponent2) % q1 


mat = column_matrix(ZZ, token_add + [target])
mat = mat.augment(identity_matrix(BLOCK_LEN))
mat = mat.stack(vector(ZZ, [q1] + [0] * BLOCK_LEN))

w = identity_matrix(mat.nrows())
w[:1] *= 2 ** 1024 

lll = (mat * w).LLL() / w 

for r in lll.rows():
    if r[0] == 0 and abs(r[-1]) == 1: 
        print(r)

(0, -60, 109, -308, -1071, 414, 505, 243, -112, 429, -784, 1005, 333, 130, -376, 55, -224, -42, -91, 903, 22, 568, -528, 194, -421, -183, -195, -382, 433, -295, 79, -467, -686, -187, 890, 207, -319, -127, 69, -188, -400, -390, -612, 383, 234, 40, -176, -712, 43, 146, 153, 334, -77, -66, -56, -272, 344, -125, 130, 111, -401, -414, -471, 558, 315, 171, 440, -702, -289, 469, -121, 11, -298, 504, 258, 19, 418, -421, -156, 146, 188, 238, -68, 824, -457, -253, 480, 517, -138, -161, -240, -305, 542, -208, 356, 783, 338, 401, 164, -680, -7, 619, 15, -46, -16, -184, -723, 293, -511, -60, -559, -418, 302, 63, -18, -111, 90, -21, -222, 22, 4, 42, -30, 37, -23, 5, 29, 27, -11, 1)

Khá buồn khi lúc thi, mình đã code bug lattice của mình và kết quả $v$ thu được trông rất khả quan, mình nghĩ cách này chắc chắn sẽ ra được nhưng rõ ràng cách này không có gì đảm bảo nó sẽ hoạt động được cả (chả khác gì lấy đại một số trong $Z_q$ rồi tìm password thỏa phương trình), vì mình không thể đảm bảo rằng tồn tại một password gần password của mình thỏa phương trình trên. Chỉ còn cách giải quyết việc cái vector ra toàn số dương để mình có thể cộng vào các block sau thôi.

Vậy mình ép vector sau khi LLL ra các giá trị dương như thế nào?

Ở đây mình đã dùng basis $M$ như sau:

\[\begin{aligned} M = \left(\begin{array}{cc} S \cdot token_0 & 1 & 0 & \dots & 0 & 0\\ S \cdot token_1 & 0 & 1 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ S \cdot token_{128} & 0 & 0 & \dots & 1 & 0\\ S \cdot h & scaler & scaler & \dots & scaler & 1 \\ S \cdot q & 0 & 0 & \dots & 0 & 0 \end{array}\right) \end{aligned}\]

Với tổ hợp tuyến tính giống phía trên, mình sẽ thu được vector $v = (0, \delta_0 - scaler, \delta_1 - scaler, \dots, -1)$.

Giống như mình đang nói với LLL rằng: “Giờ tui thêm cái scaler vô $\delta_i$ rồi đó, ông muốn mấy giá trị sau nó nhỏ thì ông phải reduce $\delta_i + scaler$ nhỏ đó nha”

Và nếu mình chọn hợp lý thì $\delta_i - scaler \geq -scaler$, tức là LLL sẽ không cho phép tồn tại số $< scaler$ vì điều này sẽ làm độ dài của vector tăng lên. Từ đây thì mình chỉ cần cộng lại $scaler$ để có $\delta_i$.

scaler = 2 ** 10

mat = column_matrix(ZZ, token_add + [target])
mat = mat.augment(identity_matrix(BLOCK_LEN))
mat[mat.nrows() - 1, 1:-1] = scaler
mat = mat.stack(vector(ZZ, [q1] + [0] * BLOCK_LEN))
w = identity_matrix(mat.nrows())
w[:1] *= 2 ** 1024 

print(mat.nrows(), mat.ncols())

print('Doing LLL')

timer = time.time()

lll = (mat * w).LLL() / w 

print(f"Done LLL, took {time.time() - timer:.3f}s")

found = False 

for r in lll.rows():
    if r[0] == 0 and abs(r[-1]) == 1:
        if r[-1] == 1: 
            r = [0] + [-x for x in r[1:]] 
        # print(r)
        found = True  
        break 

assert found, "unlucky"

delta = list(r[1:-1])

assert abs(min(delta)) <= scaler, "unlucky" 

delta = [x + scaler for x in delta]

print(delta)

Có thể thấy các giá trị $\delta_i$ của mình đều dương cả

130 130
Doing LLL
Done LLL, took 7.336s
[1066, 1129, 941, 1248, 725, 1198, 1368, 1414, 1477, 948, 845, 960, 1087, 1070, 1260, 1483, 649, 1299, 130, 876, 721, 1250, 1227, 1061, 691, 865, 1181, 698, 1481, 2059, 518, 1499, 1347, 561, 269, 838, 1353, 1147, 745, 751, 742, 333, 913, 685, 971, 267, 968, 1433, 1083, 1100, 923, 1599, 1333, 1359, 625, 613, 515, 1525, 1886, 1221, 1344, 1038, 1434, 1180, 1768, 859, 454, 382, 1347, 1188, 258, 721, 784, 1646, 1053, 1445, 1305, 775, 895, 1002, 532, 849, 1106, 936, 1953, 1180, 601, 1089, 534, 696, 865, 1099, 1410, 371, 405, 2116, 772, 737, 1246, 1754, 834, 1214, 888, 783, 1550, 1101, 1157, 1518, 587, 847, 680, 660, 1034, 1266, 950, 1020, 937, 934, 1021, 762, 775, 888, 923, 1047, 889, 927, 1098, 1047]

Tới đây thì mình có thể xây dựng password mới như sau:

\[char_i = char_i' + \delta_i\]

Nhưng thay vì cộng hết $1$ lần thì mình chỉ cần cộng từ từ đủ byte range và chừa lại giá trị sang block tiếp theo để cộng sau

def construct_password(offset, original_pw): 
    pw = original_pw
    i = 0 
    while any(offset):
        if i == BLOCK_LEN - 1:
            pw.append(0)
            i = 0  
        sign = -1 if (offset[i % BLOCK_LEN] < 0) else 1 
        pw.append(sign * min(abs(offset[i % BLOCK_LEN]), 127))
        offset[i % BLOCK_LEN] -= sign * min(abs(offset[i % BLOCK_LEN]), 127)

        if not any(offset): 
            break
        i += 1 
    pw += [0] * (BLOCK_LEN - (len(pw) % BLOCK_LEN))
    return pw  

new_pw = bytes(construct_password(delta, [127] * (BLOCK_LEN - 1) + [0]))

Mình truyền original_pw = [127, 127, ...] là do password của mình full 127 (làm vậy thì sẽ ít block đi).

Sau khi cộng hết rồi thì mình cần đảm bảo là độ dài của password chia hết cho BLOCK_LEN, để không ảnh hưởng kết quả hash thì mình chọn null byte.

Tuy nhiên tới đây thì có lẽ nhiều người cũng nhận ra, mình không cần phải làm $\delta_i$ gì cho mệt, mình có thể bỏ việc cộng trên password cũ luôn, lúc này thì chỉ cần để pw = []

Solution script

import random
import string
from Crypto.Util.number import isPrime
from pwn import process, remote
import time 

BLOCK_LEN = 129
CHARSET = string.ascii_uppercase + string.ascii_lowercase + string.digits
users, pwd_hashes = {}, []
allowed_blocks = []

q1 = 57895665874783536962369408363969823887021530656373208299565102620846005563716018275834077962292286213472570266375824572745671541793458387390711613089471407869558363212866932533545785125988453002675479793768261480181947144057144941974626043243654731721303589851520175899531854692118423229594279209070187162279
p1 = 2 * q1 + 1
g1 = 2
assert isPrime(p1)
assert isPrime(q1)
assert pow(g1, q1, p1) == 1

io = process(["python3", "chall.py"])

# io = remote('183.91.11.30', 666)

def get_token(name): 
    io.sendlineafter(b'>', b'1337')
    io.sendlineafter(b'Give me the victim name: ', name)
    io.recvuntil(b"Shhhhh, don't tell anyone about this\n")
    return eval(io.recvline())

def register(name, pw = None): 
    io.sendlineafter(b'>', b'1')
    io.sendlineafter(b"Enter username: ", name)

    if not pw: 
        pw = bytes([127] * (BLOCK_LEN - 1)) + b'\x00'

    io.sendlineafter(b"Enter password: ", pw.hex().encode())
    io.recvline()
    return pw

my_pass = register(b'elita')[:-1]

token_add = get_token(b'admin')
token_eli = get_token(b'elita')

target = sum([a * b for a, b in zip(token_eli, my_pass)]) % q1  

from sage.all import * 

scaler = 2 ** 10

mat = column_matrix(ZZ, token_add + [target])
mat = mat.augment(identity_matrix(BLOCK_LEN))
mat[mat.nrows() - 1, 1:-1] = scaler
mat = mat.stack(vector(ZZ, [q1] + [0] * BLOCK_LEN))
w = identity_matrix(mat.nrows())
w[:1] *= 2 ** 1024 

print(mat.nrows(), mat.ncols())

print('Doing LLL')

timer = time.time()

lll = (mat * w).LLL() / w 

print(f"Done LLL, took {time.time() - timer:.3f}s")

found = False 

for r in lll.rows():
    if r[0] == 0 and abs(r[-1]) == 1:
        if r[-1] == 1: 
            r = [0] + [-x for x in r[1:]] 
        found = True  
        break 

assert found, "unlucky"

delta = list(r[1:-1])

assert abs(min(delta)) <= scaler, "unlucky" 

delta = [x + scaler for x in delta]

def construct_password(offset): 
    pw = []
    i = 0 
    while any(offset):
        if i == BLOCK_LEN - 1:
            pw.append(0)
            i = 0  
        sign = -1 if (offset[i % BLOCK_LEN] < 0) else 1 
        pw.append(sign * min(abs(offset[i % BLOCK_LEN]), 127))
        offset[i % BLOCK_LEN] -= sign * min(abs(offset[i % BLOCK_LEN]), 127)

        if not any(offset): 
            break
        i += 1 
    pw += [0] * (BLOCK_LEN - (len(pw) % BLOCK_LEN))
    return pw  

new_pw = bytes(construct_password(delta)) 

print(f"{len(new_pw) = }")

register(b'dumb cry and sad', new_pw)

io.sendlineafter('>', b'2')
io.sendline(b'admin')
io.sendline(new_pw.hex().encode())

io.interactive()

130 130
Doing LLL
Done LLL, took 4.113s
len(new_pw) = 2193
Welcome admin, here is your flag:
ASCIS{d1d_1_g3t_My_r3v3ng3???}

Yes you did, big time.

Như đã nói ở đầu thì ý nghĩa của Love-Linh-a-Lot:

Cảm ơn anh Zayn vì đã cho 1 bài hay, nice cooking chef.