1. はじめに
- picoCTFの「Shared Secrets」の解説記事です
2. 問題の概要
- 難易度:Easy
- カテゴリ:Cryptography
- 配布ファイル:
message.txt(実行結果)、encryption.py(暗号化スクリプト) - 説明文:
A message was encrypted using a shared secret... but it looks like one side of the exchange leaked something. Can you piece together the secret and get the flag?
Download the message. And source code
メッセージが共有秘密鍵を使って暗号化されましたが、どうやら通信の一方の側で何かが漏洩したようです。秘密鍵を解読してフラグを入手できますか?
メッセージとソースコードをダウンロードしてください。
3. 実行環境の構築(uv を使用)
- Python環境で
pycryptodomeが必要 - 今回は高速なパッケージマネージャー
uvを使用してセットアップuv pip install pycryptodome
4. ソースコードの解析
encryption.py を読み解き、以下のポイントを整理します。
- $A = g^a \pmod{p}$ と $B = g^b \pmod{p}$ から、共通鍵
sharedを作っている -
不自然な部分:
AとBを作るために必要な変数a、b、pが、ランダムな値だったり文字列だったりするので、このままでは実行しても正しいAとBは得られない。
shared % 256を鍵とした XOR演算 で暗号化している
enc = bytes([x ^ (shared % 256) for x in flag])
5. 攻略のステップ
①message.txt から値を抽出
-
p,A,b,enc(16進数の暗号文) を取得 -
pythonソースコード内の
getPrimeとrandintは実行のたびに値が変わる関数のため、ソースコードの値ではなくmessage.txtの固定値に置き換える -
また
encは元の'bytes([x ^ (shared % 256) for x in flag])'だと正しくないflag値picoCTF{...}を参照してしまっているので、これもmessage.txtの固定値に置き換える
②XORの性質を利用した復号ロジック
XOR(排他的論理和)には「AにBをXORしてCになったなら、CにBをXORするとAに戻る」という性質があります。
つまり、 $Flag \oplus Key = Enc$ なので、 $Enc \oplus Key = Flag$ によって復号できるということです。
よって①で置き換える前の暗号文の式
bytes([x ^ (shared % 256) for x in flag])
の、flagをencに置き換えると、暗号前の文字列が得られます。
bytes([x ^ (shared % 256) for x in enc]
6. 解法スクリプト
実際に作成・実行したコードを掲載します。
from Crypto.Util.number import getPrime
from random import randint
# Public parameters
g = 2
# p = getPrime(1048)
# 以下変更
p = (message.txtの固定値)
# print("p", p)
# Server's secret
# a = randint(2, p - 2)
# A = pow(g, a, p)
# 以下変更
A = (message.txtの固定値)
# Client secret
# 以下変更
b = (message.txtの固定値)
B = pow(g, b, p)
# Shared key
shared = pow(A, b, p)
print("shared % 256 =", shared % 256)
# Encrypt flag
# flag = b"picoCTF{...}"
# enc = bytes([x ^ (shared % 256) for x in flag])
# 以下変更
enc = bytes.fromhex(" (message.txtの固定値)")
print("enc =", enc)
# Write challenge info
with open("file.txt", "w") as f:
f.write(f"g = {g}\n")
f.write(f"p = {p}\n")
f.write(f"A = {A}\n")
f.write(f"b = {b} \n")
f.write(f"enc = {enc.hex()}\n")
# 以下追記
print(bytes([x ^ (shared % 256) for x in enc]))
7. まとめ
最初、bだけ固定値にすればいいかと思って進めていたらうまくいかないので、Shared%256の値をprintしてみたら実行の度に値が変わって、randintとgetPrimeの存在に気づきました。
print関数でのこまめな出力チェックは大事。
おまけ
- XOR暗号は、同じ鍵で再度XORすることで元に戻る
- getPrime(1048) は、「1048ビットの長さを持つ素数(Prime Number)をランダムに1つ生成する」関数