Redigerer Meet-in-the-middle-angrep

'''Meet-in-the-middle-angrep''' er et [[kryptografi]]sk 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 [[Whitfield Diffie|Diffie]] og [[Martin Hellman|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 [[bit]]s. Det er sikkert at et søk gjennom alle mulige kombinasjoner av nøkler ville ta <math>2^{2n}</math> forsøk hvis hver nøkkel er n [[bit]]s lang, sammenlignet med <math>2^n</math> 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.<ref>{{cite journal
| author=W. Diffie and M. E. Hellman
| date=juni 1977
| title=Exhaustive Cryptanalysis of the NBS Data Encryption Standard
| journal=Computer
| volume=10
| issue=6
| pages=74-84
}}</ref> 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 et sett med klartekst og chiffertekst: ''P'' og ''C''. Det vil si
: <math>
  C=E_{K_2}(E_{K_1}(P))
  </math>,
hvor ''K''<sub>1</sub> og ''K''<sub>2</sub> er de to nøklene.

Angriperen kan derfor beregne ''E<sub>K</sub>''(''P'') for alle mulige nøkler ''K'' og lagre resultatet i hukommelsen. Deretter kan han beregne ''D<sub>K</sub>''(''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 et nytt sett med klartekst og chiffertekst. Om nøkkelstørrelsen er ''n'', så bruker dette angrepet kun <math>2^{n+1}</math> krypteringer (og <math>O(2^n)</math> hukommelse) i sterk kontrast til det naive angrepet som trenger <math>2^{2n}</math> krypteringer (men kun <math>O(1)</math> hukommelse).

==Se også==
*[[bursdagsangrep]]
*[[Trippel DES]]

== Referanser ==
<references />

{{Autoritetsdata}}

[[Kategori:Kryptografiske algoritmer]]