Fastprocess#

문제의 f 함수를 다음과 같이 Python pseudocode로 옮길 수 있다.

1
def func_a(c):
2
    if c <= 0x1e:
3
        return 0
4
    if c == 31:
5
        return 1
6
    v7 = [0] * 0x100
7
    v7[31] = 1
8
    v2 = 1
9
    v4 = 0
10
    for _ in range(32, c + 1):
11
        v6 = v2
12
        v3 = modsub(v2, v7[v4], 2 ** 64)
13
        v7[v4] = v6
14
        v2 = modadd(v6, v3, 2 ** 64)
15
        v4 = (v4 + 1) & 0x1f
16
    return v7[(v4 + 31) & 0x1f]

이 경우 시간 복잡도는 O(c) 이며 마지막 Hard 난이도를 통과할 수 없다. 하지만 함수가 피보나치를 닮아 있으니 행렬 제곱으로 환원할 수 있다. 이때 시간 복잡도는 O(log c) 가 된다.

1
def func_a_log(c: int) -> int:
2
    # base cases
3
    if c <= 30:
4
        return 0
5
    if c == 31:
6
        return 1
7
    mask = (1 << 64) - 1
8
    dim = 33
9

10
    M = [[0] * dim for _ in range(dim)]
11
    M[0][0]   = 2               # coefficient of X_n
12
    M[0][32]  = mask            # -1 mod 2^64
13
    for i in range(1, dim):
14
        M[i][i-1] = 1           # shifting rows
15
    def mat_mult(A, B):
16
        C = [[0] * dim for _ in range(dim)]
17
        for i in range(dim):
18
            Ai, Ci = A[i], C[i]
19
            for k, a in enumerate(Ai):
20
                if a:
21
                    rowB = B[k]
22
                    mul  = a
23
                    for j in range(dim):
24
                        Ci[j] = (Ci[j] + mul * rowB[j]) & mask
25
        return C
26

27
    def mat_pow(mat, exp):
28
        R = [[0] * dim for _ in range(dim)]
29
        for i in range(dim):
30
            R[i][i] = 1
31
        base = mat
32
        while exp > 0:
33
            if exp & 1:
34
                R = mat_mult(R, base)
35
            base = mat_mult(base, base)
36
            exp >>= 1
37
        return R
38

39
    P = mat_pow(M, c - 32)
40
    return (P[0][0] + P[0][1]) & mask

1
wane@wane:~/Hacking/ctf/lake25f/badp$ sha256sum solve1.py
2
74d8835780ade07f7407ad71cfe3f69a64393a4b9ab5afac8991209bb3afc1b4  solve1.py

퍼블 먹었다.

Jump Around#

모든 코드 조각을 쪼개놓는 난독화를 해 놓은 것을 알 수 있다. 디컴파일러를 작성하지 않아도 문제가 꽤나 정직한 AES라서 피지컬으로 극복이 된다.

1
wane@wane:~/Hacking/ctf/lake25f/ja$ sha256sum test.py
2
496dfe17ac0b82f355e4d58dd7c1e20685679e845e08390c80d677dd85a72092  test.py

Hygeine#

특이한 문제이다. 시스템 해킹과 접목한 문제인 것을 알 수 있다. 우선 문제에서 제공하는 암호화 함수는 다음과 같다.

1
def crypt(plain, counter=0):
2
    key = b"???" # Originally random.
3
    nonce = b"\x00" * 8 # 고정
4
    cipher = ChaCha20.new(key=key, nonce=nonce)
5
    cipher.seek(counter * 64)
6
    ciphertext = cipher.encrypt(plain)
7
    return ciphertext

우리가 지정할 수 있는 것은 counter 와 plaintext 이지만, counter 의 범위는 3 이상이여야 한다. counter를 조작하여 임의의 암호문에 대해 평문을 복호화할 수 있지만 우리가 원하는 플래그는 블록 1과 2에 있으므로 우리는 원래대로라면 이 문제를 풀 수 없다.

신기한 점은 counter가 3일 때 모든 바이트가 0이여야 하지만 실제로 랜덤한 주소가 릭이 되고 있음을 확인하였다. 이는 스택에 정리되지 않고 잔류하는 바이트들이 정보를 형성한 것으로, 이것을 통해 문제를 풀 수 있다.

실제로 스택을 조사하면 잔류하는 키를 찾을 수 있다. 이를 통해 복호화하면 된다.

1
wane@wane:~/Hacking/ctf/lake25f/hyg$ sha256sum a.py
2
3753fc23347be4e569f1516cee29da1fc06d8a7895a3edd1e43645a4cb8a7621  a.py