SHA-3は、元はKeccak (あるいは)として知られた暗号学的ハッシュ関数である。RadioGatúnを基にし、Guido Bertoni、Joan Daemen、Michaël Peeters、Gilles Van Asscheによって設計された。2004年のCRYPTOにはじまる、MD5への攻撃成功の確認とSHA-1への攻撃の理論的確立という急速に進んだ在来の関数の危殆化を動機とした、アメリカ国立標準技術研究所(NIST)によるこれらに類似した構造を持たないハッシュ関数を求めたコンペティションによるものであるが、その後、SHA-2への有望な攻撃法は2015年8月現在発表されていないため結果として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の冪で表現した "w" を1ビットにまで小さくすることも定義されている（全状態で25ビット）。小さい状態長は、暗号研究でのテストに有用であり、中間状態長（"w"=4のとき100ビット、"w"=32のとき800ビット）が小さくなることで、実用的な軽量の代替実装の可能性も開ける。2の冪をワード長とするとき、"w" = 2 ビットと定義される。SHA-3では64ビットのワード長を用いていることから ℓ = 6 である。状態は5×5×"w"アレイのビットで表現される。"A"["x"]["y"]["z"] はリトルエンディアンに従うと (5"y" + "x")×"w" + "z" 番目の入力ビットとなる。インデックス演算は、最初の2つの次元に対しては modulo 5、3つめの次元に対しては modulo "w" となる。基本的なブロック置換関数は5つの副ラウンドからなる 12+2ℓ の繰り返しで構成される。それぞれの副ラウンドは単純なものである（代入形式で記述される場合、入力状態を "A"、出力状態を "A’" とする）。Keccakはスポンジ構造を採用しており、入力が一定の比率で内部状態に「吸収」され、ハッシュ出力では同じ比率で「絞り出」される。データの "r" ビットを吸収するときには、データと状態の先頭ビットの排他的論理和を取り、ブロック置換を行う。絞り出すときには、状態の先頭 "r" ビットを出力として生成し、さらなる出力が必要な時にはブロック置換を行う。この機構の中心はハッシュ関数の「キャパシティ」であり、入力でも出力でも触れられることのない "c"=25"w"−"r" ビットの状態である。これは求められるセキュリティ強度に応じて調整可能であり、SHA-3では出力ハッシュ長を "n" ビットとしたとき "c"=2"n" と保守的な設定がなされている。そのため、ブロック置換の単位となる "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に加えられた修正は以下の通りである。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の草稿に反映された。また最終的に、キャパシティを含めたハッシュ関数全体は草稿より変更されなかった。空の入力に対するハッシュ値の例： Keccak-224(")入力メッセージのわずかな違いも、出力されるハッシュ値に大きな変化を及ぼす。例えば、メッセージの最後にピリオドを加えた場合：SHA-3 においては、SHAKE128 および SHAKE256 と呼ばれる 2 つの可変長出力の関数も追加され、望みのセキュリティ強度に応じて利用可能となる。これらの関数ではキャパシティおよびパディングが SHA-3 のうち固定長を出力するものとは異なる。キャパシティは SHAKE128 では 256 ビット、SHAKE256 では 512 ビットである。メッセージの後、パディングの前に 4 ビット列 1111 がメッセージに追加され、出力は任意長に切りつめられる。追加ビット列のうち最初の 2 ビットは SHAKE と固定長出力の SHA-3 を区別するためのものである、続く 2 ビットは Sakura コーディングスキームのためのものであり、将来的な SHA-3 の拡張の際にそれと区別するためのものとなる。

出典:wikipedia