← ブログ

自分のMD5ダイジェストを表示するPNG:The Arma Of Efe hashquine

テンプレートを使わずに、自分のMD5ダイジェストを自分のピクセルに書き込むPNGをどう作ったのか。MD5、衝突キー、PNGのレイヤー、そしてRTX 5070で行った efe23…23efe の探索を、インタラクティブな解説でたどります。

上の画像は、ただのロゴではありません。右側の曲線の上に、上から下へ efe235ae1b88c53e73d1c11515623efe と書かれており、これはファイル自身のMD5ダイジェストです。画像をダウンロードして md5sum を実行すれば、同じ32桁が表示されます。

このような自己参照的なファイルはhashquineと呼ばれます。ネット上で有名な例は retr0id のドラゴンPNGで、多くの人がそのテンプレートを使っています。私たちはテンプレートを使わず、自分のロゴ(The Arma Of Efe)、自分のブログのリンク、そして efe で始まり efe で終わるカスタムダイジェストを使って、ゼロから作りました。以下、試行錯誤の過程を順番にご説明します。

自身の MD5 を表示する、Retr0id によるドラゴンの PNG hashquine

David “Retr0id” Buchanan による PNG hashquine。MD5 は 1337e2ef42b9bee8de06a4d223a51337 です。画像:Retr0id(corkami/collisions より)。

ハッシュとは何か、なぜ文字ごとに変わるのか?

ハッシュ(ダイジェスト)とは、ファイルの内容から得られる、長さが固定された指紋のようなものです。MD5は、1991年に Ronald Rivest が設計したダイジェスト関数です。入力が1バイトでも50 GBでも、出力は常に128ビット、つまり 0-9 と a-f の文字からなる32桁になります。

ダイジェスト関数の基本的な性質は雪崩効果です。入力のわずかな変更でも、出力は先頭から末尾まで変わります。下に何か書いて試してみてください:

鶏と卵の問題

雪崩効果があるため、自分自身のMD5を載せた画像は、一見すると不可能に思えます:

  1. 画像を描画し、そのMD5を求めます。例えば 4a8c91e0…。
  2. そのコードを画像に書き込んで保存します。
  3. ピクセルが変わったため、ファイルのMD5は別のものになります。例えば 9f02d71a…。
  4. 新しいコードを書き込むと、ダイジェストはまた変わります。

このループを断ち切るには、MD5の内部を見る必要があります。

ループを断ち切る発想:MD5を変えない鍵

MD5はファイルを一度に処理しません。64バイトのブロックに分割して、順番に処理します。初期状態(IV)は最初のブロックと混ぜ合わされ、中間状態(IHV)を生み出します。その中間状態は次のブロックと混ぜ合わされ、ファイルの終わりまで同じことが続きます。最後の中間状態が、32桁のMD5そのものです。

重要な点は、64バイトの境界に揃えた128バイトの異なる2つのデータ片(A と B)が存在し、どちらも同じ中間状態に至ることです。これを同一接頭辞衝突と呼び、FastColl のようなツールは短時間でそれを生成できます。この片の後に続くブロックは、どれも同じ中間状態から処理されるため:

  • A 片を置くと画面に線分が見え、B 片を置くと見えなくなります。
  • しかし、ファイル末尾のMD5はまったく変わりません。

つまり、どの衝突ペアも、MD5を壊すことなく開閉できる鍵です。まずファイルのMD5を計算し、次にその正確なダイジェストを描くように鍵を調整します。ダイジェストは変わらないため、ループは断ち切られます。

曲線の文字は一文字ずつどう描かれたか?

このファイルでは、ロゴの弧に沿って上から下へ並ぶ32文字を描いています。各文字は7セグメントの数字で、各セグメントは専用の鍵が描きます。合計224個の鍵です。スライダーを動かすと、ダイジェストが曲線にどう配置されるかを追えます:

既成のテンプレートを使わなかったため、PNGの4つの検証レイヤーを同時にクリアする必要がありました:

  1. 64バイトの整列: 各鍵は、ファイル内で必ず オフセット % 64 == 0 の境界に乗らなければなりません。DEFLATE圧縮ストリームにゼロ長の空ブロックを挿入して、各鍵をこの境界に揃えました。
  2. PNGの Sub および Up フィルタ: パレットの 0..254 のインデックスを黒、255 のみを白にしました。衝突ペアの2つの片は、いくつかのバイトの最上位ビットでだけ異なります。Sub フィルタの行では、その差が後続のピクセルを128ずらし、水平線になります。Up フィルタの行はそれを下へ運びます。鍵のあとのバイトは、一方の状態では線が正確に 255(白)、もう一方では黒になるように選びました。
  3. Zlibの Adler-32 調整: 圧縮データは展開時に Adler-32 チェックサムを通過し、各鍵はこのチェックサムを数百単位ずらします。黒い行に160個の調整用鍵を置き、合計をちょうど元に戻す組み合わせを動的計画法と中間一致探索(meet-in-the-middle)で選びました。
  4. IDAT の CRC-32 検証: 各 IDAT チャンクの末尾には32ビットの CRC-32 があります。圧縮ストリームの直後に40個の追加ブロックを置き、GF(2) 上の線形方程式系をガウスの消去法で解いて、CRC-32 の値を 0x1807EFE0 に固定しました。

カスタムダイジェスト:桁を一つ増やすと作業は16倍になる

ファイル自身のMD5を表示するだけでは足りず、ダイジェストが efe で始まり efe で終わるようにしたいと考えました。そのため、ファイル末尾にある64バイトのノンスブロックを変えながら、数十億回ものダイジェストを試しました。

各桁は16通りの値をとれるため、固定する桁が一つ増えるたびに、平均試行回数は16倍になります。固定桁数が N なら、平均で 16^N 回の試行が必要です。24コアのCPUでは、単純なCのループが毎秒1億7700万回のMD5を試せました。同じ処理をRTX 5070 ノートPC向けGPUでOpenCLを使って行うと、毎秒35.4億回、約20倍になりました。efe23…23efe には平均で1.1兆回の試行が必要ですが、私たちのものは900億回目、約25秒で見つかりました。

スライダーで桁数を変えてみてください。実際に見つかった結果は、印の付いた点に表示されています:

自分で検証する

画像をダウンロードして、ターミナルで実行してください。Windowsでは certutil -hashfile dosya.png MD5、macOSでは md5 dosya.png コマンドを使えます。

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

出力に表示される32桁は、曲線の上に上から下へ描かれたコードとまったく同じです。

画像を生成するコードの全体は GitHub にあります:the-arma-of-owl/the-arma-of-efe-hashquine。衝突の骨格もリポジトリに含まれているので、自分のnonce値で新しいhashquineを生成することもできます。

参考資料: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗