Giải khó vãi cả ẻ, mình giải được đúng 2 beginner chall :'(

## yet another login
> Yet another login task... Authenticate as admin to get the flag!
>
> Regards,
> joseph
>
> AU: nc chal.2025.ductf.net 30010
> US: nc chal.2025-us.ductf.net 30010

chall.py

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from hashlib import sha256
from secrets import randbits
import os

FLAG = os.getenv('FLAG', 'DUCTF{FLAG_TODO}')

class TokenService: 
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.n = self.p * self.q
        self.n2 = self.n * self.n
        self.l = (self.p - 1) * (self.q - 1)
        self.g = self.n + 1
        self.mu = pow(self.l, -1, self.n)
        self.secret = os.urandom(16)

    def _encrypt(self, m):
        r = randbits(1024)
        c = pow(self.g, m, self.n2) * pow(r, self.n, self.n2) % self.n2
        return c

    def _decrypt(self, c):
        return ((pow(c, self.l, self.n2) - 1) // self.n) * self.mu % self.n

    def generate(self, msg):
        h = bytes_to_long(sha256(self.secret + msg).digest())
        return long_to_bytes(self._encrypt(h))

    def verify(self, msg, mac):
        h = sha256(self.secret + msg).digest()
        w = long_to_bytes(self._decrypt(bytes_to_long(mac)))
        return h == w[-32:]


def menu():
    print('1. Register')
    print('2. Login')
    return int(input('> '))


def main():
    ts = TokenService()
    print(ts.n)

    while True:
        choice = menu()
        if choice == 1:
            username = input('Username: ').encode()
            if b'admin' in username:
                print('Cannot register admin user')
                exit(1)
            msg = b'user=' + username
            mac = ts.generate(msg)
            print('Token:', (msg + b'|' + mac).hex())
        elif choice == 2:
            token = bytes.fromhex(input('Token: '))
            msg, _, mac = token.partition(b'|')
            if ts.verify(msg, mac):
                user = msg.rpartition(b'user=')[2]
                print(f'Welcome {user}!')
                if user == b'admin':
                    print(FLAG)
            else:
                print('Failed to verify token')
        else:
            exit(1)


if __name__ == '__main__':
    main()

**1. Giải thích code**
1.1 Một số hàm cần lưu ý
* Hàm **encrypt()**: mã hóa message => E(msg) <br> $c = g^m \cdot r^n \ mod\ n^2$ (thực ra cái $r^n$ có hay không cũng được, không ảnh hưởng đến quá trình **decrypt()**)
* **generate()**: Mã hóa hash của msg => E(h)
* **verify()**: kiểm tra 32 byte cuối của D(E(h)) =? h

1.2 Flow
* Server sẽ trả lại n ngay sau khi kết nối, và có 2 lựa chọn
* Quá trình Register, sau khi nhập Username server sẽ trả về Token = username + b'|' + E(H(username)), và sử dụng Token vừa được cung cấp ta sẽ đăng nhập được (khi này server sẽ tách token thành msg và mac (chính là E(h)), và verify xem h và D(E(h)) có trùng nhau hay không).

* Hàm **rpartition(m)** sẽ tách chuỗi thành 3 phần, trước chuỗi m, chuỗi m và chuỗi sau m, và điều đặc biệt là hàm này sẽ "mò" từ phải sang trái<br>
VD: msg = 'user= skibidi user=admin' <br> rpartition('user=') <br> -> [user= skibidi, user=, admin]

2. Solution
* Để lấy được flag thì trong msg phải có b'admin', nhưng input không cho phép có b'admin' và do cơ chế khá thú vị của hàm **rpartition(m)**, nên ta sẽ khai thác qua việc gửi token (username = b'user' + b'user=admin' + '|' + mac hợp lệ cho username)
* Ta sẽ làm điều đó thông qua Hash length extention attack, nếu biết được msg và Hash(secret | msg), ta có thể tính được Hash(secret | msg | padding | extra) mà không cần biết secret, trong bài chúng ta sẽ là Hash(secret | b'user' | padding | b'user=admin'). <br>
**Key 1**: Tìm ra Hash(secrete | b'user')
* Đối với các hàm Paillier, có một số tính chất khá thú vị <br>
Additive Homomorphism:
Scalar Multiplication

Do n (1024 bit) >> h (256 bit) nên ta có thể bỏ mod n. Ta sẽ phải lợi dụng tính chất này để tìm ngược lại thứ cần ở **Key 1**

**Key 2**: Recover từng bit trong Hash(secrete | b'user'), ta sẽ sử dụng công thức sau
* Tôi sẽ lấy ví dụ trên 4 bit để hình dung rõ hơn tại sao lại có công thức trên
* Để check bit_i là 0 hay 1, thì ta sẽ làm những hành động <br>
1. Xử lí phần trước của bit_i (nhân $2^{255 -i}$))
* Nhân với $2^{255 -i}$ là để dịch bit_i sang trái lên đầu, do bit đầu của h luôn luôn là 1 nên khi cộng vào sẽ check được trạng thái (0/1) của bit_i
* Nếu bit_i = 1 => kết quả hàm verify sẽ sai <br>
bit_i = 0 thì ở bit_i sẽ dịch số 0 lên đầu => kết quả hàm verify đúng

2. Xử lí phần sau của bit bit_i (trừ đi phần đã biết của h)
t
* Và hàm verify cũng chỉ quan tâm đến 32 byte (256 bit) cuối nên đếch cần quan tâm mấy cái bị dịch lên trước là cái gì <br>
Code:

from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwn import *
from tqdm import tqdm
import hlextend

def adding(c, a, n):
    return int(c * pow(n+1, a, n**2) % n**2)

def multiplying(c, k, n):
    return int(pow(c, k, n**2))

def adding_ct(c, c2, n):
    return int(c * c2 % n**2)

def get_token(username, conn):
    conn.sendlineafter(b'> ', b'1')
    conn.sendlineafter(b'Username: ', username)
    return bytes_to_long(bytes.fromhex(conn.recvline().decode().split('Token: ')[1]).partition(b'|')[2])

def login(msg, mac, conn):
    conn.sendlineafter(b'> ', b'2')
    conn.sendlineafter(b'Token: ', (msg + b'|' + mac).hex().encode())
    response = conn.recvline().decode()
    return 'Welcome' in response

def main():
    conn = remote('chal.2025.ductf.net', 30010)
    n = int(conn.recvline().decode())
    mac = get_token(b'user', conn)
    rec_pt = 0
    for i in tqdm(range(256)):
        w = adding_ct(multiplying(adding(mac, -rec_pt, n), 2** (255 - i), n), mac, n)
        if not login(b'user=user', long_to_bytes(w), conn):
            rec_pt |= 1 << i
    hle = hlextend.sha256()
    ext = hle.extend(b'user=admin', b'user=user', 16, long_to_bytes(rec_pt).hex())
    h = bytes.fromhex(hle.hexdigest())
    mac = long_to_bytes(pow(n + 1, bytes_to_long(h), n**2))
    login(ext, mac, conn)
    print(conn.recvline().decode())
    conn.close()
    
main()
flag: DUCTF{now_that_youve_logged_in_its_time_to_lock_in}