Rokiのチラ裏

学生による学習のログ

sha-2 の理論と実装

C++ algorithm

ふと国内でもある程度取り上げられている記事 Learn Blockchains by Building One – Hacker Noon を見て自分も何か実装してみるか〜と思ったのだが、私の観測範囲内では C++ の sha-2 ハッシュ関数がライブラリとしてあまりよく整備されていない気がしたので、ブロックチェーンの実装に取り組む前に FIPS180-4を参考にこの際実装する事とし、その過程をメモ。尚、本エントリにおける文中(x) 下線はその内容がテーブルや式と関連付いている事を示す。

SHA-2は、Secure Hash Algorithmシリーズの暗号学的ハッシュ関数で、SHA-1の改良版である。National Security Agency（NSA）によって設計され、2001年にNational Institute of Standards and Technology（NIST）によってFederal Information Processing Standard（FIPS） PUB 180-4として標準化された。[..] SHA-2には、前身のSHA-1から多くの改良が加えられている。それ以前のハッシュ関数は出力が固定長で強度もその長さによって決まる値に固定されていたが、SHA-2はSHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256の6つのバリエーションを持ち、ハッシュ長は224、256、384、512ビットのいずれかである。[..] SHA-2シリーズは US 6829355 によってカバーされているが、アメリカ合衆国は、この特許をロイヤリティフリーで開放している。-- wikipedia
全ての SHA-2 アルゴリズムは、メッセージダイジェストと呼ばれる凝縮表現を生成するためにメッセージを処理できる反復的な一方向ハッシュ関数であり、これらのアルゴリズムにより、メッセージの整合性を検証する事ができる。メッセージの変更は、非常に高い確率で異なるメッセージダイジェストとなり、デジタル署名やメッセージ認証コードの生成と検証、乱数やビットの生成に役立つ。
FIPS180-4/5.3 で定められた初期値*1を入力データによって反復的に変化させる。入力データを(a)一定の単位(メッセージブロック)に分割し、各単位に(b)各アルゴリズムごとによって定められた関数による計算処理(Hash computation)を施す。この時、各計算処理はその前回の計算処理で発生したハッシュを用い、全てのメッセージブロックにこの操作を行う。最後のメッセージブロックで発生した値をハッシュ値の最終結果(メッセージダイジェスト)とする。メッセージブロックやその他のサイズは下図の通り各アルゴリズムによって異なる。

アルゴリズムメッセージサイズ (bits)(a) ブロックサイズ(bits)(c) ワードサイズ (bits)メッセージダイジェストサイズ
SHA-1 2^{64}51232160
SHA-224 2^{64}51232224
SHA-256 2^{64}51232256
SHA-384 2^{128}102464384
SHA-512 2^{128}102464512
SHA-512/224 2^{128}102464224
SHA-512/256 2^{128}102464256

メッセージブロックに分割する時、(a) 指定のブロックサイズに余りなく切り分けられるとは限らない。そのような入力データに対して*2、メッセージブロックの生成においてパディングを追加する。以下各記号を FIPS18-4 に準じて次のように定義する。

  • M: ハッシュされるメッセージ。
  • M^{(i)}: m ビットのサイズを有するメッセージブロック i。
  • l: メッセージの長さ、 M をビット単位で示す。
  • k: パディングステップ中にメッセージに追加された 0 の数。
  • w: ワードのビット数。

    パディングは、入力データの直後にまず 1 ビットを置く。次に SHA-256 などでは式 l + 1 + k = 448 \bmod{512} に対する最小で非負の解である k ビット分を、SHA-512 などでは式 l + 1 + k = 896 \bmod{1024} に対する最小で非負の解である k ビット分を、先ほどの 1 ビットの直後に続くようにして拡張し、拡張したパディングを 0 で埋める。さらに続くようにして SHA-256 などでは l に等しい 64 ビットの、SHA-512 などでは l に等しい 128 ビットのブロックを追加する。これらの違いは(c) ワードサイズに起因する(つまり、 l は 2w_{len} ビットで表される)。以下にメッセージブロックの全体構造を示す*3。
 \large{M=\underbrace{\overbrace{\underbrace{01100001}_{\rm ``{\bf a}”}\quad\underbrace{01100010}_{\rm ``{\bf b}”}\quad\dots\quad\underbrace{01100011}_{\rm ``{\bf c}”}}^{l\,{\rm bits}}}_{{\rm Massage\,(}M_{\rm in}{\rm )}}\quad\underbrace{1\quad\overbrace{00\dots0}^{k\,{\rm zero\,bits}}\quad\overbrace{00\dots0\underbrace{110\dots00}_{l}}^{2w_{\rm len}\,{\rm bits}}}_{\rm Padding}}

例えば、SHA-256 において M が "abc"(8 ビット ASCII)であるとき M は 24 ビットの長さを有するため、まず"abc"の後方に 1 ビットを置き、次に k ビットすなわち 423 ビット分( k = 448 - (24 + 1))を 0 で埋め、最後尾に l を置く( 24 + 1 + 423 + 64 = 512)。

 \large\underbrace{01100001}_{"a"}\ \underbrace{01100010}_{"b"}\ \underbrace{01100011}_{"c"}\ 1\ \overbrace{00...00}^{423}\ \overbrace{00...0\underbrace{11000}_{l = 24}}^{64}

SHA-512 などでは 896 - (24 + 1) = 871 = k から 871 ビット分を 0 で埋める事となる( 24 + 1 + 871 + 128 = 1024)。

 \large\underbrace{01100001}_{"a"}\ \underbrace{01100010}_{"b"}\ \underbrace{01100011}_{"c"}\ 1\ \overbrace{00...00}^{871}\ \overbrace{00...0\underbrace{11000}_{l = 24}}^{128}

これらパディング済みのメッセージブロックを(c) アルゴリズムごとの指定のワードサイズで分割したベクトルとする。また N をパディング済みのメッセージのブロック数、分割によって得られた N 個のブロックを M^{(1)}, M^{(2)}, ..., M^{(N)} と表す。各メッセージブロック M^{(1)}, M^{(2)}, ..., M^{(N)} は以下のステップを使用して順番に( M^{(i)} (1 \leq i \leq N) というように)処理される。

  1. M^{(i)} を 16 分割したベクトルとし、 M^{(i)}_{j} を i 番目のメッセージブロックの j 番目のワードとし、 M^{(i)}_{0}, M^{(i)}_{1}, ..., M^{(i)}_{15} と表す(例えば M^{(i)}_{0} はメッセージブロック i の左端のワードである。)。次に、 H^{(i)} を i 番目のハッシュ値とし、同様に各 H^{(i)} を 16 分割したベクトルにし、 H^{(i)}_{0}, H^{(i)}_{1}, ..., H^{(i)}_{15} と表す(つまり、 H^{(0)} は初期ハッシュ値、 H^{(N)}は最終ハッシュ値であり最終ハッシュ値においてはメッセージダイジェストを決定するために使用される)。両者ともに、 w_{len} の長さを持つビット列である。
  2. メッセージスケジュールを準備する。 W_{t} を t 番目の w ビットワードとする。尚 \sigma_0(x) と \sigma_1(x) は各アルゴリズムごとに異なる(SHA-224, 256 は \sigma_0^{\\\{ 256 \\\}} と \sigma_1^{\\\{ 256 \\\}} 、SHA-384, 512, 512/224, 512/256 は \sigma_0^{\\\{ 512 \\\}} と \sigma_1^{\\\{ 512 \\\}})。 
     \large{{W_t = \left\{
\begin{array}{ll}
M_t^{(i)} & (0 \leq t \leq 15)\\
\sigma_1(W_{t-2})+W_{t-7}+\sigma_0(W_{t-15})+W_{t-16} & (16 \leq t \leq (n_{\rm rnd} - 1))
\end{array}
\right.}}
  3. a, b, c, d, e, f, g, h の 8 つを作業変数とする。次のように、 (i - 1) 番目のハッシュ値で初期化する。
     \large{\begin{align}
a&=H_0^{(i-1)}\\
b&=H_1^{(i-1)}\\
c&=H_2^{(i-1)}\\
d&=H_3^{(i-1)}\\
e&=H_4^{(i-1)}\\
f&=H_5^{(i-1)}\\
g&=H_6^{(i-1)}\\
h&=H_7^{(i-1)}
\end{align}
}
  4. Ch(x, y, z) = (x \land y) \bigoplus (-x \land z)、 Maj(x, y, z) = (x \land y) \bigoplus (x \land z) \bigoplus (y \land z)、 K_{t} を利用する定数値とする。また、次の通り各記号を定義する。

    • \land: Bitwise AND
    • \lor: Bitwise OR
    • \bigoplus: Bitwise XOR
    • \lnot: Bitwise 補数演算
    • +: \pmod{2^{w}} の加算

    また、次の通り各関数を定義する。
    Hash operations
    ROTL^{n}(x): 左回転(circular left shift)。 x が w ビットワードであり整数 n は 0 \leq n \lt w である。 ROTL^{n}(x) = (x \ll n) \lor (x \gg w - n) と定義される。
    ROTR^{n}(x): 右回転(circular right shift)。 x が w ビットワードであり整数 n は 0 \leq n \lt w である。 ROTR^{n}(x) = (x \gg n) \lor (x \ll w - n) と定義される。
    SHR^{n}(x): 右シフト。 x が w ビットワードであり整数 n は 0 \leq n \lt w である。 SHR^{n}(x) = x \gg n と定義される。
    Hash computation
    (b) SHA-224, SHA-256 ( x, y, z は 32 ビットワードである。)
    \sum_{0}^{(256)}(x) = ROTR^{2}(x) \bigoplus ROTR^{13}(x) \bigoplus ROTR^{22}(x)
    \sum_{1}^{(256)}(x) = ROTR^{6}(x) \bigoplus ROTR^{11}(x) \bigoplus ROTR^{25}(x)
    \sigma_{0}^{(256)}(x) = ROTR^{7}(x) \bigoplus ROTR^{18}(x) \bigoplus SHR^{3}(x)
    \sigma_{1}^{(256)}(x) = ROTR^{17}(x) \bigoplus ROTR^{19}(x) \bigoplus SHR^{10}(x)
    (b) SHA-384, SHA-512, SHA-512/224, SHA512/256( x, y, z は 64 ビットワードである。)
    \sum_{0}^{(512)}(x) = ROTR^{28}(x) \bigoplus ROTR^{34}(x) \bigoplus ROTR^{39}(x)
    \sum_{1}^{(512)}(x) = ROTR^{14}(x) \bigoplus ROTR^{18}(x) \bigoplus ROTR^{41}(x)
    \sigma_{0}^{(512)}(x) = ROTR^{1}(x) \bigoplus ROTR^{8}(x) \bigoplus SHR^{7}(x)
    \sigma_{1}^{(512)}(x) = ROTR^{19}(x) \bigoplus ROTR^{61}(x) \bigoplus SHR^{6}(x)
    t を 0 から n_{\rm rnd} - 1 まで繰り返して次のようにローテートする。尚 K_{t} は各アルゴリズムごとに異なる( \Sigma_0(x)、 \Sigma_1(x) に関しては前述した通り)(SHA-224, 256 は K_{t}^{\\\{256\\\}}、SHA-384, 512, 512/224, 512/256 は K_{t}^{\\\{512\\\}})。 
     \large{\begin{align}
T_1&=h+\Sigma_1(e)+{\it Ch}(e,f,g)+K_t+W_t\\
T_2&=\Sigma_0(a)+{\it Maj}(a,b,c)\\
h&=g\\
g&=f\\
f&=e\\
e&=d+T_1\\
d&=c\\
c&=b\\
b&=a\\
a&=T_1+T_2
\end{align}
}
  5. i 番目の中間ハッシュ値 H^{(i)} を次のようにして計算する。
     \large{\begin{align}
H_0^{(i)}&=a+H_0^{(i-1)}\\
H_1^{(i)}&=b+H_1^{(i-1)}\\
H_2^{(i)}&=c+H_2^{(i-1)}\\
H_3^{(i)}&=d+H_3^{(i-1)}\\
H_4^{(i)}&=e+H_4^{(i-1)}\\
H_5^{(i)}&=f+H_5^{(i-1)}\\
H_6^{(i)}&=g+H_6^{(i-1)}\\
H_7^{(i)}&=h+H_7^{(i-1)}\\
\end{align}
}

以上の操作をメッセージブロックに対して反復的に実行する*4。

実装

github.com

sha-224, 256, 384, 512, 512/224, 512/256 の全てに対応しており、ハッシュ値の生成において当コンポーネントはスレッドセーフである。さらに、これの C++ Library-Wide Hash コンセプトを満たす関数オブジェクト型を用意してあるので、例えば次のようにして標準コンテナのハッシュ生成などに利用できる(オーバーキル気味のような気もするが)。

なおテストは次のようにして実行している。

*1:この値は Nothing up my sleeve number であり、SHA-2 では小さな素数の平方根と立方根から成る値で定義している。

*2:厳密に設計の観点で補足するならば、実際は例え M がブロックサイズの倍数だったとしてもパディング処理は施される。

*3:FIPS180-4/5.1 には各アルゴリズムごとの具体的な全体構造が示されている

*4:この一連の操作は Merkle–Damgård construction と呼ばれる