Tapaaminen keskellä menetelmää

Kryptoanalyysissä "meet-in-the-middle" -menetelmä tai " meet-in-the-middle-hyökkäys " on luokka salausalgoritmeja vastaan tehtyjä hyökkäyksiä, jotka lyhentävät asymptoottisesti täydellisen luetteloinnin aikaa " hajoita ja hallitse " -periaatteen vuoksi. , sekä lisäämällä tarvittavan muistin määrää . Tätä menetelmää ehdottivat ensimmäisen kerran Whitfield Diffie ja Martin Hellman vuonna 1977 [1] .

Alkuehdot

Avoin (salaamaton) ja salattu teksti on annettu. Salausjärjestelmä koostuu salausjaksoista . Sykliset näppäimet ovat riippumattomia ja niillä ei ole yhteisiä bittejä. Järjestelmänäppäin on syklisten näppäinten yhdistelmä . Tehtävänä on löytää avain . $h$ $K$ $h$ ${\displaystyle k_{1},k_{2}...k_{h))$ $K$

Yksinkertainen tapausratkaisu

Yksinkertainen esimerkki on kaksinkertainen peräkkäinen lohkosalaus kahdella eri avaimella ja . Salausprosessi näyttää tältä: $K_1$ $K_{2}$

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

missä on selväteksti, on salateksti ja on kertaluonteinen salausoperaatio avaimella . Vastaavasti käänteinen toiminta - salauksen purku - näyttää tältä: $s$ $s$ $ENC_{K_{i}}()$ $K_{i}$

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

Ensi silmäyksellä näyttää siltä, että kaksoissalauksen käyttö lisää suuresti koko järjestelmän turvallisuutta, koska nyt on selvitettävä kaksi avainta, ei yksi. DES-algoritmin tapauksessa suojaus kasvaa arvosta arvoon . Se ei kuitenkaan ole. Hyökkääjä voi luoda kaksi taulukkoa: $2^{56}$ $2^{112}$

Kaikki arvot kaikille mahdollisille arvoille , $m_{1}=ENC_{K_{1}}(p)$ $K_1$
Kaikki arvot kaikille mahdollisille arvoille . $m_{2}=ENC_{K_{2}}^{-1}(s)$ $K_{2}$

Sitten hänen tarvitsee vain löytää osumat näistä taulukoista, eli sellaiset arvot ja , että . Jokainen vastaavuus vastaa ehdon täyttävää näppäinsarjaa. $m_1$ $m_2$ $ENC_{K_{1}}(p)=ENC_{K_{2}}^{-1}(s)$ ${\näyttötyyli (K_{1}, K_{2})}$

Tämä hyökkäys vaati salaus-salauksenpurkuoperaatioita (vain kaksi kertaa enemmän kuin yhden avaimen laskeminen) ja muistia. Lisäoptimoinnit - hash-taulukoiden käyttö , laskelmat vain puolelle avaimista ( DES :ssä tyhjentävä haku vaatii itse asiassa vain toimintoja) - voivat vähentää näitä vaatimuksia. Hyökkäyksen tärkein tulos on se, että kahden avaimen peräkkäinen salaus vain kaksinkertaistaa raa'an voiman ajan. $2^{57}$ $2^{57}$ $2^{55}$

Yleinen ratkaisu

Merkitään algoritmin muunnos muodossa , jossa on selväteksti ja on salateksti. Se voidaan esittää sävellyksenä , jossa on syklinen muunnos avaimessa . Jokainen avain on binääripituusvektori ja järjestelmän julkinen avain on pituusvektori . $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$

Muistin täyttäminen

Kaikki arvot on järjestetty , eli ensimmäiset sykliset näppäimet. Jokaisessa tällaisessa avaimessa salaamme selkeän tekstin - (eli käymme läpi salausjaksot :n sijaan ). Pidämme sitä tiettynä muistiosoitteena ja kirjoitamme arvon tähän osoitteeseen . On tarpeen toistaa kaikki arvot . $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'$

Avaimen määritelmä

Kaikki mahdolliset on selvitetty . Vastaanotetuilla avaimilla salakirjoitus puretaan - . Jos osoite ei ole tyhjä, saamme sieltä avaimen ja saamme avainehdokkaan . $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$

On kuitenkin huomattava, että ensimmäinen vastaanottama ehdokas ei välttämättä ole oikea avain. Kyllä, datan ja , mutta todellisesta avaimesta saadun selkeän tekstin salatekstin muilla arvoilla tasa-arvo saattaa loukata. Kaikki riippuu kryptojärjestelmän erityisominaisuuksista . Mutta joskus riittää saada tällainen "pseudo-ekvivalentti" avain. Muuten toimenpiteiden suorittamisen jälkeen saadaan tietty joukko avaimia , joiden joukossa on todellinen avain. $k$ $a$ $b$ $E_{k}(a)=b$ $a'$ $b'$ $a'$ ${\näyttötyyli {k',k''...))$

Jos tarkastelemme tiettyä sovellusta, salateksti ja pelkkä teksti voivat olla suuria (esimerkiksi grafiikkatiedostot) ja edustaa riittävän suurta määrää lohkoja lohkosalaukselle . Tässä tapauksessa prosessin nopeuttamiseksi voit salata ja purkaa ei koko tekstiä, vaan vain sen ensimmäisen lohkon (joka on paljon nopeampi) ja sitten saatuaan useita ehdokkaita etsiä siitä todellista avainta ja tarkistaa se. loput lohkot.

Hyökkäys, jossa näppäinsarja jaetaan kolmeen osaan

Joissakin tapauksissa voi olla vaikeaa erottaa näppäinsarjan bittejä eri avaimiin liittyviin osiin. Tässä tapauksessa käytetään Bogdanovin ja Richbergerin vuonna 2011 ehdottamaa 3-osajoukon MITM-hyökkäysalgoritmia , joka perustuu tavanomaiseen tapaamismenetelmään keskellä. Tätä algoritmia voidaan soveltaa, kun avainbittisarjoja ei ole mahdollista jakaa kahteen itsenäiseen osaan. Se koostuu kahdesta vaiheesta: avainten poimiminen ja tarkistaminen [2] .

Avaimen purkuvaihe

Tämän vaiheen alussa salaus jaetaan 2 alisalaukseen ja , kuten hyökkäyksen yleisessä tapauksessa, kuitenkin mahdollistaa yhden alisalauksen joidenkin bittien käytön toisessa. Joten jos , niin ; tässä tapauksessa käytetyn avaimen bitit merkitään , ja in — . Sitten näppäinsarja voidaan jakaa kolmeen osaan: $f$ $g$ $b=E_{k}(a)$ $E_{k}(*)=f(g(*))$ $k$ $f$ ${\displaystyle k_{f))$ $g$ $k_{g}$

$A_0$ on joukkojen ja , ${\displaystyle k_{f))$ $k_{g}$
$A_{1}$ - avainbitit, jotka ovat vain , ${\displaystyle k_{f))$
$A_{2}$ - avainbitit, jotka ovat vain . $k_{g}$

Seuraavaksi hyökkäys suoritetaan tapaamismenetelmällä keskellä seuraavan algoritmin mukaisesti:

Jokaiselle elementille alkaen $A_0$

Laske väliarvo , jossa on selkeä teksti, ja ovat joitakin avainbittejä kohteesta ja , eli se on tulos avaimessa olevan selkeän tekstin välisalauksesta . $i=f(k_{f},a)$ $a$ ${\displaystyle k_{f))$ $A_0$ $A_{1}$ $i$ ${\displaystyle k_{f))$
Laske väliarvo , jossa on yksityinen teksti, ja ovat joitakin avainbittejä kohteesta ja , eli se on tulos avaimen yksityisen tekstin salauksen välipurkusta . $j=g^{-1}(k_{g},b)$ $b$ $k_{g}$ $A_0$ $A_{2}$ $j$ $k_{g}$
Vertaa ja . Ottelun sattuessa saamme ehdokkaan avaimiin. $i$ $j$

Avaimen validointivaihe

Avainten tarkistamiseksi vastaanotetut ehdokkaat verrataan useisiin tunnettuihin julkisen ja yksityisen tekstin pareihin. Yleensä varmentamiseen ei tarvita kovin suurta määrää tällaisia tekstipareja [2] .

Esimerkki

Otetaan esimerkkinä hyökkäys KTANTAN-salakirjoitusperheeseen [3] , joka mahdollisti avaimen saamisen laskennallisen monimutkaisuuden vähentämisen arvosta (raaka voimahyökkäys) arvoon [1] . $2^{80}$ $2^{75 170}$

Valmistellaan hyökkäystä

Jokainen KTANTANin 254 salauskierroksesta käyttää 2 satunnaista avaimen bittiä 80-bittisestä sarjasta. Tämä tekee algoritmin monimutkaisuudesta riippuvaiseksi vain kierrosten lukumäärästä. Aloittaessaan hyökkäyksen kirjoittajat huomasivat seuraavat ominaisuudet:

Kierroksilla 1-111 seuraavia avainbittejä ei käytetty: . ${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75))$
Kierroksilla 131-254 seuraavia avainbittejä ei käytetty: . ${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74))$

Tämä mahdollisti avainbittien jakamisen seuraaviin ryhmiin:

$A_0$ - yleiset avainbitit: ne 68 bittiä, joita ei mainita yllä.
$A_{1}$ - bitit, joita käytetään vain kierrosten ensimmäisessä lohkossa (1 - 111),
$A_{2}$ - bittejä käytetään vain kierrosten toisessa lohkossa (131 - 254).

Vaihe yksi: Avaimen purkaminen

Yllä kuvattujen ja arvojen laskemisessa oli ongelma , koska kierrokset 112:sta 130:een puuttuvat tarkastelusta, mutta sitten suoritettiin osittainen vertailu : hyökkäyksen tekijät huomasivat 8 bitin osuman. ja , tarkistamalla ne normaalilla hyökkäyksellä käyttämällä keskikokousmenetelmää kierroksella 127. Tältä osin tässä vaiheessa verrattiin näiden 8 bitin arvoja alikoodeissa ja . Tämä lisäsi keskeisten ehdokkaiden määrää, mutta ei laskennallista monimutkaisuutta. $i$ $j$ $i$ $j$ $i$ $j$

Toinen vaihe: avainten tarkistus

KTANTAN32-algoritmin avainehdokkaiden testaamiseksi kesti keskimäärin kaksi julkisen ja yksityisen sektorin tekstiparia lisää avaimen purkamiseen.

Tulokset

KTANTAN32: Avainarvauksen laskennallinen monimutkaisuus on vähennetty kolmen julkisen ja yksityisen tekstiparin käyttämiseen. $2^{75 170}$
KTANTAN48: Avain arvauksen laskennallinen monimutkaisuus on vähennetty kahden julkisen ja yksityisen tekstiparin käyttämiseen. $2^{75 044}$
KTANTAN64: Avain arvauksen laskennallinen monimutkaisuus on vähennetty kahden julkisen ja yksityisen tekstiparin käyttämiseen. $2^{75,584}$

Tämä ei kuitenkaan ole paras hyökkäys KTANTANin salausperhettä vastaan. Vuonna 2011 tehtiin hyökkäys [4] , joka vähensi algoritmin laskennallisen monimutkaisuuden käyttämään neljää avointa-suljettua tekstiparia. $2^{72.9}$

Hyökkäys täydelliseen kaksiosaiseen kaavioon

Täysin kaksiosaisen graafin hyökkäystä käytetään lisäämään välityspalvelinhyökkäysyritysten määrää rakentamalla täysi kaksiosainen kaavio . Diffien ja Hellmanin ehdottama vuonna 1977.

Monimuuttujaalgoritmi

Moniulotteista keskikokous-algoritmia käytetään, kun käytetään suurta määrää salausjaksoja eri avaimilla lohkosalauksissa . Tavallisen "kokouksen keskellä" sijaan tämä algoritmi käyttää kryptotekstin jakamista useilla välipisteillä [5] .

Oletetaan, että hyökkäyksen kohteena oleva teksti on salattu tietyn määrän kertoja lohkosalauksella:

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

Algoritmi

Laskettu:

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

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

sC_{1}

tallennetaan yhdessä d :n kanssa .

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}

tallennetaan yhdessä d :n kanssa .

k_{b_{n+1))

H_{b_{n+1))

Laske jokaiselle mahdolliselle välitilalle : $s_{1}$

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

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

jokaiselle ottelulle , jossa on elementti välillä - , ja tallennetaan .

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}

tallennettu sisään .

k_{f_{2))

H_2

Laske jokaiselle mahdolliselle välitilalle : $s_{2}$

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

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

jokaiselle osumalle elementin kanssa osoitteesta tarkistetaan , minkä jälkeen ja tallennetaan kohtaan .

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}

tallennettu sisään .

k_{f_{3))

H_3

Laske jokaiselle mahdolliselle välitilalle : $s_{n}$

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

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

ja jokaiselle osumalle elementin kanssa osoitteesta tarkistetaan , minkä jälkeen ja tallennetaan tiedostoon .

sC_{n}

H n

{\displaystyle 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

ja jokaisesta ottelusta , ottelun kanssa

sC_{n+1}

H_{n+1}

T_{n}

Seuraavaksi löydettyä ehdokkaiden sarjaa testataan toisella julkisen ja yksityisen tekstin parilla avainten oikeellisuuden varmistamiseksi. On huomattava, että algoritmi on rekursiivinen: tilan avainten valinta perustuu tilan tuloksiin . Tämä tuo tähän algoritmiin eksponentiaalisen monimutkaisen elementin [5] . $s_{j}$ $s_{j-1}$

Vaikeus

Tämän hyökkäyksen aika monimutkaisuus on $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}}|}+...))$

Muistin käytöstä puheen ollen on helppo nähdä, että jokaisen kasvaessa rajoituksia asetetaan yhä enemmän, mikä vähentää siihen kirjoitettavien ehdokkaiden määrää. Tämä tarkoittaa paljon vähemmän . $i$ $T_{i}$ ${\displaystyle T_{2},T_{3},...,T_{n))$ $T_{1}$

Käytetyn muistin määrän yläraja:

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

missä on avaimen kokonaispituus.

k

Tietojen käytön monimutkaisuus riippuu väärän avaimen "läpäisemisen" todennäköisyydestä. Tämä todennäköisyys on yhtä suuri kuin , jossa on ensimmäisen välitilan pituus, joka on useimmiten yhtä suuri kuin lohkon koko. Kun otetaan huomioon avainehdokkaiden määrä ensimmäisen vaiheen jälkeen, monimutkaisuus on . ${\näyttötyyli 1/2^{l))$ $l$ $2^{|k|-|l|}$

Tuloksena saamme , missä on lohkon koko. ${\näyttötyyli 2^{|k|-2b))$ $|b|$

Joka kerta kun ehdokasavainsarja testataan uudella julkisen ja yksityisen sektorin tekstiparilla, testin läpäisevien avainten määrä kerrotaan avaimen läpäisyn todennäköisyydellä, joka on . $1/2^{|b|}$

Osa raa'an voiman hyökkäyksestä (avainten tarkistaminen uusia julkisen ja yksityisen sektorin tekstipareja vastaan) on ajallisesti monimutkainen , jossa myöhemmillä termeillä on luonnollisesti tapana nollata nopeammin ja nopeammin. $2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+...$

Tämän seurauksena tietojen monimutkaisuus on samanlaisten arvioiden mukaan rajoitettu noin julkisen ja yksityisen sektorin avainpareihin. $\left\lceil |k|/n\right\rceil$

Muistiinpanot

↑ 12 Diffie , Whitfield; Hellman, Martin E. NBS Data Encryption Standardin kattava salausanalyysi (englanti) // Computer : Journal. - 1977. - Kesäkuu ( osa 10 , nro 6 ). - s. 74-84 . - doi : 10.1109/CM.1977.217750 . Arkistoitu alkuperäisestä 14. toukokuuta 2009.
↑ 1 2 Andrey Bogdanov ja Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN" Arkistoitu 7. marraskuuta 2018 Wayback Machinessa
↑ Christophe De Cannière, Orr Dunkelman, Miroslav Knežević. "KATAN & KTANTAN – Pienten ja tehokkaiden laitteistolähtöisten lohkosalausten perhe" Arkistoitu 20. huhtikuuta 2018 Wayback Machinessa
↑ Lei Wei, Christian Rechberger, Jian Guo, Hongjun Wu, Huaxiong Wang ja San Ling. "KTANTANin parannettu Meet-in-the-Middle Cryptanalysis" Arkistoitu 7. marraskuuta 2018 Wayback Machinessa
↑ 1 2 3 Zhu, Bo; Guang Gong. MD-MITM Attack ja sen sovellukset GOST:iin, KTANTANiin ja Hummingbird-2 :een (englanniksi) // eCrypt : Journal. – 2011.

Kirjallisuus

Moore, Stephane. Meet-in-the-Middle Attacks (uuspr.) . - 2010 - 16. marraskuuta. - S. 2 .