Union CTF | Cr0wn St3rling

#UnionCTF

#!/usr/bin/env python3

from secrets import flag, musical_key
from Crypto.Util.number import isPrime
import math


def sieve_for_primes_to(n):
    # Copyright Eratosthenes, 204 BC
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1, limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i > 0]


def is_quasi_prime(n, primes):
    # novel class of semi-prime numbers
    # https://arxiv.org/pdf/1903.08570.pdf
    p2 = 0
    for p1 in primes:
        if n % p1 == 0:
            p2 = n//p1
            break
    if isPrime(p2) and not p1 in [2, 3] and not p2 in [2, 3]:
        return True
    return False


def bbp_pi(n):
    # Bailey-Borwein-Plouffe Formula
    # sounds almost as cool as Blum-Blum-Shub
    # nth hex digit of pi
    def S(j, n):
        s = 0.0
        k = 0
        while k <= n:
            r = 8*k+j
            s = (s + pow(16, n-k, r) / r) % 1.0
            k += 1
        t = 0.0
        k = n + 1
        while 1:
            newt = t + pow(16, n-k) / (8*k+j)
            if t == newt:
                break
            else:
                t = newt
            k += 1
        return s + t

    n -= 1
    x = (4*S(1, n) - 2*S(4, n) - S(5, n) - S(6, n)) % 1.0
    return "%02x" % int(x * 16**2)


def digital_root(n):
    # reveals Icositetragon modalities when applied to Fibonacci sequence
    return (n - 1) % 9 + 1 if n else 0


def fibonacci(n):
    # Nature's divine proportion gives high-speed oscillations of infinite
    # wave values of irrational numbers
    assert(n >= 0)
    if n < digital_root(2):
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


def is_valid_music(music):
    # Leverage music's infinite variability
    assert(all(c in "ABCDEFG" for c in music))


def is_valid_number(D):
    # Checks if input symbolizes the digital root of oxygen
    assert(8==D)


def get_key(motif):
    is_valid_music(motif)
    is_valid_number(len(motif))
    # transpose music onto transcendental frequencies
    indexes = [(ord(c)-0x40)**i for i, c in enumerate(motif)]
    size = sum(indexes)
    assert(size < 75000) # we will go larger when we have quantum
    return indexes, size


def get_q_grid(size):
    return [i for i in range(size) if is_quasi_prime(i, sieve_for_primes_to(math.floor(math.sqrt(size))+1))]


if __name__ == "__main__":
    print("[+] Oscillating the key")
    key_indexes, size = get_key(musical_key)
    print("[+] Generating quasi-prime grid")
    q_grid = get_q_grid(size)
    # print(f"indexes: {key_indexes}  size: {size}  len(q_grid): {len(q_grid)}")

    out = []
    for i, p in enumerate(flag):
        print(f"[+] Entangling key and plaintext at position {i}")
        index = key_indexes[i % len(key_indexes)] * fibonacci(i)
        q = q_grid[index % len(q_grid)]
        key_byte_hex = bbp_pi(q)
        # print(f"index: {index:10}  fib: {fibonacci(i):10}  q-prime: {q:10}  keybyte: {key_byte_hex:10}")
        out.append(ord(p) ^ int(key_byte_hex, 16))

    print(f"[+] Encrypted: {bytes(out).hex()}")

• 何らかのテーブルを作り table[i] と flag[i] をxor して暗号化している

• テーブルは musical_key をもとに作られる

• musical_key は ABCDEFG の 7種類のアルファベットを使った8文字であり 通りある

• ただし、 indexes = [(ord(c)-0x40)**i for i, c in enumerate(motif)] を見るとわかるように のとき indexes[i] == 0 なので実質 通り

鍵の計算を高速化して全探索では少し遅すぎるので、計算の特性や既知の情報（フラグは union{ からはじまるなど）を活かして探索量を減らす必要がある

目下問題になるのは q_grid のサイズがわからないこと、もっと言えば、get_q_gridに渡しているsizeの値がわからないこと。ただ、先頭の5文字しか考えないのであれば、size はいくら大きくても で2801、 indexの値も程度までにしかならず、size には適当に大きな値を入れておけば、先頭5文字を決定することができる。（ここで、 という観察が必要になる）

先頭5文字が決まれば、あとは全探索で良さそう

#!/usr/bin/env python3
from Crypto.Util.number import isPrime
import math
from functools import lru_cache
from itertools import product


def sieve_for_primes_to(n):
    # Copyright Eratosthenes, 204 BC
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1, limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i > 0]


def is_quasi_prime(n, primes):
    # novel class of semi-prime numbers
    # https://arxiv.org/pdf/1903.08570.pdf
    p2 = 0
    for p1 in primes:
        if n % p1 == 0:
            p2 = n//p1
            break
    if isPrime(p2) and not p1 in [2, 3] and not p2 in [2, 3]:
        return True
    return False


@lru_cache(maxsize=100000)
def bbp_pi(n):
    # Bailey-Borwein-Plouffe Formula
    # sounds almost as cool as Blum-Blum-Shub
    # nth hex digit of pi
    def S(j, n):
        s = 0.0
        k = 0
        while k <= n:
            r = 8*k+j
            s = (s + pow(16, n-k, r) / r) % 1.0
            k += 1
        t = 0.0
        k = n + 1
        while 1:
            newt = t + pow(16, n-k) / (8*k+j)
            if t == newt:
                break
            else:
                t = newt
            k += 1
        return s + t

    n -= 1
    x = (4*S(1, n) - 2*S(4, n) - S(5, n) - S(6, n)) % 1.0
    return "%02x" % int(x * 16**2)


def digital_root(n):
    # reveals Icositetragon modalities when applied to Fibonacci sequence
    return (n - 1) % 9 + 1 if n else 0


@lru_cache(maxsize=100000)
def fibonacci(n):
    # Nature's divine proportion gives high-speed oscillations of infinite
    # wave values of irrational numbers
    assert(n >= 0)
    if n < digital_root(2):
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


def is_valid_music(music):
    # Leverage music's infinite variability
    assert(all(c in "ABCDEFG" for c in music))


def is_valid_number(D):
    # Checks if input symbolizes the digital root of oxygen
    assert(8==D)


def get_key(motif):
    is_valid_music(motif)
    is_valid_number(len(motif))
    # transpose music onto transcendental frequencies
    indexes = [(ord(c)-0x40)**i for i, c in enumerate(motif)]
    size = sum(indexes)
    assert(size < 75000) # we will go larger when we have quantum
    return indexes, size


def get_q_grid(size):
    return [i for i in range(size) if is_quasi_prime(i, sieve_for_primes_to(math.floor(math.sqrt(size))+1))]


def main():
    with open("output.txt") as f:
        output = bytes.fromhex(f.read())

    max_index = 75000  # some large size
    q_grid = get_q_grid(max_index)

    actual_key = "A" # key[0] is arbitrary
    flag_head = b"union"

    # bruteforce first 5bytes
    for i in range(len(flag_head)):
        if i == 0:  # key[0] is arbitrary
            continue

        cands = []
        for k in "ABCDEFG":
            index = (ord(k) - 0x40)**i * fibonacci(i)
            assert index < max_index
            q = q_grid[index]
            key_byte = bbp_pi(q)
            if output[i] == flag_head[i] ^ int(key_byte, 16):
                cands.append(k)

        assert len(cands) == 1
        actual_key += cands[0]
        print("[+] key: {}".format(actual_key))


    # bruteforce last 3bytes
    for keys in product("ABCDEFG", repeat=3):
        key = actual_key + "".join(keys)
        print("[+] trial key: {}".format(key))
        try:
            key_indexes, size = get_key(key)
        except AssertionError:
            continue
        q_grid = get_q_grid(size)

        flag = []
        for i, p in enumerate(output):
            index = key_indexes[i % len(key_indexes)] * fibonacci(i)
            q = q_grid[index % len(q_grid)]
            key_byte_hex = bbp_pi(q)
            flag.append(p ^ int(key_byte_hex, 16))
        print(repr(bytes(flag)))


if __name__ == "__main__":
    main()

[+] trial key: ACDADCFD
b'union{b45ed_oN_iRR3fut4bL3_m4th3m4G1c}'