SHA-3

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
SHA-3[1] (Keccak)
一般
設計者 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche.
初版発行日 2015-08-05[2]
認証 FIPS PUB 202[1]
詳細
ダイジェスト長 224, 256, 384, 512 bits
または可変 (SHAKE128, SHAKE256)
速度 Core 2 上にて 12.5 en:Cycles_per_byte [r=1024,c=576][3]

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

2004年のCRYPTOにはじまる、MD5への攻撃成功の確認[6]SHA-1への攻撃の理論的確立[7]という急速に進んだ在来の関数の危殆化を動機とした、アメリカ国立標準技術研究所(NIST)によるこれらに類似した構造を持たないハッシュ関数を求めたコンペティションによるものであるが、その後、SHA-2への有望な攻撃法は2015年8月現在発表されていないため結果としてSHA-2の代替の用意が重要ではなくなるなど、状況が変化している[8]

2012年10月2日、Keccakがコンペティションの勝者として選ばれ[4]2015年8月5日に正式版が FIPS PUB 202 として公表された[2]

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

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

ブロック置換[編集]

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

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

基本的なブロック置換関数は5つの副ラウンドからなる 12+2ℓ の繰り返しで構成される。それぞれの副ラウンドは単純なものである(代入形式で記述される場合、入力状態を A、出力状態を A’ とする)。

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

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

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

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

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

この機構の中心はハッシュ関数の「キャパシティ」であり、入力でも出力でも触れられることのない c=25wr ビットの状態である。これは求められるセキュリティ強度に応じて調整可能であり、SHA-3では出力ハッシュ長を n ビットとしたとき c=2n と保守的な設定がなされている。そのため、ブロック置換の単位となる r は出力ハッシュ長に依存することとなり、224、256、384、512ビットの出力ハッシュ長に対して、r はそれぞれ1152、1088、832、576となる。SHA-2シリーズと異なり、SHA-3の関数(固定長を出力する224、256、384、512バージョンおよび可変長出力のSHAKE128およびSHAKE256)は全て同じブロック置換関数を持つ。これらのハッシュ関数を区別するものはパディングとスポンジ関数のパラメータの差のみである。

メッセージを r ビットごとのブロックに分割するためにはパディングが必要である。最終的なバージョンにおいては、ビットパターン 100....001 が採用された。最終の1ビットが必要とされるのは、スポンジ構造のセキュリティの根拠として、スポンジ構造の比率が最終ブロックにエンコードされている必要があるためである。

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

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

修正[編集]

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

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

変更に関する論争[編集]

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

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

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

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

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

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

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

2013年11月、NISTのJohn KelseyはCHESでの発表に対する反応から、近いうち正式に発表する草稿においては、キャパシティの値を応募時のものから変更しない方針であることを明らかにした[21]。この方針は、2014年4月および5月に続けて公開されたFIPS 202の草稿[22]に反映された。また最終的に、キャパシティを含めたハッシュ関数全体は草稿より変更されなかった[22][1]

ハッシュ値の例[編集]

  • 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)
パフォーマンスの例[24]
(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の試行で理論的に可能[25]
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 c SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions”. FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION. NIST (2015年8月). 2015年8月6日閲覧。
  2. ^ a b SHA-3 Standardization”. Computer Security Division - Computer Security Resource Center. NIST. 2015年8月6日閲覧。
  3. ^ a b Keccak implementation overview Version 3.2 http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
  4. ^ a b NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition”. NIST. 2014年1月2日閲覧。
  5. ^ The Keccak sponge function family: Specifications summary”. 2014年1月2日閲覧。
  6. ^ Xiaoyun Wang; Dengguo Feng, Xuejia Lai, Hongbo Yu (2004年8月17日). “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD”. 2015年8月6日閲覧。
  7. ^ Vincent Rijmen; Elisabeth Oswald (2005年1月14日). “Update on SHA-1”. 2015年8月6日閲覧。
  8. ^ Dennis Fisher (2012年9月24日). “Forthcoming SHA-3 Hash Function May Be Unnecessary”. Threatpost. 2015年8月6日閲覧。
  9. ^ Sponge Functions”. Ecrypt Hash Workshop 2007. 2014年1月2日閲覧。
  10. ^ On the Indifferentiability of the Sponge Construction”. EuroCrypt 2008. 2014年1月2日閲覧。
  11. ^ 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.
  12. ^ NIST, Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition, sections 5.1.2.1(「木」構造), 6.2(認証付き暗号), 7(将来標準化されるかもしれない「追加」)
  13. ^ Keccak parameter changes for round 2”. 2014年1月2日閲覧。
  14. ^ Simplifying Keccak's padding rule for round 3”. 2014年1月2日閲覧。
  15. ^ John Kelsey. “SHA3, Where We've Been, Where We're Going”. RSA Conference 2013. 2014年1月3日閲覧。
  16. ^ John Kelsey. “SHA3, Past, Present, and Future”. CHES 2013. 2014年1月2日閲覧。
  17. ^ Schneier on Security: Will Keccak = SHA-3?”. 2014年1月2日閲覧。
  18. ^ LShift: Why I support the US Government making a cryptography standard weaker”. 2014年1月3日閲覧。
  19. ^ Yes, this is Keccak!”. 2014年1月2日閲覧。
  20. ^ A concrete proposal”. 2014年1月2日閲覧。
  21. ^ Moving Forward with SHA-3”. 2015年7月5日閲覧。
  22. ^ a b DRAFT FIPS 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions”. 2015年8月6日閲覧。
  23. ^ Crypto++ 5.6.0 Benchmarks”. 2014年1月1日閲覧。
  24. ^ AMD Opteron 8354 2.2 GHzプロセッサと64ビット版Linuxによる計測[23]
  25. ^ Cryptanalysis of MD5 & SHA-1 (PDF)”. 2014年1月1日閲覧。

外部リンク[編集]