SHA-3

SHA-3（Secure Hash Algorithm 3）は、NISTが2015年8^月5日にリリースした^Secure Hash Algorithmファミリー標準の最新メンバー^{です。 [ 4 ] [ 5] [ 6 ] [ 7 ]}同じ標準シリーズの一部ではありますが、SHA-3は内部的にSHA-1およびSHA-2のMD5のような構造とは異なります。

SHA-3 は、RadioGatún を基にGuido Bertoni、Joan Daemen、Michaël Peeters、 Gilles Van Asscheによって設計された、より広範な暗号プリミティブファミリーKeccak ( / ˈ k ɛ tʃ æ k /または/ ˈ k ɛ tʃ ɑː k / ) ^{[ 8 ] [ 9 ]}のサブセットです。 Keccak の著者は、ストリーム暗号、認証付き暗号化システム、特定のアーキテクチャでハッシュを高速化するための「ツリー」ハッシュ方式^{[ 10 ] [ 11 ]} 、 AEAD暗号 Keyak および Ketje ^{[ 12 ] [ 13 ]}など、NIST によって (まだ) 標準化されていない、この関数の追加用途を提案しています。

Keccakは、スポンジ構築と呼ばれる新しいアプローチに基づいています。^{[ 14 ]}スポンジ構築は擬似乱数順列に基づいており、任意の量のデータを入力（スポンジ用語では「吸収」）し、任意の量のデータを出力（「圧縮」）することができ、以前のすべての入力に対して擬似乱数関数として機能します。これにより、非常に高い柔軟性が得られます。

2022年現在、NISTはSHA-2を撤回したり、改訂版セキュアハッシュ標準から削除したりする予定はない。^{[ 15 ]} SHA-3の目的は、必要に応じて現在のアプリケーションでSHA-2と直接置き換えることができるようにすること、およびNISTのハッシュアルゴリズムツールキット全体の堅牢性を大幅に向上させることである。^{[ 16 ]}

メッセージサイズが小さい場合、KeccakアルゴリズムとSHA-3関数の開発者は、調整されたパラメータと追加のオーバーヘッドのない新しいツリーハッシュモードを備えた、より高速な関数KangarooTwelveを使用することを推奨しています。

Keccak アルゴリズムは、Guido Bertoni、Joan Daemen ( Vincent Rijmenと共にRijndael暗号も共同設計)、Michaël Peeters、Gilles Van Asscheの作品です。これは、以前のハッシュ関数設計であるPANAMAとRadioGatúnに基づいています。PANAMA は、1998 年に Daemen と Craig Clapp によって設計されました。PANAMA の後継である RadioGatún は、Daemen、Peeters、Van Assche によって設計され、2006 年の NIST ハッシュ ワークショップで発表されました。^{[ 17 ]}参照実装はパブリック ドメインに公開されました。^{[ 18 ]}

2006年、NISTは新しいハッシュ標準であるSHA-3を作成するため、NISTハッシュ関数コンペティションを開始しました。SHA-3はSHA-2を置き換えることを意図したものではなく、SHA-2に対する重大な攻撃は公に実証されていません。MD5、SHA-0、SHA-1に対する攻撃が成功したため、^{[ 19 ] [ 20 ]} NISTは代替となる異なる暗号ハッシュの必要性を認識し、それがSHA-3となった。

準備期間の後、応募書類は2008年末までに提出されることになっていた。ケチャックは51名の候補者のうちの1人として受け入れられた。2009年7月、14のアルゴリズムが第2ラウンドに選ばれた。ケチャックは2010年12月の最終ラウンドに進出した。^{[ 21 ]}

コンテスト中、参加者は発見された問題に対処するためにアルゴリズムを「微調整」することが許可されました。Keccakに加えられた変更は次のとおりです。^{[ 22 ] [ 23 ]}

• セキュリティをより慎重にするため、ラウンド数を12 + ℓから12 + 2ℓに増やしました。
• メッセージのパディングは、より複雑な方式から、以下に説明する単純な10 ^× 1のパターンに変更されました。
• レートrは、最も近い2のべき乗に切り捨てるのではなく、セキュリティの上限まで引き上げられた。

2012年10月2日、ケチャックはコンテストの優勝者に選ばれた。^{[ 8 ]}

2014年、NISTはFIPS 202「SHA-3標準：順列ベースのハッシュと拡張可能な出力関数」の草案を公開した。^{[ 24 ]} FIPS 202は2015年8月5日に承認された。^{[ 25 ]}

2015年8月5日、NISTはSHA-3がハッシュ標準になったと発表した。^{[ 26 ]}

SHA-3 はスポンジ構造^{[ 14 ]}を使用し、データがスポンジに「吸収」され、その後結果が「押し出」されます。吸収フェーズでは、メッセージブロックが状態のサブセットにXOR され、その後、置換関数(または変換)を使用して全体として変換されます。${\displaystyle f}$「圧縮」フェーズでは、出力ブロックは状態の同じサブセットから読み取られ、状態変換関数と交互に実行されます。${\displaystyle f}$書き込みと読み出しが行われる状態の部分のサイズは「レート」（と表記）と呼ばれます。${\displaystyle r}$）、入力/出力の影響を受けない部分のサイズは「容量」（と表記）と呼ばれます。${\displaystyle c}$容量によってスキームのセキュリティが決まります。最大セキュリティレベルは容量の半分です。

入力ビット列が与えられた場合${\displaystyle N}$パディング関数${\displaystyle pad}$順列関数${\displaystyle f}$幅のビットブロック上で動作する${\displaystyle b}$レート${\displaystyle r}$出力長さ${\displaystyle d}$私たちには能力があります${\displaystyle c=br}$そしてスポンジ構造${\displaystyle Z={\text{sponge}}[f,pad,r](N,d)}$これによりビット列が生成されます。${\displaystyle Z}$長さ${\displaystyle d}$以下の通り：^{[ 6 ]： 18}

• pad関数を使用して入力Nをパディングし、長さがで割り切れるパディング済みビット列Pを生成します。${\displaystyle r}$（${\displaystyle n={\text{len}}(P)/r}$（整数）
• Pを_n個の連続するrビットの断片P0 , ..., Pn _{- 1}に分割する
• 状態Sをb個のゼロビットの文字列で初期化する
• 入力を状態に吸収する：各ブロックP _iについて：
  • P _{i の}末尾にc 個のゼロビット列を追加して、長さbの 1 つを得る。
  • Sとの XOR 演算
  • 結果にブロック置換fを適用し、新しい状態Sを得る。
• Zを空文字列として初期化する
• Zの長さがdより小さい間：
  • Sの最初のrビットをZに追加する
  • Zがまだdビット未満の長さである場合、 fをSに適用して新しい状態Sを生成する。
• Zをdビットに切り捨てる

内部状態Sには、 Zに出力される情報に加えてcビットの追加情報が含まれているため、SHA-2、SHA-1、MD5、およびMerkle–Damgård構造に基づくその他のハッシュ関数が脆弱な長さ拡張攻撃を防ぐことができます。

SHA-3 では、状態S はwビットのワード ( w = 64)の5 × 5配列で構成され、 b = 5 × 5 × w = 5 × 5 × 64 = 合計 1600 ビットとなります。Keccak は、1 ビット (合計状態 25 ビット) までの 2 のべき乗のワードサイズwに対しても定義されています。小さな状態サイズは暗号解読攻撃のテストに使用でき、中間の状態サイズ ( w = 8,200 ビットからw = 32,800 ビットまで) は実用的で軽量なアプリケーションに使用できます。^{[ 12 ] [ 13 ]}

SHA3​​-224、SHA3-256、SHA3-384、およびSHA3-512の場合、rはdより大きいので、スクイージングフェーズで追加のブロック置換は必要ありません。状態の先頭のdビットが目的のハッシュです。ただし、SHAKE128とSHAKE256では任意の出力長が許容されるため、最適な非対称暗号化パディングなどのアプリケーションで役立ちます。

メッセージをrビットのブロックに均等に分割できるようにするには、パディングが必要です。SHA-3 はパディング関数で 10...01 というパターンを使用します。これは、1 ビット、それに続く 0 ビット以上 (最大r - 1 )、そして最後の 1 ビットです。

r − 1ビットのゼロビットの最大数は、最後のメッセージブロックの長さがr − 1ビットの場合に発生します。その後、最初の 1 ビットの後に別のブロックが追加され、最後の 1 ビットの前にr − 1ビットのゼロビットが含まれます。

メッセージの長さが既にrで割り切れる場合でも、2 つの 1 ビットが追加されます。^{[ 6 ] : 5.1}この場合、1 ビットを含む別のブロックがメッセージに追加され、その後にr − 2 個のゼロ ビットのブロックと別の 1 ビットが続きます。これは、パディングのように見えるもので終わる長さがrで割り切れるメッセージが、それらのビットが削除されたメッセージと同じハッシュを生成しないようにするために必要です。

最初の1ビットが必要なのは、末尾に数ビットの0が追加されているだけのメッセージでは、同じハッシュ値が生成されないようにするためです。

最後の1ビットの位置は、どのレートrが使用されたか（マルチレートパディング）を示しており、これは異なるハッシュバリアントに対してセキュリティ証明が機能するために必要です。これがないと、同じ短いメッセージの異なるハッシュバリアントは、切り捨てまで同じになってしまいます。

ブロック変換f は、SHA-3 の Keccak-f[1600] であり、XOR、AND、NOT演算を使用する順列であり、ソフトウェアとハ​​ードウェアの両方で簡単に実装できるように設計されています。

これは任意の2のべき乗のワードサイズ、w = ^2ℓビットに対して定義されます。主なSHA-3提出では64ビットワード、ℓ = 6を使用しています。

状態は5 × 5 × wのビット配列と考えることができます。入力のビット(5 i + j ) × w + kをa [ i ][ j ][ k ]とします。リトルエンディアンのビット番号付け規則と行優先インデックスを使用します。つまり、i は行、 jは列、k はビットを選択します。

インデックス演算は、最初の2次元については5を法として、3次元目についてはwを法として実行されます。

基本的なブロック順列関数は、 5つのステップからなる12 + 2ℓラウンドで構成されます。

θ（シータ）

5 w ( w = 64の場合は 320 ) 個の 5 ビット列のそれぞれのパリティを計算し、それを規則的なパターンで隣接する 2 つの列に排他的 OR 演算します。正確には、 a [ i ][ j ][ k ] ← a [ i ][ j ][ k ] ⊕ parity(a[0...4][ j -1][ k ]) ⊕ parity(a[0...4][ j +1][ k −1] )となります。

ρ（ロー）

25個の各ワードを、異なる三角数0、1、3、6、10、15、...でビット単位で回転させます。正確には、 [ 0][0]は回転されず、0 ≤ t < 24のすべての場合、a [ i ][ j ][ k ] ← a [ i ][ j ][ k −( t +1)( t +2)/2]となります。${\displaystyle {\begin{pmatrix}i\\j\end{pmatrix}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}{\begin{pmatrix}0\\1\end{pmatrix}}}$。

π（パイ）

25個の単語を固定パターンで並べ替えます。a [3 i +2 j ][ i ] ← a [ i ][ j ]。

χ（カイ）

x ← x ⊕ (¬ y & z )を使用して、行ごとにビット単位の結合を行います。正確には、a [ i ][ j ][ k ] ← a [ i ] [ j ][ k ] ⊕ (¬ a [ i ][ j + 1 ][ k ] &a a [ i ][ j + 2 ][ k ])。これは SHA-3 における唯一の非線形演算です。

ι（イオタ）

ラウンド定数を排他的論理和で状態の 1 ワードに出力します。正確には、ラウンドnにおいて、0 ≤ m ≤ ℓに対して、[0][0][2 ^m −1]が次数 8 のLFSRシーケンスのビットm + 7 nと XOR されます。これにより、他のステップで保持されている対称性が破られます。

長いメッセージの SHA-3 ハッシュの速度は、f = Keccak-f[1600]の計算と、 Sと拡張P _{iの XOR 演算 (} b = 1600 ビットに対する演算)によって決まります。ただし、拡張P _iの最後のcビットはいずれにせよ 0 であり、0 との XOR 演算は NOP であるため、rビット ( SHA3-224 の場合はr = 1600 − 2 × 224 = 1152 ビット、SHA3-256 の場合は 1088 ビット、SHA3-384 の場合は 832 ビット、SHA3-512 の場合は 576 ビット) に対してのみ XOR 演算を実行すれば十分です。r が小さいほど (逆に c = b − r = 1600 − r が大きいほど)、ハッシュの効率は低下しますが、セキュリティは向上します。これは、計算コストの高いfを適用する前に、メッセージのビットを XOR 演算して状態 (高速な演算) にできる数が少なくなるためです。著者らは、Keccak-f[1600]のソフトウェア実装に1024ビットのXOR演算を加えた場合の速度を以下のように報告している^{[ 1 ]}。これはおおよそSHA3-256に相当する。

• IA-32、Intel Pentium 3で57.4 cpb ^{[ 39 ]}
• IA-32+MMX、Intel Pentium 3で41cpb
• IA-32+SSE、Intel Core 2 DuoまたはAMD Athlon 64で20 cpb
• 一般的なx86-64ベースのマシンでは12.6 cpb
• IA-64では6～7cpb ^{[ 1 ]}

x86-64 上での正確な SHA3-256 については、Bernstein は CPU に応じて 11.7～12.25 cpb と測定しています。^{[ 40 ] : 7} SHA-3 は、Keccak 関数をより速く計算するための特別な命令を持たない命令セットアーキテクチャ (CPU) では遅いと批判されています。3.2  GHz でクロックされる Intel Skylake プロセッサでは、SHA2-512 は SHA3-512 の 2 倍以上、SHA-1 は 3 倍以上高速です。^{[ 41 ]}この批判に対して、著者らは、原像耐性を半分に減らす (ただし衝突耐性は維持する) という代償を払って、SHA3-256 と SHA3-512 の代わりに SHAKE128 と SHAKE256 を使用することを提案しています^{[ 41 ]}。これにより、パフォーマンスは SHA2-256 と SHA2-512 と同等になります。

しかし、ハードウェア実装では、SHA-3は他のすべての最終候補よりも著しく高速であり^{[ 42 ]}、SHA-2およびSHA-1よりも高速である^{[ 41 ] 。}

2018年現在、ARMのARMv8 ^{[ 43 ]}アーキテクチャには、Keccakアルゴリズムをより高速に実行できる特別な命令が含まれており、IBMのz/Architecture ^{[ 44 ]}には、SHA-3とSHAKEの完全な実装が単一の命令に含まれています。RISC -VにKeccak固有の命令を追加する拡張提案もあります。^{[ 45 ]}

NIST規格では、メッセージMと出力長dに対して、以下のインスタンスが定義さ^れています。^{[ 6 ]： 20、23}

以下の定義に基づき

• Keccak[ c ]( N , d ) = sponge[Keccak-f[1600], pad10 ^* 1, r ]( N , d ) ^{[ 6 ] : 20}
• Keccak-f[1600] = Keccak-p[1600, 24] ^{[ 6 ] : 17}
• cは容量です
• rは速度 = 1600 − c
• Nは入力ビット列です

SHA-3はSHA-2の代替品としてそのまま使用でき、同じセキュリティ特性を持つように設計されています。

SHAKE は要求に応じてスポンジから必要な数のビットを生成するため、拡張可能な出力関数(XOF) となります。たとえば、SHAKE128(M, 256) は、128 ビットのセキュリティ強度を持つ 256 文字のビットストリームのハッシュ関数として使用できます。任意の長さを擬似乱数生成器として使用できます。あるいは、SHAKE256(M, 128) は、128 ビットの長さと 128 ビットの耐性を持つハッシュ関数として使用できます。^{[ 6 ]}

すべてのインスタンスはメッセージにいくつかのビットを追加します。その右端のビットはドメイン分離サフィックスを表します。これは、Keccakハッシュ関数の異なる適用に対して同じハッシュ出力を生成するメッセージを構築できないようにするためです。ドメイン分離サフィックスには次のものがあります。^{[ 6 ] [ 46 ] [ 47 ]}

2016年12月、NISTはSHA-3から派生した追加関数を記述した新しい文書NIST SP.800-185 ^{[ 47 ]を公開しました。}

• Xはメインの入力ビット列です。長さは0を含め、任意の長さを指定できます。
• Lは、要求された出力長をビット単位で表す整数です。
• Nは関数名のビット列であり、NISTがcSHAKEに基づいて関数を定義するために使用します。cSHAKE以外の関数が必要ない場合は、Nを空文字列に設定します。この場合、NはSHAKEと同じになります。
• Sはカスタマイズ用のビット列です。ユーザーはこの文字列を選択して、関数のバリエーションを定義します。カスタマイズが不要な場合は、Sは空文字列に設定されます。
• Kは、長さがゼロを含む任意のキービット列です。
• ^{B は並列ハッシュのブロックサイズ（バイト単位）です。0 < B < 2 2040}を満たす任意の整数です。

量子コンピュータは構造化原像攻撃を実行できるという一般的な結果（グローバーのアルゴリズム）がある。$\displaystyle {\sqrt {2^{d}}}=2^{d/2}}$一方、古典的な総当たり攻撃では2 ^dが必要となる。構造化された原像攻撃は、2 番目の原像攻撃^{[ 29 ]}を意味し、したがって衝突攻撃となる。量子コンピュータは誕生日攻撃も実行でき、衝突耐性を破ることができる。$\displaystyle {\sqrt[{3}]{2^{d}}}=2^{d/3}}$^{[ 55 ]}（ただし、これは議論の余地がある）。 ^{[ 56 ]}最大強度は${\displaystyle c/2}$これにより、 SHA-3の量子セキュリティに関する以下の上限値が得られます^{[ 57 ] 。}

SHA-2 で使用されているMerkle–Damgård 構成は崩壊性があり、結果として量子衝突耐性があることが示されていますが、 ^{[ 58 ]} SHA-3 で使用されているスポンジ構成については、ブロック関数f が効率的に可逆でない場合のみ証明が提供されています。しかし、Keccak-f[1600] は効率的に可逆であるため、彼らの証明は適用されません。^{[ 59 ]}

以下のハッシュ値はNIST.govからのものです。^{[ 60 ]}

SHA3​​-224（"） 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3​​-256（"） a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3​​-384（"") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3​​-512（"") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a6 15b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

1ビットを変更すると、出力内の各ビットが50%の確率で変化し、雪崩効果が生じる。

SHAKE128（「素早い茶色の狐が怠惰な犬を飛び越える」、256） f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128("素早い茶色のキツネが怠惰な犬のfを飛び越える", 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

以下の表において、内部状態とは、次のブロックに繰り越されるビット数を意味します。

AVX-512VL (つまりSkylake-X CPU上で動作するOpenSSLから)を使用した SHA3-256 の最適化された実装では、大きなメッセージの場合、1 バイトあたり約 6.4 サイクルが達成され、 ^{[ 65 ]} Skylake CPUでAVX2 を使用すると、1 バイトあたり約 7.8 サイクルになります。^{[ 66 ]}他の x86、Power、ARM CPU でのパフォーマンスは、使用する命令と正確な CPU モデルによって、1 バイトあたり約 8 ～ 15 サイクルまで変化し、^{[ 67 ] [ 68 ] [ 69 ]}一部の古い x86 CPU では、1 バイトあたり最大 25 ～ 40 サイクルになります。^{[ 70 ]}

以下は、SHA-3をサポートする暗号化ライブラリの一覧です。

• ボタン
• バウンシーキャッスル
• クリプト++
• Golangのx/crypto/sha3
• Libgcrypt
• libkeccak
• MIRACL暗号化SDK
• イラクサ
• OpenSSL
• Perl's Digest::SHA3
• Rustのsha3
• Zigのstd.crypto.sha3
• wolfSSL

Apple A13 ARMv8 6 コアSoC CPU コアは、ARMv8.2-SHA 暗号拡張セットの特殊命令を使用して SHA-3 (および SHA-512) を高速化するためのサポートを備えています^{[ 71 ] 。 [ 72 ]}これらの命令は SHA3 の手順全体を実装するのではなく、EOR3 (3 方向 XOR)、RAX (回転と XOR)、XAR (XOR と回転)、BCAX (ビットクリアと XOR) といったより小さな操作を実装します。

OpenSSLには、SHA-3（正確にはKeccak-f[1600]スポンジ関数）のさまざまなアセンブリ言語実装が含まれています。改善の大部分はスカラーコードの最適化によるもので、 SIMDによる効果はあまりありません。

• 32ビットx86では、MMX実装のみが提供されています。「MMX非対応プロセッサは絶滅種」であるためです。コメントによると、これはgcc-5.xで生成されたスカラーx86コードの約2倍の速度で動作します。^{[ 73 ]}
• 64 ビット x86 では、汎用、AVX2、AVX-512、および AVX-512VL の実装があります。プレーン バージョンは gcc-5.x で生成されたコードよりも約 15% 高速で、AVX2 バージョンは Intel プロセッサでは汎用バージョンよりもさらに 15% 高速です (ただし、Ryzen でははるかに低速です)。AVX-512 バージョンは Skylake-X で汎用よりも約 50% 高速化されています。^{[ 74 ]}
• ARMv4 以降では、手書きのスカラーコードによってコンパイラ出力に比べてパフォーマンスが 2 倍から 3 倍になります。Thumb-2 スカラーコードでは約 10% のメリットがあります。NEON コードではさらにパフォーマンスが 2 倍になりますが、最良の場合 (Snapdragon S4) でも処理する 1 バイトあたり 24 サイクルかかります。^{[ 75 ]} ARMv8 では、ハードウェア支援命令にベクトルレジスタがほとんど使用されない ARMv8.2-SHA の場合を除いて、NEON 命令を使用してもメリットはありません。^{[ 76 ]}
• PowerPC では、スカラーアセンブリ版は gcc-4.x コードよりも約 2 倍高速です (新しいコンパイラではさらに高速です)。POWER8には 2x64 ビットのベクトル回転機能があり便利ですが、POWER9 ではスカラー発行容量が高速化されているため、スカラー版が再び高速になります。^{[ 77 ]}

IBM z/Architecture は、 Message-Security-Assist Extension 6 の一部として 2017 年以降 SHA-3 をサポートしています。プロセッサは、各コアに組み込まれたハードウェア アシスト エンジンを使用して KIMD および KLMD 命令を介して SHA-3 および SHAKE アルゴリズム全体の完全な実装をサポートしています。^{[ 78 ]}

イーサリアムはKeccak-256ハッシュ関数を使用しています（BertoniらによるSHA-3コンテストの優勝作品のバージョン3に準拠しており、最終的なSHA-3仕様とは異なります）。^{[ 80 ]}

• Ethash – Keccakベースの別のハッシュ

• Solomon, MG (2019). Ethereum For Dummies . Wiley. ISBN 978-1-119-47411-12024年11月20日に取得。

• Keccakのウェブサイト
• SHA-3規格
• Excel での SHA-3 - Tim Wambach による Excel での実装例とデモンストレーション (マクロなし)。