picoCTF2024(Crypto) Writeup
学校の後輩と出場し、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の暗号文は
と表すことができ、mが平文、e,Nが公開鍵となる。ただし、e,Nは今回の問題ではわからない。
代わりに好きな平文を暗号化することが可能である。
例えば、平文50を暗号化しようとすると、
となる。ここで、
となる
と変形ができる。
一般的に、RSAの復号化には、秘密鍵dを指数にすればよい。すなわち、
である。
このことから、
となる。よって、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などで調査した結果、以下が判明しました。
- 作成している行列はヴァンデルモンドの行列式という。
- ラグランジュ補間を使うと良さそう。
しかし、ラグランジュ補間はデフォルトで
なにか良い方法はないかと探していたがタイムアップだった。
解法(他のWriteupsを参考にした)
ラグランジュ補間までは良かった。
参加者のWriteupを見ていると、ラグランジュ補間計算量が
さらに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}
Discussion