高速シンドロームベースハッシュ

暗号学において、高速シンドロームベースハッシュ関数 (FSB)は、2003 年に Daniel Augot、Matthieu Finiasz、Nicolas Sendrier によって導入された暗号ハッシュ関数のファミリーです。 ^[1] 現在使用されている他のほとんどの暗号ハッシュ関数とは異なり、FSB はある程度安全であることが証明されています。より正確には、FSB を破ることは、通常のシンドローム復号化と呼ばれる特定のNP 完全問題を解くことと少なくとも同じくらい難しいことが証明されているため、FSB は証明可能に安全です。NP完全問題が多項式時間で解けるかどうかは不明ですが、そうではないと想定されることが多いです。

FSBにはいくつかのバージョンが提案されており、その最新版はSHA-3暗号コンテストに提出されたが、第一ラウンドで却下された。FSBのすべてのバージョンは証明可能なセキュリティを主張しているが、いくつかの初期バージョンは最終的に破られた。^[2] しかし、FSBの最新バージョンの設計ではこの攻撃が考慮されており、現在知られているすべての攻撃に対して安全である。

いつものように、証明可能なセキュリティにはコストがかかります。FSB は従来のハッシュ関数よりも遅く、大量のメモリを使用するため、メモリが制限された環境では実用的ではありません。さらに、FSB で使用される圧縮関数は、セキュリティを保証するために大きな出力サイズを必要とします。この最後の問題は、最近のバージョンでは、Whirlpoolと呼ばれる別の圧縮関数で出力を圧縮するだけで解決されています。ただし、著者は、この最後の圧縮を追加してもセキュリティは低下しないと主張していますが、正式なセキュリティ証明は不可能になります。^[3]

まず、および となるパラメータを持つ圧縮関数から始めます。この関数は、長さ のメッセージでのみ機能し、は出力のサイズになります。さらに、と は自然数である必要があります。ここで、 は2 進対数を表します。 の理由は、 を圧縮関数にしたいので、入力は出力よりも大きくなければならないからです。後でMerkle–Damgård 構成を使用して、ドメインを任意の長さの入力に拡張します。 ${\displaystyle \phi}$${\displaystyle {n,r,w}}$${\displaystyle n>w}$${\displaystyle w\log(n/w)>r}$${\displaystyle s=w\log(n/w)}$${\displaystyle r}$${\displaystyle n,r,w,s}$${\displaystyle \log(n/w)}$${\displaystyle \log}$${\displaystyle w\cdot \log(n/w)>r}$${\displaystyle \phi}$

この関数の基礎は、行列乗算によってビットのメッセージに作用する(ランダムに選択された) バイナリ行列で構成されます。ここでは、 ビットのメッセージを、 2 つの要素の体上の次元ベクトル空間である のベクトルとしてエンコードします。そのため、出力は ビットのメッセージになります。 ${\displaystyle r\times n}$${\displaystyle H}$${\displaystyle n}$${\displaystyle w\log(n/w)}$${\displaystyle (\mathbf {F} _{2})^{n}}$${\displaystyle n}$${\displaystyle r}$

セキュリティ上の理由とハッシュ速度の高速化のため、マトリックスの入力として「重み の通常の単語」のみを使用します。 ${\displaystyle w}$

• メッセージは、ビットで構成され、そのビットのすべてが 1 である場合、重みと長さのあるワードと呼ばれます。${\displaystyle w}$${\displaystyle n}$${\displaystyle n}$${\displaystyle w}$
• 重みと長さの単語は、すべての区間で に対して1 つの非ゼロのエントリが正確に含まれる場合、正規と呼ばれます。より直感的に言えば、これは、メッセージをw個の等しい部分に分割すると、各部分に 1 つの非ゼロのエントリが正確に含まれることを意味します。${\displaystyle w}$${\displaystyle n}$${\displaystyle [(i-1)(n/w),i(n/w))}$${\displaystyle 0<i<w+1}$

重みと長さの異なる正規語が正確に存在するため、これらの正規語をエンコードするには、正確に ビットのデータが必要です。長さのビット文字列のセットから重みと長さの正規語のセットへの一対一変換を固定すると、FSB 圧縮関数は次のように定義されます。 ${\displaystyle (n/w)^{w}}$${\displaystyle w}$${\displaystyle n}$${\displaystyle \log((n/w)^{w})=w\log(n/w)=s}$${\displaystyle s}$${\displaystyle w}$${\displaystyle n}$

1. 入力: サイズのメッセージ${\displaystyle s}$
2. 長さと重さの通常の単語に変換する${\displaystyle n}$${\displaystyle w}$
3. 行列を掛ける${\displaystyle H}$
4. 出力: サイズのハッシュ${\displaystyle r}$

このバージョンは通常、シンドロームベース圧縮と呼ばれます。これは非常に低速で、実際には別の高速な方法で実行され、高速なシンドロームベース圧縮になります。 をサイズのサブマトリックスに分割し、長さ のビット文字列から1 から までの数字のシーケンスのセットへの全単射を固定します。これは、長さと重みの通常の単語のセットへの全単射と同等です。これは、そのような単語を 1 から までの数字のシーケンスとして見ることができるためです。圧縮関数は次のようになります。 ${\displaystyle H}$${\displaystyle H_{i}}$${\displaystyle r\times n/w}$${\displaystyle w\log(n/w)}$${\displaystyle w}$${\displaystyle n/w}$${\displaystyle n}$${\displaystyle w}$${\displaystyle n/w}$

1. 入力: サイズのメッセージ${\displaystyle s}$
2. 1から10までの数字の列に変換します${\displaystyle s}$${\displaystyle w}$${\displaystyle s_{1},\dots ,s_{w}}$${\displaystyle n/w}$
3. 行列の対応する列を追加して、長さのバイナリ文字列を取得します。${\displaystyle H_{i}}$${\displaystyle r}$
4. 出力: サイズのハッシュ${\displaystyle r}$

これで、 Merkle-Damgård 構造を使用して、圧縮関数を一般化し、任意の長さの入力を受け入れることができるようになりました。

状況と初期化:サブブロック、、に 分割された行列 H を使用してメッセージをハッシュします。 ${\displaystyle s=010011}$${\displaystyle 4\times 12}$
${\displaystyle H=\left({\begin{array}{llllcllllcllll}1&0&1&1&~&0&1&0&0&~&1&0&1&1\\0&1&0&0&~&0&1&1&1&~&0&1&0&0\\0&1&1&1&~&0&1&0&0&~&1&0&0&~&1&0&0\\1&1&0&0&~&1&0&1&1&~&0&0&0&1\end{array}}\right)}$
${\displaystyle w=3}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle H_{3}}$

アルゴリズム:

1. 入力を長さの部分に分割すると、、、が得られます。${\displaystyle s}$${\displaystyle w=3}$${\displaystyle \log _{2}(12/3)=2}$${\displaystyle s_{1}=01}$${\displaystyle s_{2}=00}$${\displaystyle s_{3}=11}$
2. それぞれを整数に変換すると、、、が得られます。${\displaystyle s_{i}}$${\displaystyle s_{1}=1}$${\displaystyle s_{2}=0}$${\displaystyle s_{3}=3}$
3. 最初のサブマトリックスから列 2 を選択し、2 番目のサブマトリックスから列 1 を選択し、3 番目のサブマトリックスから列 4 を選択します。${\displaystyle H_{1}}$${\displaystyle H_{2}}$
4. 選択した列を追加して結果を取得します。${\displaystyle r=0111\oplus 0001\oplus 1001=1111}$

Merkle -Damgård 構造のセキュリティは、使用される圧縮関数のセキュリティのみに基づいていることが証明されています。したがって、圧縮関数が安全であることを示すだけで済みます。 ${\displaystyle \phi}$

暗号ハッシュ関数は、次の 3 つの側面で安全である必要があります。

1. 原像困難性: ハッシュhが与えられた場合、ハッシュ( m ) = hとなるメッセージm を見つけるのは困難である。
2. 2番目の原像抵抗: メッセージm _{1が与えられた場合、Hash(} m ₁ ) = Hash( m ₂ )となるメッセージm ₂を見つけるのは困難である。
3. 衝突耐性: Hash( m ₁ )=Hash( m ₂ )となる2つの異なるメッセージm ₁とm _2を見つけるのは困難であるべきである。

敵が 2 番目のプリイメージを見つけることができれば、衝突も確実に見つけられることに注意してください。つまり、システムが衝突耐性があることを証明できれば、2 番目のプリイメージにも耐性があることが確実になります。

通常、暗号学における「ハード」とは、「システムを破ることを阻止しなければならない敵の手の届かないところにある」という意味です。しかし、「ハード」という言葉のより正確な意味が必要になります。ここでは、「衝突または原像を見つけるアルゴリズムの実行時間は、ハッシュ値のサイズに指数関数的に依存する」という意味として「ハード」をとらえます。これは、ハッシュ サイズを比較的小さく追加するだけで、すぐに高いセキュリティを実現できることを意味します。

前述のように、FSB のセキュリティは、正規シンドローム復号 (RSD)と呼ばれる問題に依存します。シンドローム復号は、もともと符号理論の問題ですが、NP 完全性により暗号化に適しています。正規シンドローム復号は、シンドローム復号の特殊なケースであり、次のように定義されます。

RSD の定義:次元の行列と長さのビット文字列が与えられ、各 に 1 つずつあり、その合計が となる列の集合が存在します。そのような列の集合を見つけます。 ${\displaystyle w}$${\displaystyle H_{i}}$${\displaystyle r\times (n/w)}$${\displaystyle S}$${\displaystyle r}$${\displaystyle w}$${\displaystyle H_{i}}$${\displaystyle S}$

この問題は、 3 次元マッチングからの簡約によってNP 完全であることが証明されています。繰り返しになりますが、NP 完全問題を解決するための多項式時間アルゴリズムが存在するかどうかは不明ですが、そのようなアルゴリズムは知られておらず、発見されれば大きな発見となるでしょう。

与えられたハッシュの原像を見つけることがまさにこの問題と同等であることは容易に分かるので、FSB で原像を見つける問題も NP 完全でなければなりません。 ${\displaystyle S}$

まだ衝突耐性を証明する必要があります。そのためには、RSD の別の NP 完全なバリエーションである2 正則ヌル シンドローム デコードが必要です。

2-RNSD の定義:次元の行列と長さのビット文字列が与えられ、各列に 2 列または 0 列があり、その合計が 0 になる列の集合が存在します。そのような列の集合を見つけます。 ${\displaystyle w}$${\displaystyle H_{i}}$${\displaystyle r\times (n/w)}$${\displaystyle S}$${\displaystyle r}$${\displaystyle w'}$${\displaystyle H_{i}}$${\displaystyle (0<w'<2w)}$

2-RNSD は、 3 次元マッチングからの縮約によってNP 完全であることも証明されています。

RSD が本質的に となる正規の単語を見つけることと同等であるのと同様に、 2-RNSD はとなる2-正規の単語を見つけることと同等です。長さと重みの 2-正規の単語は、すべての区間で2 つまたは 0 つのエントリが 1 に等しい長さのビット文字列です。2-正規の単語は 2 つの正規の単語の合計にすぎないことに注意してください。 ${\displaystyle w}$${\displaystyle Hw=S}$${\displaystyle w'}$${\displaystyle Hw'=0}$${\displaystyle n}$${\displaystyle w}$${\displaystyle n}$${\displaystyle [(i-1)w,iw)}$

衝突が見つかったと仮定すると、Hash( m ₁ ) = Hash( m ₂ ) となり、 となります。すると、となる2 つの正規語とを見つけることができます。すると が得られます。は2 つの異なる正規語の合計なので、ハッシュが 0 である 2 正規語でなければなりません。したがって、2-RNSD の例を解決したことになります。FSB で衝突を見つけることは、少なくとも 2-RNSD を解くのと同じくらい難しく、NP 完全でなければならないという結論に達します。 ${\displaystyle m_{1}\neq m_{2}}$${\displaystyle w_{1}}$${\displaystyle w_{2}}$${\displaystyle Hw_{1}=Hw_{2}}$${\displaystyle H(w_{1}+w_{2})=Hw_{1}+Hw_{2}=2Hw_{1}=0}$${\displaystyle (w_{1}+w_{2})}$

FSB の最新バージョンでは、圧縮関数Whirlpool を使用してハッシュ出力をさらに圧縮します。これは証明できませんが、著者らはこの最後の圧縮によってセキュリティが低下することはないと主張しています。Whirlpool で衝突を検出できたとしても、FSB で衝突を検出するには、元の FSB 圧縮関数で衝突のプリイメージを検出する必要があることに注意してください。

RSD を解くときは、ハッシュのときとは逆の状況になります。前の例と同じ値を使用して、サブブロックに分割されたと文字列 が与えられます。各サブブロックで、すべての合計が となる 1 つの列だけを見つけるように求められます。したがって、予想される答えは、、です。これは、大きな行列では計算が難しいことが知られています。 ${\displaystyle H}$${\displaystyle w=3}$${\displaystyle r=1111}$${\displaystyle r}$${\displaystyle s_{1}=1}$${\displaystyle s_{2}=0}$${\displaystyle s_{3}=3}$

2-RNSD では、各サブブロックで 1 つの列ではなく、合計が 0000 ( ではなく) になる 2 列または 0 列を見つけます。例では、 から列 (0 から数えて) 2 列目と 3 列目を使用し、列 0 からは列を使わず、 からは 2 列目を使用します。より多くの解法が可能で、たとえば から列を使わずに済むかもしれません。 ${\displaystyle r}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle H_{3}}$${\displaystyle H_{3}}$

FSB の証明可能なセキュリティとは、衝突を見つけることが NP 完全であることを意味します。しかし、その証明は、漸近的に困難な最悪のケースの複雑さを持つ問題への還元です。問題空間のサブセットの問題を簡単に解決するアルゴリズムがまだ存在する可能性があるため、これでは限られたセキュリティ保証しか提供されません。たとえば、 2^128 のセキュリティを主張する FSB の初期のバリアントでは、デスクトップ PC で数秒で の衝突を生成するために使用できる線形化方法が存在します。メッセージ空間が特定の方法で選択された場合、ハッシュ関数は最小限のプリイメージまたは衝突耐性を提供することが示されています。

次の表は、FSB に対する最もよく知られている攻撃の複雑さを示しています。

FSB は、シンドロームベースハッシュ関数 (SB) の高速化バージョンです。SB の場合、圧縮機能は、Niederreiter のMcEliece 暗号システムのエンコード機能と非常に似ています。SB は、置換されたGoppa コードのパリティチェック行列を使用する代わりに、ランダム行列を使用します。セキュリティの観点からは、これはシステムを強化するだけです。 ${\displaystyle H}$

• ハッシュ関数のブロック サイズと出力サイズは両方とも完全にスケーラブルです。
• 速度は、入力ビットごとに FSB が使用するビット単位の演算数を調整することで調整できます。
• 出力サイズを調整することでセキュリティを調整できます。
• 悪い例も存在するため、マトリックスを選択する際には注意が必要です。${\displaystyle H}$
• 圧縮関数で使用される行列は、特定の状況では大きくなる可能性があります。これは、メモリが制限されたデバイスで FSB を使用するときに制限となる可能性があります。この問題は、Improved FSB と呼ばれる関連するハッシュ関数で解決されました。この関数は、依然として証明可能な安全性を備えていますが、やや強力な仮定に依存しています。

2007年にIFSBが公開されました。^[3] 2010年には、オリジナルよりも30%高速なS-FSBが公開されました。 ^[4]

2011年、DJ BernsteinとTanja Langeは、オリジナルのFSB-256よりも10倍高速なRFSBを発表しました。 ^{[5] RFSBは}Spartan 6 FPGA上で非常に高速に動作し、約5Gbit/sのスループットに達すること が示されました。> ^[6]

• SHA-3 コンテストに関する FSB の Web サイト