暗号アルゴリズムの評価

2001 年 度

神 戸 大 学
桑門 秀典

暗号アルゴリズムの評価
桑門 秀典
神戸大学工学部電気電子工学科

目次
1

序論

1

2

SHA-256, 512
2.1 アルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 関数の定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 SHA-256 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3 SHA-512 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 SHA-256, 512 の特徴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Draft FIPS-180-2 への公開コメント . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Jonsson のコメント . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Kelsey のコメント . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
2
2
4
5
7
7
7

3

安全性の検討3.1 安全性の評価基準 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 メッセージの変化がハッシュ値に及ぼす影響 . . . . . . . . . . . . . . . . .
3.3 BP 攻撃法による衝突困難性の検証 . . . . . . . . . . . . . . . . . . . . . .
3.4 並列処理による高速化と安全性 . . . . . . . . . . . . . . . . . . . . . . . .
3.5 既知の攻撃法の適用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 原像探索困難性について . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Kelsey 法の評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
8
9
10
11
12
14
15

4

結論

15

1

序論

Draft FIPS-180-2[11] では，256bits, 384bits, 512bits のハッシュ値を出力するハッシュ関
数 SHA-256, SHA-384, SHA-512 が提案されている．現在広く使用されている SHA-1[10]の安全性が損なわれるような報告はないが，SHA-1 のハッシュ値は 160bits なので，計算機の性能向上によってその安全性が脅かされる可能性も否定できない．
SHA-256, 384, 512 は，衝突困難かつ一方向性であるように設計されている．また，同時に入力メッセージの少しの変化が出力のハッシュ値に大きく影響するように設計されている．Draft FIPS-180-2 でも述べられているように，SHA-256, 384, 512 をディジタル署名，鍵付ハッシュによるメッセージ認証，擬似乱数生成器として使用するためには，これらの設計目標が達成されていなければならない．これらの設計目標が達成されていないという証拠はないが，逆に設計目標が達成されているという数学的な証明もないという現状に注意する必要がある．
SHA-256, 384, 512 の構造は，SHA-1 と同様に Merkle-Damgård が提案した衝突困難な
ハッシュ関数の構成法に準じている [5]．メッセージをいくつかのブロックに分割し，各ブロックを圧縮関数 f により繰り返し処理をする構造になっている (図 1)．この構成法の特徴は，ハッシュ関数全体の衝突困難性が圧縮関数 f の衝突困難性に帰着されることである．
一方，Merkle-Damgård の構成法に基づくハッシュ関数は，必ずしも汎用一方向性ハッシュ関数ではないことに注意する必要がある [2]．汎用一方向性ハッシュ関数を構成する方法として，Shoup の構成法が知られているが [13]，SHA-256, 384, 512 は Shoup の構成法に準じていない．
本報告書では，SHA-256, 384, 512 の安全性を評価する．ただし，SHA-384 は，SHA-512と本質的に同じなので，主に SHA-256, 512 について論じる．本報告書の構成は，以下のとおりである．
2.1 章: SHA-256, 512 のアルゴリズムと記号の定義を述べる．
2.2 章: SHA-1 と SHA-256, 512 のアルゴリズムの相違点をまとめる．
2.3 章: Draft FIPS-180-2 への公開コメントを簡単にまとめる．
3.1 章: SHA-256, 512 の安全性の評価基準について論じている．
(1)

(2)

m
H

(0)

f H

(n)

m
(1)

f H

m
(2)

f

図 1: Merkle-Damgård の構成法

1

H

(n)

3.2 章: SHA-256, 512 において，入力のビット系列の変化が出力のビット系列に及ぼす影響を実験的に調べている．
3.3 章: birthday paradox を利用した攻撃法を実際に行った結果を述べている．
3.4 章: SHA-256, 512 のアルゴリズム的並列処理の可能性とそれが安全性に及ぼす影響を述べている．
3.5 章: 他のハッシュ関数への攻撃法を SHA-256, 512 に適用できるかどうかを検討している．
3.6 章: SHA-256, 512 の一方向性について検討している．
3.7 章: Kelsey が提案している SHA-256, 512 の改良法の評価を行っている．
4 章: 本報告書のまとめを述べている．

2

SHA-256, 512

2.1

アルゴリズム

この章では，Draft FIPS-180-2 の SHA-256, 512 のアルゴリズムを述べる．Draft FIPS180-2 で記述されているアルゴリズムと本質的に同じであるが，後の安全性解析の記述を明確にするため，アルゴリズム中の変数等の表記法が Draft FIPS-180-2 と異っている．

2.1.1

関数の定義

SHA-256, 512 で共通に使用される関数をまとめる．変数のビット長は，SHA-256 の場
合は 32bits，SHA-512 の場合は 64bits である．
Ch(x, y, z) = (x ∧ y) ⊕ (¬x ∧ z)
Maj(x, y, z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)
SHRn (x) : x を n bits 右へシフト
ROTRn (x) : x を n bits 右へ巡回シフト
2.1.2

SHA-256

メッセージ m を padding して，512 の倍数の長さのビット系列に変換する．padding 方法については，Draft FIPS-180-2 p. 12 を参照．そして，m を n 個の 512bits のメッセー
ジブロックに分割する．それを m(1) , m(2) , . . . , m(n) と書く．i = 1, 2, . . . , n に対して，以
(n)
(n)
(n)
下の処理を行う (各変数は 32bits)．メッセージ m のハッシュ値は，H0 |H1 | · · · |H7 である．

2

1. m(i) を 32bits 毎に分割し，それらを m[t] (0 ≤ t ≤ 15) と書く．そして，w[t] を以下のように計算する．
w[t] =

 m[t]

0 ≤ t ≤ 15

 σ {256} (w[t − 2]) + w[t − 7] + σ {256} (w[t − 15]) + w[t − 16] 16 ≤ t ≤ 63
1
0

(1)
ここで，
{256}

σ0

(x) = ROTR7 (x) ⊕ ROTR18 (x) ⊕ SHR3 (x){256}
σ1 (x)

17

19

(2)

10

= ROTR (x) ⊕ ROTR (x) ⊕ SHR (x)

(3)

である．

2. 変数を初期化する1 ．

(i−1)

a[0] = H0 ,(i−1)
c[0] = H2 ,(i−1)
e[0] = H4 ,(i−1)
g[0] = H6 ,
(0)

(0)

(i−1)

b[0] = H1 ,(i−1)
d[0] = H3 ,(i−1)
f [0] = H5 ,(i−1)
h[0] = H7(0)

なお，H0 , H1 , . . . , H7 については，Draft FIPS-180-2 p. 13 を参照．

3. t = 0, 1, . . . , 63 に対して以下の計算を繰り返す (一つの t に対する以下の処理をまとめて，1 ステップと呼ぶ)．
{256}

T1 [t] = h[t] + Σ1
{256}

T2 [t] = Σ0{256}

(e[t]) + Ch(e[t], f [t], g[t]) + Kt

+ w[t](a[t]) + Maj(a[t], b[t], c[t])

(4)
(5)

a[t + 1] = T1 [t] + T2 [t](6)b[t + 1] = a[t](7)c[t + 1] = b[t](8)d[t + 1] = c[t](9)e[t + 1] = d[t] + T1 [t](10)

f [t + 1] = e[t](11)g[t + 1] = f [t](12)h[t + 1] = g[t]

(13)

ここで，
{256}

Σ0

(x) = ROTR2 (x) ⊕ ROTR13 (x) ⊕ ROTR22 (x){256}Σ1 (x){256}

である．なお，Kt
1

(i)

6

11

25

= ROTR (x) ⊕ ROTR (x) ⊕ ROTR (x)

(14)
(15)

については，Draft FIPS-180-2 p. 9 を参照．
(i)

(i)

Draft FIPS-180-2 では，H0 , H1 , . . . , H7 で初期化している．これは Draft FIPS-180-2 の誤記と思われる．SHA-1, 384, 512 の記述にも同様の誤記がある．

3

4. i 番目の中間ハッシュ値を計算する．
(i)

(i−1)

H0 = a[64] + H0 ,
(i)
(i−1)
H2 = c[64] + H2 ,
(i)
(i−1)
H4 = e[64] + H4 ,
(i)
(i−1)
H6 = g[64] + H6 ,

(i)

(i−1)

H1 = b[64] + H1 ,
(i)
(i−1)
H3 = d[64] + H3 ,
(i)
(i−1)
H5 = f [64] + H5 ,
(i)
(i−1)
H7 = h[64] + H7

上記の 1.∼4. までの処理が SHA-256 の圧縮関数である．

2.1.3

SHA-512

メッセージ m を padding して，1024 の倍数の長さのビット系列に変換する．padding 方法については，Draft FIPS-180-2 p. 12 を参照．そして，m を n 個の 1024bits のメッセー
ジブロックに分割する．それを m(1) , m(2) , . . . , m(n) と書く．i = 1, 2, . . . , n に対して，以
(n)
(n)
(n)
下の処理を行う (各変数は 64bits)．メッセージ m のハッシュ値は，H0 |H1 | · · · |H7 である．

1. m(i) を 64bits 毎に分割し，それらを m[t] (0 ≤ t ≤ 15) と書く．そして，w[t] を以下のように計算する．
 m[t]

w[t] = 

{512}
{512}
σ1 (w[t − 2]) + w[t − 7] + σ0 (w[t − 15]) + w[t − 16]

0 ≤ t ≤ 15
16 ≤ t ≤ 79
(16)

ここで，
{512}

(x) = ROTR1 (x) ⊕ ROTR8 (x) ⊕ SHR7 (x)

(17)

{512}

(x) = ROTR19 (x) ⊕ ROTR61 (x) ⊕ SHR6 (x)

(18)

σ0
σ1
である．

2. 変数を初期化する．

(i−1)

a[0] = H0 ,(i−1)
c[0] = H2 ,(i−1)
e[0] = H4 ,(i−1)
g[0] = H6 ,
(0)

(0)

(i−1)

b[0] = H1 ,(i−1)
d[0] = H3 ,(i−1)
f [0] = H5 ,(i−1)
h[0] = H7(0)

なお，H0 , H1 , . . . , H7 については，Draft FIPS-180-2 p. 14 を参照．

3. t = 0, 1, . . . , 63 に対して以下の計算を繰り返す (一つの t に対する以下の処理をまとめて，1 ステップと呼ぶ)．
{512}

T1 [t] = h[t] + Σ1
{512}

T2 [t] = Σ0{512}(e[t]) + Ch(e[t], f [t], g[t]) + Kt

(a[t]) + Maj(a[t], b[t], c[t])a[t + 1] = T1 [t] + T2 [t]+ w[t]

(19)
(20)
(21)

4

b[t + 1] = a[t](22)c[t + 1] = b[t](23)

d[t + 1] = c[t](24)e[t + 1] = d[t] + T1 [t](25)

f [t + 1] = e[t](26)g[t + 1] = f [t](27)h[t + 1] = g[t]

(28)

ここで，
{512}

(x) = ROTR28 (x) ⊕ ROTR34 (x) ⊕ ROTR39 (x)

(29)

{512}

(x) = ROTR14 (x) ⊕ ROTR18 (x) ⊕ ROTR41 (x)

(30)

Σ0
Σ1

{512}

である．なお，Kt

については，Draft FIPS-180-2 p. 10 を参照．

4. i 番目の中間ハッシュ値を計算する．
(i)

(i−1)

H0 = a[80] + H0 ,
(i)
(i−1)
H2 = c[80] + H2 ,
(i)
(i−1)
H4 = e[80] + H4 ,
(i)
(i−1)
H6 = g[80] + H6 ,

(i)

(i−1)

H1 = b[80] + H1 ,
(i)
(i−1)
H3 = d[80] + H3 ,
(i)
(i−1)
H5 = f [80] + H5 ,
(i)
(i−1)
H7 = h[80] + H7

上記の 1.∼4. までの処理が SHA-512 の圧縮関数である．
SHA-384 のアルゴリズムは，以下の二点を除いて SHA-512 のアルゴリズムと同じである．
(0)• 2. の Hi の値が異る．
(n)

(n)

(n)

• メッセージ m のハッシュ値を H0 |H1 | · · · |H5 とする．

2.2

SHA-256, 512 の特徴

SHA-256, 512 のアルゴリズムは，SHA-1 のアルゴリズムとかなり異る．その相違点を
表 1 ∼ 表 3 にまとめる．
安全性に関係すると思われる変更点を列挙する．
• メッセージ拡張処理が複雑になっている．これは，後の章で述べるように，安全性の向上に役立っている．
• 1 ステップで更新される変数が二つになっている．これは，後の章で述べるように，
既存の攻撃法の適用を困難にしている．
なお，SHA-1 では，巡回シフトが全て左向きであるの対し，SHA-256 では，全て右向きである．左向き巡回シフトは，右向き巡回シフトで実現することができるので，この変更
は安全性に影響しない．

5

表 1: 入出力サイズと内部のステップ数
ワード[bits]

メッセージ[bits]

ハッシュ値[bits]

ステップ数

32
32
64

512
512
1024

160
256
512

80
64
80

SHA-1
SHA-256
SHA-512

表 2: 1 回のメッセージ拡張処理
演算の種類

SHA-1
SHA-256
SHA-512⊕, ROTL(),+, ⊕, ROTR(), SHR()+, ⊕, ROTR(), SHR()

演算回数

4
13
13

表 3: 1 ステップの処理

SHA-1
SHA-256
SHA-512

演算の種類

演算回数

+, ROTL(), ∧, ∨, ¬, ⊕+, ROTR(), ⊕, ∧, ∨, ¬+, ROTR(), ⊕, ∧, ∨, ¬

8 又は 10
25
25

6

2.3

Draft FIPS-180-2 への公開コメント

Draft FIPS-180-2 に対しては，三つの公開コメントがある [12]．そのうちの一つは技術的内容がないので，それ以外の二つのコメントを以下にまとめる．
2.3.1

Jonsson のコメント

Jonsson のコメントの主旨を以下に述べる．いずれも妥当なコメントである．特に 1. は重要であり，NIST の今後の対応が注目される．
1. SHA-256, 384, 512 の設計は，SHA-1 の設計とはかなり異る．NIST は SHA-256, 384,
512 の安全性評価を公開し，SHA-1 と異る設計にした理由を明らかにせよ．
2. SHA-256 の出力を 160bits に制限した方法も SHA-1 の代替として標準化してはどうか．
3. SHA-256 と SHA-512 のアルゴリズムは非常に良く似ているため，コードサイズを小さくすることができることを明記すべきである．
2.3.2

Kelsey のコメント

Kelsey は，SHA-256, 384, 512 のもつ extension property について言及している．この
extension property は，SHA-256, 384, 512 固有の性質ではなく，MD4 の改良と位置づけられるハッシュ関数全て (SHA-1, MD5 等) がもつ性質である．extension property が問題となるのは，SHA-256, 384, 512 を鍵付ハッシュ関数として利用する場合である．Kelsey
は extension property 問題を解決する方法を提案している．
以下に Kelsey のコメント，特に extension property とその解決法についてまとめる．
Extension property SHA-256, 384, 512 を h() と書く．あるメッセージ m に対するハッシュ値を h(m) とする．このとき，m が未知であっても，m の長さと h(m) から別のメッセージ m|p|m0 のハッシュ値 h(m|p|m0 ) を計算することができる．ここで，pは h(m) を計算するときに m に付加される padding データ (主に m の長さ) であり，
m0 は任意のメッセージである．
Extension property 問題 送信者と受信者が鍵 k を共有しており，k を用いてメッセー
ジ認証を行うとする．メッセージ m に対する MAC 関数を
M AC(k, m) = h(k|m)とする．このとき，攻撃者は k の長さ, m の長さ及び h(m) が分かれば，extension
property より，別のメッセージ m|p|m0 の MAC 値を計算することができる．

7

解決方法 h() のアルゴリズムを以下のように変更する．m の最終ブロック (padding デー
(n−1)
(n−1)
(n−1)
タを含むブロック) を処理するとき，H0, H1, . . . , H7に固定ビット系列(0xa5a5· · ·a5) を排他的論理和で加える，つまり，
(n−1)

Hj

(n−1)

= Hj
(n−1)

このように更新された Hj

3

安全性の検討3.1

安全性の評価基準⊕ 0xa5a5a5a5 (j = 0, 1, . . . , 7).

に対して，最終ブロックの処理を行う．

Draft FIPS-180-2 では，ハッシュ関数の安全性を同じハッシュ値になる異るメッセージ(衝突) を発見するために必要な計算量で評価している．これは妥当な評価基準である．
これまでに代表的なハッシュ関数各々に対して安全性の検討，攻撃法の提案がなされている．しかし，強力な攻撃法であるほど，個々のハッシュ関数の仕様に強く依存している
ため，その攻撃法を別のハッシュ関数の安全性の検討に利用することは難しい．どのハッシュ関数にも適用可能な攻撃法 (衝突を発見する方法) としては，birthday paradox に基づく攻撃法 (BP 攻撃法) 以外に見当たらない．
Draft FIPS-180-2 では，SHA-256, 384, 512 に対して，BP 攻撃法により衝突を発見するために必要なメッセージ数を各々2128 , 2192 , 2256 と見積もっている．これは，SHA-256,
384, 512 が任意長のメッセージを 256, 384, 512bits に写像する理想的なランダム関数と仮定した場合，衝突するメッセージを確率約 1/2 で発見するために必要なメッセージ数である．
したがって，SHA-256, 384, 512 が安全であることを示すには，あらゆる攻撃法の計算量がこれらのメッセージ数を生成する計算量よりも多いことを示す必要がある．SHA-256,
384, 512 への攻撃方法は，主に次の四つに分類される．
ランダム性 暗号プロトコルでの利用を考えると，ハッシュ関数の出力は，擬似乱数のようになっていることが望ましい．例えば，入力ビット系列の少しの変化が全ての出
力ビット系列に影響する方が良い．これについては，3.2 章で述べる．

BP 攻撃法 SHA-256, 384, 512 が任意長のメッセージを 256, 384, 512bits に写像する理想的なランダム関数でない場合，少ないメッセージ数で衝突が生じる可能性がある．
これについては，3.3 章と 3.4 章で述べる．
衝突困難性 SHA-256, 384, 512 を h() とするとき，h(m) = h(m0 ) となる二つの異るメッ
セージ m, m0 を発見することが難しくなければらならない．これについては，3.5 章
で述べる．
一方向性 SHA-256, 384, 512 を h() とする．一方向性を二つの場合に分けて考える．

1. m と h(m) が与えれたとき，h(m) = h(m0 ) となる m0 を発見することが難しい．

8




! 

 

 



 

 

 











d

図 2: SHA-256 におけるメッセージの変化がハッシュ値に及ぼす影響 (サンプル数: 226 対)

2. h(m) が与えれたとき，h(m) の原像 m を発見することが難しい．
後者について，3.6 章で述べる．

3.2

メッセージの変化がハッシュ値に及ぼす影響

任意長のビット系列を n ビットに写像する一様分布のランダムな写像 h を考える．二つのビット系列 m1 , m2 の写像されたビット系列 h(m1 ), h(m2 ) のハミング距離が d となる確率 Pn (d) は，³ ´Pn (d) =nd2n

上記の確率 Pn (d) は，d = n/2 とき最大となる．これは，入力のビット系列のハミング距
離に関わらず，出力のビット系列の各ビットが変化する確率が 1/2 であることを意味する．
SHA-256, 512 も上記の性質を満たすべきである．そこで，ハミング距離が 1 の二つのメッセージ m1 , m2 の SHA-256, 512 によるハッシュ値 h(m1 ), h(m2 ) のハミング距離を計算機実験で調べた．その結果を図 2, 図 3 に示す．図 2, 図 3 の理論値とは，各々P256 (d) ∗100, P512 (d) ∗ 100 の値である．図 2, 図 3 から，ハッシュ値 (出力のビット系列) の変化は
理論値どおりであることが分かる．

9




! 

 

 


 

 












d

図 3: SHA-512 におけるメッセージの変化がハッシュ値に及ぼす影響 (サンプル数: 223 対)

3.3

BP 攻撃法による衝突困難性の検証

SHA-256, 512 に対して，BP 攻撃法を行った結果を表 4 示す．表 4 のメッセージ数は，
表 4: SHA-256, 512 への BP 攻撃
メッセージ数 [個]SHA-256
SHA-512衝突したメッセージ数 [個]225 (≈ 3.36 × 107 )1.5 × 223 (≈ 1.26 × 107 )

00

使用した計算機の RAM に記憶できる最大のメッセージ数である．SHA-256, 512 のいずれの場合も衝突するメッセージを発見できなかった．
SHA-256 が任意長のメッセージを 256bits に写像する理想的なランダム関数であると仮定した場合，この実験で衝突するメッセージが発見できる確率 p256 (225 ) は，以下のように見積もることができる．

p256 (225 ) = 1 − (1 −

1

)(1 −
256

2
2
25
2
25
< 1 − (1 − 256 )22
225 · 225)
≈ 1 − (1 −
2256

10

2

) · · · (1 −256

225 − 1
)
2256

=

1
2206

同様に，SHA-512 の場合の確率 p512 (223 + 222 ) は以下のようになる．

p512 (223 + 222 ) = 1 − (1 −

1

)(1 −
512

2
2
224 224< 1 − (1 − 512 )2
224 · 224
≈ 1 − (1 −
)
2512
1
= 464
2

2

) · · · (1 −512

223 + 222 − 1)
2512

この実験ではメッセージ数が非常に少ないので，この実験結果から，SHA-256, 512 が任意長のメッセージを 256bits, 512bits に写像する理想的なランダム関数であるということは言えない．さらに，BP 攻撃法を実行することにより，SHA が任意長のビット系列を
固定長のビット系列に写像する理想的なランダム関数であるかどうかを検証することは，現実的でない．なぜなら，BP 攻撃法を実行することが現実的でないように，ハッシュ値のビット長を設定しているからである．

3.4

並列処理による高速化と安全性

SHA-1 の 1 ステップあたりのメッセージ拡張処理も含めた算術・論理演算回数は，高々14 回である．SHA-1 の圧縮関数は 80 ステップあるので，高々1120 回の算術・論理演算が必要である．一方，SHA-1 のアルゴリズムは並列処理に向いていることが知られている [3]．全て算術・論理演算が同じ時間で実行可能かつ完全に並列動作可能な算術・論理演算器を 7 つ使用できるならば，メッセージ拡張処理も含めて 2 回の演算時間で 1 ステッ
プを終了することができる，つまり，ハッシュ値の計算時間 1/7 にすることができる．ただし，現在のところ，並列動作可能な 7 つの演算器をもつ汎用 CPU はなく，そのような演算器をもつプロセッサを実現することは容易ではないだろう [3]．
しかし，もし攻撃者がそのようなプロセッサを作成して SHA-1 に対して BP 攻撃法を行った場合，280 個のメッセージの生成時間を 1/7 に短縮できる．このように，ハッシュ関数のアルゴリズムの内部処理が並列化できるならば，それが BP 攻撃法に対する安全性の低下の原因となる可能性がある．
SHA-256 のアルゴリズムの並列化の可能性を考えよう．SHA-256 のアルゴリズムにおける 1 ステップで更新される変数は式 (6) と式 (10) の a[t + 1], e[t + 1] であり，その他の変数は直前のステップの別の変数の代入である．したがって，式 (6) と式 (10) の計算を “いつから開始か?”という点が重要である．
式 (6) の計算には，e[t] の値が必要である．e[t] は e[t] = d[t−1]+T1 [t−1] であるので，直前のステップで更新された値である．したがって，T1 [t − 1] の計算が終了しなければ，e[t]を計算することができない．再帰的に，T1 [t − 1] の計算には e[t − 1] が必要であり，e[t − 1]
は T1 [t − 2] の計算が終了していなければならない．また，式 (10) の計算には，a[t] の値が11必要である．そして，a[t] は直前のステップで更新された値なので，T1 [t − 1], T2 [t − 1] の計算が終了しなければ，a[t] は求めることができない．したがって，その直前のステップの計算が終了する前に，計算可能な部分としては，{256}• 式 (4) の h[t] + Kt

+ w[t] の計算• 式 (5) の Maj(a[t], b[t], c[t]) の一部の計算だけである．このように，SHA-256 では，その直前のステップの計算が終了しないと，そのステップの大部分の計算を開始することができない．
以上のことより，SHA-256 では，仮に並列動作可能な多くの演算器があったとしても，それらを有効に使うことはアルゴリズム的に難しい．SHA-1 の場合，特別なプロセッサの使用により BP 攻撃法への安全性がやや低下する場合があるが，SHA-256 の場合，そのような安全性の低下はほとんどない．なお，SHA-512 の場合も，変数のビット長が異るだけなので，SHA-256 と同様の結論を得ることができる．
SHA-1 では，あるステップで更新される変数を計算するために使われる変数の値がそのステップより数ステップ前にすでに決定されているため，優れた並列化が可能になっている．一方，SHA-256, 512 では，あるステップで更新される変数を計算するために使われる変数の値が，直前のステップの計算により決定される．この違いが，SHA-1 と SHA-256,
512 のアルゴリズム的な並列可能性の違いの原因である．
ただし，SHA-256, 512 のアルゴリズム中の演算の並列処理が全く不可能ではないことに注意しよう．例えば，上述の演算は，直前のステップと並列に計算することが可能である．また，式 (1) から，2 ステップ前のメッセージが得られていれば，メッセージ拡張処理を開始することができる．現在の汎用 CPU は，数個の演算を並列に処理することができる．よって，SHA-256, 512 のアルゴリズムは，現在の汎用 CPU の並列処理能力を活用する程度の並列処理は可能なアルゴリズムである．また，Pentium III 上の実装で，SHA-1,
256, 512 は，MD5, RIPEMD と比較して，複数のメッセージの並列処理に向いていることも報告されている [9]．
したがって，SHA-256, 512 のアルゴリズム的な並列処理可能性が安全性と処理速度に及ぼす影響は，次のようにまとめることができる: SHA-256, 512 のアルゴリズムは，非常に高度な並列処理能力をもつプロセッサがあったとしても，BP 攻撃により安全性が低下するほどの並列化はアルゴリズム的に難しくなるように設計されているが，現在のプロセッサの並列処理能力を活用すると，ハッシュ値の計算速度の向上が期待できるように設計されている．

3.5

既知の攻撃法の適用

この章では，これまでに提案された他のハッシュ関数への代表的な攻撃法を SHA-256,
512 へ適用することを検討する．

Dobbertin の MD4 の衝突探索アルゴリズム Dobbertin は，MD4 で衝突する二つのメッセージ発見する効率的なアルゴリズムを提案している [6]．このアルゴリズムは極め12て強力であり，MD4 が衝突困難な関数でないことを明らかにした．しかし，このアルゴリズムは MD4 の仕様に深く依存しているので，このアルゴリズムを SHA-256,
512 へ適用することは極めて難しい．特に，以下の部分が適用を難しくしている．

• MD4 にはメッセージ拡張処理がないが，SHA-256, 512 にはメッセージ拡張処理がある．
• MD4 では，1 ステップで更新される変数は一つだが，SHA-256, 512 では，それが二つある．
• MD4 では，1 ステップ中のビットの巡回シフトは 1 回だが，SHA-256, 512 では，それが 6 回ある．
このアルゴリズムは，MD5 の擬似衝突を求めるアルゴリズム [6] や短縮された RIPEMDの衝突を求めるアルゴリズム [7] に発展したが，それらを SHA-256, 512 へ適用することは同様の理由で極めて難しい．

Chabaud と Joux の SHA-0 の差分を利用した衝突探索アルゴリズム Chabaud と Joux
は，差分攻撃法を利用して SHA-0 の衝突探索アルゴリズムの計算量を 261 と理論的に評価した [4]．SHA-0 のハッシュ値は 160bits であるから，このアルゴリズムは BP
攻撃法よりも効率の良い攻撃法である．しかし，このアルゴリズムを SHA-1 に適用しても BP 攻撃法よりも効率良く衝突を発見することはできない．その原因は，
SHA-1 のメッセージ拡張処理における 1 ビットの巡回シフトにある．つまり，メッ
セージ拡張処理における 1 ビットの巡回シフトによって，SHA-1 の差分攻撃法に対する安全性は SHA-0 よりも向上している．
Chabaud と Joux のアルゴリズムを SHA-256, 512 へ適用することは極めて難しい．
ハッシュ値の長さの違いだけでなく，SHA-256, 512 のメッセージ拡張処理は，SHA-1のそれよりもさらに複雑になっているためである．
ラウンド数を削減した SHA-1 の衝突探索アルゴリズム 1 ラウンド (ステップ 1 からステップ 20) のみの SHA-1 の衝突探索アルゴリズムが提案されている [8]．このアルゴリ
ズムを SHA-256, 512 に適用することは，以下の理由により極めて困難である．

• SHA-256, 512 のメッセージ拡張処理が SHA-1 のそれよりも多くの巡回シフトを含んでいる．
• MD4 では，1 ステップで更新される変数は一つだが，SHA-256, 512 では，それが二つある．さらに，その二つの変数が直前のステップで更新された値に依存している．
いずれの攻撃法に対しても，メッセージ拡張処理が安全性の向上に寄与していることが分
かる．

13

3.6

原像探索困難性について

SHA-256, 512 の場合，メッセージ m とそのハッシュ値 h(m) が与えられたとき，h(m) =h(m0 ) となるメッセージ m0 が存在する．そのような m0 を求めることが計算量的に困難な場合，そのハッシュ関数は一方向性であるという．この章では，SHA-256 のハッシュ値
h(m) のみが与えられたとき，原像である m を求めることを検討する．最初に以下の補題を証明する．
補題 1 SHA-256 において，式 (6) ∼ 式 (13) の a[t], b[t], . . . , h[t] と a[t+4], b[t+4], . . . , h[t+4]が与えられたとき，W [t], W [t + 1], W [t + 2], W [t + 3] の値は一意であり，効率良く求められる．
証明 1 SHA-256 のアルゴリズムから，h[t + 4] = d[t] + T 1[0] であるので，T 1[0] の値を求めることができる．そのとき，W [t] の値は，以下の式で計算できる．
{256}

W [t] = T 1[t] − (h[t] + Σ256
1 (e[t]) + Ch(e[t], f [t], g[t]) + Kt)

式 (5) ∼ 式 (13) を用いて，a[t + 1], b[t + 1], . . . , h[t + 1] を計算する．
次に，T 1[1] = g[t + 4] − c[t]+ から T 1[1] を計算する．そのとき，W [t + 1] の値は，以下の式で計算できる．
{256}

W [t + 1] = T 1[t + 1] − (h[t + 1] + Σ256
1 (e[t + 1]) + Ch(e[t + 1], f [t + 1], g[t + 1]) + Kt+1 )式 (5) ∼ 式 (13) を用いて，a[t + 2], b[t + 2], . . . , h[t + 2] を計算する．同様の計算を繰り返すことにより，W [t + 2], W [t + 3] を計算することができる．
上記の補題より，以下の定理を直ちに得ることができる．
定理 1 SHA-256 において，式 (6) ∼ 式 (13) の (a[t], b[t], . . . , h[t]), (a[t+4], b[t+4], . . . , h[t+4]), . . . (a[t + 16], b[t + 16], . . . , h[t + 16]) が与えられたとき，W [t], W [t + 1], . . . , W [t + 16]の値は一意であり，効率良く求められる．
上記の定理において，もし t = 0 ならば，求めた W [0], W [1], . . . , W [16] はメッセージそのものである．一般には，W [t], W [t+1], . . . , W [t+16] から式 (1) を用いて，W [0], W [1], . . . , W [16]を計算する必要がある．しかし，16 個の式 (1) の連立方程式には，シフト，巡回シフト，
論理演算，法加算の演算が混在しているため，それを解く効率の良いアルゴリズムは自明
ではなく，今回の評価では，そのアルゴリズムを考案することができなかった．なお，上記と同様の議論が SHA-512 に対しても成立する．
次に，SHA-1 に対して，同様の攻撃を考える．同様の記法を用いると，(a[t], b[t], . . . , e[t]),(a[t + 5], b[t + 5], . . . , e[t + 5]), . . . (a[t + 15], b[t + 15], . . . , e[t + 15]) が与えられたとき，O(232 ) の計算量で，W [t], W [t + 1], . . . , W [t + 16] の値は一意に決定することができる．さらに，SHA-1 のメッセージ拡張処理は巡回シフトと排他的論理和だけからなり，この二つの演算は可換なので，t 6= 0 のでも W [0], W [1], . . . , W [16] を容易に決定することができる．
アルゴリズムの実行中の変数の値が攻撃者に知られることは，現実には起りにくい．しかし，仮にそのようなことが起ったとしても，SHA-256, 512 の場合，そのハッシュ値の原像を求めることは容易ではない．この章で考察したような攻撃法に対しても，SHA-256,
512 のメッセージ拡張処理が安全性の向上に役立っていることがわかる．

14

3.7

Kelsey 法の評価

2.3.2 章で述べた Kelsey 法の評価を述べる．Draft FIPS-180-2 には，ハッシュ関数を鍵付ハッシュのメッセージ認証に利用することを述べているので，Kelsey のコメントは検討する価値がある．[12] では，Kelsey 法は安全性と処理速度を損なうことなく，extension
property をなくすことができると述べられている．処理速度が著しく低下しないことは自明であるが，安全性については，証明はされていない．
一方，安全なハッシュ関数を用いて，効率的かつ安全性が証明可能な鍵付ハッシュ関数の構成法が知られている [1]．この構成法を Kelsey 法を比較した場合，処理速度は Kelsey法の方が優れているが，安全性の面で Kelsey 法はまだ検討が十分ではない．したがって，
Kelsey 法の安全性の証明がされるまでは，[1] の構成法を利用する方がよいであろう．

4

結論

この報告では，SHA-256, 384, 512 の安全性の検討を行った．現在のところ，SHA-256,
384, 512 の致命的な欠点はもちろん，安全性を疑わせるような点も見当たらない．しかし，
SHA-256, 384, 512 のアルゴリズムは提案されてから日が浅く，安全性が十分に研究されているとは言えない．今後も引き続き安全性を検討する必要がある．
SHA-256, 384, 512 の設計は，SHA-1 の設計とはかなり異っている点に十分に注意をする必要がある．その設計の変更は，いくつかの攻撃に対して SHA-256, 384, 512 の安全性の向上に役立っていることが今回の検討で確認できた．特に，メッセージ拡張処理が複雑になっている点が既存の攻撃法に対する安全性の向上に大きく寄与している．しかし，逆に，設計の変更点が安全性の低下の要因になる可能性も否定はできない．Jonsson のコメ
ントにもあるように，NIST が SHA-256, 384, 512 の安全性評価を公開し，SHA-1 と異る設計にした理由を明らかにすることが望まれる．

15

参考文献
[1] M. Bellare, R. Canetti, and H. Krawczyk, “Keying hash functions for message authentication,” Advances in Cryptology - CRYPTO’96, Lecture Notes in Computer
Science, vol. 1109, pp. 1–15, 1996.
[2] M. Bellare and P. Rogaway, “Collision-resistant hashing: Towards making UOWHFs
practical,” Advances in Cryptology - CRYPTO’97, Lecture Notes in Computer Science, vol. 1294, pp. 470–484, 1997.
[3] A. Bosselaer, R. Govaerts, and J. Vandewalle, “SHA: A design for parallel architectures ?,” Advances in Cryptology - EUROCRYPT’97, Lecture Notes in Computer
Science, vol. 1233, pp. 348–362, 1997.
[4] F. Chabaud and A. Joux, “Differential collisions in SHA-0,” Lecture Notes in Computer Science Advances in Cryptology - CRYPTO’98, vol. 1462, pp. 56–71, 1998.
[5] I. B. Damgård, “A design principle for hash functions,” Advances in Cryptology CRYPTO’89, Lecture Notes in Computer Science, vol. 435, pp. 416–427, 1990.
[6] H. Dobbertin, “Cryptanalysis of MD4,” Lecture Notes in Computer Science Fast
Software Encryption, vol. 1039, pp. 53–69, 1996.
[7] H. Dobbertin, “RIPEMD with two-round compress function is not collision-free,”
Journal of Cryptology, vol. 10, no. 1, pp. 51–69, 1997.
[8] 木村太一，桑門秀典, 田中初一, “SHA の高速衝突探索の一手法,” 第 22 回情報理論とその応用シンポジウム予稿集, pp. 463-466, 1999.
[9] J. Nakajima and M. Matsui, “Parallel implementations of dedicated hash functions,”
Proceedings of the 2002 Symposium on Cryptography and Information Security,
vol. II, pp. 867–872, 2002.
[10] National Institute of Standards and Technology, “Secure hash standard,” NIST FIPS
PUB 180-1, 1993.
[11] National Institute of Standards and Technology, “Secure hash standard,”
Federal Information Processing Standards Publication 180-2,
http://csrc.nist.gov/encryption/shs/dfips-180-2.pdf, 2001.
[12] National Institute of Standards and Technology, “Public comments on the draft federal information processing standard (FIPS) draft FIPS 180-2, secure hash standard(SHS),” http://csrc.nist.gov/encryption/shs/dfips-180-2-comments1.pdf, 2001.
[13] V. Shoup, “A composition theorem for universal one-way hash functions,” Advancesin Cryptology - EUROCRYPTO 2000, Lecture Notes in Computer Science, vol. 1807,
pp. 445–452, 2000.

16