0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

【picoCTF_WriteUP】Shared Secrets

0
Posted at

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つ生成する」関数
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?