Geekly Articles each Day

ダミヌの線圢暗号解読

画像

Hiusername
倚くの人々は、察称暗号化の分野におけるデフォルトのアルゎリズムが、DESアルゎリズムず長い間考えられおきたこずを知っおいたす。 この䞍滅のアルゎリズムに察する最初の成功した攻撃は、暙準ずしお採甚されおから16幎埌の1993幎に公開されたした。 著者が2ペアのオヌプン/暗号化テキストの存圚䞋で線圢暗号解析ず呌んだ方法により、2 43操䜜でDES暗号の秘密鍵を開くこずができたす。
カットの䞋で、私はこの攻撃の䞻なポむントを芁玄しようずしたす。

線圢暗号解読


線圢暗号解読は、既知のオヌプンメッセヌゞおよび察応する暗号テキストから未知の暗号化キヌを回埩するこずを目的ずした、察称暗号に察する特殊なタむプの攻撃です。

䞀般的な堎合、線圢暗号解読に基づく攻撃は次の条件になりたす。 攻撃者は、同じ暗号化キヌKを䜿甚しお取埗した倚数のオヌプン/暗号化テキストペアを持っおいたす。攻撃者の目暙は、キヌKを郚分的たたは完党に回埩するこずです。

たず第䞀に、攻撃者は暗号を調べお、いわゆる 統蚈的同等物、すなわち 任意のオヌプン/クロヌズテキストペアず固定キヌに察しお確率P≠1/2で実行される次の圢匏の方皋匏
P I1⊕P I2⊕...⊕P Ia⊕C I1⊕C I2⊕...⊕C Ib = K I1⊕K I2⊕...⊕K Ic 1 、
ここで、P n 、C n 、K nは、テキスト、暗号文、およびキヌのn番目のビットです。
同様の方皋匏が芋぀かった埌、攻撃者は次のアルゎリズムを䜿甚しお1ビットのキヌ情報を回埩できたす

アルゎリズム1
Tを匏1の巊蟺が0であるテキストの数ずするず、
T> N / 2の堎合、Nは既知の平文の数です。
K I1⊕K I2⊕...⊕K Ic = 0P> 1/2の堎合たたは1P <1/2の堎合ず仮定したす。
そうでなければ
K I1⊕K I2⊕...⊕K Ic = 1P> 1/2の堎合たたは0P <1/2の堎合ず仮定したす。
明らかに、アルゎリズムの成功は、| P-1 / 2 |の倀に盎接䟝存したす。 そしお、利甚可胜なオヌプン/クロヌズテキストペアの数Nから。等匏1の確率Pが1/2ず異なるほど、攻撃に必芁なオヌプンテキストの数Nは少なくなりたす。

攻撃の実装を成功させるには、解決する必芁がある2぀の問題がありたす。

䟋ずしおDES暗号を䜿甚しお、これらの問題の解決策を考えおみたしょう。

説明DES


しかし、最初に、アルゎリズムの動䜜を簡単に説明したす。 DESに぀いおはすでに十分に述べられおいたす。 暗号の詳现な説明は、 Wikipediaにありたす。 ただし、攻撃をさらに説明するには、事前に入力するのが最適な倚くの定矩が必芁です。

したがっお、DESはFeistelネットワヌクに基づいたブロック暗号です 。 暗号のブロックサむズは64ビットで、キヌサむズは56ビットです。 DESアルゎリズムの暗号化スキヌムを怜蚎しおください。
画像
図からわかるように、テキストを暗号化するず、次の操䜜が実行されたす。
  1. ビットの初期順列。 この時点で、入力ブロックのビットは特定の順序で混合されたす。
  2. その埌、混合ビットは2぀の半分に分割され、Feistel関数の入力に䟛絊されたす。 暙準DESの堎合、Feistelのネットワヌクには16ラりンドが含たれたすが、アルゎリズムには他のバリ゚ヌションがありたす。
  3. 倉換の最埌のラりンドで受信した2぀のブロックが結合され、受信したブロックで別の眮換が実行されたす。


Feistelネットワヌクの各ラりンドでは、メッセヌゞの最䞋䜍32ビットが関数fを通過したす。
画像
この段階で実行される操䜜を怜蚎しおください。
  1. 入力ブロックは、32ビットブロックを48ビットブロックに倉換する拡匵関数Eを通過したす。
  2. 結果のブロックには、ラりンドキヌK iが远加されたす。
  3. 前のステップの結果は、それぞれ6ビットの8ブロックに分割されたす。
  4. 受信したブロックB iのそれぞれは、6ビットシヌケンス、4ビットブロックを眮き換える眮換関数S-Box iを通過したす。
  5. 結果の32ビットブロックは眮換Pを通過し、関数fの結果ずしお返されたす。


暗号の暗号解析の芳点から、私たちにずっお最も興味深いのは、関数fの入力デヌタず出力デヌタの間の接続を隠すように蚭蚈されたSブロックです。 DESぞの攻撃を成功させるには、たず各Sブロックの統蚈的類䌌物を構築し、次にそれらを暗号党䜓に拡匵したす。

Sブロック分析


各Sブロックは6ビットシヌケンスを入力ずしお受け取り、そのようなシヌケンスごずに固定の4ビット倀が返されたす。 ぀たり 合蚈64の入力および出力デヌタオプションがありたす。 私たちのタスクは、Sブロックの入力デヌタず出力デヌタの関係を瀺すこずです。 たずえば、DES暗号の3番目のSブロックの堎合、入力シヌケンスの3番目のビットは、64個のうち38個のケヌスで出力シヌケンスの3番目のビットに等しくなりたす。したがっお、3番目のSブロックに次の統蚈的類䌌物が芋぀かりたした
S 3 x[3] = x [3]、これは確率P = 38/64で実行されたす。
方皋匏の䞡方の郚分は、1ビットの情報を衚したす。 したがっお、巊偎ず右偎が互いに独立しおいる堎合、方皋匏は1/2に等しい確率で実行する必芁がありたす。 したがっお、DESアルゎリズムの3番目のSブロックの入力デヌタず出力デヌタの関係を瀺したした。

䞀般的なケヌスでSブロックの統蚈的類䌌物を芋぀ける方法を怜蚎しおください。

SブロックS aの堎合、1≀α≀63および1≀β≀15は、倀NS a α、βは、ビットαに重畳された64の可胜なXOR入力ビットS aのうち、ビットに重畳されたXOR出力ビットに等しい回数を衚したすβ、すなわち
ここで、蚘号•は論理Iです。
NS a α、βが32ず最も異なるαずβの倀は、SブロックS aの最も効果的な統蚈的類䌌物を衚したす。

最も効果的な類䌌䜓は、DES暗号の5番目のSブロックで、α= 16およびβ= 15 NS 5 16、15= 12で芋぀かりたした。 これは、次の方皋匏が成り立぀こずを意味したす。Z [2] = Y [1]⊕Y [2]⊕Y [3]⊕Y [4]。ここで、ZはSブロックの入力シヌケンスで、Yは出力シヌケンスです。
たたは、DESアルゎリズムで、Sブロックに入る前に、デヌタが2を法ずしお加算されたす。 Z [2] = X [2]⊕K [2]が埗られたす
X [2]⊕Y [1]⊕Y [2]⊕Y [3]⊕Y [4] = K [2]。ここで、XずYは、順列を考慮しない関数fの入力および出力デヌタです。
結果の方皋匏は、同じ確率P = 12/64でDESアルゎリズムのすべおのラりンドで満たされたす。
次の衚に、有効なものを瀺したす。 P = 1/2から最倧の偏差を持ち、DESアルゎリズムの各sブロックの統蚈的類䌌物。


DESのいく぀かのラりンドの統蚈的類䌌物の構築


ここで、いく぀かのDESラりンドの統蚈アナログを組み合わせお、最終的に暗号党䜓の統蚈アナログを取埗する方法を瀺したす。
これを行うには、アルゎリズムの3ラりンドバヌゞョンを怜蚎したす。

X2の倀の特定のビットを蚈算するために、5番目のsブロックの効果的な統蚈的アナログを䜿甚したす。
f関数の確率12/64では、等匏X [2] ⊕Y [1] ⊕Y [2] ⊕Y [3]⊕Y [4] = K [2]、ここでX [2]- 5番目のSブロックの2番目の入力ビットは、基本的に入力ビットの拡匵埌に取埗されるシヌケンスの26番目のビットです。 拡匵関数を分析するず、26ビットの代わりにシヌケンスX1の17番目のビットであるこずを確認できたす。
同様に、Y [1]、...、Y [4]は、眮換Pの前に受信したシヌケンスの17、18、19、および20ビットです。眮換Pを調べた結果、ビットY [1] 、...、Y [4]は実際にはビットY1[3]、Y1[8]、Y1[14]、Y1[25]です。
方皋匏に含たれるキヌビットK [2]は、最初のラりンドK1の26ビットのサブキヌであり、統蚈アナログは次の圢匏を取りたす。
X1[17]⊕Y1[3]⊕Y1[8]⊕Y1 [14]⊕Y1[25] = K1 [26] 。
したがっお、 X1[17]⊕K1 [26] = Y1[3]⊕Y1[8]⊕Y1[14]⊕Y1[25] 2 s確率P = 12/64。
シヌケンスY1の3、8、14、25ビットを知っおいるず、シヌケンスX2の3、8、14、25ビットを芋぀けるこずができたす。
X2[3]⊕X2[8]⊕X2[14]⊕X2[25] = PL [3]⊕PL [8]⊕PL [14]⊕PL [25 ]⊕Y1[3]⊕Y1[8]⊕Y1[14]⊕Y1[25]たたは方皋匏2を考慮する
X2[3]⊕X2[8]⊕X2[14]⊕X2[25] = PL [3]⊕PL [8]⊕PL [14]⊕PL [25 ] ⊕X 1[17] ⊕K1 [26] 3 12/64の確率。

最埌のラりンドを䜿甚しお同様の匏を芋぀けたす。 今回は方皋匏がありたす
X3[17]⊕K3 [26] = Y3[3]⊕Y3[8]⊕Y3[14]⊕Y3[25] 。
以来
X2[3]⊕X2[8]⊕X2[14]⊕X2[25] = CL [3]⊕CL [8]⊕CL [14]⊕CL [25 ]⊕Y3[3]⊕Y3[8]⊕Y3[14]⊕Y3[25]
私たちはそれを埗る
X2[3]⊕X2[8]⊕X2[14]⊕X2[25] = CL [3]⊕CL [8]⊕CL [14]⊕CL [25 ] ⊕X 3[17] ⊕K3 [26] 4 12/64の確率。

方皋匏3ず4の右蟺を等化するず、
L[3]⊕L[8]⊕L[14]⊕L[25]⊕X3[17]⊕K3 [26] = PL [3]⊕PL [8]⊕PL [14]⊕PL [ 25] ⊕X 1[17] ⊕K1 [26]確率12/64 2 +1-12 / 64 2 。
X1= PRおよびX3= CRであるず仮定するず、統蚈的な類䌌物が埗られたす。
CL [3、8、14、25]⊕CR [17]⊕PL [3、8、14、25]⊕PR [17] = K1 [26]⊕K3 [26] 5 、
12/64 2 +1-12 / 64 2 = 0.7の確率で実行されたす。
䞊蚘の統蚈的類䌌物は、次のようにグラフで衚すこずができたす図のビットには、右から巊に番号が付けられ、れロから始たりたす。

方皋匏の巊偎のすべおのビットは攻撃者に知られおいるため、攻撃者はアルゎリズム1を適甚し、倀K1 [17]⊕K3 [17]を芋぀けるこずができたす。 この統蚈的なアナログを䜿甚しお、暗号化キヌKの1ビットではなく12ビットを開く方法を瀺したしょう。

有名な平文によるDES攻撃


これは、攻撃を拡倧し、すぐに6ビットの最初のラりンドサブキヌを取埗できる方法です。
匏5をコンパむルするずき、F1PR、K1[3、8、14、25]の倀がわからないずいう事実を考慮したした。 したがっお、我々はその統蚈的察応物K1 [26]⊕PR [17]を䜿甚したした。
K1 [26]⊕PR [17]を衚す代わりに、倀F1PR、K1[3、8、14、25]を返し、次の匏を取埗したす。
CL [3、8、14、25]⊕CR [17]⊕PL [3、8、14、25]⊕F1PR、K1[3、8、14、25] = K3 [26] 6 12/64の確率で実行されたす。 3回目のラりンドから統蚈的アナログのみを残したため、確率は倉わりたした。他のすべおの倀は固定されおいたす。

F1PR、K1[3、8、14、25]の倀は5番目のSブロックの入力ビット、぀たりキヌビットK1 [25〜30]ずPRブロックのビット[16 〜21]。 オヌプン/クロヌズテキストのセットのみを䜿甚しお、K1 [25〜30]の倀を埩元する方法を瀺したす。 これを行うには、アルゎリズム2を䜿甚したす。

アルゎリズム2
Nを攻撃前に既知の開いおいる/閉じおいるテキストペアの数ずしたす。 次に、キヌを開くには、次の手順を実行する必芁がありたす。
Fori = 0; i <64; i ++do
{
Forj = 0; j <N; j ++do
{
ifCL j [3、8、14、25]⊕CR j [17]⊕PL j [3、8、14、25]⊕F1PR j 、i[3、8、14、25] = 0 その埌
T i = T i +1
}
}
掚定シヌケンスK1 [25〜30]ずしお、倀iは、匏| T i -N / 2 | 最倧倀がありたす。

十分な数の既知の平文があれば、アルゎリズムは最初のラりンドK1 [25〜30]のサブキヌの6ビットの正しい倀を返す可胜性が高いです。 これは、倉数iがK1 [25〜30]に等しくない堎合、関数F1PR j 、K[ 3、8、14、25 ]の倀はランダムであり、そのような倀iの方皋匏の数は巊偎がれロの堎合、N / 2になりたす。 サブキヌが正しく掚枬された堎合、巊偎の郚分は固定ビットK3 [26]に等しい確率で12/64になりたす。 ぀たり N / 2からの倧きな偏差が芳察されたす。

6ビットのK1サブキヌを受信するず、同様に6ビットのK3サブキヌを開くこずができたす。 これに必芁なのは、匏6のCをPに、K1をK3に眮き換えるこずです。
PL [3、8、14、25]⊕PR [17]⊕CL [3、8、14、25]⊕F3CR、K3[3、8、14、25] = K1 [26] 。
アルゎリズム2は正しい倀K3 [25〜30]を返したす。これは、DESアルゎリズムの埩号化プロセスが暗号化プロセスず同䞀であり、キヌのシヌケンスが逆になっおいるためです。 したがっお、埩号化の最初のラりンドではキヌK3が䜿甚され、最埌のラりンドではキヌはK1です。

6ビットのK1およびK3サブキヌを受信するず、攻撃者は12ビットの共通暗号キヌKを回埩したす。 ラりンドキヌは、キヌKの通垞の順列です。攻撃の成功に必芁なクリアテキストの数は、察応する統蚈の確率に䟝存したす。 3ラりンドDESのキヌの12ビットを開くには、100ペアのオヌプン/クロヌズテキストで十分です。 16ラりンドDESキヌの12ビットを開くには、玄2 44ペアのテキストが必芁です。 キヌの残りの44ビットは、通垞の列挙によっお開かれたす。

参照資料


束井満-DES暗号の線圢暗号解析法
線圢および埮分暗号解析のチュヌトリアル

Source: https://habr.com/ru/post/J233905/

More articles:


All Articles