# Aero CTF 2022 - Crypto
## Astronaut

Đầu tiên khi giải nén ra thì sẽ có 1 file python và 1 file text
- astronaut.py:

#!/usr/bin/env python3
import os
import random
from typing import List, Generator

def flight(galaxy: List[int], black_holes: List[int]) -> Generator[int, None, None]:
    while True:
        yield (
            black_holes := black_holes[1:] + [sum(x * y for x, y in zip(galaxy, black_holes))]
        )[0]

def main():
    rnd = random.SystemRandom(1337)
    limit = 1000
    galaxy = [rnd.randrange(0, limit) for _ in range(16)]
    black_holes = [rnd.randrange(0, limit) for _ in range(16)]
    emotions = os.getenv('FLAG').strip()
    emptiness = '\0' * 64
    message = (emotions + emptiness).encode()
    astronaut = flight(galaxy, black_holes)
    for memory in message:
        print(memory ^ next(astronaut) % limit, end = ' ')

if __name__ == '__main__':
    main()

- output.txt:

676 137 333 207 646 118 386 547 92 567 163 866 25 181 485 262 910 3 225 385 784 792 95 810 1019 500 527 442 693 293 236 372 829 551 211 726 217 932 317 521 129 4 285 964 876 972 747 361 136 835 657 138 731 684 831 525 0 426 989 129 674 192 412 187 936 652 559 257 991 354 44 759 599 383 801 110 744 771 163 798 406 493 161 991 737 908 340 733 746 944 629 554 559 545 978 380

Đọc file nguồn 1 chút, ta thấy bài này sử dụng `Random.SystemRandom()` để tạo ra 2 mảng `black_holes` và `galaxy` làm tham số cho hàm `flight` để tạo ra 1 hàm sinh số với `yield` rồi sinh các số ra để **XOR** `FLAG` sau khi được chia dư với `1000`.

Tiếp đến mình phân tích hàm `fligt` để xem coi hàm này tạo ra output như thế nào.

def flight(galaxy: List[int], black_holes: List[int]) -> Generator[int, None, None]:
    while True:
        yield (
            black_holes := black_holes[1:] + [sum(x * y for x, y in zip(galaxy, black_holes))]
        )[0]

`yield` sẽ trả về giá trị và ở lần gọi tiếp theo sẽ chạy tiếp thay vì chạy lại từ đầu nên mình mới nói hàm `flight` là 1 hàm sinh số. Vậy số đó được sinh ra thế nào?

while True:
    newnum = sum(x * y for x, y in zip(galaxy, black_holes))
    black_holes = black_holes[1:].append(newnum)
    yield black_holes[0]

Dòng `yield` trong source khá là viết tắt nên mình đã rút gọn lại như trên cho dễ hiểu. Đoạn code hoạt động như sau:

1. Tính tích vô hướng của 2 mảng trên
2. Lấy toàn bộ phần tử của của mảng `black_holes` trừ phần tử đầu tiên
3. Thêm kết quả vừa tính đc vào cuối mảng ở bước 2 và tạo thành mảng `black_holes` mới
4. Trả về phần tử phần tử đầu tiên của `black_holes` vừa tạo
5. Lặp lại bước 1 nếu được gọi tiếp

Tóm lại là phần tử sinh ra tiếp theo sẽ có công thức:
$$
\sum_{i=1}^{16} b_i*g_i = b_{16}'
$$
$\forall$ b~i~, g~i~ là phần tử thứ *i* của `black_holes` và`galaxy`

Như vậy chỉ cần tìm được giá trị của mảng `galaxy` và có được 16 phần tử của mảng `black_holes`, ta sẽ hoàn toàn kiểm soát được số được sinh tiếp theo và thậm chí là cả phần tử bị xoá trước đó của `black_holes` như sau:
$$
\begin{align}
b_1g_1+b_2g_2+\dots+b_{16}g_{16} & = b_16' \\
b_1 & =\frac{b_16'-\left(b_2g_2+\dots+b_{16}g_{16}\right)}{g_1}
\end{align}
$$

Đọc lại hàm `main` thì mình thấy có 1 đoạn pad thêm 64 bytes `b'0'` mà trong phép toán **XOR**, mọi số `^` với `0` đều bằng `0`
=> Đề leak cho chúng ta tới `64` số sinh ra gần nhất của`flight` sau khi chia dư `1000`. Quá ngon :smiley_cat:

Mặc dù số bị leak không trọn vẹn nhưng mình vẫn bảo 'ngon' là vì 2 tính chất sau của đồng dư thức:
$$
\begin{align}
a + b\equiv \left(a\bmod m + b\bmod m \right)\pmod m \\
ab\equiv (a\bmod m)(b\bmod m)\pmod m
\end{align}
$$

Việc chia dư trước hay sau đều sẽ trả về 1 kết quả do đó cái này chỉ cần lưu ý mọi phép toán đều phải được thực thi trong vành hữu hạn `1000` thì kết quả sẽ không ảnh hưởng

Khi đã có tới 64 phần tử thì việc lập ra 16 phương trình để giải hệ là quá đơn giản. Do đó có thể nói ta đã bỏ túi mảng `galaxy` rồi :smiling_face_with_smiling_eyes_and_hand_covering_mouth:.
Mình sẽ sử dụng ==sagemath== để code bài này. Bắt đầu code thôi!

Đầu tiên lấy 64 số cuối ra 1 mảng mới.

a='676 137 333 207 646 118 386 547 92 567 163 866 25 181 485 262 910 3 225 385 784 792 95 810 1019 500 527 442 693 293 236 372 829 551 211 726 217 932 317 521 129 4 285 964 876 972 747 361 136 835 657 138 731 684 831 525 0 426 989 129 674 192 412 187 936 652 559 257 991 354 44 759 599 383 801 110 744 771 163 798 406 493 161 991 737 908 340 733 746 944 629 554 559 545 978 380'.split(' ')
s=list(map(int, a)) 
need=s[-64:]
print(need)

[829, 551, 211, 726, 217, 932, 317, 521, 129, 4, 285, 964, 876, 972, 747, 361, 136, 835, 657, 138, 731, 684, 831, 525, 0, 426, 989, 129, 674, 192, 412, 187, 936, 652, 559, 257, 991, 354, 44, 759, 599, 383, 801, 110, 744, 771, 163, 798, 406, 493, 161, 991, 737, 908, 340, 733, 746, 944, 629, 554, 559, 545, 978, 380]

Như mình đã nói ở trên nên mình sẽ tạo 1 vành hữu hạn`1000` cho mọi phép tính `1000`.

Z=Zmod(1000)

Tiếp theo sẽ là giải hệ phương trình 16 ẩn tìm mảng `galaxy`. Cách giải hệ thì có nhiều cách, đối với mình thì mình sẽ giải bằng ma trận. Tạo 2 ma trận `A`~16x16~ là các hệ số của hệ phương trình, `B`
~16x1~ với mỗi dòng là kết quả của từng phương trình trong `A`. Mảng `galaxy` cần tìm là mảng `x` sao cho $A\times x = B$. Tương đương với hệ:

$$
\left\{
\begin{array}{c}
A_{11}x_1+A_{12}x_2+A_{13}x_3+\cdots + A_{116}x_{16} &= B_1 \\
A_{21}x_1+A_{22}x_2+A_{23}x_3+\cdots + A_{216}x_{16} &= B_2 \\
A_{31}x_1+A_{32}x_2+A_{33}x_3+\cdots + A_{316}x_{16} &= B_3 \\
\vdots \\
A_{161}x_1+A_{162}x_2+A_{163}x_3+\cdots + A_{1616}x_{16} &= B_{16} \\
\end{array}
\right.
$$

Ta có:
$$
\begin{align}
A\times x &= B \\
A^{-1}\times A\times x &= A^{-1}\times B \\
x &= A^{-1}\times B
\end{align}
$$

A=[]
B=[]
for i in range(16):
    A.append(need[i:i+16])
    B.append([need[i+16]])
Z=Zmod(1000)
A=matrix(Z, A)
B=matrix(Z, B)
x=[i[0] for i in A^(-1)*B]
print(x)

[971, 666, 498, 123, 902, 388, 24, 658, 307, 253, 477, 830, 546, 974, 328, 699]

Sau khi có được mảng `galaxy`, bắt đầu từ 16 số bị leak gần nhất mình sẽ áp dụng công thức đã trình bày ở trên và bắt đầu khôi phục lại toàn bộ 80 số trước đó (tổng độ dài trong file output.txt là 96 số).

state=s[-16:]
for i in range(80):
    tmp=sum(a*b for a,b in zip(x[1:],state[:15]))
    state = [(state[15] - tmp)/x[0]]+state
print(state)

[741, 236, 319, 160, 765, 58, 452, 624, 14, 616, 202, 785, 70, 129, 393, 369, 954, 122, 146, 478, 885, 812, 44, 851, 932, 390, 574, 477, 733, 337, 211, 265, 829, 551, 211, 726, 217, 932, 317, 521, 129, 4, 285, 964, 876, 972, 747, 361, 136, 835, 657, 138, 731, 684, 831, 525, 0, 426, 989, 129, 674, 192, 412, 187, 936, 652, 559, 257, 991, 354, 44, 759, 599, 383, 801, 110, 744, 771, 163, 798, 406, 493, 161, 991, 737, 908, 340, 733, 746, 944, 629, 554, 559, 545, 978, 380]

Như vậy là mình đã khôi phục được toàn bộ các số được sinh ra. Bỏ 64 số cuối là phần được leak ra thì 32 số đầu chính là số được **XOR** với các chữ cái trong `FLAG`.

flag =''
for a, b in zip(state[:32], s[:32]):
    flag += chr(int(a)^^int(b)) 
print(flag)

Aero{LFSR_is_4lw4ys_e4sy_r1ght?}

> ^^ mới là XOR trong sagemath không giống như python gốc vì ^ được định nghĩa là lũy thừa

Flag cần tìm là: ==Aero{LFSR_is_4lw4ys_e4sy_r1ght?}==.

Vậy là đã xong challenge Crypto duy nhất của Aero CTF 2022 :smile: . Đánh giá của mình là câu này khá dễ nếu bạn hiểu được lý thuyết đồng dư và có kiến thức về việc xử lý các phép toán trên trường hoặc vành số nguyên hữu hạn.