kitctf 中的 crypto 題目

One Trick Pony

題目

I know a few secrets about this KAsino. But they would not be secrets if a shared them with everybody, so of course I do not share them in plaintext. Good luck getting past my information-theoretic secure encryption.

This challenge is the first from a set of two challenges.

nc kitctf.me 12345

附件

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main() {
    char* secret_msg = "<redacted>";
    size_t msg_len = strlen(secret_msg);


    unsigned char* random_bytes = malloc(msg_len);
    for (size_t i = 0; i < msg_len; i++) {
        random_bytes[i] = rand();
    }

    unsigned char* enc = malloc(msg_len);
    for (size_t i = 0; i < msg_len; i++) {
        enc[i] = secret_msg[i] ^ random_bytes[i];
    }

    printf("This is my message to you: ");
    for (size_t i = 0; i < msg_len; i++) {
        printf("%02X", enc[i]);
    }
    printf("\n");
}

解題思路

nc kitctf.me 12345 之後，拿到以下字串。

33AE0C532293259809A0DBC89A928D235CAB3AD86F8082AD15355C0D56EDE9F207412DC64431D73F053B6461379B3FB6C7D7EDA9FFD0273F2ED61C28521DB1EE17814A8124808E091E7811E2CAAF04FBEA183F4285C048DB46C01C279879A928226D973793C08A71B87D979D76544CE119BCE109BD8F39E4DDEA3CF1EEDFAEC036DC937D

看似已經沒有其他東西了，但在使用rand();的情況下，我在gcc中測試發現不論版本每次運行中輸出的值都一樣，所以也可以拿到一串字串。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main() {
    char* secret_msg = "<redacted>";
    size_t msg_len = 132;


    unsigned char* random_bytes = malloc(msg_len);
    for (size_t i = 0; i < msg_len; i++) {
        random_bytes[i] = rand();
    }

    printf("This is my message to you: ");
    for (size_t i = 0; i < msg_len; i++) {
        printf("%02X", random_bytes[i]);
    }
    printf("\n");
}

0x67C6697351FF4AEC29CDBAABF2FBE3467CC254F81BE8E78D765A2E63339FC99A66320DB73158A35A255D051758E95ED4ABB2CDC69BB454110E827441213DDC8770E93EA141E1FC673E017E97EADC6B968F385C2AECB03BFB32AF3C54EC18DB5C021AFE43FBFAAA3AFB29D1E6053C7C9475D8BE6189F95CBBA8990F95B1EBF1B305EFF700

最終就很簡單了，依照 One-time pad 的特性。

$\text{if a or b = c,} \\ \text{then a = b or c, b = a or c}$

解答

from Crypto.Util.number import long_to_bytes

a = 0x33AE0C532293259809A0DBC89A928D235CAB3AD86F8082AD15355C0D56EDE9F207412DC64431D73F053B6461379B3FB6C7D7EDA9FFD0273F2ED61C28521DB1EE17814A8124808E091E7811E2CAAF04FBEA183F4285C048DB46C01C279879A928226D973793C08A71B87D979D76544CE119BCE109BD8F39E4DDEA3CF1EEDFAEC036DC937D
b = 0x67C6697351FF4AEC29CDBAABF2FBE3467CC254F81BE8E78D765A2E63339FC99A66320DB73158A35A255D051758E95ED4ABB2CDC69BB454110E827441213DDC8770E93EA141E1FC673E017E97EADC6B968F385C2AECB03BFB32AF3C54EC18DB5C021AFE43FBFAAA3AFB29D1E6053C7C9475D8BE6189F95CBBA8990F95B1EBF1B305EFF700
a = long_to_bytes(a)
b = long_to_bytes(b)
print(a)
print(b)

for i in range(132):
    print(chr(a[i]^b[i]), end='')

Crooked Roulette

題目

Your Seatmate is sure to know what you have to bet in the next Round of K-Roulette™. But he does not have the guts to bet it himself. Can you make the bet and win it all?

nc kitctf.me 4545

附件

#!/usr/bin/env python3
from math import gcd
from Crypto.Util.number import getPrime,getRandomInteger

flag = "KITCTF{fake_flag}"

p = getPrime(512)
q = getPrime(512)
n = p*q
phi = (p-1)*(q-1)
e = getPrime(256)
while gcd(e, phi) != 1:
    e = getPrime(256)

d = pow(e, -1, phi)

def sign(m):
    return pow(m, d, n)

def check(c, m):
    return pow(c, e, n) == m

result = getRandomInteger(256)
print(f"Number of pockets: {hex(n)}")
print(f"The Manager told me, the roulette is crooked and will hit {hex(result)}")
base = 16
m2 = int(input(f"What should I bet? "), base)
if m2 % n == result:
    print("It is too obvious if I bet that")
else:
    s2 = sign(m2)
    print(f"My Signatur is {hex(s2)}")
    message = int(input(f"What do you want to bet? "), base)
    signature = int(input(f"Please sign your bet "), base)
    if result == message and check(signature, message):
        print(f"You Win: {flag}")
    else:
        print("You Lose") 

解題思路

這題是我很喜歡的一題，本來弄了一堆做法想要靠數學解都弄不出來，後來想說是不是我想得太複雜了，就慢慢看題目，突然想到應該是可以透過sign(m)這個方程來幫我算解答的。

後來也證實這題雖然看起來像RSA，但核心完全不一樣。

但直接代入題目顯示的result，會進到下面此行，從而不能取得flag。

if m2 % n == result:
    print("It is too obvious if I bet that")

後來我突然想到一個很漂亮的方法，把 n - result 塞進去，拉出來的 sign * -1 + n，就可以還原出真正的 sign，數學上的等價我就不證明了，大致等價於以下。

$m′≡(−1)*m\text{ mod }n\\ sign(m′)=(n−1)*sign(m)$

連上nc kitctf.me 4545之後，得到以下資訊。

Number of pockets: 0x86d14a294d4ecd523e982ab61b40e716b8a78ef12ce3e3367cc29396c45963a0c509c813159e7fa5418dca1e1ec5014e9653448b54ba6daa5aef6314f0d88cc16c5fca79a119b3766319f3e182d817acce98b4b4c296ca89827a8de5c7b91e0570f6abaec565224c6d8f0d93f0b32acc9f34bbb27216249517291bb0b3cd8f7f
The Manager told me, the roulette is crooked and will hit 0x512be59180e3aad84744af1f538316e9c4ead8e2a96f1e3a4b61a5a25a44aa8f
What should I bet? 0x86d14a294d4ecd523e982ab61b40e716b8a78ef12ce3e3367cc29396c45963a0c509c813159e7fa5418dca1e1ec5014e9653448b54ba6daa5aef6314f0d88cc16c5fca79a119b3766319f3e182d817acce98b4b4c296ca89827a8de5c7b91e051fcac61d44817774264a5e749d3013e2da49e2cfc8a7065acbc7760e5988e4f0
My Signatur is 0x6ec031cb61c947db7ee3b1998f7ecc547366f7049eb00ac71f0526ab8b75d0a828d31c92369599c92e3eed640796cd02fb708d051a1407191b2697c87708088ed518d533b1a0b6206272cdedb2075ca905f49d8fe096047368fc807a12fb69effbea54f8a657adb079ac7c031c9ac34a6280ed92c3d7fe8d8aeaf2c0ee0511e0
What do you want to bet? 0x512be59180e3aad84744af1f538316e9c4ead8e2a96f1e3a4b61a5a25a44aa8f
Please sign your bet 0x1811185deb858576bfb4791c8bc21ac2454097ec8e33d86f5dbd6ceb38e392f89c36ab80df08e5dc134edcba172e344b9ae2b7863aa666913fc8cb4c79d084329746f545ef78fd5600a725f3d0d0bb03c8a41724e200c616197e0d6bb4bdb415750c56b61f0d749bf3e29190d41867823cb3ce1fae3e26078c3e28efc5c87d9f
You Win: KITCTF{1nvers4_need_n0_k4y_101492}

解答

基本上照著1、2、3的順序填就好。

n = 0x86d14a294d4ecd523e982ab61b40e716b8a78ef12ce3e3367cc29396c45963a0c509c813159e7fa5418dca1e1ec5014e9653448b54ba6daa5aef6314f0d88cc16c5fca79a119b3766319f3e182d817acce98b4b4c296ca89827a8de5c7b91e0570f6abaec565224c6d8f0d93f0b32acc9f34bbb27216249517291bb0b3cd8f7f
result = 0x512be59180e3aad84744af1f538316e9c4ead8e2a96f1e3a4b61a5a25a44aa8f
print("1 : ", hex(n - result))
print("2 : ", result)
sign = 0x6ec031cb61c947db7ee3b1998f7ecc547366f7049eb00ac71f0526ab8b75d0a828d31c92369599c92e3eed640796cd02fb708d051a1407191b2697c87708088ed518d533b1a0b6206272cdedb2075ca905f49d8fe096047368fc807a12fb69effbea54f8a657adb079ac7c031c9ac34a6280ed92c3d7fe8d8aeaf2c0ee0511e0
print("3:", hex(n - sign))

Optimal Technology Project (未解決)

題目

There are some more secrets. Again, this one is encrypted. And I did not make the same mistake as last time. And I heard everything would be better in rust, so I will use that now.

This challenge is the second from a set of two challenges. (Due to problems with the third challenge, it won’t be released)

附件

use rand::{Rng, SeedableRng};
use rand::rngs::StdRng;
use std::time::SystemTime;

mod secret;
use crate::secret::{MSG};

fn main() {
    const MSG_LEN: usize = MSG.len();

    let t = SystemTime::now()
            .duration_since(SystemTime::UNIX_EPOCH)
            .expect("Duration since UNIX_EPOCH failed");
    let mut rng = StdRng::seed_from_u64(t.as_micros() as u64);
    let mut random_bytes = [0u8; MSG_LEN];
    for x in &mut random_bytes {
        *x = rng.gen::<u8>();
    }
    let flag_bytes  = MSG.as_bytes();

    let enc: Vec<_> = random_bytes.iter().zip(flag_bytes).map(|(x, y)| x ^ y).collect();

    let enc_b64 = base64::encode(enc);
    println!("Here is your message: {}", enc_b64);
}

解題思路

這題跟 One Trick Pony 很像，本來以為可以爆開的，但 rust 的 rand 在未定義時，會自動代入 seed = 1970 年以來到現在的毫秒數。

我後來想到 nc 拿到密文之後，再往前倒推窮舉硬猜系統當下時間，但不知道為什麼失敗了。

Prime Guesser 1

題目

The Prime Guesser 9000 is a simple game: Guess the prime and win it all. Due to quantum computers, we encrypted the number before handing it to you. Luckily you installed the smartEncrypt™ on your smartphone to encrypt numbers yourself. Win 100 Rounds to receive the big jackpot!

nc kitctf.me 4646

附件

#!/usr/bin/env python3

import numpy as np
from numpy.polynomial import polynomial as poly
import random

def polymul(x, y, modulus, poly_mod):
    return np.int64(
        np.round(poly.polydiv(poly.polymul(x, y) % modulus, poly_mod)[1] % modulus)
    )


def polyadd(x, y, modulus, poly_mod):
    return np.int64(
        np.round(poly.polydiv(poly.polyadd(x, y) % modulus, poly_mod)[1] % modulus)
    )

def gen_binary_poly(size):
    return np.random.randint(0, 2, size, dtype=np.int64)


def gen_uniform_poly(size, modulus):
    return np.random.randint(0, modulus, size, dtype=np.int64)


def gen_normal_poly(size):
    return np.int64(np.random.normal(0, 2, size=size))

def keygen(size, modulus, poly_mod):
    sk = gen_binary_poly(size)
    a = gen_uniform_poly(size, modulus)
    e = gen_normal_poly(size)
    b = polyadd(polymul(-a, sk, modulus, poly_mod), -e, modulus, poly_mod)
    return (b, a), sk

def encrypt(pk, size, q, t, poly_mod, pt):
    m = np.array([pt] + [0] * (size - 1), dtype=np.int64) % t
    delta = q // t
    scaled_m = delta * m  % q
    e1 = gen_normal_poly(size)
    e2 = gen_normal_poly(size)
    u = gen_binary_poly(size)
    ct0 = polyadd(
            polyadd(
                polymul(pk[0], u, q, poly_mod),
                e1, q, poly_mod),
            scaled_m, q, poly_mod
        )
    ct1 = polyadd(
            polymul(pk[1], u, q, poly_mod),
            e2, q, poly_mod
        )
    return (ct0, ct1)


def decrypt(sk, size, q, t, poly_mod, ct):
    scaled_pt = polyadd(
            polymul(ct[1], sk, q, poly_mod),
            ct[0], q, poly_mod
        )
    decrypted_poly = np.round(scaled_pt * t / q) % t
    return int(decrypted_poly[0])

def get_factors(number):
    factors = set()
    for i in [2, 3, 5, 7, 11, 13, 15, 17, 19, 23]:
        if i >= number:
            break
        if (number % i == 0):
            factors.add(i)
            other = number // i
            prime_set = get_factors(other)
            if len(prime_set) == 0:
                factors.add(other)
            else:
                for num in prime_set:
                    factors.add(num)
            
    return factors

# polynomial modulus degree
n = 2**6 # EXAMPLE !!! ON THE SERVER ARE OTHER NUMBERS
# ciphertext modulus
q = 2**20 # EXAMPLE !!! ON THE SERVER ARE OTHER NUMBERS
# plaintext modulus
t = 2**10 # EXAMPLE !!! ON THE SERVER ARE OTHER NUMBERS
# polynomial modulus
poly_mod = np.array([1] + [0] * (n - 1) + [1])
pk, sk = keygen(n, q, poly_mod)


def oracle(c):
    p = decrypt(sk, n, q, t, poly_mod, c)
    print(p == 0)

def smart_enrypt(p):
    if p > 0 and p < 25:
        return encrypt(pk, n, q, t, poly_mod, p)

def loose():
    print("Failed")
    exit()

def outputCipher(c):
    print(''.join([str(l) + "," for l in c[0]])[:-1])
    print(''.join([str(l) + "," for l in c[1]])[:-1])

for _ in range(100):
    number = random.randint(11, 200)
    
    ct = encrypt(pk, n, q, t, poly_mod, number)
    outputCipher(ct)
    while True:
        choice = int(input("What do you want?\n").strip())
        if choice == 0:
            number_input = int(input("What do you want to encrypt?\n").strip(), 10)
            if number_input > 20 or number_input < 1:
                print("Thats out of bound")
            else:
                outputCipher(smart_enrypt(number_input))
        elif choice == 1:
            cipher_input = input("What is the first part of the Cipher?\n").strip()
            c0 = [int(n, 10) for n in cipher_input.split(",")]
            cipher_input = input("What is the second part of the Cipher?\n").strip()
            c1 = [int(n, 10) for n in cipher_input.split(",")]
            c = (c0, c1)
            oracle(c)
        elif choice == 2:
            break
    
    real_factors = get_factors(number)
    primes = input("What are the factors?\n").strip()
    if len(primes) == 0:
        if len(real_factors) == 0:
            continue
        else:
            loose()

    primes_set = set()
    for num in primes.split(","):
        primes_set.add(int(num, 10))
    
    if not (real_factors == primes_set):
        loose()

print("You won: Flag")

解題思路

賽中看到檔案太長了，有點被繞暈就沒細看，星期天我就跑去找林妤瑄了，現在來補題消業障哇哇，還好系統都還開著

在重新做題的過程中，有參考 https://github.com/JoshuaTurner3/kitctfctf_2022，感謝他在我迷茫的時候給我了很多很多的思路。

實際運行起來的樣子如下。

725604,61748,736872,167264,726582,230045,684241,402364,500164,378821,676833,385962,883217,283011,821625,140155,818496,211240,1004947,476860,795144,628346,262435,659908,531596,453064,997759,725680,363241,37811,19872,2529,695247,348406,34052,930284,737477,690703,307210,155771,891828,214473,421622,962674,114283,878362,209636,158230,724381,10328,63827,815739,480336,540171,486032,507201,775681,388709,359443,853874,683789,506695,644574,119382
272313,686933,572275,728941,120913,719663,236207,699985,919947,400987,746845,590894,424709,992827,503516,859481,900467,44294,142993,899039,245844,382608,699096,429861,222196,893746,347212,250884,174694,675941,36680,576091,1027585,285770,632236,204018,975537,974106,455340,413858,730194,988460,235061,674460,357323,959157,239613,342672,798037,154907,969014,870285,717003,713114,609277,781704,320023,791527,130071,683095,223396,469920,226228,1006353
What do you want?

這裡在程式中的這個迴圈內。

while True:
    choice = int(input("What do you want?\n").strip())
    if choice == 0:
        number_input = int(input("What do you want to encrypt?\n").strip(), 10)
        if number_input > 20 or number_input < 1:
            print("Thats out of bound")
        else:
            outputCipher(smart_enrypt(number_input))
    elif choice == 1:
        cipher_input = input("What is the first part of the Cipher?\n").strip()
        c0 = [int(n, 10) for n in cipher_input.split(",")]
        cipher_input = input("What is the second part of the Cipher?\n").strip()
        c1 = [int(n, 10) for n in cipher_input.split(",")]
        c = (c0, c1)
        oracle(c)
    elif choice == 2:
        break

他的意思大概是這樣，輸入0時，可以給server一個1-20的數字加密，數字被加密後，會再全部輸出出來，大概長下面這樣。

What do you want?
0
What do you want to encrypt?
1
297546,894548,962397,632798,959320,389716,782894,244256,892723,534020,49760,208546,84828,801198,908730,1009738,565059,180967,268117,596152,788023,101575,509054,819493,758312,32607,414340,915833,843780,1047765,1048513,953350,727494,656769,387283,342312,542116,1011629,161946,30789,560224,881280,617889,690969,51193,802264,97521,841614,391192,736971,401794,154903,230990,485572,1031211,722401,234762,321451,1023873,1048122,773534,267151,788630,566988
1028112,1021826,866175,678874,719734,63464,934545,147031,87452,999046,942908,54279,861074,302974,808473,33251,389249,888962,343766,334198,333827,831235,981448,600307,67075,472428,638,337256,347730,887133,462562,951685,128271,370183,512643,715276,461479,957018,440753,115606,968993,858054,305873,660926,920597,1040339,233936,958199,862394,50361,923216,1013148,954379,348796,540653,1034910,285680,695212,697321,1037273,882961,253055,1030856,899596

輸入1的時候，要輸入兩串list給server，server會跑解密程式來比對兩串list解密出來的值是否為0，我丟輸入0時取得的密文，可想而知的失敗了，果然事情沒那麼簡單。

What do you want?
1
What is the first part of the Cipher?
297546,894548,962397,632798,959320,389716,782894,244256,892723,534020,49760,208546,84828,801198,908730,1009738,565059,180967,268117,596152,788023,101575,509054,819493,758312,32607,414340,915833,843780,1047765,1048513,953350,727494,656769,387283,342312,542116,1011629,161946,30789,560224,881280,617889,690969,51193,802264,97521,841614,391192,736971,401794,154903,230990,485572,1031211,722401,234762,321451,1023873,1048122,773534,267151,788630,566988
What is the second part of the Cipher?
297546,894548,962397,632798,959320,389716,782894,244256,892723,534020,49760,208546,84828,801198,908730,1009738,565059,180967,268117,596152,788023,101575,509054,819493,758312,32607,414340,915833,843780,1047765,1048513,953350,727494,656769,387283,342312,542116,1011629,161946,30789,560224,881280,617889,690969,51193,802264,97521,841614,391192,736971,401794,154903,230990,485572,1031211,722401,234762,321451,1023873,1048122,773534,267151,788630,566988
False

輸入2時，會跳出迴圈，進入以下程式碼。

real_factors = get_factors(number)
primes = input("What are the factors?\n").strip()
if len(primes) == 0:
    if len(real_factors) == 0:
        continue
    else:
        loose()

primes_set = set()
for num in primes.split(","):
    primes_set.add(int(num, 10))

if not (real_factors == primes_set):
    loose()

大概就是要連續猜對隨機生成數字的質數100次，在過程中可以一直重複跑0跟1來蒐集資訊。

接下來來看解密函數。

def polyadd(x, y, modulus, poly_mod):
    return np.int64(
        np.round(poly.polydiv(poly.polyadd(x, y) % modulus, poly_mod)[1] % modulus)
    )

def decrypt(sk, size, q, t, poly_mod, ct):
    scaled_pt = polyadd(
            polymul(ct[1], sk, q, poly_mod),
            ct[0], q, poly_mod
        )
    decrypted_poly = np.round(scaled_pt * t / q) % t
    return int(decrypted_poly[0])

整個程式太過複雜了，但幸運的是解密函數真正用到的東西並不多，並且只有解密的部分，不需要猜測種子等等東西，不過還是有一些全域變數影響解密。

# polynomial modulus degree
n = 2**6 # EXAMPLE !!! ON THE SERVER ARE OTHER NUMBERS
# ciphertext modulus
q = 2**20 # EXAMPLE !!! ON THE SERVER ARE OTHER NUMBERS
# plaintext modulus
t = 2**10 # EXAMPLE !!! ON THE SERVER ARE OTHER NUMBERS
# polynomial modulus
poly_mod = np.array([1] + [0] * (n - 1) + [1])
pk, sk = keygen(n, q, poly_mod)

然後就幹，輸光，去床上躺一下再說。

def keygen(size, modulus, poly_mod):
    sk = gen_binary_poly(size)
    a = gen_uniform_poly(size, modulus)
    e = gen_normal_poly(size)
    b = polyadd(polymul(-a, sk, modulus, poly_mod), -e, modulus, poly_mod)
    return (b, a), sk

接下來開始算初始值。

poly_mod = np.array([1] + [0] * (arrSize - 1) + [1])

q, t, sk 我是從這裡找到求解函數的。

接下來就可以在本地端從一開始給出的密碼開始算，然後我發現我Kubeflow還沒弄，先這樣哇哇，後續就是推算初始值和算完100輪他要什麼，但老實說這題我的能力不夠，在來一次賽中也解不出來，不過學到很多東西。