回転暗号解読

暗号学において、回転暗号解読は、モジュラー加算、回転、XORという3つの演算（略してARX）に依存するアルゴリズムに対する一般的な暗号解読攻撃である。これらの演算に依存するアルゴリズムは、ハードウェアとソフトウェアの両方において比較的低コストで、一定時間で実行できるため、一般的な実装ではタイミング攻撃に対して安全であることから広く用いられている。

回転暗号解読の基本的な考え方は、ビット回転とXOR演算の両方がビット回転された入力ペア間の相関関係を保持し、ビット回転された入力の加算もビット回転の相関関係を部分的に保持するというものです。したがって、回転された入力ペアを使用すると、予想以上に高い精度で暗号システムのカスケード ARX 演算を「見通す」ことができます。^{[ 1 ]}この、処理ラウンドを通して相関関係を「見通す」能力は、差分暗号解読と同様の方法で暗号システムを破るために悪用できます。

「回転暗号解読」という用語は、Dmitry KhovratovichとIvica Nikolićが2010年の論文「ARXの回転暗号解読」で提唱したもので、当時、SHA-3コンペティション候補であるSkeinハッシュ関数の一部である、ラウンド数を削減したThreefish暗号に対する最良の暗号解読攻撃が提示された。[ 1 ] [ 2 ]同じ^{著者とChristian Rechbergerによる追跡}攻撃では、Skein-256では72ラウンド中最大53ラウンド、Skein-512では72ラウンド中最大57ラウンドの衝突耐性が破られた。 ^{[ 3 ]}また、 Threefish暗号に対しても、256ビット鍵では最大39ラウンド、512ビット鍵では最大42ラウンド、1024ビット鍵では最大43ラウンドの複雑度で影響を与える。$2^252.4$、$2507$、 そして$2^{1014.4}}$それぞれ。^{[ 1 ]}

回転暗号解読は、XOR関数がデータに対して行われた回転を確率1で保持するという事実と、モジュラー加算が必ずしも回転を保持するとは限らないものの、その確率は（暗号システムによっては）十分に高くなる可能性があるため、ラウンド数を削減したバージョン、モジュラー加算を削除して変更された暗号システム、または十分な加算を使用しない非常に脆弱なARX暗号システムが容易に脆弱になる可能性があるという事実を利用します。

任意の文字をバイナリの変数とし、括弧 "()" 内の演算やデータを "r" だけシフトされたデータに関するステートメントとする。

(x${\displaystyle \oplus }$y)=(x)${\displaystyle \oplus }$(y)、そして「(x)r」は「(xをrだけシフトした)」と自明に等しい（出力を決定するのはxとrだけなので）。

モジュール式の追加$2n$ほとんどの場合非線形になる可能性があるため、より複雑です。シフトされた文字列がモジュラー加算（つまり、「(x+y) = (x)+(y)」）に耐える確率は次のとおりです。

${\displaystyle (1/4)(1+2^{rn}+2^{-r}+2^{-n})}$^{[ 1 ]}

ここで「n」は指数です$2n$、rは以前と同様に回転量です。

回転したバイナリの一部がARX暗号システムを通過する確率は${\displaystyle (p{r})^{q}}$ここで、「pr」は上記の式で与えられた単一のモジュラー加算を生き残る確率であり、「q」はARXスキーム内の加算の数です。^{[ 1 ]}攻撃が理論的に関連性を持つためには、攻撃によって鍵を取得する確率が、ランダムに鍵を発見する確率（つまり、平均的なケースの複雑さ）よりも低くなければなりません。$2n$回転暗号解読攻撃の$2n$（総当たり攻撃による）。ほとんどのARX暗号システムの完全版は脆弱ではないが、ラウンド数を減らしたバージョンは脆弱である。これは、鍵を復元できる確率が、混合プロセスの開始時（ラウンド）の方が終了時よりも高いためである。

また、多くのARXスキームには、通常のスキーム内でXOR演算して加算する必要のある定数項があることにも注意が必要です。これは、使用される定数が回転されている場合（既に述べたように、(x${\displaystyle \oplus }$y)=(x)${\displaystyle \oplus }$(y)、変数の1つが定数である可能性がある)が、回転されていない定数は回転が存続する確率を低下させる。元の攻撃論文の著者は、モンテカルロ法によって発見された「誤り訂正」変数を導入することでこれを補おうとしている。この変数は、ラウンド処理全体を通して定数が無効化される可能性を最大化することを目的としている。誤り訂正定数は、関数の出力と指定された誤り定数をXORすることで、暗号システムの特定のラウンドの定数難読化を解除する可能性がある。

例えば、Skeinでは、エラー定数によって以下の等価性が生じる可能性があり、ハッシュ圧縮関数が定数が関与する前の状態に戻ります。

${\displaystyle Skein((X)\oplus {E})=(Skein(X))}$^{[ 4 ]}ここで「e」は誤差定数であり、「${\displaystyle (Skein(X))}$「」は、定数を含まない、指定された時刻におけるラウンド関数の出力です。

誤り訂正定数は各暗号システム固有のものであり、モンテカルロシミュレーションによって求める必要があると考えられます。現在、実行時に必要な誤り訂正変数を求めるための公式は公表されていません。

回転暗号解読のラウンド数が少ない性質と、攻撃の成功に必要な運以外にも、大きな対策として、暗号のセキュリティレベルに合わせて必要な数の加算を追加することが挙げられます。ARX暗号の場合、$2^128$セキュリティに関しては、以前の規定に従って、最大で約128個のモジュール式追加部品が必要となります。${\displaystyle (p{r})^{q}}$その他の制約条件は含まない方程式。

Threefishに対する攻撃方法は、選択平文攻撃を実行する必要があるが、この攻撃にはそのような攻撃に伴う制約がある。

もう1つの制限は、エラー訂正変数の適用が成功しても、ラウンド内の定数が元に戻るという保証がないことです。元の論文では、ハミング重みが高くなるにつれて、特定のラウンドで定数がランダムに無効化される可能性が低くなると主張しています。^{[ 1 ]}キーラウンドと圧縮ラウンドの定数のハミング重みを上げると、セキュリティマージンが増加します。