フーガ（ハッシュ関数）

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では1バイトあたり最大36.2サイクル、Intel Core 2プロセッサT7700では1バイトあたり最大25サイクルを達成しています。45nm Core 2プロセッサ（例：T9400）では、Fugue-256はSSE4.1命令を使用して1バイトあたり16サイクルで動作します。Core i5などの新しいWestmereアーキテクチャ（32nm）では、Fugue-256は1バイトあたり14サイクルで動作します。

Fugueの設計はGrindahlのハッシュ関数から出発しており、Grindahlと同様にAESのSボックスを使用していますが、4×4列の混合行列を16×16の「スーパーミックス」演算に置き換えており、これにより拡散が大幅に改善されています。ただし、「スーパーミックス」演算の実装にかかる計算コストは​​、AESの混合戦略と比べてわずかに高いだけです。

スーパーミックス

Fugueの224ビット版と256ビット版は、4×30の符号なしバイト行列で表現できる状態を扱いますが、384ビット版と512ビット版は4×36バイト行列で表現します。この状態に対しては、インプレース演算を実行できます。

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

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

${\displaystyle {\text{スーパーミックス}}(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_{ji{\pmod {4}}}^{i}}$

フーガ 2.0

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

外部リンク

• ハッシュ関数フーガ