# Le Hash Qui Rit

## Challenge

Tóm tắt đề bài: Nhập không quá 256 messages $M_i$ ở dạng hex (dòng cuối cùng trống để exit) sao cho $\bigoplus_i$ $SHA256(M_i)$ = một giá trị target cho trước (ở dạng hex).

## Solution

Vì đây là mình đang thao tác trên các giá trị hash SHA256, nên rất khó để có thể tìm được mối liên hệ nào giữa giá trị hash và message ban đầu. Vì vậy ta chỉ có thể khai thác ở phép XOR giữa các giá trị hash.

Ta đã biết, khi viết một số nguyên ra dạng nhị phân thì khi XOR 2 chuỗi nhị phân lại với nhau sẽ giống như việc mình cộng từng giá trị bit của mỗi vị trí lại rồi mod 2. Như vậy, thực ra phép XOR chính là phép cộng trên GF(2). Cộng thêm việc các chuỗi nhị phân đó ta hoàn toàn có thể viết được dưới dạng các vector.

=> XOR 2 chuỗi nhị phân = cộng 2 vector nhị phân.

Giả sử ta có 500 messages ban đầu và 500 giá trị hash khác nhau. Dễ dàng thấy được, để chọn ra các giá trị hash thỏa mãn yêu cầu bài toán, đồng nghĩa với việc tìm ra được một tổ hợp tuyến tính của target trong tập vector giá trị hash.

=> Bài toán trở thành: tìm tổ hợp tuyến tính của target trong tập vector giá trị hash đó.

Để tìm cơ sở của không gian 500 vector giá trị hash đó:

Gọi $basis_i$ là vector có bit nhỏ nhất được bật là i mà vector đó có được bằng cách XOR một số giá trị trong 500 vector hash ban đầu.

Giả sử với mọi vị trí $i$ mà bit $i$ của $target$ đều bằng $1$, ta đều tính được $basis_i$. Thì luôn tồn tại cách để XOR một số vector $basis$ đó để có được $target$. Nói cách khác, luôn tồn tại cách XOR một số vector trong 500 vector giá trị hash ban đầu để có được $target$ vì $basis$ có được từ việc XOR các vector đó.

Thuật toán để tìm được mảng $basis$:

- Ban đầu khỏi tạo toàn bộ $basis$ có giá trị là $0$.
- Viết một hàm $InsertVector(mask)$ để thêm lần lượt các vector giá trị hash ban đầu để tính toán mảng $basis$.
- Trong hàm $InsertVector(mask)$:
- Ta xét qua từng bit từ bit nhỏ đến bit lớn.
- Với $i$ là bit hiện tại đang xét nếu bit thứ $i$ của $mask$ = $0$ thì bỏ qua và xét đến bit tiếp theo.
- Ngược lại, nếu bit thứ $i$ của $mask$ = $1$, có 2 trường hợp:
- TH1: nếu $basis_i$ = $0$ có nghĩa là ta chưa tìm được vector thỏa mãn cho $basis_i$, mà ta lại có bit thứ $i$ của $mask$ = 1 và các bit nhỏ hơn đều = 0 (*). Vậy nên ta gán giá trị của $basis_i$ = $mask$.
- TH2: nếu $basis_i$ != $0$ có nghĩa là ta đã tìm được một vector thỏa mãn cho $basis_i$ bằng các giá trị $mask'$ đã được $Insert$ trước đó. Nên ta không cần phải tìm giá trị cho $basis_i$ nữa, mà ta có thể dùng $basis_i$ để XOR với $mask$ để triệt tiêu bit $i$ của $mask$ thành $0$ và xét đến bit lớn hơn (mục đích để giữ cho điều kiện (*) luôn đúng vì (i - 1) bit trước của cả $basis_i$ và $mask$ đều bằng $0$ nên khi XOR hai giá trị lại thì $i$ bit đầu tiên của $mask$ sẽ bằng 0).

basis = [0] * 256
def Insert_Vector(mask):
    for i in range(256):
        if (mask & (1 << i)) == 0:
            continue
            
        if not basis[i]:
            basis[i] = mask
            return 
        
        mask ^= basis[i]

Khi đã tìm cơ sở $basis$ rồi, ta sẽ thấy rằng, mọi vector thuộc $\mathbb{R}^{256}$ sẽ luôn được sinh ra từ $basis$. Từ đó, viết hàm để tìm các vector $basis_i$ sao cho các vector đó XOR lại với nhau = $target$.

def Check_Xor(mask, basis):
    idx = []  # idx: lưu lại các vị trí i mà basis[i] được chọn
    for i in range(256):
        if (mask & (1 << i)) == 0:
            continue

        if not basis[i]:
            return []

        idx.append(i)
        mask ^= basis[i]
    return idx

Ý tưởng cơ bản là như vậy, ta chỉ cần xử lí thêm việc với mỗi vector $basis_i$, ta biết được các message ban đầu nào XOR lại với nhau thì = $basis_i$ (đến đây thì các bạn có thể dùng các cấu trúc dữ liệu để lưu lại). Nên nhớ là mình chỉ cần quan tâm tính chẵn lẻ của số lượng các message thôi (bởi vì nếu như 1 message xuất hiện 2 lần thì khi XOR lại thì nó sẽ bị triệt tiêu). Điều đó sẽ làm giảm số lượng message mình gửi cho server đi khá nhiều.

Sau khi truy vết lại được các message ban đầu thì việc đơn giản là gửi nó cho server và lấy flag :D.

**Note**: Nếu thuật toán trên không tìm được mảng $basis$ thì random lại 500 vector khác và thực hiện lại thuật toán (xác suất không tìm được mảng $basis$ sau 10 lần là cực kì bé).

Code:

from pwn import *
from hashlib import *
from os import urandom
from Crypto.Util.number import *

basis = [0] * 256
lst = []
for i in range(256):
    lst.append([])

def Insert_Vector(mask):
    used = {mask}  # used: lưu lại các giá trị hash ban đầu mà nó xuất hiện lẻ lần
    for i in range(256):
        if (mask & (1 << i)) == 0:
            continue

        if not basis[i]:
            lst[i].clear()
            for v in used:
                lst[i].append(v)
            basis[i] = mask
            return

        for v in lst[i]:
            if v in used:
                used.remove(v)
            else:
                used.add(v)
        mask ^= basis[i]

def Check_Xor(mask, basis):
    idx = []
    for i in range(256):
        if (mask & (1 << i)) == 0:
            continue

        if not basis[i]:
            return []

        idx.append(i)
        mask ^= basis[i]
    return idx

origin = {}
for i in range(500):
    msg = urandom(32)
    hash_val = int(sha256(msg).hexdigest(), 16)
    origin[hash_val] = msg.hex()
    Insert_Vector(hash_val)

conn = remote("localhost", 4000, level = 'debug')
conn.recvuntil("such that \\bigoplus_i SHA256(M_i) = ")
target = conn.recvline().decode()[2:-1]
target = int(target, 16)

idx = Check_Xor(target, basis)

# chỉ chọn các message ban đầu xuất hiện lẻ lần
messages = set()
for i in idx:
    for v in lst[i]:
        if not v in messages:
            messages.add(v)
        else:
            messages.remove(v)

for msg in messages:
    conn.recvuntil(">>> ")
    conn.sendline(origin[msg])
conn.recvuntil(">>> ")
conn.sendline("")
print(f"Flag: {conn.recvline()}")