SHA-3

SHA-3は、元はKeccak として知られた暗号学的ハッシュ関数である。SHAシリーズの代替という目的からSHA-3という名があるが、その内部構造はSHA-2までの方式とは全く異なっている。RadioGatúnを基にし、Guido Bertoni、Joan Daemen、Michaël Peeters、Gilles Van Asscheによって設計された。

SHA-3は、2004年のCRYPTOにはじまる、MD5への攻撃成功の確認とSHA-1への攻撃の理論的確立という急速に進んだ在来の関数の危殆化を動機とした、アメリカ国立標準技術研究所によるこれらに類似した構造を持たないハッシュ関数を求めたコンペティションによるものである。しかしその後、SHA-2への攻撃法の研究は進んだものの、2017年初頭時点では効率的な攻撃法の報告はまだ無いことなどのため、結果としてSHA-2の代替の用意が重要ではなくなるなど、状況が変化している。

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

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

Keccakの設計者は、認証付き暗号や特定のアーキテクチャにおいてより高速のハッシュ計算を実現する「木」構造のハッシュなど、標準化されていない関数の利用法を提唱している。Keccakでは、2の冪で表現できる任意のワード長を使うことができる。小さい状態長は暗号研究でのテストに有用であり、中間的な状態長は、実用的な軽量の代替実装として利用できる。

1. ハッシュ関数の構造
------------

Keccakはスポンジ構造を採用しており、入力が一定の比率で内部状態に「吸収」され、ハッシュ出力では同じ比率で「絞り出」される。データの //r// ビットを吸収するときには、データと状態の先頭ビットの排他的論理和を取り、ブロック置換を行う。絞り出すときには、状態の先頭 //r// ビットを出力として生成し、さらなる出力が必要な時にはブロック置換を行う。

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

ハッシュの計算においては、状態を 0 に初期化し、入力をパディングし、それを //r// ビットごとに分割する。入力を状態に吸収するには、//r// ビットごとに分割した入力と状態の排他的論理和を取ってからブロック置換を行う。 最終ブロック置換の後の、状態の先頭の //n// ビットが求めるハッシュ値である。//r// は常に //n// より大きいため、絞り出す過程において更なるブロック置換は不要である。

1.1. パディング
----------

メッセージを //r// ビットごとのブロックに分割するためにはパディングが必要である。SHA-3 では、ビットパターン 100....001 が採用されている。つまり、メッセージの後ろに、1つのビット1、その後に幾つかのビット0、そして最後に1つのビット1を追加する。

パディングの最初と最後のビット1は必須であり、メッセージの長さがすでに //r// で割り切れる場合であっても追加される。5.1}}この場合、//100...001//である長さ //r// のブロックが追加される。 最後のメッセージブロックが //r-1// ビットの場合は、そのブロックに1を追加して //r// ビットとし、さらに//00...001//である長さ //r// のブロックが追加される。 このような処理は、ブロック数が増加するため無駄に見えるかもしれないが、安全性のために必要である。

もし最初のパディングビット1がない場合は、パディングが必要なメッセージのハッシュ値と、「パディングされたかのようなメッセージ」のハッシュ値が同じになってしまう。

また、最後のビット1は、異なるレートのバリアントに対して安全性を保障するために必要である。もし最後の1がなければ、一つの短いメッセージに対する2つのハッシュ値が同じになってしまう。

1.2. ブロック置換
-----------

この置換は、ワード長を //w// としたとき、//5×5×w// ビットの状態を別の状態に変換する。2の冪である任意の //w=2ℓ// に対して定義されているが、SHA-3においてはワード長は //w=64//  が使われる。

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

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

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

2. 修正
-----

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

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

3. 変更に関する論争
-----------

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

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

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

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

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

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

4. ハッシュ値の例
----------

SHA3-n および Keccak-n において、n = 224, 256, 384, 512 は出力ハッシュ長である。
固定長出力の SHA-3 においては、メッセージの後、パディングの前に 2 ビット列 01 がメッセージに追加される。
キャパシティは出力ハッシュ長の2倍 //c//=2//n// である。
比率は //r//=1600−//c// である。 空の入力に対するハッシュ値の例：Keccak-224 0x f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abdKeccak-256 0x c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470Keccak-384 0x 2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ffKeccak-512 0x 0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e

SHA3-224 0x 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7SHA3-256 0x a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434aSHA3-384 0x 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004SHA3-512 0x a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26

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

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

5. SHAシリーズの比較
-------------

6. 実装ライブラリ
----------

SHA-3をサポートしているライブラリは以下の通り。

Botan
OpenSSL
wolfSSL

7. 脚注
-----

8. 外部リンク
--------

[1]
[2]
[3]
[4]
[5]
[6]