フーガ（ハッシュ関数）

Fugue は、 IBMがNIST ハッシュ関数コンペティションに提出した暗号ハッシュ関数です。これはShai Halevi、William E. Hall、Charanjit S. Jutla によって設計されました。Fugue は、任意の長さのメッセージを受け取り、それを固定ビット長 (224、256、384、または 512 ビット) に圧縮します。異なる出力長のハッシュ関数は、Fugue-224、Fugue-256、Fugue-384、および Fugue-512 と呼ばれます。著者らは、Fugue のパラメーター化されたバージョンについても説明しています。このパラメーター化されたバージョンを使用して、Fugue-256 の弱いバージョンも説明しています。

Fugue のセールスポイントは、差分暗号解析に基づく現在のさまざまな攻撃戦略がFugue に対して有効ではないことを証明したという著者の主張です。また、ソフトウェアとハ​​ードウェアの両方の効率において NIST ハッシュ関数SHA-256と競合し、Intel Family 6 Model 15 Xeon 5150 で最大 36.2サイクル/バイト、Intel Core 2 プロセッサ T7700 で最大 25サイクル/バイトを達成していると言われています。45 nm Core2 プロセッサ (例: T9400) では、Fugue-256 は SSE4.1 命令を使用して 16 サイクル/バイトで動作します。より新しい Westmere アーキテクチャ (32 nm) (例: Core i5) では、Fugue-256 は 14 サイクル/バイトで動作します。

Fugue の設計はハッシュ関数 Grindahl から始まり、Grindahl と同様にAESのS ボックスを使用しますが、4×4 列の混合行列を 16×16 の「スーパーミックス」操作に置き換えて、拡散を大幅に改善します。ただし、「スーパーミックス」操作の実装にかかる計算コストは​​、AES の混合戦略よりもわずかに高くなります。

Fugue の 224 ビットおよび 256 ビット バリアントは、4 x 30 の符号なしバイトのマトリックスで表現できる状態で動作しますが、384 ビットおよび 512 ビット バリアントは、4 x 36 バイトのマトリックスで動作します。この状態では、インプレースで操作を実行できます。

「SuperMix 変換」と呼ばれるアルゴリズムの核心は、4×4 行列を入力として受け取り、新しい 4x4 行列を返します。SuperMix への入力は、現在の 30 列の状態の最初の 4 列のみであり、出力は同じ状態領域を置き換えるために使用されます (つまり、SuperMix は状態の先頭にある 4x4 行列にのみ影響します)。

SuperMix 関数は次のように定義できます。

${\displaystyle {\text{SuperMix}}(U)={\text{ROL}}\left(M\cdot U+{\begin{pmatrix}\sum _{j\neq 0}U_{j}^{i}&0&0&0\\0&\sum _{j\neq 1}U_{j}^{i}&0&0\\0&0&\sum _{j\neq 2}U_{j}^{i}&0\\0&0&0&\sum _{j\neq 3}U_{j}^{i}\end{pmatrix}}\cdot M^{T}\right)}$

どこ：

${\displaystyle M={\begin{pmatrix}1&4&7&1\\1&1&4&7\\7&1&1&4\\4&7&1&1\end{pmatrix}}}$;

${\displaystyle U}$4x4バイトの行列（つまり、入力のSボックス置換後の行列）であり、

${\displaystyle M^{T}}$M の転置です。

変換は4x4行列を取り、行目をバイト数だけ左に回転します。つまり、 ${\displaystyle ROL}$${\displaystyle i}$${\displaystyle i}$

${\displaystyle {\text{ROL}}(W)_{j}^{i}=W_{j-i{\pmod {4}}}^{i}}$

Fugue 2.0 はオリジナルの Fugue を改良したもので、256 ビット出力では Fugue の約 2 倍の速度で動作します。設計者は、この改良版では差分衝突攻撃に対する耐性が高度に証明されていると主張しています。完全な仕様については、以下のリンクを参照してください。

• ハッシュ関数フーガ^{[永久リンク切れ‍ ]}