スポンジ機能

暗号学において、スポンジ関数またはスポンジ構造は、任意の長さの入力ビットストリームを受け取り、任意の長さの出力ビットストリームを生成する有限内部状態を持つアルゴリズムのクラスのいずれかです。スポンジ関数には、理論的および実用的な用途があります。スポンジ関数は、暗号ハッシュ、メッセージ認証コード、マスク生成関数、ストリーム暗号、疑似乱数ジェネレータ、認証暗号化など、多くの暗号プリミティブをモデル化または実装するために使用できます。^[1]

スポンジ関数は3つの要素から構成されます: ^[2]

• bビットを含む状態メモリS 、
• 関数${\displaystyle f:\{0,1\}^{b}\rightarrow \{0,1\}^{b}}$
• パディング関数P

S は2 つのセクションに分かれています。1 つはサイズr (ビットレート) のセクション、もう 1 つはサイズc (容量) のセクションです。これらのセクションはそれぞれRとC で示されます。

f はSの状態の疑似ランダム順列を生成します。 ${\displaystyle 2^{b}}$

P は、パディングされた入力の長さがビットレートrの整数倍になるように、入力文字列に十分なビットを追加します。つまり、入力はrビットのブロックに分割されます。

スポンジ関数は、次のように、埋め込まれた入力文字列のすべてのブロックを 「吸収」します (スポンジのメタファーで)。

• Sはゼロに初期化される
• P（文字列） の各rビットブロックBについて
  • RはR XOR Bに置き換えられます（ビット単位のXORを使用）
  • Sはf ( S )に置き換えられる

スポンジ関数の出力は、次のように生成（「絞り出す」）する準備が整いました。

• 出力がいっぱいになるまで繰り返す
  • SのR部分を出力する
  • Sはf ( S )に置き換えられる

出力されるビットがr未満の場合、 R は切り捨てられます ( Rの一部のみが出力されます)。

別の比喩では、状態メモリを「エントロピープール」と表現し、入力がプールに「注ぎ込まれ」、変換関数が「エントロピープールをかき混ぜる」と表現されます。^[3]

入力ビットが状態メモリのC部分に XOR 演算されることはなく、 Cのビットが直接出力されることもないことに注意してください。入力によってC がどの程度変更されるかは、変換関数f によって完全に決まります。ハッシュ アプリケーションでは、衝突攻撃や原像攻撃に対する耐性はCによって決まり、そのサイズ (「容量」c ) は通常、必要な耐性レベルの 2 倍になります。

吸収と圧縮を交互に行うことも可能です。^[1]この操作はデュプレックス構成またはデュプレックス化と呼ばれ、シングルパス認証暗号化システムの基礎となります。

• 状態Sはゼロに初期化される
• 入力の 各rビットブロックBについて
  • RはBと排他的論理和をとる
  • Sはf ( S )に置き換えられる
  • R はサイズrビットの出力ブロックになります。

選択したセキュリティレベルを維持しながら、吸収中にXOR演算を省略することができます。^[1]このモードでは、吸収フェーズで、入力の次のブロックが状態のR部分を上書きします。これにより、ステップ間でより小さな状態を保持できます。R部分はいずれにせよ上書きされるため、事前に破棄することができ、C部分のみを保持する必要があります。

スポンジ関数には理論的および実用的な用途があります。理論的な暗号解読では、ランダムスポンジ関数はスポンジ構造であり、fはランダムな順列または変換です。ランダムスポンジ関数は、広く使用されているランダムオラクルモデルよりも、特に有限の内部状態など、暗号プリミティブの実用的な制限をより多く捉えています。 ^[4]

スポンジ構造は実用的な暗号プリミティブの構築にも使用できます。たとえば、1600ビットの状態を持つKeccak暗号スポンジは、NISTによってSHA-3コンペティションの優勝者に選ばれました。Keccakの強さは、その作者が開発した複雑な複数ラウンドの順列fに由来しています。^[5] RC4の再設計であるSpritzは、アルゴリズムを定義するためにスポンジ構造を参照しています。

他の例としては、スポンジ関数は、関連データ付き認証暗号化（AEAD）^[3]やパスワードハッシュスキーム^[6]の構築に使用できます。