😽

picoCTF2024(Crypto) Writeup

2024/04/05に公開

crypto

picoctf

tech

学校の後輩と出場し、116位でした！僕は特にCrypto担当していたため、今回はCrypto問題のWriteupを書きました！

interencdec

Description

Can you get the real meaning from this file.
Download the file here.

解答

ファイル内には、以下の文字列が記されていた。
YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclgya3lNRFJvYTJvMmZRPT0nCg==

==で終わっていることから、base64だと予測しデコード。
b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrX2kyMDRoa2o2fQ=='

まだbase64だと思い再度デコードする。

wpjvJAM{jhlzhy_k3jy9wa3k_i204hkj6}

文字列と大文字小文字からROT13だろうと思いずらしてみる。
実際は19文字をずらすとフラグが現れた。
picoCTF{caesar_d3cr9pt3d_b204adc6}

Custom encryption

Description

Can you get sense of this code file and write the function that will decode the given encrypted file content.
Find the encrypted file here flag_info and code file might be good to analyze and get the flag.

プログラムはPython形式で渡され、フラグ情報には、a,bと暗号文が一緒に書かれていた。

from random import randint
import sys


def generator(g, x, p):
    return pow(g, x) % p


def encrypt(plaintext, key):
    cipher = []
    for char in plaintext:
        cipher.append(((ord(char) * key*311)))
    return cipher


def is_prime(p):
    v = 0
    for i in range(2, p + 1):
        if p % i == 0:
            v = v + 1
    if v > 1:
        return False
    else:
        return True
def dynamic_xor_encrypt(plaintext, text_key):
    cipher_text = ""
    key_length = len(text_key)
    for i, char in enumerate(plaintext[::-1]):
        key_char = text_key[i % key_length]
        encrypted_char = chr(ord(char) ^ ord(key_char))
        cipher_text += encrypted_char
    return cipher_text


def test(plain_text, text_key):
    p = 97
    g = 31
    if not is_prime(p) and not is_prime(g):
        print("Enter prime numbers")
        return
    a = randint(p-10, p)
    b = randint(g-10, g)
    print(f"a = {a}")
    print(f"b = {b}")
    u = generator(g, a, p)
    v = generator(g, b, p)
    key = generator(v, a, p)
    b_key = generator(u, b, p)
    shared_key = None
    if key == b_key:
        shared_key = key
    else:
        print("Invalid key")
        return
    semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
    cipher = encrypt(semi_cipher, shared_key)
    print(f'cipher is: {cipher}')


if __name__ == "__main__":
    message = sys.argv[1]
    test(message, "trudeau")


a = 94
b = 29
cipher is: [260307, 491691, 491691, 2487378, 2516301, 0, 1966764, 1879995, 1995687, 1214766, 0, 2400609, 607383, 144615, 1966764, 0, 636306, 2487378, 28923, 1793226, 694152, 780921, 173538, 173538, 491691, 173538, 751998, 1475073, 925536, 1417227, 751998, 202461, 347076, 491691]

暗号化のために二つの動作をしており、

dynamic_xor_encrypt関数で文字列とkey_charのXORをとっている
encrypt関数で1の暗号文に key*311を乗算している

が読み取れる。つまり、これらを逆順に行えば復号できる。

解法

encrypt関数の処理

encrypt関数の引数をみると、
cipher = encrypt(semi_cipher, shared_key)

と書かれており、shared_keyは

key = generator(v, a, p)
b_key = generator(u, b, p)

の2つが一致したときのkeyがshared_keyとなっている。
幸い、a,bはフラグ情報から、p,gはソースコードに書かれているため、u,vも求めることができる。
計算した結果、shared_keyは93だったため。91*311を暗号文から割ればOK

semi_flag = [c / (shared_key * 311) for c in cipher]

dynamic_xor_encrypt関数の処理

基本的には、関数の処理の逆を行えば復元ができる。
流れとしては、

暗号文の長さ取得
i%key_lengthに対応する文字を取得
対応する文字列と暗号文をXOR
配列に格納する

上記の流れを実装したプログラムは以下となる。

def decrypt(cipher_text, text_key):
    s= ""
    key_length = len(text_key)
    for i, char in enumerate(cipher_text):
        key = text_key[i % key_length]
        decrypted_char = chr(int(char) ^ ord(key)) 
        s += decrypted_char
    decrypted_text = s[::-1]  
    return decrypted_text

プログラム

上記のコードをまとめたプログラムは以下となる。

def decrypt(cipher_text, text_key):
    s= ""
    key_length = len(text_key)
    for i, char in enumerate(cipher_text):
        key = text_key[i % key_length]
        decrypted_char = chr(int(char) ^ ord(key)) 
        s += decrypted_char
    decrypted_text = s[::-1]  
    return decrypted_text


cipher = [260307, 491691, 491691, 2487378, 2516301, 0, 1966764, 1879995, 1995687, 1214766, 0, 2400609, 607383, 144615, 1966764, 0, 636306, 2487378, 28923, 1793226, 694152, 780921, 173538, 173538, 491691, 173538, 751998, 1475073, 925536, 1417227, 751998, 202461, 347076, 491691]
shared_key = 93
text_key = "trudeau"
semi_cipher = [c / (shared_key * 311) for c in cipher]
plain_text = decrypt(semi_cipher, text_key)
print(plain_text)

picoCTF{custom_d2cr0pt6d_751a22dc}

C3

Description

This is the Custom Cyclical Cipher!
Download the ciphertext here.
Download the encoder here.
Enclose the flag in our wrapper for submission. If the flag was "example" you would submit "picoCTF{example}".

暗号文は以下である。
DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl

添付されているconvert.pyは以下。

import sys
chars = ""
from fileinput import input
for line in input():
  chars += line

lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"

out = ""

prev = 0
for char in chars:
  cur = lookup1.index(char)
  out += lookup2[(cur - prev) % 40]
  prev = cur

sys.stdout.write(out)

for文内で、

lookup1に対してcharをインデックスとして取り出す
(cur - prev) % 40 で、平文の2文字間の差を計算
2の結果をインデックスとして出た結果を1文字ずつ結合

を実行して暗号化している。

なので、これの逆操作を行えばよい

lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"

s= 'DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl'

out = ""

prev = 0
for char in s:
    cur = lookup2.index(char)
    prev = (prev + cur) % len(lookup1)
    out += lookup1[prev]

print(out)

実行すると、以下のコードが表示された。

#asciiorder
#fortychars
#selfinput
#pythontwo

chars = ""
from fileinput import input
for line in input():
    chars += line
b = 1 / 1

for i in range(len(chars)):
    if i == b * b * b:
        print chars[i] #prints
        b += 1 / 1

コメントにself inputとpython2と書かれているので、inputにソースコードを渡しPython2で実行してみる。

└─$ python2 aaa.py aaa.py 
a
d
l
i
b
s

picoCTF{adlibs}

rsa_oracle

Description

Can you abuse the oracle?
An attacker was able to intercept communications between a bank and a fintech company. They managed to get the message (ciphertext) and the password that was used to encrypt the message.
After some intensive reconassainance they found out that the bank has an oracle that was used to encrypt the password and can be found here nc xxx. Decrypt the password and use it to decrypt the message. The oracle can decrypt anything except the password.

ファイルはsecret.encとpassword.encが添付されており、secret.encは暗号化されていた。

password.encには数字列が書かれており、RSAの暗号化結果だと予想する。
873224563026311790736191809393138825971072101706285228102516279725246082824238887755080848591049817640245481028953722926586046994669540835757705139131212
また、nc xxxをすると、RSAの暗号化、復号化をすることができるサーバにアクセスすることができる。ただし、passwordの数字列をそのまま復号化しようとするとエラーメッセージが出て復号化することができない。

*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you? 
E --> encrypt D --> decrypt. 
E
enter text to encrypt (encoded length must be less than keysize): aaaa
aaaa

encoded cleartext as Hex m: 61616161

ciphertext (m ^ e mod n) 5141811729664063726904087644156339603695714534222073457902142347660277161961771273446668176764058069336393335412428849448728024218484603068759595730524407

what should we do for you? 
E --> encrypt D --> decrypt. 
D
Enter text to decrypt: 873224563026311790736191809393138825971072101706285228102516279725246082824238887755080848591049817640245481028953722926586046994669540835757705139131212
Lol, good try, can't decrypt that for you. Be creative and good luck

what should we do for you? 
E --> encrypt D --> decrypt.

解法

Chosen Plaintext Attack(CPA)を考えると解くことができる。
まず、一般的に、RSAの暗号文は

C = m^e\mod(N)

と表すことができ、mが平文、e,Nが公開鍵となる。ただし、e,Nは今回の問題ではわからない。
代わりに好きな平文を暗号化することが可能である。

例えば、平文50を暗号化しようとすると、

C_x = 50^e\mod (N)

となる。ここで、

C_y = C_x * C

となる

C_y

を考える。すると、

C_y = 50^e * C = 50^e * m^e\mod(N)

と変形ができる。
一般的に、RSAの復号化には、秘密鍵dを指数にすればよい。すなわち、

C^d = (m^e)^d \equiv m\mod(N)

である。
このことから、

(C_y)^d = (50^e * m^e)^d =(50^e)^d ・(m^e)^d\equiv 50 * m\mod　N

となる。よって、50で除算することでmを求めることができる。

以上の操作を行ったプログラムを以下に示す。
何を入力したかは忘れたが、Hexで50になるように設定した。

a = 873224563026311790736191809393138825971072101706285228102516279725246082824238887755080848591049817640245481028953722926586046994669540835757705139131212 
b = 4499631234915012698453861238023214079343974969038366688081854806566195608247062767505103431144848763924885290143599253078838317570145351124171041575846246

print(a*b)

hex_number = "102cd549fbaab068951d"
divisor = 0x48656c6c6f 

decimal_number = int(hex_number, 16)

result_decimal = int(decimal_number / divisor)  

result_hex = hex(result_decimal)

print(result_hex)
# 0x3932643533 -> 92d53

Hexでは通らなくて少し戸惑ったが、PWなので文字列やんと気づいた。
後はPWを使って復号すればOK

openssl enc -d -aes-256-cbc -in secret.enc -out secret.txt

復号した結果以下のフラグを得られた。

 picoCTF{su((3ss_(r@ck1ng_r3@_92d53250}

flag_printer (Not Solve)

Description

I made a program to solve a problem, but it seems too slow :(
Download the program here.
Download the message here.

問題文と一緒にプログラムとメッセージが渡されました。

import galois
import numpy as np
MOD = 7514777789

points = []

for line in open('encoded.txt', 'r').read().strip().split('\n'):
    x, y = line.split(' ')
    points.append((int(x), int(y)))

GF = galois.GF(MOD)

matrix = []
solution = []
for point in points:
    x, y = point
    solution.append(GF(y % MOD))

    row = []
    for i in range(len(points)):
        row.append(GF((x ** i) % MOD))
    
    matrix.append(GF(row))

open('output.bmp', 'wb').write(bytearray(np.linalg.solve(GF(matrix), GF(solution)).tolist()[:-1]))

メッセージは約170万個の点であり、上記のコードで解き終わる頃には私は生きているのでしょうか。それよりも電気代が心配です。

処理の高速化などを行ってもよいですが、solveが少ないためそんな単純なことではないと予測できます。Googleなどで調査した結果、以下が判明しました。

作成している行列はヴァンデルモンドの行列式という。
ラグランジュ補間を使うと良さそう。

しかし、ラグランジュ補間はデフォルトで $O(N^2)$ のため、実際に実行しても終わらなさすぎて心配になり止めてしまった。
なにか良い方法はないかと探していたがタイムアップだった。

解法(他のWriteupsを参考にした)

ラグランジュ補間までは良かった。
参加者のWriteupを見ていると、ラグランジュ補間計算量が $O(N\log^2 N)$ で解けるみたい。
さらにDiscordで解いた人を見てみると、FLINで解いている人もいた。今回はFLINTを書いておく(ありがとうpetepriority)

#include <flint/nmod_poly.h>
#include <strings.h>
#include <stdlib.h>
#include <stdint.h>

#define NUM_POINTS 1769611
#define MOD 7514777789

int main() {
    int result = 0;

    mp_limb_t *x = malloc(NUM_POINTS * sizeof(mp_limb_t));
    mp_limb_t *y = malloc(NUM_POINTS * sizeof(mp_limb_t));

    FILE* f = fopen("encoded.txt", "r");
    for (int i = 0; i < NUM_POINTS; i++)
    {
        int matches = fscanf(f, "%lu %lu", &x[i], &y[i]);
        if (matches != 2) {
            printf("Error reading file\n");
            result = 1;
            goto cleanup;
        }
    }
    fclose(f);

    nmod_poly_t poly;
    nmod_poly_init(poly, MOD);

    nmod_poly_interpolate_nmod_vec_fast(poly, x, y, NUM_POINTS);

    int degree = nmod_poly_degree(poly);

    f = fopen("output_flint.bmp", "w");
    for (int i = 0; i < degree; i++) 
    {
        mp_limb_t coeff = nmod_poly_get_coeff_ui(poly, i);
        uint8_t byte = coeff & 0xFF;
        fwrite(&byte, sizeof(uint8_t), 1, f);
    }
    fclose(f);

    nmod_poly_clear(poly);

cleanup:
    free(x);
    free(y);
    return result;
}

30秒位で終わった。。。。

picoctf{i_do_hope_you_used_the_favorite_algorithm_of_every_engineering_student}

interencdec

Description

解答

Custom encryption

Description

解法

encrypt関数の処理

dynamic_xor_encrypt関数の処理

プログラム

C3

Description

rsa_oracle

Description

解法

flag_printer (Not Solve)

Description

解法(他のWriteupsを参考にした)

Discussion