SHA-256 in C from Scratch

SHA-256は256ビットのハッシュ値を生成する暗号学的ハッシュ関数。SHA-2ファミリの一員で、入力が何バイトだろうと出力は常に64文字の16進数文字列になる。Bitcoin、TLS、Git、パスワードストレージ、至るところで使われている。

何をしてるかをざっくり言うと、「任意長のメッセージを受け取って、決定的に256ビットの指紋を生成する一方向関数」。ここではその内部で何が起きているかを、Cの実装を読みながら追っていくつもり。

Cのコードは、https://github.com/rxxuzi/Algorithm/blob/main/lang/c/crypto/sha256.cにある。

全体の流れ

SHA-256の処理は大きく4ステップ。

1. 初期化 — 8個の32ビットハッシュ値を素数の平方根から導いた初期値で埋める
2. ブロック分割 — 入力を512ビット（64バイト）のブロックに分割する
3. 圧縮 — 各ブロックに対して64ラウンドの圧縮関数を回す
4. パディングとファイナライズ — メッセージ長を末尾に付加して最終ブロックを処理する

入力 → パディング → ブロック分割 → [圧縮関数 × ブロック数] → 256ビットハッシュ。これがMerkle-Damgård構造と呼ばれるフレームワークで、SHA-256だけじゃなくてMD5やSHA-1も同じ骨格を持っている。

ビット演算の道具箱

SHA-256の演算は全て32ビット整数の世界で完結する。浮動小数点演算は一切出てこない。使う道具はAND、OR、XOR、NOT、右ローテーション、右シフトだけ。

ローテーションは普通のシフトと違って、はみ出たビットが反対側から戻ってくる。32ビット整数の世界をぐるぐる回すイメージ。

この道具で6つの関数を定義する。

Ch（Choose）は $x$ のビットが1なら $y$ を、0なら $z$ を選ぶ。MUXと同じ。Maj（Majority）は3入力の多数決。2つ以上が1なら1を返す。

残りの4つ（$\Sigma_0, \Sigma_1, \sigma_0, \sigma_1$）はローテーションとシフトとXORの組み合わせで、ビットを拡散させる役割を持つ。回転量はSHA-256の仕様で固定されている。FIPS 180-4に全部書いてある。

#define CH(x,y,z)  (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
#define EP0(x)  (ROTRIGHT(x,2)  ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x)  (ROTRIGHT(x,6)  ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))
#define SIG0(x) (ROTRIGHT(x,7)  ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

初期値の由来

SHA-256の初期ハッシュ値は8個の32ビット整数。

ctx->state[0] = 0x6a09e667;
ctx->state[1] = 0xbb67ae85;
// ... 以下6個

これは最初の8個の素数（2, 3, 5, 7, 11, 13, 17, 19）の平方根の小数部分。$\sqrt{2} = 1.41421356...$ の小数部 $0.41421356...$ を16進数32ビットで表すと 0x6a09e667 になる。ラウンド定数 k[64] は最初の64個の素数の立方根の小数部分。

こういう「数学的に導出された初期値」を"nothing-up-my-sleeve numbers"（袖の中には何もないよ）と呼ぶ。設計者がバックドアを仕込んでいないことの根拠。

圧縮関数は64ラウンドの心臓部

SHA-256の核心は圧縮関数。512ビットブロックを受け取って、256ビットのハッシュ状態を更新する。

まず入力の16ワード（512ビット）を64ワードに拡張する。メッセージスケジュールと呼ばれる処理で、

16個の入力ワードから64個のワードを再帰的に生成する。入力の1ビットの変化を64ラウンドにわたって拡散させるのがこいつの仕事。アバランシェ効果の源泉。

次に8つの作業変数 $a, b, c, d, e, f, g, h$ をハッシュ状態で初期化して、64ラウンドの圧縮ループを回す。

そのあと8つの変数を「ずらす」。$a \leftarrow T_1 + T_2$、$e \leftarrow d + T_1$、残りは1つずつスライド。Ch は $e, f, g$ に依存、Maj は $a, b, c$ に依存していて、全ラウンドで全変数が混ざり合う。

64ラウンド後に元のハッシュ状態に加算する。この加算がMerkle-Damgård構造のフィードフォワードで、これがないと圧縮関数が可逆になってしまう。

パディング

SHA-256はメッセージ長が512ビットの倍数じゃないと処理できないから、末尾にパディングを追加する。

ルールはシンプルで、メッセージ直後にビット 1 を置いて、ゼロで埋めて、最後の64ビットにメッセージのビット長をビッグエンディアンで格納する。全体が512ビットの倍数になるように調整。

実装上のポイントは56バイトの境界。最後のブロックに長さフィールド（8バイト）を入れる余裕があるかどうかで、追加ブロックが必要になるかが決まる。

if (ctx->datalen < 56) {
    // 1ブロックで済む
    ctx->data[i++] = 0x80;
    while (i < 56) ctx->data[i++] = 0x00;
} else {
    // もう1ブロック必要
    ctx->data[i++] = 0x80;
    while (i < 64) ctx->data[i++] = 0x00;
    SHA256Transform(ctx, ctx->data);
    memset(ctx->data, 0, 56);
}

パディングにメッセージ長を含めることで、長さの異なるメッセージが同じハッシュを持つことを防ぐ。length extension attackへの部分的な対策でもある（SHA-256自体はlength extension attackに脆弱だけど、HMAC-SHA256なら安全）。

256 bit

"Hello" を入力すると 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969 が出力される。同じ入力に対して常に同じ出力。"Hello" を "hello" にするだけで全く違うハッシュになる。1文字の大文字小文字が変わっただけで256ビット全体が変わるのがアバランシェ効果。

SHA-256の出力空間は $2^{256}$ 通り。宇宙の原子数と同じらしい。256個のスイッチが宇宙より大きいって夢があるんだか無いんだか。衝突を見つけるには誕生日攻撃で $O(2^{128})$ の計算が必要で、これは現在の計算資源では非現実的。

暗号学的ハッシュ関数に求められるのは3つの性質。ハッシュ値から元のメッセージを復元できない（原像攻撃耐性）、同じハッシュ値を持つ別のメッセージを作れない（第二原像攻撃耐性）、同じハッシュ値を持つ2つのメッセージを見つけられない（衝突耐性）。SHA-256はこの3つ全てに対して安全とされている。

SHA-1は2017年にGoogleが衝突を実証して終わった。SHA-256がいつまで持つかは誰にもわからないけど、少なくとも今のところは大丈夫。大丈夫だよね？