Metoda întâlnirii la mijloc

În criptoanaliza , metoda întâlnirii la mijloc sau „ atacul întâlnirii la mijloc ” este o clasă de atacuri asupra algoritmilor criptografici care reduc asimptotic timpul unei enumerari complete datorită principiului „ împărțiți și cuceriți ”. , precum și creșterea cantității de memorie necesară . Această metodă a fost propusă pentru prima dată de Whitfield Diffie și Martin Hellman în 1977 [1] .

Condiții inițiale

Sunt date textele deschise (necriptate) și cifrate . Un criptosistem constă din cicluri de criptare . Cheile ciclice sunt independente și nu au biți comuni. Cheia de sistem este o combinație de taste -ciclice . Sarcina este de a găsi cheia . $h$ $K$ $h$ $k_{1},k_{2}...k_{h)$ $K$

Soluție simplă de caz

Un exemplu simplu este criptarea blocului secvenţial dublu cu două chei diferite şi . Procesul de criptare arată astfel: $K_1$ $K_{2}$

$s=ENC_{K_{2}}(ENC_{K_{1}}(p))$ ,

unde este textul simplu, este textul cifrat și este operația de criptare unică cu cheia . În consecință, operația inversă - decriptare - arată astfel: $p$ $s$ $ENC_{K_{i}}()$ $K_{i}$

$p=ENC_{K_{1}}^{-1}(ENC_{K_{2}}^{-1}(e))$

La prima vedere, se pare că utilizarea criptării duble crește foarte mult securitatea întregii scheme, deoarece acum trebuie rezolvate două chei, și nu una. În cazul algoritmului DES , securitatea crește de la la . Cu toate acestea, nu este. Un atacator poate crea două tabele: $2^{56}$ $2^{112}$

Toate valorile pentru toate valorile posibile , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Toate valorile pentru toate valorile posibile . $m_{2}=ENC_{K_{2}}^{-1}(e)$ $K_{2}$

Apoi, trebuie doar să găsească potriviri în aceste tabele, adică astfel de valori și , că . Fiecare potrivire corespunde unui set de chei care satisface condiția. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(e)$ $(K_{1},K_{2})$

Acest atac a necesitat operațiuni de criptare-decriptare (doar de două ori mai multe decât pentru enumerarea unei chei) și memorie. Optimizări suplimentare - utilizarea tabelelor hash , calcule pentru doar jumătate din chei (pentru DES , căutarea exhaustivă, de fapt, necesită doar operații) - pot reduce aceste cerințe. Principalul rezultat al atacului este că criptarea secvenţială cu două chei dublează doar timpul brute-force. $2^{57}$ $2^{57}$ $2^{55}$

Soluție generală

Să notăm transformarea algoritmului ca , unde este textul simplu și este textul cifrat. Poate fi reprezentat ca o compoziție , unde este o transformare ciclică pe cheie . Fiecare cheie este un vector de lungime binar , iar cheia publică a sistemului este un vector de lungime . $E_{k}(a)=b$ $A$ $b$ $E_{k_{1}}E_{k_{2}}...E_{k_{h}}(a)=b$ $E_{k_{i)}$ $k_i$ $k_i$ $n$ $n\times h$

Umplerea memoriei

Toate valorile sunt sortate , adică primele chei ciclice. Pe fiecare astfel de cheie, criptăm textul simplu - (adică trecem prin cicluri de criptare în loc de ). O vom considera ca o anumită adresă de memorie și vom scrie valoarea la această adresă . Este necesar să se repete peste toate valorile . $k'=(k_{1},k_{2}...k_{r})$ $r$ $k'$ $A$ $E_{k'}(a)=E_{k_{1}}E_{k_{2}}...E_{k_{r}}(a)=S$ $r$ $h$ $S$ $k'$ $k'$

Definiția cheii

Toate posibilele sunt rezolvate . Pe cheile primite , textul cifrat este decriptat - . Dacă adresa nu este goală, atunci obținem cheia de acolo și obținem un candidat cheie . $k''=(k_{r+1},k_{r+2}...k_{h})$ $b$ $E_{k''}^{-1}(b)=E_{k_{h}}^{-1}...E_{k_{r+1}}^{-1}(b) =S'$ $S'$ $k'$ $(k',k'')=k$

Cu toate acestea, trebuie menționat că primul candidat primit nu este neapărat cheia adevărată. Da, pentru date și , dar pentru alte valori ale textului cifrat simplu obținut de pe cheia adevărată, egalitatea poate fi încălcată. Totul depinde de caracteristicile specifice ale criptosistemului . Dar uneori este suficient să obțineți o astfel de cheie „pseudo-echivalentă”. În caz contrar, după finalizarea procedurilor, se va obține un anumit set de chei , printre care se numără și cheia adevărată. $k$ $A$ $b$ $E_{k}(a)=b$ $A'$ $b'$ $A'$ ${\displaystyle {k',k''...))$

Dacă luăm în considerare o anumită aplicație, atunci textul cifrat și textul simplu pot fi mari (de exemplu, fișiere grafice) și reprezintă un număr suficient de mare de blocuri pentru un cifru bloc . În acest caz, pentru a accelera procesul, puteți cripta și decripta nu întregul text, ci doar primul său bloc (care este mult mai rapid) și apoi, după ce ați primit mulți candidați, căutați cheia adevărată în ea, verificând-o. blocurile rămase.

Atacul cu ruperea secvenței de taste în 3 părți

În unele cazuri, poate fi dificil să se separe biții unei secvențe de taste în părți legate de taste diferite. În acest caz, algoritmul de atac MITM cu 3 subseturi propus de Bogdanov și Richberger în 2011 este utilizat pe baza metodei obișnuite de întâlnire la mijloc. Acest algoritm este aplicabil atunci când nu este posibilă împărțirea secvențelor de biți cheie în două părți independente. Se compune din două faze: extragerea și verificarea cheilor [2] .

Faza de extragere a cheilor

La începutul acestei faze, cifrul este împărțit în 2 subcifre și , ca și în cazul general al atacului, permițând însă posibila folosire a unor biți dintr-un subcifr în altul. Deci, dacă , atunci ; în acest caz, biții cheii utilizați în vor fi notați cu , iar în — cu . Apoi, secvența de taste poate fi împărțită în 3 părți: $f$ $g$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $f$ $k_{f)$ $g$ $kg}$

$A_0$ este intersecția mulțimilor și , $k_{f)$ $kg}$
$A_{1}$ - biți cheie care sunt doar în , $k_{f)$
$A_{2}$ - biți cheie care sunt doar în . $kg}$

În continuare, un atac este efectuat prin metoda întâlnirii la mijloc conform următorului algoritm:

Pentru fiecare element din $A_0$

Calculați valoarea intermediară , unde este textul simplu și sunt câțiva biți de cheie de la și , adică este rezultatul criptării intermediare a textului simplu de pe cheie . $i=f(k_{f},a)$ $A$ $k_{f)$ $A_0$ $A_{1}$ $i$ $k_{f)$
Calculați valoarea intermediară , unde este textul privat și sunt niște biți de cheie de la și , adică este rezultatul decriptării intermediare a textului privat de pe cheie . $j=g^{-1}(k_{g},b)$ $b$ $kg}$ $A_0$ $A_{2}$ $j$ $kg}$
Comparați și . În cazul unui meci, obținem un candidat pentru chei. $i$ $j$

Faza de validare a cheii

Pentru a verifica cheile, candidații primiți sunt verificați cu mai multe perechi de texte cunoscute public-privat. De obicei, nu este necesar un număr foarte mare de astfel de perechi de texte pentru verificare [2] .

Exemplu

Ca exemplu, să luăm un atac asupra familiei de cifră KTANTAN [3] , care a făcut posibilă reducerea complexității de calcul a obținerii unei chei de la (atac de forță brută) la [1] . $2^{80}$ $2^{75.170}$

Pregătirea unui atac

Fiecare dintre cele 254 de runde de criptare folosind KTANTAN utilizează 2 biți aleatori ai cheii dintr-un set de 80 de biți. Acest lucru face ca complexitatea algoritmului să depindă doar de numărul de runde. Începând atacul, autorii au observat următoarele caracteristici:

În rundele de la 1 la 111, următorii biți cheie nu au fost utilizați: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
În rundele 131 la 254, următorii biți cheie nu au fost utilizați: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

Acest lucru a făcut posibilă împărțirea biților cheie în următoarele grupuri:

$A_0$ - biți cheie comune: cei 68 de biți nemenționați mai sus.
$A_{1}$ - biți utilizați numai în primul bloc de runde (de la 1 la 111),
$A_{2}$ - biți utilizați numai în al doilea bloc de runde (de la 131 la 254).

Faza 1: Extragerea cheilor

A existat o problemă în calcularea valorilor și descrise mai sus , deoarece rundele de la 112 la 130 lipsesc în considerare, dar apoi a fost efectuată o comparație parțială : autorii atacului au observat o potrivire de 8 biți în și , verificându-i cu un atac normal folosind metoda întâlnirii la mijloc la runda 127. În acest sens, în această fază, valorile acestor 8 biți din subcifre și au fost comparate . Acest lucru a crescut numărul de candidați cheie, dar nu și complexitatea de calcul. $i$ $j$ $i$ $j$ $i$ $j$

A doua fază: verificarea cheilor

Pentru a testa candidații cheie pentru algoritmul KTANTAN32, a fost nevoie în medie de încă două perechi de text public-privat pentru a extrage cheia.

Rezultate

KTANTAN32: Complexitatea computațională a ghicirii cheilor s-a redus la utilizarea a trei perechi de text public-privat. $2^{75.170}$
KTANTAN48: Complexitatea computațională a ghicirii cheilor s-a redus la utilizarea a două perechi de text public-privat. $2^{75.044}$
KTANTAN64: Complexitatea computațională a ghicirii cheilor s-a redus la utilizarea a două perechi de text public-privat. $2^{75.584}$

Cu toate acestea, acesta nu este cel mai bun atac asupra familiei de cifrare KTANTAN. În 2011, a fost făcut un atac [4] care a redus complexitatea de calcul a algoritmului la utilizarea a patru perechi de text deschis-închis. $2^{72.9}$

Atacul asupra unui grafic bipartit complet

Atacul complet cu graf bipartit este utilizat pentru a crește numărul de încercări de atac proxy prin construirea unui graf bipartit complet . Propus de Diffie și Hellman în 1977.

Algoritm multivariat

Algoritmul multidimensional meeting-in-the-middle este utilizat atunci când se utilizează un număr mare de cicluri de criptare cu chei diferite pe cifrurile bloc . În loc de obișnuita „întâlnire la mijloc”, acest algoritm folosește împărțirea criptotextului prin mai multe puncte intermediare [5] .

Se presupune că textul atacat este criptat de un anumit număr de ori cu un cifru bloc:

$C=ENC_{k_{n}}(ENC_{k_{n-1}}(...(ENC_{k_{1}}(P)))...))$ $P=DEC_{k_{1}}(DEC_{k_{2}}(...(DEC_{k_{n}}(C)))...))$

Algoritm

Calculat:

sC_{1}=ENC_{f_{1}}(k_{f_{1}},P)

\forall k_{f_{1}}\in K

sC_{1}

este stocat împreună cu d .

k_{1}

H_1

sC_{n+1}=DEC_{b_{n+1}}(k_{b_{n+1}}),C)

\forall k_{b_{n+1}}\in K

sC_{n+1}

este stocat împreună cu d .

k_{b_{n+1)}

H_{b_{n+1)}

Pentru fiecare stare intermediară posibilă , calculați: $s_{1}$

sC_{1}=DEC_{b_{1}}(k_{b_{1}},s_{1})

\forall k_{b_{1}}\in K

pentru fiecare potrivire cu un element de la până la , și sunt stocate .

sC_{1}

H_1

T_{1}

k_{b_{1)}

k_{f_{1)}

sC_{2}=ENC_{f_{2}}(k_{f_{2}},s_{1})

\forall k_{f_{2}}\in K

sC_{2}

salvat cu în .

k_{f_{2)}

H_2

Pentru fiecare stare intermediară posibilă , calculați: $s_{2}$

sC_{2}=DEC_{b_{2}}(k_{b_{2}},s_{2})

\forall k_{b_{2}}\in K

pentru fiecare potrivire cu un element din , se bifează o potrivire cu , după care și sunt stocate în .

sC_{2}

H_2

T_{1}

T_{2}

k_{b_{2)}

k_{f_{2)}

sC_{3}=ENC_{f_{3}}(k_{f_{3}},s_{2})

\forall k_{f_{3}}\in K

sC_{3)

salvat cu în .

k_{f_{3)}

H_3

Pentru fiecare stare intermediară posibilă , calculați: $s_{n}$

sC_{n}=DEC_{b_{n}}(k_{b_{n}},s_{n})

\forall k_{b_{n}}\in K

iar pentru fiecare potrivire cu un element din , se bifează o potrivire cu , după care și sunt stocate în .

sC_{n}

H_n

T_{n-1)

T_{n}

k_{b_{n)}

k_{f_{n)}

sC_{n+1}=ENC_{f_{n+1}}(k_{f_{n+1}},s_{n})

\forall k_{f_{n+1}}\in K

iar pentru fiecare meci cu , un meci cu

sC_{n+1}

H_{n+1}

T_{n}

Apoi, secvența de candidați găsită este testată pe o altă pereche de text public-privat pentru a confirma validitatea cheilor. Trebuie remarcat faptul că algoritmul este recursiv: selecția cheilor pentru stare se bazează pe rezultatele pentru starea . Aceasta introduce un element de complexitate exponențială în acest algoritm [5] . $s_{j}$ $s_{j-1}$

Dificultate

Complexitatea de timp a acestui atac este $2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}\cdot (2^{| k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}\cdot (2^{|k_{b_{2}}|} +2^{|k_{f_{3}}|}+...))$

Apropo de utilizarea memoriei, este ușor de observat că , pe măsură ce fiecare crește , sunt impuse din ce în ce mai multe restricții, ceea ce reduce numărul de candidați care i-au scris. Asta înseamnă mult mai puțin . $i$ $T_{i}$ $T_{2},T_{3},...,T_{n)$ $T_{1}$

Limita superioară a cantității de memorie utilizată:

2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s+n|}+...

unde este lungimea totală a cheii.

k

Complexitatea utilizării datelor depinde de probabilitatea de a „trece” o cheie falsă. Această probabilitate este egală cu , unde este lungimea primei stări intermediare, care este cel mai adesea egală cu dimensiunea blocului. Având în vedere numărul de candidați cheie după prima fază, complexitatea este de . $1/2^{l}$ $l$ $2^{|k|-|l|}$

Ca rezultat, obținem , unde este dimensiunea blocului. ${\displaystyle 2^{|k|-2b))$ $|b|$

De fiecare dată când o secvență de chei candidată este testată pe o nouă pereche de text public-privat, numărul de chei care trec testul este înmulțit cu probabilitatea de a trece cheia, care este . $1/2^{|b|}$

O parte a atacului cu forță brută (verificarea cheilor împotriva noilor perechi de text public-privat) are o complexitate de timp , în care, evident, termenii ulterioare tind să se zero din ce în ce mai repede. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

Ca rezultat, complexitatea datelor prin judecăți similare este limitată la aproximativ perechi de chei public-privat. $\left\lceil |k|/n\right\rceil$

Note

↑ 12 Diffie , Whitfield; Hellman, Martin E. Criptanaliză exhaustivă a standardului de criptare a datelor NBS (engleză) // Computer : jurnal. - 1977. - Iunie ( vol. 10 , nr. 6 ). - P. 74-84 . - doi : 10.1109/CM.1977.217750 . Arhivat din original pe 14 mai 2009.
↑ 1 2 Andrey Bogdanov și Christian Rechberger. „Atacul Meet-in-the-Middle din 3 subseturi: Cryptanalysis of the Lightweight Block Cipher KTANTAN” Arhivat 7 noiembrie 2018 la Wayback Machine
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. „KATAN & KTANTAN - O familie de cifruri bloc orientate pe hardware mici și eficiente” Arhivat 20 aprilie 2018 la Wayback Machine
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang și San Ling. „Cryptanalysis Meet-in-the-Middle îmbunătățită a KTANTAN” Arhivat 7 noiembrie 2018 la Wayback Machine
↑ 1 2 3 Zhu, Bo; Guang Gong. Atacul MD-MITM și aplicațiile sale la GOST, KTANTAN și Hummingbird-2 (engleză) // eCrypt : jurnal. — 2011.

Literatură

Moore, Stephane. Atacurile Meet-in-the-Middle (neopr.) . - 2010. - 16 noiembrie. - S. 2 .