SHA-3

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
SHA-3
(Keccak)
一般
設計者 Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
認証 SHA-3採用
詳細
ダイジェスト長 224, 256, 384, or 512 bits(Keccak本来の仕様では可変長)
速度 12.5 en:Cycles_per_byte on Core 2 [r=1024,c=576].

SHA-3は、元はKeccak ( /ˈkætʃæk/あるいは /kɛtʃɑːk/)[2][3]として知られた暗号学的ハッシュ関数である。RadioGatúnを基にし、Guido Bertoni、Joan Daemen、Michaël Peeters、Gilles Van Asscheによって設計された。

2012年10月2日、Keccakはアメリカ国立標準技術研究所 (NIST)によるSHA-3公募の勝者に選ばれた[2]。SHA-3はSHA-2の置き換えを目指したものではない(SHA-2への攻撃は未だ成功していない)。MD5SHA-0への実際の攻撃の成功と、SHA-1への理論的攻撃の成功から、NISTはこれらに類似した構造を持たないハッシュ関数を求めており、これがSHA-3となった。

Keccakはスポンジ関数英語版[4][5]を採用しており、メッセージのブロックは状態の初期ビットとのXORを取ったのちに反転される。SHA-3で用いられているバージョンでは、状態は64ビットのワード長の5×5アレイから構成され、総計で1600ビットである。設計者によれば、KeccakはIntel Core 2で12.5 cycles per byteの速度が出ると主張している[6]。また、ハードウェア実装では他のどの最終候補よりも高速であった[7]

Keccakの設計者は、認証付き暗号や特定のアーキテクチャにおいてより高速のハッシュ計算を実現する「木」構造のハッシュなど、標準化されていない関数の利用法を提唱している[8]。Keccakでは、ワード長を2の冪で表現した w を1ビットにまで小さくすることも定義されている(全状態で25ビット)。小さい状態長は、暗号研究でのテストに有用であり、中間状態長(w=4のとき100ビット、w=32のとき800ビット)が小さくなることで、実用的な軽量の代替実装の可能性も開ける。

ブロック置換[編集]

2の冪をワード長とするとき、w = 2 ビットと定義される。SHA-3では64ビットのワード長を用いていることから ℓ = 6 である。

状態は5×5×wアレイのビットで表現される。a[i][j][k] はリトルエンディアンに従うと (i×5 + jw + k の入力ビットとなる。インデックス演算は、最初の2つの次元に対しては modulo 5、3つめの次元に対しては modulo w となる。

基本的なブロック置換関数は5つの副ラウンドからなる 12+2ℓ の繰り返しで構成される。それぞれの副ラウンドは単純なものである。

θ
ww = 64のとき320)ごとの5ビットのカラムのパリティを計算し、隣接する2つのカラムとの排他的論理和を取る。
a[i][j][k] ⊕= parity(a[i][j−1][k]) ⊕ parity(a[i][j+1][k−1])
ρ
25ワードごとに異なる三角数 0, 1, 3, 6, 10, 15, .... でローテートする。
a[0][0]はローテートしない。すべての 0≤t<24 に対して a[i][j][k] = a[i][j][k−(t+1)(t+2)/2] とする。このとき \begin{pmatrix} i \\ j \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 0 \end{pmatrix}^t \begin{pmatrix} 0 \\ 1 \end{pmatrix} とする。
π
25ワードを決まったパターンで置換する。
a[j][2i+3j] = a[i][j]
χ
a = a ⊕ (¬b & c) を用いてビット列を結合する。
a[i][j][k] ⊕= ¬a[i][j+1][k] & a[i][j+2][k]
SHA-3においてこの過程のみが非線形操作である。
ι
ラウンド定数と状態ワードの排他的論理和を取る。
ラウンド n において、0≤m≤ℓ のとき a[0][0][2m−1] と degree-8 LFSR sequenceの m+7n ビットの排他的論理和を取る。これにより他の副ラウンドで保たれていた対称性が破られる。

可変長メッセージのハッシュ計算[編集]

スポンジ構造の模式図
ハッシュ関数のスポンジ構造
pi:入力
zi:ハッシュ出力
使われない「キャパシティ」 cは、衝突攻撃原像攻撃に対して望む耐性の2倍必要である。

Keccakはスポンジ構造を採用しており、入力が一定の比率で内部状態に「吸収」され、ハッシュ出力では同じ比率で「絞り出」される。

データの r ビットを吸収するときには、データと状態の先頭ビットの排他的論理和を取り、ブロック置換を行う。絞り出すときには、状態の先頭 r ビットを出力として生成し、さらなる出力が必要な時にはブロック置換を行う。

この機構の中心はハッシュ関数の「キャパシティ」であり、入力でも出力でも触れられることのない c=25wr ビットの状態である。これは求められるセキュリティ強度に応じて調整可能であり、SHA-3では出力ハッシュ長を n ビットとしたとき c=2n と保守的な設定がなされている。そのため、ブロック置換の単位となる r は出力ハッシュ長に依存することとなり、224、256、384、512ビットの出力ハッシュ長に対して、r はそれぞれ1152、1088、832、576となる。RSA Conference 2013およびWorkshop on Cryptographic Hardware and Embedded Systems 2013において、NISTのJohn Kelseyは「224ビットおよび256ビットの出力ハッシュ長ではキャパシティ c を256ビットに、384ビットおよび512ビットの出力ハッシュ長ではキャパシティ c を512ビットに小さくするであろう」とアナウンスしている[9][10]SHA-2シリーズと同様に、224ビットバージョンは256ビットバージョンを、384ビットバージョンは512ビットバージョンを切り詰めたものである。NISTは、Keccakの他の利用モードの標準化も検討している。

メッセージを r ビットごとのブロックに分割するためにはパディングが必要である。現在の提案では、ビットパターン 100....001 が提唱されている。最終の1ビットが必要とされるのは、スポンジ構造のセキュリティの根拠として、スポンジ構造の比率が最終ブロックにエンコードされている必要があるためである。このパディングは、Keccakの設計者によって提唱されているスキームであるSakuraのパディングに合致するようにSHA-3の最終的な標準化では変更される可能性がある。

ハッシュの計算において、状態を0に初期化し、入力を置き、それを r ビットごとに分割する必要がある。入力を状態に吸収するには、r ビットごとに分割した入力と状態の排他的論理和を取ってからブロック置換を行う。

最終ブロック置換の後の、状態の先頭の n ビットが求めるハッシュ値である。r は常に n より大きいため、絞り出す過程において更なるブロック置換は不要である。

修正[編集]

NISTによる公募の期間中、発見された問題への対処として応募者がアルゴリズムを修正することが許されていた。Keccakに加えられた修正は以下の通りである[11][12]

  • セキュリティ向上のためラウンド数が 12+ℓ から 12+2ℓ に増やされた
  • メッセージパディングが、複雑なものから上述のより単純なものに変更された
  • 比率 r が、可能な限り大きくされた

論争[編集]

2013年2月のRSA Conferenceおよび2013年8月のCHESにおいて、NISTはSHA-3標準のセキュリティパラメータとして、キャパシティの大きさを応募時のものから変更するであろうと発表した[9][10]。この変更が騒動をもたらしている。

ブルース・シュナイアーは、アルゴリズムを受け入れるにあたって有害なものであるとしてこの決定を批判している。

非常に多くの不信が広まっている。NISTは、誰にも信頼されず、(強制された場合を除いて)誰も使わないアルゴリズムを発表する危険を冒している。[13]

一方、Paul Crowleyはこの決定に賛意を表明している。その内容を要約すると以下の通りである。

  • Keccakはこのように可変性を持つよう設計されている。SHA-3の仕様において、今回の決定はさほど重要なものではない。キャパシティの大きさと出力長は、要求されるセキュリティに応じてそれぞれ独立に変更できるのだから。
  • ハッシュ関数に、衝突攻撃よりも第二原像攻撃に対して途方もなく高い耐性を求めるべき理由はない。
  • 「よりセキュアでない」Keccakを心配するのであれば、スポンジ構造のキャパシティを大きくするのではなくラウンド数を増やすべきだ。
  • あるセキュリティレベルを要求して公募を行ったにもかかわらずそれと異なるレベルを最終標準とすることはちょっと恥ずかしいことだ。しかし、それを改めようとしたら公募をやり直す以外にできることはないし、そうしたところで事態は改善しない。[14]

ダニエル・バーンスタインは、オリジナルのKeccakで提唱されていたようにキャパシティを576ビットに強化することを提唱している。

Keccakの設計チームは、新しいパラメータに賛意を表明しており、NISTによるパラメータ変更は、NISTのハッシュチームと自分たちによる議論の結果によるものであると表明している[15]。しかし、暗号コミュニティに対しては、すべての場合において512ビットのキャパシティを用いることを提唱している[16]

ハッシュ値の例[編集]

  • SHA3-n および Keccak-n において、n = 224, 256, 384, 512 は出力ハッシュ長である。
  • SHA-3 においては、パディングの前に 2 ビット列 01 がメッセージに追加される。
  • キャパシティは出力ハッシュ長の2倍 c=2n である。
  • 比率は r=1600−c である。
  • 出力は十六進法である。

空の入力に対するハッシュ値の例:

Keccak-224("")
0x f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd
Keccak-256("")
0x c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
Keccak-384("")
0x 2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ff
Keccak-512("")
0x 0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e
SHA3-224("")
0x 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
0x a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0x 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
0x a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26

入力メッセージのわずかな違いも、出力されるハッシュ値に大きな変化を及ぼす。例えば、メッセージの最後にピリオドを加えた場合:

Keccak-224("The quick brown fox jumps over the lazy dog")
0x 310aee6b30c47350576ac2873fa89fd190cdc488442f3ef654cf23fe
Keccak-224("The quick brown fox jumps over the lazy dog.")
0x c59d4eaeac728671c635ff645014e2afa935bebffdb5fbd207ffdeab

SHA-3 においては、SHAKE128 および SHAKE256 とよばれる 2 つの可変長出力の関数も追加され、望みのセキュリティ強度に応じて利用可能となる。これらの関数ではキャパシティおよびパディングが SHA-3 とは異なる。キャパシティは SHAKE128 では 256 ビット、SHAKE256 では 512 ビットである。パディングの前に 4 ビット列 1111 がメッセージに追加され、出力は任意長に切りつめられる。追加ビット列のうち最初の 2 ビットは SHAKE と SHA-3 を区別するためのものであり、続く 2 ビットは Sakura コーディングスキームのためのものであり。将来的な SHA-3 の拡張の際にそれと区別するためのものとなる。

SHAシリーズの比較[編集]

SHAシリーズの比較 [編集]
アルゴリズムとバリエーション 出力長
(bits)
内部状態長
(bits)
ブロック長
(bits)
最大メッセージ長
(bits)
ラウンド数 ビット演算 セキュリティ強度
(bits)
パフォーマンスの例[18]
(MiB/s)
MD5(参照) 128 128
(4 × 32)
512 264 − 1 64 And, Xor, Rot,
Add (mod 232),
Or
<64(強衝突 335
SHA-0 160 160
(5 × 32)
512 264 − 1 80 And, Xor, Rot,
Add (mod 232),
Or
<80(強衝突 -
SHA-1 160 160
(5 × 32)
512 264 − 1 80 <80
(261の試行で理論的に可能[19]
192
SHA-2 SHA-224
SHA-256
224
256
256
(8 × 32)
512 264 − 1 64 And, Xor, Rot,
Add (mod 232),
Or, Shr
112
128
139
SHA-384
SHA-512
SHA-512/224
SHA-512/256
384
512
224
256
512
(8 × 64)
1024 2128 − 1 80 And, Xor, Rot,
Add (mod 264),
Or, Shr
192
256
112
128
154
SHA-3 SHA3-224
SHA3-256
SHA3-384
SHA3-512
224
256
384
512
1600
(5 × 5 × 64)
1152
1088
832
576
24 And, Xor, Rot,
Not
112
128
192
256
-
SHAKE128
SHAKE256
d(可変長)
d(可変長)
1344
1088
d/2と128のいずれか小さい方
d/2と256のいずれか小さい方
-

脚注[編集]

  1. ^ a b DRAFT FIPS 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions”. 2014年5月19日閲覧。
  2. ^ a b NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition”. NIST. 2014年1月2日閲覧。
  3. ^ The Keccak sponge function family: Specifications summary”. 2014年1月2日閲覧。
  4. ^ Sponge Functions”. Ecrypt Hash Workshop 2007. 2014年1月2日閲覧。
  5. ^ On the Indifferentiability of the Sponge Construction”. EuroCrypt 2008. 2014年1月2日閲覧。
  6. ^ Keccak implementation overview Version 3.2 http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
  7. ^ Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick (Aug. 2010), “Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations”, NIST 2nd SHA-3 Candidate Conference: 12, http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SCHAUMONT_SHA3.pdf 2014年1月2日閲覧。  Keccak is second only to Luffa, which did not advance to the final round.
  8. ^ NIST, Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition, sections 5.1.2.1(「木」構造), 6.2(認証付き暗号), 7(将来標準化されるかもしれない「追加」)
  9. ^ a b John Kelsey. “SHA3, Where We've Been, Where We're Going”. RSA Conference 2013. 2014年1月3日閲覧。
  10. ^ a b John Kelsey. “SHA3, Past, Present, and Future”. CHES 2013. 2014年1月2日閲覧。
  11. ^ Keccak parameter changes for round 2”. 2014年1月2日閲覧。
  12. ^ Simplifying Keccak's padding rule for round 3”. 2014年1月2日閲覧。
  13. ^ Schneier on Security: Will Keccak = SHA-3?”. 2014年1月2日閲覧。
  14. ^ LShift: Why I support the US Government making a cryptography standard weaker”. 2014年1月3日閲覧。
  15. ^ Yes, this is Keccak!”. 2014年1月2日閲覧。
  16. ^ A concrete proposal”. 2014年1月2日閲覧。
  17. ^ Crypto++ 5.6.0 Benchmarks”. 2014年1月1日閲覧。
  18. ^ AMD Opteron 8354 2.2 GHzプロセッサと64ビット版Linuxによる計測[17]
  19. ^ Cryptanalysis of MD5 & SHA-1 (PDF)”. 2014年1月1日閲覧。

外部リンク[編集]