CTFのCryptoにおけるハッシュまとめ

CTFにおけるCrypto入門とまとめの1つです。

Hash

• 一方向ハッシュ関数, メッセージダイジェスト関数、メッセージ要約関数、暗号的ハッシュ関数
• 暗号学的ハッシュ関数（RFC4270に記載がある）
  • 第１原像攻撃困難性: ハッシュ値Hに対して、H=HASH(M)となるような入力Mを計算することが困難。つまり、狙ったハッシュ値を出力させる入力を作ることが困難
  • 第２原像攻撃困難性: 入力値M1に対して HASH(M1)=HASH(M2)となるようなM1と異なるM2を計算することが困難
  • 衝突困難性（強衝突耐性）: ハッシュ値が同じになる(M1,M2)の組を計算することが困難。原像攻撃とは異なり、どんなハッシュ値でも成り立つとき
• 使われる所
  • ソフトウェアの改ざん検知
  • PBE: Password Based Encryption, 暗号化ではないがパスワードとソルトを使った辞書攻撃を防ぐアレ
    • これには計算空間量、また、探索空間量をストレッチングする効果がある
  • MAC: メッセージ認証コード
    • 鍵付きハッシュ関数 Keyed hash function: HMAC-SHA256など
    • CBC-MAC
    • EMAC: CBC-MACを改良したMAC
    • CMAC: CBC-MACを改良したMAC
  • デジタル署名
  • 疑似乱数生成器
  • ワンタイムパスワード
• HMAC: Keyed-Hashing for Message Authentication Code
  • メッセージ認証符号(MAC)の1つで、一方項ハッシュ関数を用いてメッセージ認証コードを構成する手法
  • 秘密鍵とデータとハッシュ関数をもとに計算される
  • HMAC-MD5のように使用するハッシュ関数を名前に組み込んだりする
• 文字列からハッシュ取るときはecho -n "[plain]" | md5sumみたいにすること
  • -nを入れると最後に改行を入れずにハッシュが取れる。有無でハッシュが変わる
• リプレイ攻撃には弱い（シーケンス番号、タイムスタンプ、ノンスとかを使いましょう）

アルゴリズム

• RIPEMD : RACE Integrity Primitives Evaluation Message Digest
  • RIPEMD-160: 160ビットのハッシュ値を生成する。他にも128,256,320もある
    • ビットコインで使われている
• SHA
• MD5
  • ハッシュの衝突耐性が弱く、突破されている
  • GitHub - corkami/collisions: Hash collisions and their exploitations
    • サンプルが色々紹介されている。pdfはここにある
  • テキストの衝突例 https://twitter.com/realhashbreaker/status/1770161965006008570
    • md5("TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak") = md5("TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak")
  • 良い感じのmd5衝突ペアを見つけたいとき -> https://github.com/upbit/clone-fastcoll
    • 出典 https://blog.y011d4.com/20221011-cyber-security-rumble-writeup
  • 前身はMD4だが、こっちも衝突の方法が既に考案されていて安全ではない
• SHA-1
  • Exploiting SHA-1-signed messagesによるとソルトがあれば署名は衝突可能？
• SHA-2
• SHA-3 (Keccak, ケチャック)
  • SHA3-224, SHA3-256, SHA3-384, SHA3-512がある
  • スポンジ構造というのを使って攪拌を行う
    • 吸収フェーズと搾出フェーズがあるのでスポンジ構造というらしい
• パスワード保持によく使われるやつ
  • bcrypt: 最近は古いっぽい
  • scrypt
  • phpass
  • PBKDF2 : Password-Based Key Derivation Function 2
    • FIPS準拠のためにはこれにする必要がある
    • それでも、RTX5090とHashcatを使うと、1秒あたり680万個のハッシュを試行可能らしい https://gist.github.com/Chick3nman/09bac0775e6393468c2925c1e1363d5c
  • Argon2id / Argon2
• KerberosはRC4とソルトなしNTハッシュ（MD4）の組み合わせで、これはRTX5090で毎秒41億8000万個のハッシュを試行可能らしい https://blog.cryptographyengineering.com/2025/09/10/kerberoasting/

関連ワード

• Merkle-Damgard: MD5, SHA-1, SHA-2が持つ構造。どれも似たようなアルゴリズム
• ソルト: ハッシュを作成する前に適当な文字列をくっつける
• ストレッチング: ハッシュ値の総当たりを大変にするために何重もハッシュを計算すること
  • 例えばbcryptoのようにハッシュブルートフォースに時間がかかるようにしてあるものがある
• HMAC: 鍵とハッシュ関数を用いてメッセージに改ざん防止用の符号を付与するアルゴリズム
  • Poly1305: ブロック暗号（AES）を使ってMACを作成
  • HMAC-SHA1
  • HMAC-MD5
  • HMAC-SHA256
  • HKDF: HMACベースのKDF（鍵導出関数）
    • KDF: 鍵導出関数、鍵を構成する初期値を受け取って、1つないしは複数の暗号学的に強い鍵を生成することができる仕組み
    • 手順
      1. 入力となる鍵の初期値(IKM:Input Keying Material)を受け取り、固定長となるPRK(PesedoRandom Key)を取得する
      2. 生成したPRKを複数のPRKへと拡張する
• ハッシュ衝突攻撃
  • RFC4270で定義されている衝突攻撃の要件はハッシュのビット長Lに対して、2の2分のL乗回未満の攻撃で突破できること
  • MITM, Meet-in-the-Middle Attack: ハッシュの衝突が起きれば大丈夫という状況で2つの平文A,Bに対してハッシュ値をたくさん取っていくことで、一致するハッシュと平文の組を探そうとする方針
  • 誕生日のパラドックス Birthday Attack
    • 全探索したときに衝突する組が見つかる確率は集合全体がNであればsqrt(N)回の試行で50%の確率で見つけられる
    • 確率論における生日パラドックスに根ざしています。n個の異なる値を持つハッシュ関数において、約√n回の試行で50%の確率で衝突が発生する現象 WikipediaMahalozを利用します。 Wikipedia +2実際の攻撃実装では、メモリ効率を考慮したFloydsサイクル検出アルゴリズムやPollardのrho法が使用されます。
  • 差分解析
  • 線形解析
  • z3で衝突を解析

Length Extension Attack

• 特定のハッシュ関数（Merkle-Damgard）に対して[unknown][known]という平文に対してハッシュ化されたものが判明しているときに、[unknown][known][many zerobytes][any]のような形に対してのハッシュ値を得られる
  • 対応: crc32, md5,. sha1, sha256, sha512
  • unknownは長さは分かっている必要がある
    • MACとしてハッシュを使っていればここに秘密鍵が置かれていることがある
      • [秘密鍵][平文]のハッシュ値を署名に使ってるいるとか
  • knownに制約があるかは分からない。末尾にある必要はある（最後のブロックを構成するための長さくらいは必要そうだけれど）
  • many zerobytesはアルゴリズム上勝手につく
  • anyは自由に決められる。最後にしかくっつけることができないので注意
• CTF/Toolkit/HashPump - 電気通信大学MMA
  • HashPumpを使えば達成できる
    • git clone https://github.com/bwall/HashPump && cd HashPump && makeで用意
  • $ ./hashpump -s (既知ハッシュ) -d (既知初期文字列) -k (UNKNOWNの長さ) -a (追加文字列)
  • ./hashpump -s 846624fb43da2ad7adcf1e4a6a760e54ed1830050cbd44a0baafbf6260b861e5e6723d2f6a0c5c265267dfe1c984fb3a29d07e347d1c273899615e96c52bb015 -d 8,8 -k 21 -a ,10とすると、以下のようになる。1行目が新しいハッシュで、2行目が追加後の文字列となる。unknown + (2行目の\xを%に変換したもの) 6b25918b4b2b303c44d3cdd67f337d3acbdf722e2f006b19226e8b0c6f77ea2b0dbfcf6d9f4c2a5bbe98d252c6c1f5ae8af70dceee7df0c22e690c92bf35fd0e 8,8\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xc0,10
• iagox86/hash_extender
  • ./hash_extender --data "" --secret [unknownの長さ] --append [追加文字列] --signature [既知ハッシュ] --format [md5]
• stephenbradshaw/hlextend: Pure Python hash length extension module
  • SHA1, SHA256, SHA512で使える

Bcrypt Truncation

• bcryptは72bytesを超えると72bytesに丸められる制約がある
• これを使って不明文字列を平文の末尾において先頭から1文字ずつ特定していく方法がある https://blog.hamayanhamayan.com/entry/2024/06/10/003618#Web-Rusty-Road-%E8%A7%A3%E3%81%91%E3%81%AA%E3%81%8B%E3%81%A3%E3%81%9F
• 言語によらずbcyrpt側の仕様っぽい？
  • phpだとpassword_hashとpassword_verify
    • password_hashでアルゴリズムをPASSWORD_BCRYPTとして使うと、 password が最大 72 バイトまでに切り詰められる。ハッシュの元の先頭72バイトが一致するように作れば署名を共有することができる。偽装できる。
  • rust
    • use bcrypt::{hash, verify, DEFAULT_COST};でhash(password, DEFAULT_COST).unwrap()みたいになっていると使われている

自作ハッシュ衝突問題

• X-MAS CTF 2020 Help a Santa helper? https://blog.y011d4.com/20201219-xmas-ctf-writeup#help-a-santa-helper
• Zh3r0 CTF V2 chaos https://blog.y011d4.com/20210606-zh3r0-ctf-writeup#chaos
• ACSC 2021 Wonderful Hash https://blog.y011d4.com/20210919-acsc-writeup#wonderful-hash
• N1CTF - n1fnv https://github.com/tl2cents/CTF-Writeups/tree/master/2025/n1ctf/n1fnv1
  • 2のべき乗modのため、下位ビットで衝突させ、そこから上位ビットへ漸近的に確定させていき、全体のハッシュが衝突するようにする
  • また、MITMも有効に使って、下位ビットの衝突を探している

ハッシュ関数署名

• SPHINCS+