• HOME
• ABOUT
• CONTACT

AlpacaHackで始めるCTF入門7：AlpacaHack Round 5 - XorshiftStreamに挑戦

記事投稿日: 2024年12月9日（月）

最終更新日: 2024年12月9日（月）

目次

• はじめに
• 前回の記事
• 問題内容
• chall.pyを読んでみる
• 解法の方針
• おわりに
• お知らせ
• シリーズ記事一覧

はじめに

概要

かなり遅れてにはなりますが、今回はAlpacaHack Round 5の問題に挑戦してみます。 今回は一問目の「XorshiftStream」を解いてみます。 ジャンルとしては「Crypto」とのことで、すなわち暗号解読みたいな問題ということになります。 今回もChatGPTに教えてもらいながら挑戦できたらと思います。

※ 注意：解けていません！

AlpacaHack

AlpacaHackへのリンクはこちら

私のCTF環境

前回の記事

2024年10月14日の記事です。

問題内容

XorshiftStreamの問題ページを開くと「tar.gz」ファイルが取得できます。 これを下記のようなコマンドで展開すると「chall.py」「output.txt」が取得できます。 chall.pyを実行してoutput.txtが出力された場合、chall.pyの中に書かれているflagはどういう文字列になるか求める問題っぽいです。

tar -zxvf xorshift-stream.tar.gz

chall.pyを読んでみる

output.txtは一つの文字列が書かれているだけなので、 読み解くべきものはchall.pyだけです。 chall.pyにはXorshiftStreamというクラスが用意されていて、このクラスの中のencryptという関数を実行して得られた出力がoutput.txtとなるみたいです。

まずXorshiftStreamクラスではインスタンス化の際に引数として受け取ったkeyを2の64乗で割った余り（64ビットの範囲におさめるため？）をstateという変数に格納しています。

def __init__(self, key: int):
  self.state = key % 2**64

次に_next関数では問題のタイトルにも含まれているXORShiftを使って疑似乱数的なものを生成しているようです。 ^がXOR、<<と>>がシフト演算となります。

def _next(self):
  self.state = (self.state ^ (self.state << 13)) % 2**64
  self.state = (self.state ^ (self.state >> 7)) % 2**64
  self.state = (self.state ^ (self.state << 17)) % 2**64
  return self.state

そして肝心のencrypt関数では引数で受け取ったdataを8バイトずつ切り出して、_next関数で生成した疑似乱数とのXORを取っているようです。 そしてその結果をctという変数にバイト形式の文字列として連結しているようです。

def encrypt(self, data: bytes):
  ct = b""
  for i in range(0, len(data), 8):
      pt_block = data[i : i + 8]
      ct += (int.from_bytes(pt_block, "little") ^ self._next()).to_bytes(
          8, "little"
      )[: len(pt_block)]
  return ct

最後にXorshiftStreamクラスを使用しています。

FLAGが求めるべき文字列っぽいです（encodeでバイト形式に変換されているっぽい）。

FLAG = os.environ.get("FLAG", "fakeflag").encode()

xssではランダムな初期値（secrets.randbelow(2**64)、keyとなる）を渡してクラスをインスタンス化しています。

xss = XorshiftStream(secrets.randbelow(2**64))

keyではFLAGと同じ長さのランダムなバイト列を取得しています。

key = secrets.token_bytes(len(FLAG))

最後に、encrypt関数にFLAGを含んだバイト列を渡して暗号化した結果のcを取得しています。 hex()は16進数として扱うためのものらしいです。 strxor()は二つの引数をXORするための関数らしいです。

c = xss.encrypt(key.hex().encode() + strxor(key, FLAG))
print(c.hex())

解法の方針

chall.pyの暗号化の手順を逆方向に辿っていけば解けそうな気はしますが、 そんなに簡単な話なのかは分かりません。 この後は時間がかかりそうなので他の方のwriteupなどを参考にしながら進めてみます。

おわりに

今日もAlpacaHackに挑戦させていただきました。 Cryptoジャンルの問題はどこから手を付けたらよいのか分からないぐらい理解できていないので、 やっぱりAlpacaHack以外（DreamHackなど）でも勉強が必要そうな感じです。 それでは、また。

お知らせ

• 2024/09/21: ズグロシロハラインコ「ぐぐ」我が家へ
• 2024/09/07: ズグロシロハラインコ「ぽぽ」我が家へ
• 2024/08/01: れもんが我が家に来て一ヶ月
• 2024/06/29: セキセイインコ「れもん」我が家へ
• 2024/05/03: シェル芸オンラインジャッジ一周年

シリーズ記事一覧

各シリーズの記事を下記にまとめてあります。