Meet-in-the-middle-angrep

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Meet-in-the-middle-angrep er et kryptografisk angrep som, tilsvarende bursdagsangrep, bruker en rom-tid avveiing. Mens bursdagsangrep forsøker å finne to verdier innen domenet til en funksjon som peker mot den samme veriden innen sitt område, så forsøker meet-in-the-middle-angrepet å finne en verdi i hvert av områdene og domenene som er bygget opp av to funksjoner, slik at resultatet av den første funksjonen vil være det samme som den reverserte funksjonen av det andre området. Bokstavlig talt så møtes man på midten.

Metoden ble i utgangspunktet utviklet for å angripe et forsøk på å utvide et blokkchiffer laget av Diffie og Hellman i 1977. For å forsøke å forbedre sikkerheten i et blokkchiffer så kan man få den enkle ideen å bruke to uavhengige krypteringsnøkler for å kryptere data dobbelt. Man vil i sin naive tenkemåte tro at dette ville øke antall nøkler med kvadratet av antall bits. Det er sikkert at et søk gjennom alle mulige kombinasjoner av nøkler ville ta 2^{2n} forsøk hvis hver nøkkel er n bits lang, sammenlignet med 2^n forsøk som er påkrevet ved en enkel nøkkel.

Diffie og Hellmann derimot, laget en tid-hukommelse avveiing som kunne knekke dette systemet ved å kun doble tiden som brukes på å knekke et ett-nøkkels system[1]. Angrepet virker på den måten at man krypterer fra den ene enden, og dekrypterer fra den andre, og møtes derved på midten.

Gå ut fra at en angriper kjenner ett sett med klartekst og chiffertekst: P og C. Det vil si


  C=E_{K_2}(E_{K_1}(P))
  ,

hvor K1 og K2 er de to nøklene.

Angriperen kan derfor beregne EK(P) for alle mulige nøkler K og lagre resultatet i hukommelsen. Deretter kan han beregne DK(C) for alle K og sammenligne med tabellen i hukommelsen. Om han får et sammenfallende resultat, så er det sannsynlig at han har oppdaget de to nøklene som har vært i bruk, og han kan verifisere dette med en nytt sett med klartekst og chiffertekst. Om nøkkelstørrelsen er n, så bruker dette angrepet kun 2^{n+1} krypteringer (og O(2^n) hukommelse) i sterk kontrast til det naive angrepet som trenger 2^{2n} krypteringer (men kun O(1) hukommelse).

Se også[rediger | rediger kilde]

Referanser[rediger | rediger kilde]

  1. [2] W. Diffie and M. E. Hellman (juni 1977). «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer, 10 (6), s. 74-84.