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

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

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

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

はじめに

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

セキュリティの記事一覧

・第1回：Ghidraで始めるリバースエンジニアリング（環境構築編）
・第2回：Ghidraで始めるリバースエンジニアリング（使い方編）
・第3回：VirtualBoxにParrotOS（OVA）をインストールする
・第4回：tcpdumpを理解して出力を正しく見れるようにする
・第5回：nginx（エンジンエックス）を理解する
・第6回：Python＋Flask（WSGI＋Werkzeug＋Jinja2）を動かしてみる
・第7回：Python＋FlaskのファイルをCython化してみる
・第8回：shadowファイルを理解してパスワードを解読してみる
・第9回：安全なWebアプリケーションの作り方（徳丸本）の環境構築
・第10回：Vue.jsの2.xと3.xをVue CLIを使って動かしてみる（ビルドも行う）
・第11回：Vue.jsのソースコードを確認する（ビルド後のソースも見てみる）
・第12回：徳丸本：OWASP ZAPの自動脆弱性スキャンをやってみる
・第13回：徳丸本：セッション管理を理解してセッションID漏洩で成りすましを試す
・第14回：OWASP ZAPの自動スキャン結果の分析と対策：パストラバーサル
・第15回：OWASP ZAPの自動スキャン結果の分析と対策：クロスサイトスクリプティング（XSS）
・第16回：OWASP ZAPの自動スキャン結果の分析と対策：SQLインジェクション
・第17回：OWASP ZAPの自動スキャン結果の分析と対策：オープンリダイレクト
・第18回：OWASP ZAPの自動スキャン結果の分析と対策：リスク中すべて
・第19回：CTF初心者向けのCpawCTFをやってみた
・第20回：hashcatの使い方とGPUで実行したときの時間を見積もってみる
・第21回：Scapyの環境構築とネットワークプログラミング
・第22回：CpawCTF2にチャレンジします（クリア状況は随時更新します）
・第23回：K&Rのmalloc関数とfree関数を理解する
・第24回：C言語、アセンブラでシェルを起動するプログラムを作る（ARM64）
・第25回：機械語でシェルを起動するプログラムを作る（ARM64）
・第26回：入門セキュリhttps://github.com/SECCON/SECCON2017_online_CTF.gitティコンテスト（CTFを解きながら学ぶ実践技術）を読んだ
・第27回：x86-64 ELF（Linux）のアセンブラをGDBでデバッグしながら理解する（GDBコマンド、関連ツールもまとめておく）
・第28回：入門セキュリティコンテスト（CTFを解きながら学ぶ実践技術）のPwnable問題をやってみる
・第29回：実行ファイルのセキュリティ機構を調べるツール「checksec」のまとめ
・第30回：setodaNote CTF Exhibitionにチャレンジします（クリア状況は随時更新します）
・第31回：常設CTFのksnctfにチャレンジします（クリア状況は随時更新します）
・第32回：セキュリティコンテストチャレンジブックの「Part2 pwn」を読んだ
・第33回：セキュリティコンテストチャレンジブックの「付録」を読んでx86とx64のシェルコードを作った
・第34回：TryHackMeを始めてみたけどハードルが高かった話
・第35回：picoCTFを始めてみた（Beginner picoMini 2022：全13問完了）
・第36回：picoCTF 2024：Binary Exploitationの全10問をやってみた（Hardの1問は後日やります）
・第37回：picoCTF 2024：Reverse Engineeringの全7問をやってみた（Windowsプログラムの3問は後日やります）
・第38回：picoCTF 2024：General Skillsの全10問をやってみた
・第39回：picoCTF 2024：Web Exploitationの全6問をやってみた（最後の2問は解けず）
・第40回：picoCTF 2024：Forensicsの全8問をやってみた（最後の2問は解けず）
・第41回：picoCTF 2024：Cryptographyの全5問をやってみた（最後の2問は手つかず） ← 今回

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

picoctf.com

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

picoCTF 2024：Cryptography

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

interencdec（50ポイント）

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

interencdec問題

ファイルを開くと、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）がダウンロードできます。

Custom encryption問題

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）がダウンロードできます。

C3問題

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

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）がダウンロードできます。また、サーバが起動できるようです。

rsa_oracle問題

暗号文のファイルとパスワードのファイルを確認します。暗号文は 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ポイント）

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

flag_printer問題

これで、Cryptography は終了です。

おわりに

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

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

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

今回は以上です！

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