Loading article…
暗号学において、線形暗号解読は、暗号の動作に対するアフィン近似を見つけることに基づく暗号解読の一般的な形式です。ブロック暗号とストリーム暗号に対する攻撃が開発されています。線形暗号解読は、ブロック暗号に対する最も広く使用されている 2 つの攻撃の 1 つであり、もう 1 つは差分暗号解読です。
この発見は松井充によるもので、彼はこの技術を初めてFEAL暗号に適用した（松井・山岸、1992年）。[1]その後、松井はデータ暗号化標準（DES）に対する攻撃を発表し、最終的にはオープンコミュニティで報告された暗号の最初の実験的暗号解読につながった（松井、1993年、1994年）。[2] [3] DESに対する攻撃は一般に実用的ではなく、247の 既知の平文を必要とする。[3]
この攻撃には、複数の線形近似の使用や非線形表現の組み込みなど、さまざまな改良が提案されており、一般化された分割暗号解読につながります。新しい暗号設計には通常、線形暗号解読に対するセキュリティの証拠が求められます。
概要
線形暗号解読には 2 つの部分があります。1 つ目は、平文、暗号文、およびキー ビットを関連付ける線形方程式を構築することです。この線形方程式はバイアスが高く、つまり、(変数のすべての可能な値の空間にわたって) 保持される確率が 0 または 1 に可能な限り近くなります。2 つ目は、これらの線形方程式を既知の平文と暗号文のペアと組み合わせて使用し、キー ビットを導出することです。
線形方程式の構築
線形暗号解析の目的で、線形方程式は排他的論理和 (XOR) 演算と組み合わせたバイナリ変数で構成される 2 つの式の等式を表します。たとえば、仮想暗号からの次の方程式は、(ブロック暗号のブロックのように) 平文の 1 番目と 3 番目のビットの XOR 合計を示しており、最初の暗号文ビットはキーの 2 番目のビットに等しくなります。
理想的な暗号では、平文、暗号文、鍵ビットを関連付ける任意の線形方程式は、確率 1/2 で成立します。線形暗号解読で扱われる方程式は確率が変化するため、より正確には線形近似と呼ばれます。
近似値を構築する手順は暗号ごとに異なります。最も基本的なタイプのブロック暗号である置換–置換ネットワークでは、解析は主に暗号の唯一の非線形部分であるS ボックスに集中しています(つまり、S ボックスの操作は線形方程式でエンコードできません)。十分に小さい S ボックスの場合、S ボックスの入力ビットと出力ビットに関連するすべての可能な線形方程式を列挙し、それらのバイアスを計算して最適なものを選択することができます。次に、S ボックスの線形近似を、置換やキー混合などの暗号の他のアクションと組み合わせて、暗号全体の線形近似に到達する必要があります。積み重ね補題は、この組み合わせステップに役立つツールです。線形近似を反復的に改善する手法もあります (Matsui 1994)。
キービットの導出
次の形式の線形近似が得られる:
次に、既知の平文と暗号文のペアを使用して、近似に関係するキービットの値を推測するための簡単なアルゴリズム (Matsui のアルゴリズム 2) を適用できます。
右側のキー ビットの値の各セット (部分キーと呼ばれる) について、既知の平文と暗号文のペアすべてに対して近似が成立する回数を数えます。この回数をTと呼びます。Tが平文と暗号文のペアの半数との絶対差が最も大きい部分キーは、そのキー ビットの最も可能性の高い値のセットとして指定されます。これは、正しい部分キーによって近似が大きなバイアスで成立すると想定されるためです。ここでは、確率自体の大きさではなく、バイアスの大きさが重要です。
この手順は、他の線形近似を使用して繰り返すことができ、未知のキービットの数がブルートフォース攻撃が可能になるくらい十分に少なくなるまで、キービットの値を推測することができます。
参照
参考文献
外部リンク
- DESの線形暗号解析
- 線形および差分暗号解読のチュートリアル
- 線形暗号解読デモ
- ブロック暗号の線形（および差分）暗号解析に関するチュートリアル
- 「松井の線形暗号解読の時間計算量の改善」は、高速フーリエ変換のおかげで計算量が改善されます。