picoCTF 2024：Cryptographyの全5問をやってみた（最後の2問は手つかず）

前回 は、picoCTF の picoCTF 2024 のうち、Forensics をやってみました。全8問のうち、最後の 2問は解けませんでした。

今回は、引き続き、picoCTF の picoCTF 2024 のうち、Cryptography というカテゴリの全5問をやっていきたいと思います。Easy が 1問、Medium が 3問、Hard が 1問です。

それでは、やっていきます。

• はじめに
• picoCTF 2024：Cryptography
  • interencdec（50ポイント）
    • Base64のデコード
    • シーザー暗号
  • Custom encryption（100ポイント）
  • C3（200ポイント）
  • rsa_oracle（300ポイント）
  • flag_printer（500ポイント）
• おわりに

はじめに

「セキュリティ」の記事一覧です。良かったら参考にしてください。

picoCTF の公式サイトは以下です。英語のサイトですが、シンプルで分かりやすいので困らずに進めることができます。

picoctf.com

それでは、やっていきます。

picoCTF 2024：Cryptography

ポイントの低い順にやっていきます。

interencdec（50ポイント）

Easy の問題です。ファイルが1つ（enc_flag）ダウンロードできます。

ファイルを開くと、YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclh6ZzVNR3N5TXpjNWZRPT0nCg== と書かれています。Base64 っぽいので、デコードしてみます。

うーん、違うようです。もう 1回 Base64 でデコードするといい感じになりました。

$ cat enc_flag | base64 -d
b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg5MGsyMzc5fQ=='

$ echo -n 'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg5MGsyMzc5fQ==' | base64 -d
wpjvJAM{jhlzhy_k3jy9wa3k_890k2379}

あとは、シーザー暗号ですかね。では、ASCIIコードの数値を求めます。7 を減算すれば良さそうです。

>>> ord('C'), ord('T'), ord('F')
(67, 84, 70)
>>> ord('J'), ord('A'), ord('M')
(74, 65, 77)

picoCTF{caesar_d6cr2pt6d_123d5602} だと思ったのですが、違いました。

Base64のデコード

ちょっと適当だったので、もうちょっと真面目に考えます。enc_flag に書かれている文字列は、70文字と == です。== は 4文字アライメントに不足していただけなので気にしないでいいです。Base64 は 6bit を 1文字で表すので、デコードすると、70文字×6bit=420bit になりますが、元の文字は 8bit なので、416bit で 4bit は 0 が足されただけです。最後の文字は g で、これは、2進数で 100000 を変換したものなので、この後ろの 4つの 0 は足されただけで気にしないでいいです。416bit は 52文字になります。しかし、b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg5MGsyMzc5fQ==' は 51文字しかありません。

うーん、困ったので、自分で base64 をデコードするプログラムを作りました。

def base64_decode_manual( ss ):
    
    print( f"len(ss)={len(ss)}" )
    
    table = {
        'A': "000000", 'B': "000001", 'C': "000010", 'D': "000011",
        'E': "000100", 'F': "000101", 'G': "000110", 'H': "000111",
        'I': "001000", 'J': "001001", 'K': "001010", 'L': "001011",
        'M': "001100", 'N': "001101", 'O': "001110", 'P': "001111",
        'Q': "010000", 'R': "010001", 'S': "010010", 'T': "010011",
        'U': "010100", 'V': "010101", 'W': "010110", 'X': "010111",
        'Y': "011000", 'Z': "011001", 'a': "011010", 'b': "011011",
        'c': "011100", 'd': "011101", 'e': "011110", 'f': "011111",
        'g': "100000", 'h': "100001", 'i': "100010", 'j': "100011",
        'k': "100100", 'l': "100101", 'm': "100110", 'n': "100111",
        'o': "101000", 'p': "101001", 'q': "101010", 'r': "101011",
        's': "101100", 't': "101101", 'u': "101110", 'v': "101111",
        'w': "110000", 'x': "110001", 'y': "110010", 'z': "110011",
        '0': "110100", '1': "110101", '2': "110110", '3': "110111",
        '4': "111000", '5': "111001", '6': "111010", '7': "111011",
        '8': "111100", '9': "111101", '+': "111110", '/': "111111",
    }
    
    # 1文字ずつ逆変換して6bitを連結する
    ret = ""
    for cc in ss:
        if cc == "=":  # = が来たら終了
            break
        ret += table[cc] # 逆変換した6bitを連結
    
    # 前から 8bit ずつで文字列を作る
    lst = []
    idx = 0
    while idx + 8 <= len(ret):
        lst.append( int(ret[idx:idx+8], base=2) ) # 2進数を10進数に変換して格納
        idx += 8
    
    # 余った分は 0 のはず
    assert int(ret[idx:], base=2) == 0, f"ret[idx:]={ret[idx:]}"
    
    ret = ""
    for ii, nn in enumerate(lst):
        if nn < 0x20 or nn >= 0x7F:
            print( f"ii={ii}, nn={nn:02X}" )
        else:
            ret += chr(nn)
    
    print( f"len(ret)={len(ret)}, ret={ret}" )

base64_decode_manual( "YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclh6ZzVNR3N5TXpjNWZRPT0nCg==" )
base64_decode_manual( "d3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg5MGsyMzc5fQ" )

実行してみます。なるほど、最後の 1文字は改行コードだったようです。

$ python tmp.py
len(ss)=72
ii=51, nn=0A
len(ret)=51, ret=b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg5MGsyMzc5fQ=='
len(ss)=46
len(ret)=34, ret=wpjvJAM{jhlzhy_k3jy9wa3k_890k2379}

シーザー暗号

シーザー暗号のところは、実装が間違えていました。数字と記号はそのままにしておくのが普通らしいです。

def str2int( ss, offset=0, num_disable=False ):
    
    lst = []
    for cc in ss:
        
        if cc == ' ':
            lst.append( ord(cc) )
        
        elif ('0' <= cc <= '9') and not num_disable:
            mm = (ord(cc) - ord('0') + offset) % (ord('9') - ord('0') + 1)
            lst.append( mm + ord('0') )
        
        elif 'A' <= cc <= 'Z':
            mm = (ord(cc) - ord('A') + offset) % (ord('Z') - ord('A') + 1)
            lst.append( mm + ord('A') )
        
        elif 'a' <= cc <= 'z':
            mm = (ord(cc) - ord('a') + offset) % (ord('z') - ord('a') + 1)
            lst.append( mm + ord('a') )
        
        else:
            
            lst.append( ord(cc) )
    
    print( f"str2int={lst}" )
    print( f"str2int={[hex(ii) for ii in lst]}" )
    
    return lst

def int2chr( lst ):
    
    ss = ""
    lst_ret = []
    for ii in lst:
        ss += chr(ii)
        lst_ret.append( chr(ii) )
    
    #print( lst_ret )
    print( f"int2chr={ss}" )
    
    return lst_ret

lst = str2int( "wpjvJAM{jhlzhy_k3jy9wa3k_890k2379}", -7, num_disable=True )
lst_ret = int2chr( lst )

実行します。

$ python tmp.py
str2int=[112, 105, 99, 111, 67, 84, 70, 123, 99, 97, 101, 115, 97, 114, 95, 100, 51, 99, 114, 57, 112, 116, 51, 100, 95, 56, 57, 48, 100, 50, 51, 55, 57, 125]
str2int=['0x70', '0x69', '0x63', '0x6f', '0x43', '0x54', '0x46', '0x7b', '0x63', '0x61', '0x65', '0x73', '0x61', '0x72', '0x5f', '0x64', '0x33', '0x63', '0x72', '0x39', '0x70', '0x74', '0x33', '0x64', '0x5f', '0x38', '0x39', '0x30', '0x64', '0x32', '0x33', '0x37', '0x39', '0x7d']
int2chr=picoCTF{caesar_d3cr9pt3d_890d2379}

picoCTF{caesar_d3cr9pt3d_890d2379} でした。

Custom encryption（100ポイント）

Medium の問題です。暗号化されたファイル（enc_flag）と、Pythonスクリプト（custom_encryption.py）がダウンロードできます。

enc_flag の中身は、以下です。

a = 97
b = 22
cipher is: [151146, 1158786, 1276344, 1360314, 1427490, 1377108, 1074816, 1074816, 386262, 705348, 0, 1393902, 352674, 83970, 1141992, 0, 369468, 1444284, 16794, 1041228, 403056, 453438, 100764, 100764, 285498, 100764, 436644, 856494, 537408, 822906, 436644, 117558, 201528, 285498]

Pythonスクリプトは以下です。

is_prime(p) は、引数で指定した p が、素数だったら True を返し、素数じゃなかったら False を返すようです。

randint(a, b) は、a <= x <= b の範囲で整数の乱数を返します。

generator(g, x, p) は、g を x乗して、p で割った余りを返します。

dynamic_xor_encrypt(plaintext, text_key) は、paintext を末尾から順番に取り出して、変数char に格納します。ループの中では、text_key を前から順番に取り出して、変数key_char に格納します。変数char と、変数key_char を XOR して、ASCIIコードで文字を作り、これまで作ったものと連結して、結果を返します。

encrypt(plaintext, key) は、plaintext を前から順番に文字を取り出して、整数に直して、key と 311 をかけてリストに格納していき、そのリストを返します。

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")

復号して、plain_text を得られればいいわけですが、enc_flag には a、b、cipher があり、p、g は固定値で、text_key も固定の文字列です。

愚直にやるとすると、encrypt関数の逆の働きをする decrypt関数を実装します。shared_key は a、b と固定値で求まりそうなので、decrypt関数が実行できそうです。結果として、semi_cipher が求まります。

次は、dynamic_xor_encrypt関数の逆の働きをする dynamic_xor_decrypt関数を実装します。まぁ、何とかできそうな気がします。これで plain_text が得られそうです。

このやり方でいいんでしょうか。100ポイントなので、そこまでひねった問題ではないかな、と思いました。では実装していきます。

from random import randint
import sys

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

def decrypt(cipher, key):
    
    plaintext = []
    for ii, num in enumerate(cipher):
        assert num % (key * 311) == 0, f"fatal: ii={ii}, num={num}"
        tmp = num // key // 311
        #assert tmp >= 0x21 and tmp < 0x7f, f"fatal: ii={ii}, num={num}, tmp={tmp}"
        plaintext.append( chr(tmp) )
    
    return ''.join( plaintext )

def dynamic_xor_decrypt(semi_cipher, text_key):
    
    plain_text = ""
    key_length = len(text_key)
    for ii, cc in enumerate(semi_cipher):
        key_char = text_key[ii % key_length]
        decrypted_char = chr( ord(cc) ^ ord(key_char) )
        plain_text += decrypted_char
    
    return plain_text[::-1]

if __name__ == "__main__":
    
    cipher = [151146, 1158786, 1276344, 1360314, 1427490, 1377108, 1074816, 1074816, 386262, 705348, 0, 1393902, 352674, 83970, 1141992, 0, 369468, 1444284, 16794, 1041228, 403056, 453438, 100764, 100764, 285498, 100764, 436644, 856494, 537408, 822906, 436644, 117558, 201528, 285498]
    
    p = 97
    g = 31
    a = 97
    b = 22
    
    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:
        raise
    print( f"shared_key={shared_key}" )
    
    semi_cipher = decrypt( cipher, shared_key )
    print( f"semi_cipher={semi_cipher}" )
    
    plain_text = dynamic_xor_decrypt(semi_cipher, "trudeau")
    print( f"plain_text={plain_text}" )

実行します。お、出来ました。

$ python tmp.py
shared_key=54
semi_cipher=    ELQUR@@*SDV>3 1

plain_text=picoCTF{custom_d2cr0pt6d_e4530597}

picoCTF{custom_d2cr0pt6d_e4530597} でした。

C3（200ポイント）

Medium の問題です。暗号文のファイル（ciphertext）と、エンコーダの Pythonスクリプト（convert.py）がダウンロードできます。

まず、暗号文から見てみます。だいぶ長いです。

DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl

次にエンコーダの Pythonスクリプトを見てみます。

最初に標準入力から改行文字含めて、複数行の文字列を受け取り、chars に格納します。

chars を前から順番に 1文字ずつ取り出して、lookup1 の中で一致する文字のインデックスを取得します。ちなみに、index関数は見つからなかった場合は -1 を返しますが、そういう状況があっても動きそうです。

そのインデックスから prev（前回値）を引いて、40 で割った余りを out に格納していきます。ちなみに、lookup1 と lookup2 はともに 40文字です。

最後に out を標準出力に出力します。

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)

問題文には明確に書かれてませんでしたが、デコーダーを実装すればいいんでしょうか。先ほどの「Custom encryption」より簡単に見えますが、前回値というのがあるので、実はやっかいかもしれません。

暗号文（ciphertext）は、237文字あります。ということは、入力も 237文字だったということになります。まず、1文字目が入力されて、cur に 0 から 39 までの値が入り、lookup2 から cur のインデックスで文字を抽出すると、D だったということです。ということは、cur は 3 だったので、入力は # だったということになります。prev には 3 が入ります。うーん、前からやれば出来るんじゃないでしょうか。

では実装していきます。

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

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

prev = 0
out  = ""
for ii, cc in enumerate(chars):
    cur = lookup2.index( cc )
    out += lookup1[(cur + prev) % 40]
    prev = cur + prev
    
    #print( f"ii={ii}, cc={cc}, cur={cur}, out[ii]={out[ii]}" )

sys.stdout.write(out)

実行します。なんかソースコードが出てきました。なるほど、リダイレクトしてソース（tmp2.py）に落とします。

$ python tmp.py < ../picoCTF/picoCTF2024_Cryptography/C3/ciphertext > tmp2.py
#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

では、今度は、tmp2.py を実行してみます。あ、Python2 なので、print のところだけ直して実行します。でも、何を入力すればいいのでしょうか。コメントを見ると、アスキー順に 40文字を入力するということでしょうか。

アスキー順は、どこから入力するんでしょうか。とりあえず、英文字に限定して入力してみましたがダメでした。スペース から G まで入力したファイルを入力してみましたがダメでした。

$ echo -n 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmn' | python tmp2.py
b=1.0, len(chars)=40
B
I
b

分かりません。考えても分からなさそうなのでギブアップです。

writeupを見ると、この tmp2.py 自体を入力するということみたいです。selfinput とは、そういう意味なんですね、なるほど。writeup を書かれた人も「エスパー成分が結構あり」と書かれていましたが、早めにギブアップして良かったです。

Python2 の環境は無いので、Python3 に書き直したものと別にソースファイルを用意します。

$ python tmp.py < ../picoCTF/picoCTF2024_Cryptography/C3/ciphertext > tmp3.py

$ python tmp2.py < tmp3.py
b=1.0, len(chars)=237
a
d
l
i
b
s

picoCTF{adlibs} でした。

rsa_oracle（300ポイント）

Medium の問題です。暗号文のファイル（secret.enc）と、パスワードのファイル（password.enc）がダウンロードできます。また、サーバが起動できるようです。

暗号文のファイルとパスワードのファイルを確認します。暗号文は 64byte のバイナリファイルで、パスワードは 154文字でした。

$ hexdump -C secret.enc
00000000  53 61 6c 74 65 64 5f 5f  67 d6 dd c5 30 27 20 5e  |Salted__g...0' ^|
00000010  e9 ba 04 09 6c 01 f4 9e  68 06 93 a3 0e 69 ba 9f  |....l...h....i..|
00000020  b3 70 18 32 ce 88 99 3f  b7 4c 63 7d 35 0f da a7  |.p.2...?.Lc}5...|
00000030  a9 ed 48 82 7c 55 56 3b  f5 fc 68 40 e3 3d b3 ea  |..H.|UV;..h@.=..|
00000040

$ cat password.enc
2575135950983117315234568522857995277662113128076071837763492069763989760018604733813265929772245292223046288098298720343542517375538185662305577375746934

サーバを起動してみます。E か D を入力すると暗号化と復号をやってくれるようです。暗号化は出来てるように見えますが、パスワードを入れて、復号させましたが、「笑、いい試みですね、解読は無理ですね。創造力を発揮して頑張ってください」と笑われました（笑）。

$ nc titan.picoctf.net 54320
*****************************************
****************THE ORACLE***************
*****************************************
what should we do for you?
E --> encrypt D --> decrypt.
E
enter text to encrypt (encoded length must be less than keysize): aaa
aaa

encoded cleartext as Hex m: 616161

ciphertext (m ^ e mod n) 4443234402154812773385501834340003636914383861160506214643463504676790998210270710730017166210361998872964038946757473353651450587613192159232519828813975

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

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

ちょっと、ここからどうしていいか分かりません。ギブアップです。Crypto は、今は、初歩的な問題しか出来ないようです。

flag_printer（500ポイント）

まだ解ける気がしないので、後日にします。

これで、Cryptography は終了です。

おわりに

今回は、picoCTF の picoCTF 2024 のうち、Cryptography というカテゴリの全5問に挑戦しましたが、とても難しかったです。これで、一通り、picoCTF 2024 はやってみた感じです。まだまだ、全然ですね、頑張ります。

最後になりましたが、エンジニアグループのランキングに参加中です。

ランキング参加中

エンジニアグループ

気楽にポチッとよろしくお願いいたします🙇

今回は以上です！

最後までお読みいただき、ありがとうございました。