SHA-256/-384/-512 の評価報告
東京理科大学理工学部電気電子情報工学科
金子敏信
2006 年 3 月

概要SHA-256/-384/-512 は 2002 年に FIPS 180-2 SECURE HASH STANDARD として SHA-1 と共に、規定されたハッシュ関数群の中の 256 ビット以上のハッシュ値を出力するＭＤ型ハッシュ関数である。これらはハッシュビット長およびその構造から、SHA-1 の上位バージョンと想定され、まとめて SHA-2 とも呼ばれる。2004 年以降の Wang らの攻撃により、SHA-1 の安全性に関し、疑問が呈されて活発な議論が行われている。本報告では、SHA-2 の安全性に関する Gilbert の 2003
年の論文以来、2006 年１月末までに公表された論文で、SHA-2 の安全性係わる記述が見られるものを網羅しまとめた。Wang らの一連のハッシュ関数の衝突探索の基本的な戦略は、(1.) 差分パスの局部衝突の重ね合わせで大域的な衝突を見つける (disturbance vector 探索)(2.) XOR 差分と符号付き算術差分を同時に解析し、確率の高い差分パスを探索する(3.) 差分伝播の十分条件を解析し、確率を高く保つメッセージ語変更法を見つけることと考えることが出来る。

SHA-2 に関しても、現在までの研究で、同様な戦略がとられている。Gilbert らは、SHA-2 の圧縮関数を線形近似し、XOR 差分について、9 ステップで確率 2−66 の局部衝突を導いている。これは最良の局部衝突であるが、大域的衝突には、SHA-256 の場合、それが少なくとも３個以上、SHA-384/-512 においては５個以上必要と見積もられ、SHA-2 は (1.) の戦略のみを持つ Joux 型の攻撃に対し安全であると結論づけている。

Hawkes らは、この局部衝突のみに,(2.),(3.) の戦略を適用している。符号付き算術差分も合わせて考察し、拡張メッセージワード差分変更法を提案している。それにより、確率が 2−39 から 2−42に上昇することを示している。

Lee らは、(3.) のメッセージ変更法が存在すると仮定して、SHA-256 の第 24 から 55 ステップを調査し、衝突には、15 個以上の局部衝突の重ね合わせが必要であり、Hawkes らの結果と合わせる
ことにより、衝突発見の確率は、2−585 以下であるとしている。彼らは、この確率は、思いの外大
きいとしているが、SHA-256 の安全性を脅かす結果ではない。

Yoshida らは、SHA-2 の全ての算術加算を XOR 加算で置き換えた SHA-2-XOR の差分特性を調査している。確率 2−8 の１ステップ繰り返し差分パスを発見しそれを用い、15 ステップ SHA-2-XORの擬似衝突が 2120 の計算量で発見できること、31 ステップ SHA-2-XOR は、ランダムハッシュ関数では無いことを示している。先頭 19 ステップの差分確率を１とするメッセージ変更法を示し、それを用いて、34 ステップ SHA-2-XOR の擬似衝突が、計算量 2120 で発見できると推定している。

Pramstaller らは、予備的調査として、SHA-256 のメッセージ拡張関数の効果を調べている。算術加算を XOR で置き換えて簡略化したメッセージ拡張関数の出力を線形符号と考え、確率的最小重み探索法を使って拡張メッセージ差分の最小ハミング重みが 42 ステップまでで 35 であることを求め、それをい、フルステップで最小ハミング重み 356 と推定している。
以上この３年間の SHA-2 の安全性評価研究を総合するに、現時点の解析結果は、SHA-2 の衝突
探索の成功確率は、誕生日攻撃の確率を上回るものではなく、その安全性を脅かすものではないと考えられる。

1

第1章

はじめに

SHA-256/-384/-512 は 2002 年に FIPS 180-2 SECURE HASH STANDARD として SHA-1 と共に、規定されたハッシュ関数群の中の 256 ビット以上のハッシュ値を出力するＭＤ型ハッシュ関数である。これらはハッシュビット長およびその構造から、SHA-1 の上位バージョンと想定され、まとめて SHA-2 とも呼ばれる。2004 年以降の Wang らの攻撃により、SHA-1 の安全性に関し、疑問が呈され、現在、活発な議論が行われている。本報告では、SHA-2 の安全性に関する Gilbert の2003 年の論文以来、2006 年１月末までに公表された論文で、SHA-2 の安全性係わる記述が見られるものを網羅しまとめた。Wang らの一連のハッシュ関数の衝突探索の基本的な戦略は、
戦略 1. 差分パスの局部衝突の重ね合わせでメッセージ拡張関数通過後の語に対し成り立つ効果的な大域的な衝突（ハッシュ関数の衝突）を見つけること (disturbance vector 探索)
戦略 2. XOR 差分のみで無く符号付き算術差分も同時に解析し、確率高く伝播する差分パスを探索すること
戦略 3. 望ましい差分伝播が起こる内部状態に関する十分条件を解析し、差分伝播確率を高く保つ
メッセージ語変更法を見つけることと考えることが出来る。

SHA-2 に関しても、現在までの研究で、同様な戦略がとられている。

本報告書では、準備として、第 2 章で、ハッシュ関数の基本と SHA-2 のアルゴリズムを紹介し、それ以降の節で、SHA-2 の安全性に関する研究として Gilbert [3], Hawkes [4], 吉田 [9], Lee [5],Pramstaller [8] らの論文をまとめる。

2

第2章

ハッシュ関数 SHA-256/384/512

ハッシュ関数の安全性

2.1

ハッシュ関数とは、与えられた任意長のデータ X から、固定長の値（ハッシュ値）Y = H(X)を生成するデータ圧縮関数 H(X) を言う。暗号の分野で使用されるハッシュ関数は、暗号論的ハッシュ関数と呼ばれ、データを効率よく圧縮する機能だけでなく、次の性質を満たす必要がある。

• 一方向性:ハッシュ値 Y = H(X) が与えられたとき、X を求める事が計算量的に困難であること。

• 第二原像発見困難性：データ X 及び、そのハッシュ値 Y = H(X) が与えられたとき、同一のハッシュ値 y を与えるデータ X  を求める事が計算量的に困難であること。
• 衝突発見困難性：同一のハッシュ値を与える (H(X) = H(X  )) 異なるデータ X,X  の対を求める事が計算量的に困難であること。
これらの計算は、衝突発見、第二原像発見、一方向性、の順により困難となる。ハッシュ値のビットサイズが n の理想的ハッシュ関数の場合、これらの、計算量は、一方向性、第二原像発見困難性に関し、2n 、衝突発見困難性に関し、2n/2 である。1 実在のハッシュ関数の安全性は、それぞれの計算困難性が、理想的ハッシュ関数のそれ、2n 、2n/2 より小さな具体的攻撃法があるか否かで評価される。

2.2

ハッシュ関数 SHA-256/384/512

ハッシュ関数 SHA-256、SHA-384、SHA-512 は、2000 年に米国標準技術局 (NIST) により提案されたハッシュ関数であり、2002 年にハッシュ関数 SHA-1 と共に FIPS 180-2 として制定されている。SHA-1 の上位規格であり、SHA-256,SHA-384,SHA-512 は、ひとまとめにして、通称 SHA-2と呼ばれる。SHA-1 及び SHA-2 は、現時点 (2006 年 3 月) において、CRYPTREC 推奨暗号リス
トのハッシュ関数である。SHA-256、SHA-384、SHA-512 は、よく似た構造を持つので、以下では、SHA-256 のアルゴリズムを中心に紹介し、SHA-384、SHA-512 に関しては、相違点のみ簡単に補足する。

2.2.1

記号と関数の定義

SHA-256 では、1 ワード=32 ビットが、基本の演算単位である。本報告書で、SHA-256 の定義や攻撃法の説明の際に、使用する演算記号を以下に説明する。
1 ビットサイズ n のランダムデータ Y を約 2n/2 個、用意すれば、その中に同一の値が見つかる確率が 1/2 以上となる。この性質を誕生日一致パラドックスといい、それを使った衝突発見攻撃を誕生日攻撃という第 2 章 ハッシュ関数 SHA-256/384/512

3+ : 232 を法とした算術加算⊕ : ビット毎の排他的論理和∨ : ビット毎の論理和∧ : ビット毎の論理積
 : ビットの連結
ROT Ry (x) : x を右に y ビット巡回シフト
SHRy (x) : x を右に y ビットシフト
x̄ : x のビット反転
ΔX : X の排他的論理和差分
δx : x の算術和差分 X[i] : X の i ビット目
SHA-384 及び SHA-512 に言及する場合、1 ワード=64 ビットとして、同じ記号を用いる。
SHA-256 では、以下の 6 種類の論理関数が用いられる。
Ch(x, y, z)=(x ∧ y) ∨ (x̄ ∧ y)

(2.1)

M aj(x, y, z)=(x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z)

(2.2)

Σ0 (x)= ROT R2 (x) ⊕ ROT R13 (x) ⊕ ROT R22 (x)Σ1 (x)= ROT R6 (x) ⊕ ROT R11 (x) ⊕ ROT R25 (x)σ0 (x)= ROT R7 (x) ⊕ ROT R18 (x) ⊕ SHR3 (x)σ1 (x)= ROT R17 (x) ⊕ ROT R19 (x) ⊕ SHR10 (x)

(2.3)

(2.4)
(2.5)

SHA-384 及び SHA-512 では、1 ワード=64 ビットとしている他に、Σ 及び σ 関数においてシフト
ビット数が異なり、以下である。

Σ0 (x)= ROT R28 (x) ⊕ ROT R34 (x) ⊕ ROT R39 (x)Σ1 (x)= ROT R14 (x) ⊕ ROT R18 (x) ⊕ ROT R41 (x)σ0 (x)= ROT R1 (x) ⊕ ROT R8 (x) ⊕ SHR7 (x)σ1 (x)= ROT R19 (x) ⊕ ROT R61 (x) ⊕ SHR6 (x)

(2.6)

(2.7)
(2.8)

2.2.2

SHA-256 の処理

SHA-256 は、264 ビット未満のメッセージから 256 ビットのハッシュ値を生成するハッシュ関数である。SHA-384/512 は、2128 ビット未満のメッセージから 384/512 ビットのハッシュ値を生成する。何れの、ハッシュ関数でも、メッセージを所定の長さにそろえる前処理を行った後、メッ
セージ圧縮関数を適用する。

2.2.3

SHA-256 の前処理

SHA-256 の前処理（パディング処理）は、以下である。

第 2 章 ハッシュ関数 SHA-256/384/512

41. 入力メッセージ M に対し、メッセージ長が 512 ビットの倍数になるように、M の末尾に下記のようなデータを付加する。

M 10k l(2.9)

ただし、l は M のメッセージ長の二進数表現 (64 ビット)、k は l + 1 + k ≡ 448(mod 512) を満たす正の最小値である。この処理をパディングという。

2. パディングされたメッセージは、N 個の 512 ビット単位のブロック M (i) に分割される。
M = M (1) M (2)  · · · M (i)  · · · M (N )(2.10)

ただし、各々の M (i) は、16 個のワード
(i)

(i)

(i)

M (i) = M0 M1  · · · M15

(2.11)からなる。

3. 初期値として
(0)

H0

(0)

H1

(0)
H2
(0)
H3
(0)
H4
(0)
H5
(0)
H6
(0)
H7

= 6a09e667= bb67ae85= 3c6ef372= a54ff53a= 510e527f(2.12)= 9b05688c= 1f83d9ab= 5be0cd19を設定する。

SHA-384/512 の前処理では、メッセージ長が 1024 の倍数となるようにパディングが施されるこ
(0)

(0)

と、ブロック M (i) の長さが 1024 ビットであること、初期値 h0 . . . h7 が、SHA-384/512 の固有の 64 ビット定数であること、が SHA-256 と異なっている。

2.2.4

SHA-256 のハッシュ値計算

N 個のメッセージブロック M (i) , ..., M (N ) の M (i) に対して、1 ≤ i ≤ N の順に以下を実行する。

メッセージ拡張
次式で定義する SHA-256 メッセージ拡張関数を用いて拡張メッセージ Wt を計算する。
(i)

Wt

= Mt

Wt

= σ1 (Wt−2 ) + Wt−7 + σ0 (Wt−15 ) + Wt−16(0 ≤ t ≤ 15)(16 ≤ t ≤ 63)(2.13)(2.14)

第 2 章 ハッシュ関数 SHA-256/384/512

5

SHA-384/512 の場合も、メッセージ拡張関数は同じであるが、処理の単位が 64 ビットになり、σ関数が、式 (2.7) の SHA-512 用の関数に変わり、再帰関係式 (2.13) が、(16 ≤ t ≤ 79) の範囲で適用され、拡張メッセージ Wt (0 ≤ t ≤ 79) が作られる。

圧縮関数

1. 8 個のバッファ変数を (i − 1) 番目のハッシュ値 H (i−1) で初期化する。
(i−1)

a0

= H0

b0

= H1

b0

= H2

d0

= H3

e0

= H4

f0

= H5

g0

= H6

h0

= H7

(i−1)
(i−1)
(i−1)
(i−1)

(2.15)

(i−1)
(i−1)
(i−1)

2. 0 ≤ t ≤ 63 に対して以下の計算を繰り返す。
T1
T2= Ht + Σ1 (et ) + Ch(et , ft , gt ) + Kt + Wt=
Σ0 (at ) + M aj(at , bt , ct )

ht+1
gt+1

=
=

gt
ft

ft+1
et+1
dt+1

=
=
=

et
dt + T 1
ct

ct+1
bt+1

=
=

bt
at

at+1

=

T1 + T2(2.16)

ただし、Kt は 32 ビットの定数である。また、ここでの 1 回の演算を、以下本稿では 1 ステッ
プとする。

3. i 番目の中間ハッシュ値を
(i)

H0

(i)
H1
(i)
H2
(i)
H3
(i)
H4
(i)
H5
(i)
H6
(i)
H7

(i−1)

= H0
=
=

(i−1)

= H3
=
=

+ d64

(i−1)
H4
+ e64
(i−1)
H5
+ f64
(i−1)

= H6
=

+ a64

(i−1)
H1
+ b64
(i−1)
H2
+ c64

+ g64

(i−1)
H7
+ h64

(2.17)

第 2 章 ハッシュ関数 SHA-256/384/5126

図 2.1: 1 ステップの構造で計算する。ここまでの 1 回の処理を、1block とする。
上記手続きを N 回繰り返した最終的な 256 ビットの値(N )

H (N ) = H0

(N )

H1

(N )

H2

(N )

H3

(N )

H4

(N )

H5

(N )

H6

(N )

H7

(2.18)

がメッセージ M のハッシュ値である。

図2

1block の構造

SHA-384/512 の場合、全ての変数が、64 ビット変数になること、定数 Kt が SHA-512 用の定数となること、拡張メッセージ Wt (0 ≤ t ≤ 79) に対して 80 ステップの処理が行われる事が圧縮処理の相違点である。最終的なハッシュ値に関しては、SHA-512 の場合、メッセージ M に対して、512
ビット値

(N )

H (N ) = H0

(N )

H1

(N )

H2

(N )

H3

(N )

H4

(N )

H5

(N )

H6

(N )

H7

(2.19)

第 2 章 ハッシュ関数 SHA-256/384/512

7が、ハッシュ値となるが、SHA-384 の場合、H (N ) の左 384 ビット(N )H (N ) = H0
がハッシュ値となる。

(N )

H1

(N )

H2

(N )

H3

(N )

H4

(N )

H5

(2.20)

8

第3章

Gilbert らの解析

Gilbert らは論文 [3] において、SHA-2 の圧縮関数を線形近似し、XOR 差分について、9 ステップで確率 2−66 の局部衝突を導いている。この局部衝突は最良のものであるが、大域的衝突を構成す
るには、SHA-256 の場合、この局部的衝突が少なくとも３個以上、SHA-384/-512 においては５個以上必要と見積もられ、SHA-2 は、戦略１のみを使う Joux 型の衝突発見攻撃に対し安全であると結論づけている。以下、その概要を紹介する。

3.1

局部衝突

3.1.1

XOR 差分、Ch 関数、M aj 関数

二つの２元ベクトル X,X  に対し、XOR 差分を、次式で表す。

ΔX = X ⊕ X (3.1)

二つのメッセージ X,X  に対し、衝突を見つける事は、ΔX = 0 のメッセージ対に対し ΔH(X) = 0
なるなる物を発見することになる。

SHA-2 においては、選択関数 Ch(x, y, z)(式 (2.1)) , 多数決関数 M aj(x, y, z)(式 (2.2)) が使われている。これらは、32 ビット (又は 64 ビット）変数を並列に処理する関数である。入力 (x, y, z)と出力 Ch、M aj において対応するビット間で、XOR 差分の伝播を調べれば、表 3.1 である。
この表に於いて、ΔCh や ΔM aj 欄が’0’ は、出力差分が常に’0’、’1’ は常に’1’ を表す。’0/1’ は、
確率 1/2 で、出力差分が、’0’ に（又は’1’ に）なることを表す。

表 3.1: Ch,M aj 関数の差分伝播

ΔX

ΔY

ΔZ

ΔCh

ΔM aj

0

0

0

0

0

0

0

1

0/1

0/1

0

1

0

0/1

0/1

0

1

1

1

0/1

1

0

0

0/1

0/1

1

0

1

0/1

0/1

1

1

0

0/1

0/1

1

1

1

0/1

1

第 3 章 Gilbert らの解析

3.2

99 ステップ局部衝突

ハッシュ値が衝突を発見する為に、ハッシュ関数の内部状態の衝突に着目する。SHA-0 に対す
る Joux と Chabaud の攻撃では, 次の手順を踏む。

1. メッセージ語 Wt の 1 ビットの変化で引き起こされる圧縮関数の内部状態の変化を打ち消す可能性の高い拡張メッセージ差分系列 ΔWi ,(i = t + 1, . . . ) を見いだす。（１ビット擾乱パター
ン：1-bit perturbative patterns 又は局部衝突:local collision）1

2. 局部衝突の合成になっている拡張メッセージ差分系列でメッセージ拡張関数の再帰関係式を満足する物を探し、衝突する可能性の高いメッセージ差分を求める。
圧縮関数の非線形性を線形近似する為、局部衝突を与える拡張メッセージ差分系列におけるハミン
グ重みが小さいほど、内部状態の変化を打ち消す確率が高くなる。

SHA-2 の圧縮関数内の Σ 関数で使われている算術加算も、XOR 差分に対して、非線形関数として影響する。Gilbert らは、ハミング重み 1 の差分に対して, 算術加算が XOR 加算と同じ出力差分を与える確率は 1/2,Ch 及び M aj 関数の出力差分が 0 となる確率も 1/2 として,1 ビット擾乱パ
ターンを求めている。
結果の、9 ステップ局部衝突を示せば, 表 3.2 である。Wi に入力した 1 ビット擾乱が、内部状態

a, b, c, d, e, f, g, h に引き起こす差分のハミング重みが、表の第１行に示してある。この擾乱で、ai 及びei に重み１の擾乱が発生している。この差分は、次のステップで Σ0 ,Σ1 関数により、それぞれ重み３の擾乱に拡散するが、それを打ち消す為に Wi+1 に重み 6 の差分を入れれば、ai+1 の擾乱が打ち消され、bi+1 , ei+1 , fi+1 に 1, 3, 1 の重みの擾乱となることが期待できる。これが、２行目に示されている。
このように、W の列に示してある、重み 1, 6, 9, · · · , 1 の差分を Wi , Wi+1 , Wi+2 · · · , Wi+8 を入れれば、(i+8) ステップにおいて、全ての内部状態の差分が０になることが期待される。１ビット擾乱 ΔWiに対し、表 3.2 の局部衝突を与えるメッセージ差分は,ΔWi+1 = Σ1 (ΔWi )⊕Σ0 (ΔWi );DeltaWi+2 =Σ1 (Σ0 (ΔWi )); ΔWi+3 = 0; ΔWi+4 = ΔWi ; ΔWi+5 = ΔWi+1 ; ΔWi+{6,7} = 0;ΔWi+8 = ΔWiである。
Gilbert らは、Σ 関数の拡散効果を考慮して、ハミング重みの低い局部衝突を与える擾乱として、
１ビット擾乱のみを解析しているが、Hawkes らは、論文 [4] において、これが、最良の局部衝突としている。

3.3

9 ステップ局部衝突の確率

表 3.2 の局部衝突が起こるためには、差分が存在するビットについて、算術和が XOR と同じ振る舞いをする事、及び Ch,M aj 関数において、出力差分が 0 になることが必要である。SHA-2 の圧縮関数において、T1 と内部状態 d の加算で、新しい内部状態 e とするときと、T1 と T2 の加算
で、新しい内部状態 a を作るとき算術加算が使われる。算術加算においてキャリが発生する確率の上界は 1/2 と評価される。１ステップ当たり２回の算術加算があることから、１ビットの非零差分当たり、確率は (1/2)2 となる。表の Wi , · · · , Wi+8 には、1 + 6 + 9 + 1 + 6 + 1 = 24 ビットの非零差分があるので、確率は (2−24 )2 = 2−48 である。さらに、Ch,M aj に、18 ビットの非零差分があ
1 変化が打ち消され、内部状態差分がゼロ（即ち、内部状態が衝突）となっている事を局部衝突、１ビットの変化で引き起こされた擾乱を１ビット擾乱パターン、また、その擾乱パターンを拡張メッセージ差分系列で訂正するという意味で、その差分系列を擾乱訂正パターン corective patterns と区別する場合もある。

第 3 章 Gilbert らの解析

10

表 3.2: 9 ステップ局部衝突

i

ΔW

Δa

Δb

Δc

Δd

Δe

Δf

Δg

Δh

i

1

1

0

0

0

1

0

0

0

i+1

6

0

1

0

0

3

1

0

0

i+2

9

0

0

1

0

0

3

1

0

i+3

0

0

0

0

1

0

0

3

1

i+4

1

0

0

0

0

1

0

0

3

i+5

6

0

0

0

0

0

1

0

0

i+6

0

0

0

0

0

0

0

1

0

i+7

0

0

0

0

0

0

0

0

1

i+8

1

0

0

0

0

0

0

0

0

り、その確率は 2−18 と評価される。従って、ランダムなメッセージに対し、この表の局部衝突が起こる確率は 2−66 である。

3.4

SHA-2 の衝突確率の評価

3.4.1

SHA-256

SHA-256 では、圧縮関数は 64 ステップの処理を行う。そのときに使う拡張メッセージ系列は、
式 (2.13) で表されており、引き続く 16 個の拡張メッセージ Wi の差分が 0 の場合、拡張メッセー
ジ全体の差分が 0 になってしまう。9 ステップ局部衝突の合成で、64 ステップの衝突を作るためには、15 + 9 + 15 + 9 + 15 = 63 < 64 であるため、9 ステップ局部衝突 2 個の合成では不十分であり、最低３個合成する必要がある。その衝突発見確率の上界は 2−132 と見積もられ、その計算量は、誕
生日攻撃の 2128 を上回る。従って、この論文で述べた手法は、有効な衝突発見攻撃とは言えない。

3.4.2

SHA-384/512

SHA-384/512 において、圧縮関数は 80 ステップの処理を行う。拡張メッセージ系列の再帰関係
式 (2.13) の中の sigma 関数を調べると、9 ステップ局部衝突の終端から、最大 7 ステップの零差
分系列は、存在しうるが、8 ステップ目には、必ず、非零差分が拡張メッセージ系列に出現する。

15 + 9 + 7 + 9 + 7 + 9 + 7 + 9 + 7 = 79 < 80 であるため、衝突を、9 ステップ局部衝突の合成で作るには、4 こでは不十分で、最低 5 個、必要である。その衝突発見確率の上界は 2−264 と見積もられ、その計算量は、誕生日攻撃の 2254 を上回る。従って、この論文で述べた手法は、有効な衝突発見攻撃とは言えない。

3.5

その他の攻撃Gilbert らは、その他の攻撃として、Dobertin 流の攻撃、擬似衝突の発見可能性について考察し、SHA-2 の場合、何れも誕生日攻撃より、攻撃計算量が大きいであろうと推測している。

第 3 章 Gilbert らの解析

11

MD4 や MD5 に対する衝突を見つけた Dobertin 流の攻撃では、それらの、ハッシュ関数のメッセージ拡張関数が、メッセージ語の並び順を変えているだけの単純なものであるから、適用可能であり、SHA-2 のような、複雑な、メッセージ拡張関数にそのまま適用することは難しいとしている2 。
擬似衝突として、Gilbert らは、同一のメッセージブロック M に対し、異なる２つのハッシュ
連鎖変数 H,H  が、同じハッシュ値を与えるものを考察している。ハッシュ関数の圧縮関数部分
を、ハッシュ連鎖変数を平文入力とメッセージブロックを鍵入力、最終内部状態を暗号文とする
暗号化関数と考えれば、SHA は、Davis-Meyer 構造を持つ。そこでは、ハッシュ連鎖変数は、式(2.17) のように、暗号化関数の出力と加算され、次のメッセージブロックの為のハッシュ連鎖変数となる。SHA-2 におけるこの暗号化関数を SHACAL-2 と呼ぶことにして、その差分特性を調べれば、衝突発見の手がかりとなる3 。彼らは、SHACAL-2 の 4 ステップに対して、確率 2−8 の差分パスを見つけている。それは、複数回の接続が不可能なパスであるが、接続可能と仮定するならば、

SHACAL-2 において、SHA-256 ならば 16 回、SHA-384/512 ならば 20 回接続すれば、それぞれ、
2−128 ,2−160 の確率を持つ差分パスとなる。しかし、この差分パスが使えたとしても、誕生日攻撃よりも効率のよい衝突発見攻撃にはならないとしている。
最後に、彼らは、変形版 SHA-256 として SHA”’-256 を考え、それの衝突発見が非常に容易である事を示している。そこでは、SHA-256 に対して

1. 全ての定数 K0 , · · · , K6 3 が４ビットパターンの繰り返し4
(0)

(0)

2. 初期値 H0 , · · · , H7 が４ビットパターンの繰り返し
3. 全ての算術加算 + は、排他的論理和 ⊕ で置き換え
4. 全てのシフト演算 SHR(x) は、巡回シフト演算 ROT R(x) で置き換えの変形が成されている。このような変形をするならば、処理過程全体に４ビットパターンの繰り返
し（対称性）が発生するので、衝突探索すべきメッセージも４ビットパターンの繰り返しで良いことになる。その下で、計算機探索を行い、SHA”’-256 の衝突発見が驚くほど簡単であるとしている。しかし、この評価が、SHA-256 の安全性評価にどの程度関係するかは、今後の課題であろう。

2 Dobertin 型攻撃の精神を、圧縮関数を解析して、衝突発見確率を上場させるようなメッセージを選択すると理解する
ならば、その考え方は、Wang らのハッシュ関数攻撃におけるメッセージ語変更法に受け継がれている。
3 Davis-Meyer 構造では、この暗号化関数において、入力差分＝出力差分となる高確率の差分パスがあれば、それを使って、ハッシュ連鎖変数の差分＝０、即ち、衝突発見となる可能性が高い
4 SHA’-256,SHA”256 として、それぞれ 16 ビット、8 ビットパターンの繰り返しも述べている

12

第4章

Hawkes らの解析

Hawkes らは、Gilbert の局部衝突の解析に、符号付き算術差分も合わせて考察し、適切な拡張メッ
セージ語差分決定法を提案し、それを使うことにより、Gilbert の局部衝突確率 2−66 が、局部衝突の開始時点の内部状態が未知の場合 2−39 に、既知の場合は、2−9 に上昇することを論文 [4] で示している。また、彼らの手法を使えば、この局部衝突は、第二原像発見攻撃として使用可能であり、攻撃の計算量は、誕生日攻撃の 2n/2 と比較するのではなく、2n と比較すべきと主張している。

Hawkes らの論文は、入力される拡張メッセージ語を攻撃者が自由に変更出来るという前提の上で、Gilbert の９ステップ局部衝突の確率を向上させる事を目指したものであり、SHA-2 の衝突発見を議論しているのでは無いが、その基本的考え方を以下に紹介する1 。詳しくは、論文 [4] を参照されたい。

4.1

Gilbert らの局部衝突

第 3.2 節の 9 ステップ局部衝突を再掲する。ここでは、ハミング重みではなく、差分ベクトルとして表示する。この局部衝突では、拡張メッセージ語 Wi に 1 ビット差分 α1 を入れて引き起こされた内部状態の差分の伝播を 4.1 のように制御する事で、９ステップ局部衝突を構成している。表中の差分は、以下である。

α1 =

ΔWi

β3
γ3

=
=

Σ0 (ΔWi )Σ1 (ΔWi )9=Σ1 (Σ0 (ΔWi ))この表において、Gilbert らは、Ch,M aj 関数の出力差分を０、圧縮関数の中の算術和が、XOR
和と同じ振る舞いをすると期待して、拡張メッセージ差分系列 ΔWi+j を、表の最右列にとれば、内部変数差分は表のように振る舞い、局部衝突が実現できると考えている。Gilbert らは、その確率を Ch,M aj 関数に関し 2−18 , 算術和に関し 2−48 、全体で 2−66 と評価している。Hawkes らは、
算術差分も併用して考えることにより、目標となる内部変数差分が、この表のように伝播するように Wi+j の算術差分を選び、確率を向上させている。

4.2

Gilbert 評価に対する Hawkes の考え

Gilbert らは、SHA-2 のメッセージ拡張関数に関し、考察を行い、9 ステップ局部衝突の合成で得られる衝突の発見確率は、大きくても、SHA-256 の場合 2−132 、(SHA-384/512 の場合 2−264 )であり、2132 (2264 ) の攻撃計算量が掛かるとし、誕生日攻撃の計算量 2128 (2192 又は 2256 ) に比べ、SHA-2 のこの攻撃に対する暗号学的安全性を確認している。
1 本章は、Hawkes らの論文を要約では無く、本報告書作成者の責任で、彼らの基本的考え方としてまとめている

第 4 章 Hawkes らの解析

13

表 4.1: 9 ステップ局部衝突

j

Δa

Δb

Δc

Δd

Δe

Δf

Δg

Δh

0

-

-

-

1

α1

-

-

2

-

α1

3

-

4

ΔWi+j

-

-

-

-

-

α1

-

α1

-

-

-

β3 ⊕ γ3

-

-

β3

α1

-

-

9

-

α1

-

-

β3

α1

-

-

-

-

-

α1

-

-

β3

α1

α1

5

-

-

-

-

α1

-

-

β3

β3 ⊕ γ3

6

-

-

-

-

-

α1

-

-

-

7

-

-

-

-

-

-

α1

-

-

8

-

-

-

-

-

-

-

-

α1

Hawkes らは、衝突発見確率が 1/N ならば、第二原像発見攻撃のように、対象となるメッセージ
M が固定されていても、相手候補である別のメッセージ M  を N 個選べば第二原像が発見できる事が期待されるので、比較する計算量は、第二原像発見攻撃の計算量,SHA-256 で 2256（SHA-384
で 2384 ,SHA-512 で 2512 ) であり、SHA-2 の Gilbert 型攻撃に対する暗号学的安全性が確認されてはいないと主張している。
本報告書作成者は、以下のように考える。Gilbert の攻撃では、差分が固定されており、第二原像発見攻撃で一つめのメッセージ M が与えられたとき、二つめのメッセージ候補 M  は一つしか選べない。従って、第二原像が発見できる確率は無視出来るほど小さいので、第二原像攻撃と考えるのは無理がある。Hawkes らの 9 ステップ局部衝突は、ハッシュ関数の内部状態に依存した拡張メッセージ差分を使うものである。内部状態を推測した上で複数の差分候補を見かけ上、使っているが、第二原像攻撃の立場で、一つめのメッセージ M が与えられたとき、内部状態は一意に決まるため、複数の差分候補 (即ち、複数の第二原像候補）が選べる訳ではない。従って、Hawkes の提案した攻撃を第二原像発見攻撃と比較する事は適切でないと考える。

4.3

算術差分併用方式による９ステップ局部衝突

4.3.1

算術差分と XOR 差分

二つの w 次元２元ベクトル X,X  を２進数として見た物を、x,x とする。0 から 2w − 1 までの数字である。算術差分 δX を

δX = x − x( mod 2w )(4.1)

で表す。ここで、w 次元ベクトル X の第 i ビットを X[i] と表すことにする。

x=

w−1


X[i]2i(4.2)

i=0である。このとき、次の補題が成り立つ。

補題:
XOR 差分 ΔX = λ が与えられたとき、λ[i] = 1 となるビット位置の X の値のみを使い、δx は、

第 4 章 Hawkes らの解析

14

次式で表される。

δX = x − x =

(1 − 2X[i])2i(4.3)

i:λ[i]=1∵) 次の２つの式を δX = x − x に代入すれば、式 (4.3)。

x =
i:λ[i]=1



x

=



X[i]2i +

i:λ[i]=0i

X [i]2 +i:λ[i]=1=

X[i]2iX  [i]2i

i:λ[i]=0(1 − 2X[i])2i +i:λ[i]=1

X[i]2ii:λ[i]=02
ここで、式 (4.1) が 2w を法とする計算であることに注意するならば、2X[w −1]2w−1 = 0( mod 2w )であり、最上位ビット (MSB) の値 X[w − 1] は知らなくても、算術差分 δX が、式 (4.3) から計算できることに注意。

4.3.2

9 ステップ局部衝突の拡張メッセージ差分 δWi+j

表 4.1 の９ステップ局部衝突で、期待する内部状態の差分伝播を、引き起こす為に、拡張メッ
セージ Wi+j の算術差分が使用される。SHA-2 の内部状態は、式 (2.16) によって更新される。変数

Wi+j の変化で、直接に影響を受けるのは、変数 e 及び a である。式に算術差分を適用して考え、Hawkes らは次の基本方針で、入力すべき拡張メッセージの算術差分 δWi+j を決定している。
性質 1. 次式

δWt = −(δHt + δΣ1 (et ) + δ(Ch(et , ft , gt ))(4.4)

を満たすように、算術差分 δWt を選べば、δT1 = ΔT1 = 0 である。このとき、

δet+1
Δet+1

=
=

δdt
Δdt

(4.5)

と成る。
性質 2. 次式

δWt = −(δHt + δΣ1 (et ) + δCh(et , ft , gt ) + δΣ0 (at ) + δM aj(at , bt , ct ))(4.6)

を満たすように、算術差分 δWt を選べば、

δat+1

=

δ(T1 + T2 ) = 0

Δat+1

=

Δ(T1 + T2 ) = 0

(4.7)

となる。
性質 3. M aj 関数の３入力 at , bt , ct の１つのみに差分が入っても、そのビット位置で、残りの２つの変数が等しければ、ΔM aj = 0 となる。

第 4 章 Hawkes らの解析

15

性質 4. Ch 関数の出力差分は、３入力 et , ft , gt の何れかのビットに差分が入っているビット位置に発生しうる。
彼らは、表 4.1 の９ステップ局部衝突のステップ番号 j = 1 に性質 1 を、j = 2, · · · , 8 に性質 2 を適用している。M aj 関数については、性質３を適用し全てのステップで,ΔM aj = 0 としている。
性質１、２の適用を合わせ考えれば、結果として、δaj = 0(j = 2, · · · , 8) を保証していることになる。ΔM aj = 0 が成立するために、内部変数 at , bt , ct の特定ビットに条件が必要となる。期待する局部衝突を実現するために、条件が付く内部変数を Hawkes らは、仮定ビットと呼んでいる。

Ch 関数について、j = 1 ステップでは、内部変数 f1 , g1 の特定ビットに条件を付け、ΔCh1 = 0 としているが、他のステップでは、Ch 関数の出力に差分を許し、その算術差分 δCh を評価し、性質
１により拡張メッセージ差分 δW でそれを打ち消し、差分の拡散を防いでいる。補題により、算術差分を求める時、ＸＯＲ差分 ΔX が非零のビットについては、その値 X[i] が必要である。Hawkes
らは、その推定すべきビットを、推定ビットと呼んでいる。内部状態が不明の場合、攻撃者は、推定ビットを総当たりで推定し、算術差分候補 δWt を試し、局部衝突を見つける。しかし、仮定ビッ
トが条件を満たしているメッセージが１つ見つかったならば、そのメッセージに対して、内部状態を攻撃者は知っている。この場合は、推定ビットを総当たりする必要はない。これが、仮定ビッ
トと推定ビットの性格の違いである。
このような方針で Hawkes らは、9 ステップ局部衝突を引き起こす拡張メッセージ差分 δWi+j を求めている。結果を表 4.2 示す。表中ではステップ番号 i を省略しているが、任意のステップ番号 i
から i + 8 にかけて、この局部衝突を実現出来る。各行はステップ番号を表す。内部変数 a, · · · , h
に関し、上段は XOR 差分、下段は算術差分を表す。δWj の列は、そのステップで入力すべき拡大
メッセージ算術差分を表す。最後の２列は、Ass で仮定ビット、Gue で推測ビットを定める内部変

ˆ = 1 となっているビット位置 i に関
ˆ は、α1[i]数 XOR 差分を表す。例えば、１行目の Ass 欄の α1
ˆ = 1 となっているビット位置 i に関
ˆ は、α1[i]し、内部変数に関する仮定条件があり、Gue 欄の α1
し、別の内部変数ビットを推測する必要があることを示す。X̂ は、２進数ベクトル X から最上位ビットをのぞいたものを表し、|X| は、X のハミング重みを表す。

ˆ = 3,
ˆ = 1,|β3| = |β3|
この局部衝突として、1 ビットの擾乱訂正パターンを選べば、|α1| = |α1|
ˆ = 3,|9| = |9
ˆ = 9 であり、仮定ビット数 u, 推定ビット数 v は、それぞれ|γ3| = |γ3|u=

4 · 1 + 2 · 1 + 3 + 3 = 12

(4.8)

v

=

5 · 1 + 1 + 2 · 3 + 3 + 2 · 3 + 9 = 30(4.9)

となる。従って、合計で、2u+v = 242 の計算量で、局部衝突を発見できる。さらに、擾乱パター
ˆ = 0)、さらにンを最上位ビットに係わるようにすれば、（例えば α1 = 0x80000000 とすれば |α1|
計算量を減らすことが出来、239 となる。
なお、拡張メッセージを攻撃者が自由に選ぶことができるという前提では、2u = 212 の計算量で、仮定ビット条件を満たす拡張メッセージが得られたならば、そのメッセージに対して、ハッシュ関数の圧縮動作を適用して、内部変数の値を確認すれば、推定ビット数分 2v = 230 の試行錯
誤は必要なく、衝突発見の計算量は、212 となる。

第 4 章 Hawkes らの解析

j

16

a

b

c

d

表 4.2: Hawkes の 9 ステップ局部衝突
e
f
g
h

δWj

Ass
ˆ
α1

Gue
ˆ
α1
ˆ
α1
ˆ
γ3

0

Δ
δ

-

-

-

-

-

-

-

-

δE1 = δA1 = δ0

1

Δ

α1

-

-

-

α1

-

-

-

−(δΣ1 (e1 ) + δΣ0 (a1 ))

δ

δ0

-

-

-

δ0

-

-

-

= −(δ1,1 + δ1,2 )α1, α1
ˆ
β3

2

Δ

-

α1

-

-

β3

α1

-

-

−(δCh2 + δΣ1 (e2 ))

α1

δ

-

δ0

-

-

−δ1,2

δ0

-

-

= −(δ2,1 + δ2,2 )

β3

α1
ˆ
9

Δ

-

-

α1

-

-

β3

α1

-

−δCh3 = −δ3

α1

α1

δ

-

-

δ0

-

-

−δ1,2

δ0

-

β3

3

β3

4

Δ
δ

-

-

-

α1
δ0

-

-

β3
−δ1,2

α1
δ0

−(δh4 + δCh4 )−(δ0 + δ4 )

ˆ
α1

5

Δ
δ

-

-

-

-

α1
δ0

-

-

β3
−δ1,2

−(δh5 + δCh5 + δΣ1 (e5 ))−(−δ1,2 + δ5,1 + δ5,2 )

-

α1
ˆ
γ3

6

Δ
δ

-

-

-

-

-

α1
δ0

-

-

−δCh6 = −δ6

-

α1

7

Δ

-

-

-

-

-

-

α1

-

−δCh7 = −δ7

-

α1

δ

-

-

-

-

-

-

δ0

-

Δ

-

-

-

-

-

-

-

α1

−δh8 = −δ0

-

-

δ

-

-

-

-

-

-

-

δ0

8

仮定ビット数
推定ビット数ˆˆ + |β3|4|α1| + 2|α1|
ˆ + |γ3|ˆˆ + 2|β3|
ˆ + |epsilon9|
5|α1| + |α1|

17

第5章

Yoshida らの解析

Yoshida らは、SHA-2 の全ての算術加算を XOR 加算で置き換えた SHA-2-XOR の安全性に関し議論をしている。SHA-2-XOR の圧縮関数部分を暗号化変換と考える SHACAL-2-XOR の差分特性を解析し, 確率 2−8 の１ステップ繰り返し差分パスを発見している。それを適用することで、15ステップ SHA-2-XOR の擬似衝突が 2120 の計算量で発見できる事、同じく、31 ステップ繰り返す
ならば、差分特性確率 2−248 > 2−256 であり、31 ステップ SHA-2-XOR は、ランダムハッシュ関数では無い事を示している。また、先頭 19 ステップの差分確率を１とするメッセージ変更法を示し、残り 15 ステップに、繰り返し差分特性を適用し、34 ステップ SHA-2-XOR の擬似衝突が、計
算量 2120 で発見できると推定している。以下、その概要を述べる。

5.1

SHA-2-XOR と SHACAL-2-XOR の差分解析

5.1.1

１段繰り返し型特性差分

SHA-2 の圧縮関数のレジスタ状態 (a0 , b0 , c0 , d0 , e0 , f0 , g0 , h0 ) を入力平文、(a64 , b64 , c64 , d64 , e64 , f64 , g64 , h64 )を出力暗号文、拡張メッセージ語 Wt (0 ≤ t ≤ 63) を段鍵と考えた暗号化変換を SHACAL-2 という。SHA-2-XOR,SHACAL-2-XOR は、それらの変換内部の算術加算を XOR 演算で置き換えたものである。以下、SHA-2-XOR の 1 段繰り返し差分特性1 を考察し、それが満足するべき制約条件を示す。
ここでレジスタ a の t 段の値を at 、差分を Δat と記す。1 段繰り返し差分では、段 t と t + 1 での差分が同じになっていることから次式である。

Δat+1

=

Δat , Δbt+1=

Δbt , Δct+1=

Δct , Δdt+1

=

Δdt ,

Δet+1

=

Δet , Δft+1=

Δft , Δgt+1=

Δgt , Δht+1

=

Δht

(5.1)

式 (2.16) のように、at+1 , et+1 以外の 6 つのレジスタの差分は、段 t での一つのレジスタの値で決定される。段 t の条件式として整理すれば、上式の 6 つのレジスタの差分に関する条件として

Δat

=

Δbt

=

Δbt

=

Δbt ,

Δet

=

Δet

=

Δgt

=

Δgt

(5.2)

が得られる。残りの二つの制約 Δat+1 = Δat と Δet+1 = Δet に関し、考察する。段関数内で使われている関数の出力差分

ΔCh
ΔM aj

=
Ch(X, Y, Z) ⊕ Ch(X  , Y  , Z  )= M aj(X, Y, Z) ⊕ M aj(X  , Y  , Z  )(5.3)

を、入力差分 ΔXt = Xt ⊕ Xl を使って書き換えれば((Y ⊕ Z) ∧ ΔX) ⊕ (X ∧ ΔY ) ⊕ (X̄ ∧ ΔZ) ⊕ (ΔX ∧ ΔY ) ⊕ (ΔX ∧ ΔZ)

ΔCh

=

ΔM J

= M J(ΔX, ΔY, ΔZ) ⊕ ((Y ⊕ Z) ∧ ΔX) ⊕ ((Z ⊕ X) ∧ ΔY ) ⊕ ((X ⊕ Y ) ∧ ΔZ)

1 ブロック暗号における言い方に従い、ハッシュ関数の演算の１ステップを、この章では、１段と表記する(5.4)

第 5 章 Yoshida らの解析

18

ここで、Ch, M aj 関数の入力は、それぞれ、(e, f, g),(a, b, c) であり、一段繰り返し型差分特性において、式 (5.2) のように、入力差分が等しく ΔX = ΔY = ΔZ である。このとき、ΔCh=(Y ⊕ Z̄) ∧ ΔX

ΔM aj

=

ΔX

(5.5)

となる。これは、M aj 関数は全ての入力差分が同じ場合、線形に振舞うという重要な特性を意味する。上式を使って、ΔT 1t , ΔT 2t , Δat+1 , Δet+1 は、SHACAL-2-XOR の場合、以下となる。

Δet ⊕ Σ1 (Δet ) ⊕ ((ft ⊕ g¯t ) ∧ Δet )

ΔT 1t

=

ΔT 2t
Δat+1

= Σ0 (Δat ) ⊕ ΔM aj(at , bt , ct ) = Σ0 (Δat ) ⊕ Δat=
ΔT 1t ⊕ ΔT 2t

Δet+1

=

(5.6)

ΔDt ⊕ ΔT 1t = Δat ⊕ ΔT 1t

従って、残った Δat+1 = Δat , Δet+1 = Δet の制約条件は以下の二つの条件となる。

Δat
Δet

= ΔT 1t ⊕ ΔT 2t= Δat ⊕ ΔT 1t(5.7)

以下、レジスタ変数差分の段番号の指標 t を、Δat = Δa などと省く。二つの条件は、以下である。

Δa=

ΔT 1t ⊕ Δe

Δe

=

ΔT 2t

(5.8)

式 (5.6) を代入し、条件式は、

Δa =
Δe

Δe ⊕ Σ1 (Δe ⊕ ((f ⊕ ḡ) ∧ Δe) ⊕ Δe
Σ0 (Δa) ⊕ Δa

=

(5.9)

ここで、Δa の条件式中の f ⊕ ḡ の値を, ランダムの値 X と考えることができ、この条件は次の条件となる。

Δa = Σ1 (Δe) ⊕ (X ∧ Δe)(5.10)

これらの条件を満たす１段繰り返し差分特性で高い確率を持つものを考える。SHACAL-2-XORの内部状態更新関数の構造より、差分 Δa, Δe が二つの条件式 (5.9) を満たせば、他の６つの条件
式 (5.2) も満たされることに注意する。二つの条件式において、確率が係わるのが、Δa の条件である。そこでは、Δe[j] が 1 でビット位置 j におけるランダム変数 X[j] の値により、成立／不成立
が変わってくる。従って、確率の一番高い１段繰り返し特性差分は Δe のハミング重みが最も小さいものとなる。以上の議論を定理としてまとめる。定理:

SHA-2-XOR において、入力差分 (Δa, Δb, Δb, Δb, Δb, Δb, Δb, Δb) の差分特性は、ある 32 ビットの値 X に対し、入力差分 Δa, Δe が以下を満たす場合に一段繰り返し特性差分となる。

ΔaΔe= Σ1 (Δe) ⊕ (X ∧ Δe)= Σ0 (Δa) ⊕ Δa

(5.11)

この条件が満たされるとき、他の差分は Δa, Δe によって以下の様に定まる。

Δb=

Δa, Δc=Δa, Δd

=

Δa,

Δf

=

Δe, Δg=Δe, Δg=Δe

また、Δe のハミング重みがもっとも小さいものが一番よい特性差分確率を与える。

(5.12)

第 5 章 Yoshida らの解析

19

表 5.1: １段繰り返し特性差分（確率＝ 2−8 )5.1.2

Δa = Δb = Δc = ΔdΔe = Δf = Δg = Δh3b3b3b3bc0c0c0c067676767
76767676

18181818
81818181

9d9d9d9d
b3b3b3b3

60606060
0c0c0c0c

cecececed9d9d9d9
ecececec

30303030
06060606
03030303

１段繰り返し型特性差分の探索

前節の定理の二つ目の条件を一つ目の条件に代入すれば、次の式となる。

Δa = Σ1 (Σ0 (Δa) ⊕ Δa) ⊕ (X ∧ (Σ0 (Δa) ⊕ Δa))(5.13)

I = Δa ⊕ Σ1 (Σ0 (Δa) ⊕ Δa),R = Σ0 (Δa) ⊕ Δa とおけば、方程式、I = X ∧ R である。この式をビット単位にみれば、i ビット目の式で解 X[i] が存在するのは、R[i] = 1 又は、R[i] = I[i] = 0 の時である。Δa を 232 回総当たりし、その差分に対し、32 ビット分の方程式 (0 ≤ i ≤ 32) が全て解を持つならば、その差分 Δa は１段繰り返し特性差分を構成しうる差分である。
このようにして、１段繰り返し特性差分を調べ上げ、その中で、Δe のハミング重みが最も小さいものを、表 5.1 に示す。
表の 8 つの繰り返しパターンは、同じパターンが循環したものとなっている。
この特性差分の確率を実験的に確認すれば、Δa = b3b3b3b3,Δe = 0c0c0c0c の場合、259/216 であり、ほぼ、2−8 である。この確率を下げているのは、Ch 関数であり、その入力差分 0c0c0c0c は、
確率 2−8 で出力差分 08080808 を与える。これは、以下のビットごとの Ch の差分特性を使って計算される。

ΔCh(0, 0, 0) = 0
ΔCh(1, 1, 1) = 0/1

with probability 1/2

Yoshida らは、同様の手法で、２段繰り返し型の特性差分の制約条件式を導出し、２段以下の繰り返し型特性差分の範囲で最良のものは、表 5.1 であるとしている。

5.1.3

繰り返し特性差分を使った SHA-2-XOR の擬似衝突攻撃

前節の繰り返し差分特性を利用して SHA-2-XOR に対して、次の二種類の攻撃が考えられる。
定義より、擬似衝突を見つけるため、攻撃者は拡張メッセージと内部レジスタに差分を注入出来る。SHA-2-XOR が理想のハッシュ関数ならば擬似衝突を見つけ計算量は 2128 演算であるが、ここで見つけた１段繰り返し特性差分を 15 段つなぐならば、特性差分確率が 2−120 となり、15 段のSHA-2-XOR に対して 2120 演算で擬似衝突を見つける攻撃へとつながる。

第 5 章 Yoshida らの解析

20

理想的ハッシュ関数の場合、もし入力差分と出力差分が固定されているとき、入力差分＝出力差分となる確率は 2−256 である。しかしながら、31 段までの SHA-2-XOR では確率 2−248 であるということは、このハッシュ関数の 31 段まではランダム関数として振舞わないということを意味する。
さらに、SHACAL-2-XOR に対する差分攻撃としてみれば、この 31 段の特性差分を使って 32 段の SHACAL-2-XOR 暗号が攻撃できることを意味する。詳細は、論文 [9] を参照されたい。

5.1.4

擬似衝突攻撃の改良

前節で述べた、一段繰り返し差分特性を使い、適切なメッセージ Wt (0 ≤ t ≤ 15) および内部変数初期値 e0 , g0 , h0 を選ぶことにより、メッセージ拡張関数を含めた SHA-2-XOR について、19 段まで特性差分が確率１で伝わることを示す2 。
第 5.1.2 節の条件式 (5.1.2) は、ビット単位に見て 32 本の I[i] = X[i] ∧ R[i] 型の方程式であ¯ = f [i] ⊕ g[i] ⊕ 1 に対し、この式を満足する解として、１段繰り返る。ある X[i] = f [i] ⊕ g[i]し差分特性が表 5.1 のように与えられている。この式で R[i] = 1 の場合、X[i] は制約を受ける
が、R[i] = I[i] = 0 の場合、X[i] はいかなる値でもよい。この X に対する、制約条件を、差分

Δa = 3b3b3b3b,Δe = c0c0c0c0 に対して求めれば以下である。
11000000 · · · 11000000

R

=

Δe

=

c0c0c0c0

=

I
X

=

Δa ⊕ Σ1 (Δe)=

40404040= 01000000 · · · 01000000= 01xxxxxx · · · 01xxxxxx(5.14)

ここで x は任意の値を示す。従って、f ⊕ g = 10xxxxxx10xxxxxx10xxxxxx10xxxxxx である。

L = 80808080 として、この X に関する条件は、ビット位置の組を J = {0, 1, 8, 9, 16, 17, 24, 25} として次式で表せる。

ft [i] ⊕ gt [i] = L[i], f ori ∈ J(5.15)

さらに、内部状態更新関数より、gt+2 = ft+1 = et であるので、この条件は

f0 [i] ⊕ g0 [i]= L[i],f or(i ∈ J)

e0 [i] ⊕ f0 [i]et [i] ⊕ et+1 [i]= L[i]= L[i],,f or(i ∈ J)
f or(i ∈ J, t = 0, 1, · · · , 16)(5.16)とまとめられる。この条件を満足するように、e0 , g0 , h0 , W0 , · · · , W15 を定めるアルゴリズムを示
せば、以下である。

Step 1. 初期値 a0 , b0 , c0 , d0 , e0 , f0 , g0 , h0 をランダムに選ぶ
Step 2. メッセージ W0 , W1 , · · · , W15 をランダムに選ぶ
Step 3. g0 [i] と e0 [i] の 8 ビットを (f0 ⊕ L)[i], (i ∈ J) に変更
Step 4. For t=0 to 15 do:
α = et+1 ⊕ et ⊕ L
Wt [i] の 8 ビットを α[i], (i ∈ J) に変更
t 段目の内部状態更新関数を Wt で計算
Step 5. W0old = W0
2 ここでは、論文 [9] の考え方を用いた別の数値例で示す。

第 5 章 Yoshida らの解析

21

Step 6. β = d16 ⊕ h16 ⊕ Σ1 (e16 ) ⊕ Ch(e16 , f16 , g16 ) ⊕ K16 ⊕ L ⊕ e16
Step 7. W16 = σ1 (W14 ) ⊕ W9 ⊕ σ0 (W1 ) ⊕ W0
Step 8. W16 [i] の 8 ビットを β[i], (i ∈ J) に変更
Step 9. W0 [i] の 8 ビットを (W16 ⊕ σ1 (W14 ) ⊕ W9 ⊕ σ0 (W1 ))[i], (i ∈ J) に変更
Step 10. h0 [i] の 8 ビットを (h0 ⊕ W0 ⊕ W0old )[i], (i ∈ J) に変更
このように変更することで、ft ⊕ gt , (0 ≤ t ≤ 18) が所定の値となり、19 段まで、特性差分が確率１で伝わる。
このアルゴリズムは、e0 [i], g0 [i], h0 [i], W0 [i], W1 [i], · · · , W15 [i], (j ∈ J) の 152 ビットの入力ビッ
ト (= 19 × 8 ビット) を修正する。擬似衝突攻撃で、攻撃者が選べるビット数は 256 + 512 = 768
ビットであり、残りの 616 ビットで、継続する 15 段の特性差分パスを考えれば、全体で、34 段のSHA-2-XOR に対し、2120 の計算量の擬似衝突攻撃となる。
Yoshida らは、23 段の SHA-2-XOR に対し、計算機実験により求めた擬似衝突データを示している。さらに、彼らの求めた１段繰り返し特性差分のハミング重みが大きいことから、実際の SHA-2にこの特性差分をそのまま適用してもが高い確率となる可能性は小さいとしている。

22

第6章

第 1 回 CRYPTOGRAPHICWORKSHOP における報告及びその他

2005 年 10 月に NIST の第 1 回ハッシュワークショップが開かれた。発表論文の中で、SHA-2 の解析を行っているものが 1 件ある。
Lee らは、メッセージ変更法による、衝突確率の向上法が存在すると仮定して、SHA-256 の第24 から 55 ステップを調査し、衝突には、15 個以上の局部衝突の重ね合わせが必要である事を報告した [5]。これを、Hawkes らの局部衝突確率 2−39 と合わせると、衝突発見の確率は、2−585 以下であるとしている。新しいハッシュ関数 DHA-256 の提案に主眼がおかれている為、詳細は不明である。彼らは、この確率は、思いの外大きいとしているが、SHA-256 の安全性を脅かす結果ではない。

Pramstaller らは、予備的調査として、SHA-256 のメッセージ拡張関数の効果を調べている [8]。
1 ビットのメッセージ差分は、SHA-1 においてハミング重み 107 の拡張メッセージ差分を引き起こすのに対し、SHA-256 の場合は、メッセージ拡張関数内の算術加算を XOR で置き換えて簡略化
しても、ハミング重み 467 の差分を引き起こし、差分拡散性に優れている。さらに、この簡略化
メッセージ拡張関数の出力を線形符号と考え、確率的最小重み探索法を使って拡張メッセージ差分の最小ハミング重みが 42 ステップまでで 35 であることを求め、それを使って、フルステップで最小ハミング重み 356 と推定している。
これ以外、サーベイ論文として、SHA-2 の解析に触れた論文 [7],[10] や、実用的側面をふまえ、次期のハッシュ関数選択で、どのような戦略をとるべきかの議論のたたき台として、SHA-2 に触れた論文 [2] などがある。
以下、SHA-2 の解析として、Lee ら及び Pramstaller らの論文の概要を紹介する。

6.1

Lee の解析

Lee らは、Wang らの攻撃を２種類のグループに分類し、彼らの提案するハッシュ関数 DHA の安全性評価の根拠としている。ここでは、SHA-2 に関する評価のみを紹介する。
Wang らの攻撃対象の１つのグループ（ Group I ）は、メッセージ語を並び替えて、圧縮関数に入力するものであり、MD4、MD5、RIPEMD、HAVAL などである。他のグループ（ Group II ）は、メッセージ語をそのまま使うのではなく、再帰関係式で定められた拡張関数の出力を圧縮関数に入力するものであり、SHA-0,SHA-1 などである。SHA-2 も Group II に属する。

Group II のハッシュ関数に対する攻撃では、第１章で述べた、３つの戦略がとられている。このうちの戦略１を再度、述べれば以下であり、二つのステップからなる。

1. 効果的な局部衝突を発見する。

第 6 章 第 1 回 CRYPTOGRAPHIC WORKSHOP における報告及びその他

23

2. 局部衝突の合成として、メッセージ拡張関数通過後の語に対し成り立つ効果的な大域的な衝突（ハッシュ関数の衝突）を発見する。

SHA-2 に関しては、Gilbert らの９ステップ局部衝突が最良の局部衝突確率を与えるものとして知られている。その確率は、圧縮関数内の各ステップ関数の解析で得られ、Gilbert らの評価で 2−66 、Hawkes らの拡張メッセージ差分修正法では、最良で 2−39 である。２つめの大域的衝突の発見は、まだ成されていないが、SHA-256 の安全性を議論する場合大域的衝突を構成する局部衝突の個数（又は、その下限）を調べる事により、安全性の下界が評価ができる。この評価に於いては、メッ
セージ拡張関数のみを解析すれば良い。

Lee らは、Wang らの SHA-1 及び SHA-0 攻撃からの類推で、SHA-256 に関しても
1. ステップ１から 23 までは、メッセージ語変更により確率を１にできる
2. ステップ 56 から 63 までは、準衝突を使う解析法で無視できると推測し、ステップ 24 から 55 までの 32 ステップを結ぶのに必要な局部衝突の最小個数を disterbance

vector の手法で求めている。
連続する 16 個の拡張メッセージ語を仮定し、メッセージ拡張関数を使えば、全ての拡張メッセー
ジ語が定まるので、Lee らは、連続する拡張メッセージに、1 ビットから 3 ビットの擾乱（局部衝突の起点）を与えるパターンを総当たりし、必要な局部衝突の最小個数を求めている。結果は、最小値が 15 であり、Hawkes らの手法が適用できると仮定するならば、SHA-256 の衝突発見確率は、

2−585 以下であるとしている。彼らは、この確率は、思いの外大きいとしているが、SHA-256 の安全性を脅かす結果ではない。かれらの論文は、新しいハッシュ関数 DHA-256 の提案に主眼がおかれている為、解析の条件等に関し、本報告書作成者の立場からは、不明な点1 が見られるが、彼らの結果を論文よりそのまま引用する。
（表 6.1, 表 6.2) 表 6.1 は、LEE らの提案する DHA-256 とSHA-256 の安全性を（彼らの評価）で比較したものである。DHA-256 の紹介は、本報告書の趣旨をはずれるので省略する。表 6.2 において、’0’ が１ビット差分を入力する語であり、局部衝突の開始位置である。
表 6.1: SHA-256 と DHA-256 の衝突発見確率

Probability of Inner Collision Pattern

6.2

SHA-256

DHA-256

−39

24

6

2

Hamming Weight of Disterbance Vector (at Step.24-55)

15

63

Total Probability

−585

−4032

2

2

Pramstaller らの解析

Pramstaller らのグループは、SHA-256 のメッセージ拡張関数の効果に関し、論文 [6] および [8]で 2 つの方法で検討している。以下、その概要を紹介する。

1 例えばメッセージ拡張関数の中の算術演算を XOR で近似したとの記述はないが、結果からは、近似が行われていると推測される。

第 6 章 第 1 回 CRYPTOGRAPHIC WORKSHOP における報告及びその他

表 6.2: 32 ステップ disturbance vector

Step
24

////////////////////////////////

25
26////////////////////////////////////////////////////////////////

27
28//////////////////////////////////////////////00////////////////

29
30
31

////////////////////////////////////////////////////////////////////////////////////////////////

32
33////////////////////////////////////////////////////////////////

34
35////////////////////////////////////////////////////////////////

3637///////0//////////0///////////////////////////00////////////////

38
39
40

////////////////////////////////////////////////////////////////////////////////////////////////

41
42////////////////////////////////////////////////////////////////

43
44////////////////////////////////////////////////////////////////

45
46////////////////////////////////////////////////////////////////

47
48
49

////////////////////////////////////////////////////////////////////////////////////////////////

50
51////////////////////////////////
0///////////////////////////////

52
53/////////////////////////////////////////////00/////////////////

54
55///////////////////////////////////00/////////////////////0000//24

第 6 章 第 1 回 CRYPTOGRAPHIC WORKSHOP における報告及びその他

6.2.1

25

算術加算に対して線形な変形 SHA-256

彼らは、局部衝突の合成で、衝突を発見する戦略の有効性を確認するために、ADD-linear SHA-

256 を想定している。その変形ハッシュ関数では、SHA-256 の関数 σ0 , σ1 , Σ0 , Σ1 を恒等変換で置き換え、M aj, Ch 関数は、232 を法とする算術加算
M aj(x, y, z) = Ch(x, y, z) = x + y + z(6.1)

で置き換ている。このハッシュ関数では、全ての演算が、232 を法とする算術加算の下で、線形となっている2 。i 番目の拡張メッセージ Wi に、算術差分 δi = Wi − Wi を擾乱として入れ、それに引き続く、8 個の拡張メッセージに、その擾乱を打ち消す差分を入れることにより、容易に、9 ス
テップの局部衝突が構成できる。この局部衝突は、次の長さ 9 の差分系列である。

{δi , −4δi , 2δi , 2δi , 4δi , 2δi , δi , 0, −δi }(6.2)

このハッシュ関数において、メッセージ拡張関数も ADD-linear であり、メッセージから、拡張
64
メッセージ系列への変換 E : Z16
232 → Z232 は、次の 64 × 16 行列

⎡

I16

⎤

⎥
⎢
⎢ A ⎥
⎥
E=⎢
⎢ A2 ⎥
⎦
⎣
A3

(6.3)

で与えられる。ここで、A はメッセージ拡張関数の再帰関係式 (2.13) を表す 16 × 16 の行列である。従って、求める問題は、式 (6.2.1) において、i = 0, 1, · · · , 55 と置いて得られる 56 本の Z64
232 のベクトルの線形結合で、且つ、上式の変換 E で生成される物を探す事になる。Pramstaller らは、
拡張メッセージ差分の擾乱開始位置として i = −8, −7, · · · , −1 及び i = 56, 57, · · · , 63 は許されないことから、条件式を導出し、局部衝突の合成を与えるメッセージ差分を導いている。そのようなメッセージ差分の中で、拡張メッセージ系列を２元ベクトルとして表したときのハミング重みが最小の物として、各拡張メッセージ語の最上位ビットにのみ差分を持つパターンを示し、そのハミング重みが 27 であるとしている。拡張メッセージ語 Wi の最上位ビット差分の系列を示せば、

108 12 01013 013 02 12 0102 12 06 13 02 1015 013 011(6.4)

である。ここで、08 の表記は、0 が 8 語続くことを表す。他も同様である。M aj, Ch 関数のみ本来のものに戻した変形 SHA-256 において、この擾乱パターン (Disturbance pattern) を用いた時の、衝突発見確率を求めるならば、2−84 とのことであり、かなり大きな値である。
彼らが、述べているように、この解析は、SHA-256 の強度に関しては、何も言及していないと考えるが、σ0 , σ1 , Σ0 , Σ1 関数が、メッセージ差分の拡散に重要な役割を担っている事が伺える。

6.2.2

XOR 演算に対して線形な変形 SHA-256

Pramstaller らは、SHA-1 と SHA-256 のメッセージ拡張関数の差分拡散効果を調べる為に初歩的調査を行っている。メッセージに入れた１ビット差分が影響する拡張メッセージビット数の最小値を、SHA-1,SHA-256, 変形 SHA-1, 変形 SHA-256 の完全版 (SHA-1 は 80 ステップ、SHA-256 は

第 6 章 第 1 回 CRYPTOGRAPHIC WORKSHOP における報告及びその他

26

表 6.3: 変形したメッセージ拡張における 1 ビット差分が影響を与えるビット数の比較

orig.SHA-1

mod.SHA-1

mod.SHA-256

orig.SHA-256

min(40step)max(40step)

18
30

18
41

110
297

137
307

min(full)max(full)

107
174

247
354

467
694

507
709

64 ステップ) と 40 ステップまで減らした縮小版に対して調べている。結果を表に示す。ここで、変形 SHA-1 のメッセージ拡張は、すべての XOR を mod232 の加算に置き換えたものであり、変形 SHA-256 のメッセージ拡張は、すべての加算を XOR に置き換えたものである。mod 加算の導入と、単なるビットシフトを、σ0 と σ1 関数に置き換える事によりメッセージ拡張の中で影響されるビット数が、著しく増えている事が解る。

mod 加算の非線形性のため、SHA-256 のメッセージ拡張は、２元線形符号で記述することはできない。しかし、もし mod 加算を XOR に置き換えたならば、線形符号として考えることが出来る。もし、N ステップまでの SHA-256 を考えると、512 × 32N の生成行列 G を持つ２元線形符号と考えられる。

XOR で線形化することにより、二つの拡張語系列のすべての起こりえる差分は、この符号での符号語となっている。それゆえ、XOR で線形化した SHA-256 のメッセージ拡張における、差分系
列の最小重みは、符号理論における確率的最小重み探索アルゴリズムで、求めることが出来る。結果を図 6.1 に論文 [8] より再掲する。見つかった最小重みを図では、実線で示してある。42 ステッ
プまでは、小さい重みが見つかっている。40 ステップまでを考えると、重み 26 は表 6.3 の最小重み 110 と比較して低くなっている。

42 ステップ以降は、確率的アルゴリズムの動作時間が長く、適切な重みが得らていない。42 ステップ以降の突然の上昇は、SHA-256 のメッセージ拡張の本来の特性ではなく、限られた動作時間の影響と考える。

42 ステップ以降の実際の小さい重みを推測するために、以下の方法をとった。42 ステップまでの小さい重みの符号語を得た後、それをメッセージ拡張関数により 64 ステップ分のワードに拡張する。このように得られた符号語は、図の中で点線で示されている。スタートの点は、42 ステッ
プまでの重み 35 のワードである。それを 64 ステップまで拡張することにより、重み 356 が与えられる。これは、表 6.3 で与えられる最小重みの 467 よりかなり小さい。
ここでは、本来の SHA-256 のメッセージ拡張関数の中の mod 演算を、ビットごとの XOR 演算で近似しているので、これが、本来関数に対して、必ずしも有効な差分系列である保証はない。また、得られたベクトルは、Chabaud と Joux が SHA-0 に行ったような衝突を生み出す disturbance パター
ンとして直接使うことはできない。理由は、拡張より前の非ゼロワードによって生じる truncated
局部衝突があるためである。

2 このハッシュ関数は、算術差分に関し線形であり、高々17 回のハッシュ関数計算で、衝突を発見できるが、彼らの主張を説明するために、導入した変形ハッシュ関数と考えられる

第 6 章 第 1 回 CRYPTOGRAPHIC WORKSHOP における報告及びその他

27

700
Lowest weight found by probabilistic algorithm
Hamming weight of expanded best 42−step word

Hamming weight of expanded message

600

500

400

300

200

100

0

0

10

20

30
40
number of steps

50

60

70

図 6.1: XOR で線形とした SHA-256 のメッセージ拡張をステップごとにみた最小ハミング重み

28

第7章

おわりに

本報告では、SHA-2 の安全性に関する Gilbert の 2003 年の論文以来、2006 年１月末までに公表された論文で、SHA-2 の安全性係わる記述が見られるものを網羅しまとめた。Wang らの一連のハッシュ関数の衝突探索の基本的な戦略は、(1.) 差分パスの局部衝突の重ね合わせでメッセージ拡張関数通過後の語に対し成り立つ効果的な大域的な衝突（ハッシュ関数の衝突）を見つけること (disturbance vector 探索)(2.) ＸＯＲ差分のみで無く符号付き算術差分も同時に解析し、確率高く伝播する差分パスを探索すること(3.) 望ましい差分伝播が起こる内部状態に関する十分条件を解析し、差分伝播確率を高く保つメッ
セージ語変更法を見つけることと考えることが出来る。

SHA-2 に関しても、現在までの研究で、同様な戦略がとられている。Gilbert らは、SHA-2の圧縮関数を線形近似し、XOR 差分について、9 ステップで確率 2−66 の局部衝突を導いている。
この局部衝突は最良のものであるが、大域的衝突を構成するには、SHA-256 の場合、この局部的衝突が少なくとも３個以上、SHA-384/-512 においては５個以上必要と見積もられ、SHA-2 は (1.)
の戦略のみを持つ Joux 型の攻撃に対し安全であると結論づけている。

Hawkes らは、この局部衝突のみに,(2.)(3.) の戦略を適用している。符号付き算術差分も合わせて考察し、適切な拡張メッセージ語差分変更法を提案し、それを使うことにより、確率が 2−39から 2−42 に上昇することを示している。

Lee らは、(3.) のメッセージ変更法が存在すると仮定して、SHA-256 の第 24 から 55 ステップを調査し、衝突には、15 個以上の局部衝突の重ね合わせが必要であり、Hawkes らの結果と合わせる
ことにより、衝突発見の確率は、2−585 以下であるとしている。新しいハッシュ関数 DHA-256 の提案に主眼がおかれている為、詳細は不明である。彼らは、この確率は、思いの外大きいとしているが、SHA-256 の安全性を脅かす結果ではない。

Yoshida らは、SHA-2 の全ての算術加算を XOR 加算で置き換えた SHA-2-XOR の差分特性を調査している。その圧縮関数部分を暗号化変換と考える SHACAL-2-XOR の差分特性を解析し, 確
率 2−8 の１ステップ繰り返し差分パスを発見している。それを用いて、15 ステップ SHA-2-XORの擬似衝突が 2120 の計算量で発見できる事、同じく、31 ステップ SHA-2-XOR は、ランダムハッ
シュ関数では無い事を示している。また、先頭 19 ステップの差分確率を 1 とするメッセージ変更法を提案し、残り 15 ステップに繰り返し差分特性を適用する事により、34 ステップ SHA-2-XORの擬似衝突が、計算量 2120 で発見できると推定している。

Pramstaller らは、予備的調査として、SHA-256 のメッセージ拡張関数の効果を調べている。
1 ビットのメッセージ差分は、SHA-1 においてハミング重み 107 の拡張メッセージ差分を引き起こすのに対し、SHA-256 の場合は、メッセージ拡張関数内の算術加算を XOR で置き換えて簡略化
しても、ハミング重み 467 の差分を引き起こし、差分拡散性に優れている。さらに、この簡略化

第 7 章 おわりに29

メッセージ拡張関数の出力を線形符号と考え、確率的最小重み探索法を使って拡張メッセージ差分の最小ハミング重みが 42 ステップまでで 35 であることを求め、それを使って、フルステップで最小ハミング重み 356 と推定している。
以上この３年間の SHA-2 の安全性評価研究を総合するに、現時点の解析結果は、SHA-2 の衝突
探索の成功確率は、誕生日攻撃の確率を上回るものではなく、その安全性を脅かすものではないと考えられる。

30

関連図書[1] ”Secure Hash Standard,” National Institute of Standards and Technology, FIPS 180-2, Aug.
2002. http://csrc.nist.gov/publications/ﬁps/ﬁps180-2/ﬁps180-2withchangenotice.pdf[2] Bill

Burr:,”Where

should

we

go

from

here?”,NIST

Hash

Function

Workshop

2005,http://www.csrc.nist.gov/pki/HashWorkshop/2005/Nov1 Presentations/Burr Future
Strategy Panel.pdf[3] H.Gilbert and H.Handschuh: ”Security Analysys of SHA-256 and Sisters”, SAC 2003, LNCS
3006, pp.175-193, 2003
[4] Philip Hawkes, Michael Paddon, and Gregory G. Rose. On corrective patterns for the SHA-2
family. Cryptology ePrint Archive, Report 2004/207, August 2004. http://eprint.iacr.org/.
[5] Jesang Lee, Donghoon Chang, Hyun Kim, Eunjin Lee, Deukjo Hong, Jaechul Sung,
Seokhie Hong, Sangjin Lee,:”A New 256-bit Hash Function DHA-256 : Enhancing the Security of SHA-256”,
NIST Hash Function Workshop 2005,
http://www.csrc.nist.gov/pki/HashWorkshop/2005/Nov1 Presentations/ChangD DHA256.pdf[6] Krystian Matusiewicz, Josef Pieprzyk, Norbert Pramstaller, Christian Rechberger, Vincent
Rijmen, ”Analysis of simpliﬁed variants of SHA-256”, WEWoRC 2005
[7] Bart Preneel:”Hash Functions: Past, Present and Future” ASCACRYPT
http://www.cs.iitm.ernet.in/ ac05/Lectures/Bart Preneel.pdf 2005
[8] Norbert

Pramstaller,

Christian

Rechberger,

Vincent

2005,

Rijmen:”PreliminaryAnal-ysis of the SHA-256 Message Expansion”,NIST Hash Function Workshop
2005,http://www.csrc.nist.gov/pki/HashWorkshop/2005/Oct31 Presentations/Rechberger
PreliminaryAnalysisOfSHA256.pdf[9] Hirotaka Yoshida and Alex Biryukov.:Analysis of a SHA-256 variant , SAC 2005, 2005,[10] 金子敏信： [招待論文] 共通鍵暗号に対する近年の攻撃− CRYPTREC 暗号リストから２年− 、
電子情報通信学会技術研究報告、IT2005-36,pp.1-8,(2005.7)