Kriptoanalízis - Cryptanalysis

Közeli kép a rotorokról Fialka titkosítógépben

A kriptoanalízis (a görög kriptósból "rejtett" és analýein , "elemezni") az információs rendszerek elemzésének folyamatára utal, hogy megértse a rendszerek rejtett aspektusait. A kriptoanalízist arra használják, hogy feltörjék a kriptográfiai biztonsági rendszereket, és hozzáférjenek a titkosított üzenetek tartalmához , még akkor is, ha a titkosítási kulcs ismeretlen.

A kriptográfiai algoritmusok matematikai elemzése mellett a kriptoanalízis olyan mellékcsatornás támadások tanulmányozását is magában foglalja , amelyek nem a titkosítási algoritmusok gyengeségeit célozzák meg, hanem a megvalósítás gyengeségeit használják ki.

Annak ellenére, hogy a cél ugyanaz volt, a kriptoanalízis módszerei és technikái drasztikusan megváltoztak a kriptográfia történetében, alkalmazkodva a növekvő titkosítási komplexitáshoz, kezdve a múltkori toll-papír módszerektől kezdve, olyan gépeken keresztül, mint a brit bombák és Colossus számítógépek a Bletchley Parkban a második világháborúban , a jelen matematikailag fejlett számítógépes rendszereihez. A modern rejtjelezési rendszerek megtörésének módszerei gyakran magukban foglalják a tiszta matematika gondosan felépített feladatainak megoldását , a legismertebb az egész faktorizálás .

Áttekintés

Adott egy titkosított adatokat ( rejtjelezett ), a cél a cryptanalyst , hogy szert a lehető legtöbb információt a helyzet az eredeti, nem titkosított adatok ( nyílt szöveg ). A kriptográfiai támadásokat többféleképpen lehet jellemezni:

A támadó rendelkezésére álló információmennyiség

A támadások osztályozhatók aszerint, hogy a támadó milyen típusú információval rendelkezik. Alapvető kiindulópontként általában azt feltételezik, hogy elemzés céljából az általános algoritmus ismert; ez Shannon Maximja "az ellenség ismeri a rendszert" - ezzel egyenértékű Kerckhoffs elvével . Ez a gyakorlatban ésszerű feltételezés - a történelem folyamán számtalan példa van arra, hogy a titkos algoritmusok szélesebb körű ismeretekbe kerülnek, különböző módon kémkedés , árulás és fordított tervezés révén . (És alkalmanként a titkosításokat törték le tiszta levonással; például a német Lorenz -kód és a japán lila kód , valamint számos klasszikus séma):

Számítási erőforrások szükségesek

A támadásokat az általuk igényelt erőforrásokkal is lehet jellemezni. Ezek az erőforrások a következők:

  • Idő - a végrehajtandó számítási lépések száma (pl. Teszt titkosítás).
  • Memória - a támadás végrehajtásához szükséges tárhely .
  • Adatok - az adott megközelítéshez szükséges közértmények és rejtett szövegek mennyisége és típusa .

Néha nehéz pontosan megjósolni ezeket a mennyiségeket, különösen akkor, ha a támadást nem praktikus megvalósítani tesztelésre. De az akadémiai kriptoanalitikusok hajlamosak legalább a támadásuk nehézségeinek becsült nagyságrendjét megadni , mondván például: "SHA-1 ütközések most 2 52 ".

Bruce Schneier megjegyzi, hogy még a számítástechnikailag nem praktikus támadások is töréseknek tekinthetők: "A rejtjelezés megszakítása egyszerűen azt jelenti, hogy olyan gyengeséget találunk a rejtjelezésben, amelyet a nyers erőnél kisebb bonyolultsággal ki lehet használni. Ne feledje, hogy a nyers erő 2 128 titkosítást igényelhet ; a 2 110 titkosítást igénylő támadás törésnek minősülne ... egyszerűen fogalmazva, a szünet csak tanúsítási gyengeség lehet: bizonyíték arra, hogy a titkosítás nem úgy működik, ahogy hirdették. "

Részleges szünetek

A kriptoanalízis eredményei hasznosságban is változhatnak. Például Lars Knudsen (1998) rejtjelező különböző típusú támadásokat osztályozott a titkosított kódok ellen a feltárt titkos információk mennyisége és minősége szerint:

  • Teljes szünet - a támadó levezeti a titkos kulcsot .
  • Globális dedukció - a támadó egy funkcionálisan egyenértékű algoritmust fedez fel a titkosításhoz és a visszafejtéshez, de a kulcs megtanulása nélkül.
  • Példányi (helyi) levonás - a támadó további, korábban nem ismert egyszerű szövegeket (vagy rejtett szövegeket) fedez fel.
  • Információlevonás - a támadó néhány Shannon -információt szerez a korábban nem ismert egyszerű szövegekről (vagy rejtett szövegekről).
  • Megkülönböztető algoritmus - a támadó meg tudja különböztetni a titkosítást a véletlenszerű permutációtól .

Az akadémiai támadások gyakran a titkosított rendszer gyengített verziói ellen irányulnak, mint például a blokk -titkosítás vagy a hash -függvény, néhány kör eltávolításával. Sok, de nem minden támadás exponenciálisan nehezebben kivitelezhető, mivel köröket adnak hozzá egy kriptorendszerhez, így lehetséges, hogy a teljes titkosítási rendszer erős lesz, még akkor is, ha a csökkentett körű változatok gyengék. Mindazonáltal a részleges szünetek, amelyek közel járnak az eredeti titkosítási rendszer megtöréséhez, azt jelenthetik, hogy teljes szünet következik; a DES , MD5 és SHA-1 elleni sikeres támadásokat mind a gyengített verziók elleni támadások előzték meg.

Az akadémiai kriptográfiában a rendszer gyengeségét vagy megszakítását általában meglehetősen konzervatív módon határozzák meg: ez nem praktikus időt, memóriát vagy ismert közértményeket igényelhet. Ez azt is megkövetelheti, hogy a támadó olyan dolgokat tegyen, amelyeket sok valós támadó nem tud: például előfordulhat, hogy a támadónak ki kell választania bizonyos szöveges titkosítandó szövegeket, vagy akár kérnie kell az egyszerű szövegek titkosítását több, a titokkal kapcsolatos kulccsal. kulcs. Ezenkívül csak kis mennyiségű információt tárhat fel, elég ahhoz, hogy bizonyítsa a rejtjelezési rendszer tökéletlenségét, de túl kevés ahhoz, hogy hasznos legyen a valós támadók számára. Végül a támadás csak a kriptográfiai eszközök gyengített verziójára vonatkozhat, mint például a csökkentett körű blokkoló titkosítás, a teljes rendszer megszakítása felé tett lépésként.

Történelem

A kriptoanalízis együtt fejlődött a kriptográfiával, és a verseny nyomon követhető a kriptográfia történetében - az új rejtjeleket a régi törött minták helyettesítésére tervezték, és az új rejtjelezési technikákat a javított sémák feltörésére találták fel. A gyakorlatban ugyanazon érem két oldalának tekintik őket: a biztonságos kriptográfia tervezést igényel az esetleges kriptoanalízis ellen.

Klasszikus rejtjelek

Al-Kindi 9. századi kéziratának első oldala a kriptográfiai üzenetek megfejtéséről

Bár a tényleges szó „ rejtjelelemzés ” viszonylag friss (ez alkotta William Friedman 1920), módszerei törés kódok és titkosírás sokkal idősebb. David Kahn a The Codebreakers című könyvben megjegyzi, hogy az arab tudósok voltak az első emberek, akik szisztematikusan dokumentálták a kriptoanalitikus módszereket.

A kriptanalízis első ismert feljegyzett magyarázatát Al-Kindi (kb. 801–873, más néven „Alkindus” Európában), a 9. századi arab polihisztor adta a Risalah fi Istikhraj al-Mu'amma ( A Manuscript on Kriptográfiai üzenetek megfejtése ). Ez az értekezés tartalmazza a frekvenciaanalízis módszerének első leírását . Az Al-Kindit tehát a történelem első kódtörőjének tekintik. Áttörő munkáját Al-Khalil (717–786) befolyásolta , aki megírta a Kriptográfiai üzenetek könyvét , amely a permutációk és kombinációk első használatát tartalmazza, hogy felsorolja az összes lehetséges arab szót magánhangzókkal és anélkül.

A frekvenciaanalízis az alapvető eszköz a legtöbb klasszikus titkosítás megtörésére . A természetes nyelvekben az ábécé egyes betűi gyakrabban jelennek meg, mint mások; A angol , „ E ” valószínűleg a leggyakoribb betű bármely mintájában szövegként . Hasonlóképpen, a "TH" digraph a legvalószínűbb betűpár angolul stb. A gyakorisági elemzés egy olyan titkosításon alapul, amely nem tudja elrejteni ezeket a statisztikákat . Például egy egyszerű helyettesítő rejtjelezésben (ahol minden betűt egyszerűen lecserélnek egy másikra) a titkosított szöveg leggyakoribb betűje valószínűleg az "E" jelöltje lenne. Az ilyen titkosítási gyakoriság elemzése ezért viszonylag egyszerű, feltéve, hogy a titkosított szöveg elég hosszú ahhoz, hogy ésszerűen reprezentatív számot adjon a benne lévő ábécé betűiről.

Al-Kindi feltalálta a frekvenciaanalízis technikáját a monoalfabetikus helyettesítési kódok megtörésére, és ez volt a legjelentősebb rejtjelezési előrelépés a második világháborúig. Al-Kindi Risalah fi Istikhraj al-Mu'amma leírta az első kriptoanalitikus technikákat, köztük néhányat a polialfabetikus kódok , a rejtjelezés osztályozása, az arab fonetika és a szintaxis számára, és ami a legfontosabb, megadta az első leírásokat a gyakorisági elemzésről. Kitért továbbá a titkosítás módszereire, egyes kódolások kriptoanalízisére, valamint arab betűk és betűkombinációk statisztikai elemzésére . Ibn Adlan (1187–1268) fontos hozzájárulása volt a gyakorisági elemzéshez használt minta méretéhez .

Európában Giambattista della Porta (1535-1615) olasz tudós volt a kriptanalízisről szóló alapvető munka, a De Furtivis Literarum Notis szerzője .

A sikeres kriptoanalízis kétségtelenül befolyásolta a történelmet; döntő előny lehet a mások feltételezett titkos gondolatainak és terveinek olvasása. Például Angliában 1587 -ben Máriát, a skót királynőt árulás miatt bíróság elé állították és kivégezték, mivel három cselekményben részt vett az I. Erzsébet meggyilkolása érdekében . A tervekre azután derült fény, hogy Thomas Phelippes megfejtette az összeesküvőtársaival folytatott kódolt levelezését .

Európában a 15. és 16. században a többalfabetikus helyettesítési kód ötletét fejlesztette ki, többek között Blaise de Vigenère francia diplomata (1523–96). Körülbelül három évszázadon keresztül a Vigenère -titkosítást , amely ismétlődő kulccsal választja ki a különböző titkosítási ábécéket forgásban, teljesen biztonságosnak tartották ( le chiffre indéchiffrable - "a megfejthetetlen titkosítás"). Ennek ellenére Charles Babbage -nek (1791–1871) és később, önállóan, Friedrich Kasiskinak (1805–81) sikerült megtörnie ezt a kódot. Alatt az I. világháború , a feltalálók több országban kifejlesztett rotor titkosító gépek , mint például Arthur Scherbius " Enigma , arra törekszik, hogy minimalizálja az ismétlés, hogy már kihasználva, hogy megtörjük a Vigenère rendszert.

Az első és a második világháború titkosításai

A visszafejtett Zimmermann -távirat .

Az első világháborúban a Zimmermann -távirat megtörése fontos szerepet játszott abban, hogy az Egyesült Államokat bevonják a háborúba. A második világháborúban a szövetségesek óriási hasznot húztak a német rejtjeleket-köztük az Enigma gépet és a Lorenz rejtjeleket- és a japán kódokat, különösen a „Purple” és a JN-25 közös kriptanalíziséből . Az „ultra” hírszerzésnek mindent tulajdonítottak az európai háború végének legfeljebb két évvel történő lerövidítése és az esetleges eredmény meghatározása között. A csendes -óceáni háborút hasonlóan segítette a „mágikus” hírszerzés.

Az ellenséges üzenetek rejtjelezése jelentős szerepet játszott a szövetségesek második világháborús győzelmében. FW Winterbotham , a háború végén idézte a nyugati szövetségesek legfőbb parancsnokát, Dwight D. Eisenhower -t, aki szerint az Ultra intelligencia "döntő" volt a szövetségesek győzelméhez. Sir Harry Hinsley , a brit hírszerzés hivatalos történésze a második világháborúban hasonlóan értékelte az Ultra -t, mondván, hogy ez "nem kevesebb, mint két évvel és valószínűleg négy évvel" lerövidítette a háborút; ráadásul azt mondta, hogy Ultra hiányában bizonytalan, hogyan végződött volna a háború.

A gyakorlatban a frekvenciaanalízis ugyanúgy a nyelvi ismeretekre támaszkodik, mint a statisztikákra, de ahogy a rejtjelek egyre összetettebbek lettek , a matematika egyre fontosabbá vált a kriptoanalízisben. Ez a változás különösen nyilvánvaló volt a második világháború előtt és alatt , amikor a tengelykódok feltörésére irányuló erőfeszítések új szintű matematikai kifinomultságot igényeltek. Ezenkívül az automatizálást először abban a korban alkalmazták a kriptoanalízisre a lengyel Bomba készülékkel, a brit Bombéval , lyukkártya -berendezések használatával, és a Colossus számítógépekben - az első elektronikus digitális számítógépen, amelyet egy program vezérel.

Indikátor

A kölcsönös gép titkosírás, mint a Lorenz titkosító és az Enigma által használt náci Németország idején a második világháború , minden egyes üzenet volt saját kulcsa. Általában az átvivő operátor tájékoztatta a fogadó operátort erről az üzenetkulcsról úgy, hogy néhány egyszerű szöveget és/vagy titkosított szöveget továbbított a titkosított üzenet előtt. Ezt jelzőnek nevezik , mivel ez jelzi a fogadó kezelőnek, hogyan kell beállítani a gépét az üzenet megfejtésére.

A rosszul megtervezett és megvalósított indikátorrendszerek lehetővé tették először a lengyel , majd a Bletchley Park brit titkosítóinak, hogy megtörjék az Enigma titkosítási rendszert. Hasonló gyenge indikátorrendszerek lehetővé tették a britek számára, hogy azonosítsák azokat a mélységeket, amelyek a Lorenz SZ40/42 titkosítási rendszer diagnosztizálásához és az üzenetek átfogó megtöréséhez vezettek anélkül, hogy a titkosító elemzők látnák a titkosítógépet.

Mélység

Két vagy több üzenet küldése ugyanazzal a kulccsal nem biztonságos folyamat. A kriptoanalitikusok szerint az üzenetek "mélyrehatóak". Ezt észlelhetik azok az üzenetek, amelyek azonos jelzővel rendelkeznek , amellyel a küldő operátor tájékoztatja a fogadó operátort az üzenet kulcsgenerátorának kezdeti beállításairól .

Általában a rejtjelező profitálhat abból, ha azonos titkosítási műveleteket sorakoztat fel egy üzenethalmaz között. Például a Vernam titkosító kódolás bitről bitre egyesíti az egyszerű szöveget egy hosszú kulccsal az " exkluzív vagy " operátor használatával, amelyet " modulo-2 összeadás " -nak is neveznek (⊕ szimbólum):

Sima szöveg ⊕ Kulcs = Titkosított szöveg

A megfejtés ugyanazokat a kulcsbiteket egyesíti a titkosított szöveggel az egyszerű szöveg rekonstruálásához:

Titkosított szöveg ⊕ Kulcs = Sima szöveg

(A modulo-2 aritmetikában az összeadás megegyezik a kivonással.) Ha két ilyen rejtjelezett szöveg mélyen igazodik egymáshoz, akkor ezek kombinálása megszünteti a közös kulcsot, és csak a két közérthető szöveg kombinációja marad:

Ciphertext1 ⊕ Ciphertext2 = Plaintext1 ⊕ Plaintext2

Az egyes egyszerű szövegeket ezután nyelvileg ki lehet dolgozni úgy, hogy különböző helyeken kipróbálnak valószínű szavakat (vagy kifejezéseket), más néven "kiságyakat" ; a helyes találgatás az egyesített egyszerű szövegárammal kombinálva érthető szöveget eredményez a másik egyszerű szövegösszetevőből:

(Egyszerű szöveg1, egyszerű szöveg2) ⊕ egyszerű szöveg1 = egyszerű szöveg2

A második egyszerű szöveg visszanyert töredéke gyakran kibővíthető egyik vagy mindkét irányban, és az extra karakterek kombinálhatók az egyesített egyszerű szövegárammal az első egyszerű szöveg kiterjesztéséhez. A két egyszerű szöveg között oda -vissza dolgozva, az érthetőség kritériumát használva a találgatások ellenőrzésére, az elemző visszanyerheti az eredeti szövegek nagy részét vagy egészét. (Ha csak két közérthető szöveggel rendelkezik, az elemző nem tudja, hogy melyik melyik titkosított szövegnek felel meg, de a gyakorlatban ez nem jelent nagy problémát.) Amikor egy visszanyert egyszerű szöveget ezután kombinálnak a titkos szövegével, kiderül a kulcs:

Sima szöveg1 ⊕ Ciphertext1 = Kulcs

A kulcs ismerete ezután lehetővé teszi az elemző számára, hogy más, ugyanazzal a kulccsal titkosított üzeneteket olvasson, a kapcsolódó kulcsok halmazának ismerete pedig lehetővé teheti a titkosítási elemzők számára, hogy diagnosztizálják a létrehozásukhoz használt rendszert.

A modern kriptográfia fejlesztése

A kormányok régóta felismerték a rejtjelezés potenciális előnyeit a katonai és diplomáciai hírszerzés számára , és elkötelezett szervezeteket hoztak létre, amelyek más nemzetek kódjainak és rejtjeleinek megtörésére szolgálnak, például a GCHQ és az NSA , amelyek ma is nagyon aktívak.

A Bombe megismételte több Enigma gép összekapcsolását. A Bletchley Park múzeumi makettjén a gyorsan forgó dobok mindegyike szimulálta az Enigma forgórész működését.

Annak ellenére, hogy számítást használjuk, hogy nagy hatással a rejtjelelemzés a Lorenz titkosító és más rendszerek a második világháború idején, azt is lehetővé tette új módszerek a kriptográfia nagyságrendekkel bonyolultabb, mint valaha. Összességében a modern kriptográfia sokkal áthatolhatatlanabbá vált a kriptoanalízis számára, mint a múltkori toll-papír rendszerek, és most úgy tűnik, fölényben van a tiszta kriptoanalízissel szemben. David Kahn történész megjegyzi:

Sok olyan kriptorendszer létezik, amelyet ma több száz kereskedelmi forgalmazó kínál, és amelyeket egyetlen ismert kriptoanalízis sem tud megtörni. Valóban, az ilyen rendszerekben még egy kiválasztott nyílt szövegű támadás sem , amelyben a kiválasztott egyszerű szöveg a titkosított szöveggel párosul, nem adhatja meg azt a kulcsot, amely feloldja a többi üzenetet. Bizonyos értelemben tehát a kriptoanalízis halott. De ezzel még nincs vége a történetnek. A kriptoanalízis halott lehet, de - a metaforáim összekeveredése érdekében - több módja is van a macska bőrének.

Kahn megemlíti az elfogás, a hibakeresés , az oldalsó csatorna támadások és a kvantumszámítógépek megnövekedett lehetőségeit a kriptoanalízis hagyományos eszközeinek helyettesítéseként. 2010 -ben az NSA korábbi technikai igazgatója, Brian Snow azt mondta, hogy mind az akadémiai, mind a kormányzati titkosító "nagyon lassan halad előre egy érett területen".

Mindazonáltal a kriptoanalízis utáni halála korai lehet. Míg a hírszerző ügynökségek által alkalmazott kriptoanalitikus módszerek hatékonysága továbbra sem ismert, a számítógépes kriptográfia modern korában számos komoly támadást publikáltak mind az akadémiai, mind a gyakorlati kriptográfiai primitívek ellen:

Így, bár a legjobb modern kódolók sokkal ellenállóbbak lehetnek a kriptoanalízissel szemben, mint az Enigma , a kriptoanalízis és az információbiztonság szélesebb területe továbbra is igen aktív.

Szimmetrikus kódok

Aszimmetrikus kódok

Az aszimmetrikus kriptográfia (vagy nyilvános kulcsú titkosítás ) olyan titkosítás, amely két (matematikailag kapcsolódó) kulcs használatán alapul; egy privát és egy nyilvános. Az ilyen titkosítások mindig "kemény" matematikai problémákra támaszkodnak biztonságuk alapjaként, ezért nyilvánvaló támadási pont a probléma megoldására szolgáló módszerek kidolgozása. A kétkulcsos kriptográfia biztonsága a matematikai kérdéseken múlik, ahogyan az egykulcsos titkosítás általában nem, és fordítva kapcsolja össze a rejtjelezést a szélesebb körű matematikai kutatásokkal.

Az aszimmetrikus sémákat különböző matematikai feladatok megoldásának (feltételezett) nehézségei körül tervezték. Ha javított algoritmus található a probléma megoldására, akkor a rendszer gyengül. Például a Diffie – Hellman kulcscsere -rendszer biztonsága a diszkrét logaritmus kiszámításának nehézségétől függ . 1983 -ban Don Coppersmith gyorsabb módszert talált a diszkrét logaritmusok megtalálására (bizonyos csoportokban), és ezáltal megkövetelte a titkosítóktól, hogy nagyobb csoportokat (vagy különböző típusú csoportokat) használjanak. Az RSA biztonsága (részben) az egész faktorálás nehézségein múlik - a faktoring áttörése hatással lenne az RSA biztonságára.

1980-ban egy nehéz, 50 számjegyű számadatot lehetett számítani 10 12 elemi számítógépes művelet rovására . 1984-re a faktorálási algoritmusok korszerűsége elérte azt a szintet, hogy egy 75 számjegyű számot 10 12 műveletben lehetett figyelembe venni . A számítástechnika fejlődése azt is jelentette, hogy a műveleteket sokkal gyorsabban is el lehetett végezni. Moore törvénye szerint a számítógépek sebessége tovább fog növekedni. A faktoring technikák továbbra is ezt teszik, de nagy valószínűséggel a matematikai éleslátástól és a kreativitástól függenek, amelyek közül egyik sem volt soha sikeresen megjósolható. Az RSA-ban használt 150 számjegyű számokat figyelembe vették. Az erőfeszítés nagyobb volt, mint fent, de nem volt ésszerűtlen a gyors, modern számítógépeken. A 21. század elejére a 150 jegyű számokat már nem tartották elég nagy kulcsméretnek az RSA számára. A több száz számjegyű számokat 2005 -ben még mindig túl nehéz volt figyelembe venni, bár a módszerek valószínűleg tovább fognak javulni az idő múlásával, és megkövetelik a kulcsméretet, hogy lépést tartsanak, vagy más módszereket, például az elliptikus görbe titkosítást kell használni.

Az aszimmetrikus sémák másik megkülönböztető jellemzője, hogy a szimmetrikus rejtjelezési rendszerek elleni támadásokkal ellentétben minden kriptoanalízisnek lehetősége van a nyilvános kulcsból szerzett ismeretek hasznosítására .

Kriptográfiai hash rendszerek támadása

Oldalcsatornás támadások

Kvantumszámítási alkalmazások kriptoanalízishez

A kvantumszámítógépek , amelyek még a kutatás korai szakaszában vannak, potenciálisan használhatók a kriptoanalízisben. Például Shor algoritmusa nagy számokat vehet figyelembe polinomiális időben , gyakorlatilag megtörve a nyilvános kulcsú titkosítás néhány általánosan használt formáját.

Segítségével Grover-algoritmus egy kvantum számítógép, brute-force legfontosabb keresési tehető négyzetesen gyorsabb. Ezt azonban a kulcshossz megduplázásával lehet ellensúlyozni.

Lásd még

Történelmi kriptoanalitikusok

Hivatkozások

Idézetek

Források

További irodalom

Külső linkek