Nyers erő

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 16-án felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

Teljes felsorolás (vagy "brute force" módszer , eng. brute force ) - matematikai problémák megoldásának módszere . Az összes lehetséges opció kimerítésével megoldást találó módszerek osztályára utal . A kimerítő keresés összetettsége a probléma összes lehetséges megoldásának számától függ. Ha a megoldási tér nagyon nagy, akkor előfordulhat, hogy a kimerítő keresés évekig vagy akár évszázadokig nem hoz eredményt.

Az NP osztály bármely problémája kimerítő kereséssel megoldható. Ugyanakkor, még ha a célfüggvény kiszámítása a probléma egyes lehetséges megoldásaiból polinomiális időben is elvégezhető, az összes lehetséges megoldás számától függően a kimerítő felsorolás exponenciális futási időt igényelhet.

A kriptográfiában a kimerítő keresés számítási bonyolultságát használják a rejtjelek kriptográfiai erősségének becslésére . A titkosítást különösen akkor mondják biztonságosnak, ha nincs a brute-force keresésnél lényegesen gyorsabb "feltörő" módszer . A brute-force kriptográfiai támadások a legsokoldalúbbak, de egyben a leghosszabbak is.

Kimerítési módszer

Terminológia

Angolul az ebben a cikkben tárgyalt " brute-force " kifejezés általában a hackertámadások egy osztályára utal . Ugyanakkor egy általánosabb fogalom, egy matematikai módszer a probléma megoldásának minden lehetséges lehetőségének kimerítésére, megfelel a " Bizonyítás kimerítéssel " kifejezésnek.

Leírás

A „kimerítési módszer” különféle módszerek egész osztályát foglalja magában. Általában a problémafelvetés magában foglalja egy adott logikai rendszer véges számú állapotának figyelembevételét annak érdekében, hogy egy logikai állítás igazságát az egyes állapotok független elemzésével azonosítsuk [1] . Az állítás bizonyításának módja két részből áll:

A rendszer összes állapotának kimeríthetőségének bizonyítása. Meg kell mutatni, hogy a rendszer bármely konkrét állapota (például a bizonyított logikai kifejezés értéke) megfelel-e legalább egy lehetséges megoldásnak.
Minden opció ellenőrzése és annak bizonyítása, hogy a szóban forgó lehetőség megoldást jelent-e a problémára.

Kimerítő felsorolással megoldott tipikus problémák

Bár a gyakorlatban a kimerítő keresést nem alkalmazzák a legtöbb alkalmazott problémában (különösen nem a titkosítások feltörésével kapcsolatban), számos kivétel létezik. Különösen, ha a kimerítő keresés mégis optimálisnak bizonyul, vagy egy algoritmus kidolgozásának kezdeti szakaszát jelenti, annak használata indokolt. A kimerítő keresés optimumára példa a mátrixok láncszorzatainak számítási idejét becsülő algoritmus, amely a "brute force" módszeren alapuló algoritmushoz képest nem gyorsítható [2] . Ez az algoritmus a dinamikus programozás klasszikus problémájának megoldására szolgál - a következő formájú mátrixszorzatok számítási prioritásainak meghatározása: . ${\displaystyle A_{1}A_{2}A_{3}\cdots A_{n))$

Példa a kimerítő felsorolás használatára

A kiinduló feladat az adott lánc (mátrixszorzat) legrövidebb időn belüli kiszámítása. Lehetőség van egy triviális szekvenciális algoritmus megvalósítására, amely kiszámítja a szükséges szorzatot. Mivel a mátrixszorzat asszociatív művelet , a láncszorzat kiszámítható úgy , hogy tetszőlegesen kiválasztunk egy pár elemet a láncból , és helyettesítjük a kapott mátrixszal . Ha megismétli a leírt eljárást , akkor a fennmaradó eredmény mátrix lesz a válasz: . Ez a képlet a következőképpen szemléltethető. Tekintsük a mátrixláncot: . A következő 5 módszer létezik a láncnak megfelelő termék kiszámítására : $(A_{i}A_{i+1}),i=1..n-1$ $A_{i}^{1}\colon A_{i}^{1}=(A_{i}A_{i+1})$ $n-1$ ${\displaystyle A_{k}^{n-1))$ $A_{k}^{n-1}=(A_{k}^{n-2}A_{k+1}^{n-2})=\ldots =A_{1}A_{2} A_{3}\cdots A_{n},k=1..n-1$ $\left\langle A_{1},A_{2},A_{3},A_{4}\right\rangle$ ${\displaystyle A_{1}A_{2}A_{3}A_{4))$

{\color {Violet}(}A_{1}{\color {BurntOrange}(}A_{2}{\color {BrickRed}(}A_{3}A_{4}{\color {Téglavörös})) }{\color {BurntOrange})}{\color {Violet})},

{\color {Violet}(}A_{1}{\color {BurntOrange}(}{\color {BrickRed}(}A_{2}A_{3}{\color {BrickRed})}A_{4 }{\color {BurntOrange})}{\color {Violet})},

{\color {Violet}(}{\color {Téglavörös}(}A_{1}A_{2}{\color {BrickRed})}{\color {BurntOrange}(}A_{3}A_{4 }{\color {BurntOrange})}{\color {Violet})},

{\color {Violet}(}{\color {BurntOrange}(}A_{1}{\color {BrickRed}(}A_{2}A_{3}{\color {Brick Red})}{\color {BurntOrange})}A_{4}{\color {Violet})},

{\color {Violet}(}{\color {BurntOrange}(}{\color {BrickRed}(}A_{1}A_{2}{\color {BrickRed})}A_{3}{\color {BurntOrange})}A_{4}{\color {Violet})}.

A számítások helyes sorrendjének kiválasztásával jelentős számítási gyorsulás érhető el. Ennek megtekintéséhez vegyünk egy egyszerű példát egy 3 mátrixból álló láncra. Feltételezzük, hogy méretük egyenlő, ill . A két mátrix mérettel való szorzására szolgáló szabványos algoritmus a számmal (a kiszámítandó belső szorzatok számával) arányos számítási időt igényel [3] . Ezért a karakterlánc sorrendben történő kiértékelésével megkapjuk a kiszámítandó pontszorzatokat , valamint további pontszorzatokat a második mátrixszorzat kiszámításához. A skalárszorzatok száma összesen: 7500. A számítási sorrend eltérő megválasztásával plusz skalárszorzatot kapunk, azaz 75000 skalárszorzatot [3] . $10\x 100 100\x 5,5\x 50$ $p\times q,q\times r$ $pqr$ $((A_{1}A_{2})A_{3})$ $10\cdot 100\cdot 5=5000$ $(A_{1}A_{2})$ $10\cdot 5\cdot 50=2500$ $100\cdot 5\cdot 50=25000$ $10\cdot 100\cdot 50=50000$

Így ennek a feladatnak a megoldása jelentősen csökkentheti a mátrixlánc kiszámítására fordított időt. Ezt a megoldást kimerítő felsorolással kaphatjuk meg: figyelembe kell venni az összes lehetséges számítási sorozatot, és ki kell választani közülük azt, amelyik a lánc kiszámításakor a legkevesebb skaláris szorzatot foglalja el. Figyelembe kell azonban venni, hogy ez az algoritmus maga is exponenciális számítási időt igényel [2] , így hosszú mátrixláncok esetén a lánc leghatékonyabb módon történő kiszámításából származó nyereség (optimális stratégia ) teljesen elveszhet a szükséges idő alatt. hogy megtaláljuk ezt a stratégiát [4] .

Kapcsolat az "oszd meg és uralkodj" fogalmával

Az algoritmusok elméletében számos széles körben alkalmazható általános fogalom létezik. A brute force módszer az egyik ilyen. Valójában a kimerítő keresés használható olyan esetekben, amikor diszkrét determinisztikus rendszerről van szó, amelynek állapotai könnyen elemezhetők [5] .

Egy másik kiváló példa az algoritmuselmélet egyik alapfogalmára az „ oszd meg és uralkodj ” elv. Ez a koncepció akkor alkalmazható, ha a rendszer több alrendszerre osztható, amelyek felépítése hasonló az eredeti rendszer szerkezetéhez [6] . Ilyen esetekben az alrendszerek is szétválaszthatók, vagy triviálisak [6] . Az ilyen rendszerek esetében az eredetileg felvetett probléma triviális. Így az „oszd meg és uralkodj” koncepció megvalósítása rekurzív .

A rekurzió viszont egyfajta kimerítő keresés. Tehát a rekurzió csak diszkrét rendszerekre alkalmazható [7] . Ez a követelmény azonban nem egy adott rendszer állapotaira vonatkozik, hanem annak alstruktúrájára . Minden szint következetes mérlegelése kimerítő megoldást ad a felvetett problémára az egész diszkrét rendszerre vonatkozóan.

A teljes felsorolás egyéb példáihoz képest a rekurziós módszer sajátossága, hogy a végső megoldás egynél több triviális alrendszeren alapul. Általános esetben a megoldást alrendszerek egész halmaza alapján alakítják ki.

A klasszikus oszd meg és uralkodj problémák alábbi példáiban a nyers erő vagy az egyetlen ismert megoldás, vagy az eredeti megvalósítás, amelyet tovább optimalizáltak:

A legnagyobb részkarakterlánc megkeresése [8] [9]
Mátrixok láncszorzata [2]
A legközelebbi szomszéd megtalálásának problémája [10]
Hash függvények ütközésérzékelése [11]

Brute force attack

A kriptográfiában a brute-force kriptográfiai támadás vagy a brute force [12] ( Eng. Brute-force attack ) a brute force támadáson alapul – a jelszó feltörésén az összes lehetséges kulcsopció keresésével. Jellemzője, hogy bármilyen gyakorlatban használt rejtjellel szemben használható [13] ( a kivételekért, vagyis az információelméleti szempontból a biztonságért lásd még: rejtjelező pad és Információelméleti biztonság ). Ez a lehetőség azonban csak elméletileg létezik, ami gyakran irreális idő- és erőforrás-költségeket igényel. Ha a döntési tér túl nagy, akkor ez a fajta támadás akár több évre vagy akár évszázadra is sikertelen lehet. A brute force támadás alkalmazása leginkább abban az esetben indokolt, ha a támadott titkosítási rendszerben nem lehet gyenge pontokat találni (vagy nincs gyenge pont a vizsgált titkosítási rendszerben). Ha ilyen hiányosságokat találnak, azok jellemzői alapján kriptográfiai technikákat fejlesztenek ki , ami segít leegyszerűsíteni a hackelést.

A brute-force támadásokkal szembeni ellenállás határozza meg a titkosítási rendszerben használt titkosítási kulcsot . Tehát a kulcs hosszának növekedésével az ezzel a módszerrel végzett repedés bonyolultsága exponenciálisan növekszik. A legegyszerűbb esetben egy N bites rejtjel törik, legrosszabb esetben 2 N -rel arányos időn belül [14] [15] . Az átlagos hackelési idő ebben az esetben kétszer kevesebb, és 2 N -1 . Vannak módok a titkosítás „nyers erővel” szembeni ellenállásának növelésére, például a titkosított adatok elhomályosításával ( obfuszkációja ), ami nem triviálissá teszi a titkosított adatok és a titkosítatlan adatok megkülönböztetését.

A "brute force" módszeren alapuló kriptográfiai támadások a legsokoldalúbbak, de egyben a leglassabbak is. Főleg kezdő hackerek használják . Hatékony egyszerű titkosítási algoritmusokhoz és legfeljebb 64 bites kulcsokhoz. A 128 bites vagy annál hosszabb modern kulcsok esetében (néha nagyszámú, 200 számjegyű kulcsot faktorizálnak) nem hatékonyak. Kimerítő kereséssel bármely jelszó kitalálható. Ugyanakkor, még ha a célfüggvény kiszámítása a probléma egyes lehetséges megoldásaiból polinomiális időben is elvégezhető, az összes lehetséges megoldás számától függően a támadás exponenciális futási időt igényelhet.

Számítások párhuzamosítása

A kulcskiválasztás sebességének növelése érdekében a számítások párhuzamosítását használják. Kétféle párhuzamosítás létezik:

az algoritmus felépítése. Legyen az algoritmus egyszerű műveletek (műveletek) láncaként ábrázolva. Legyen azoknak a processzoroknak a száma, amelyekben a sorrend be van programozva. A processzorok végzik a munkát: $N$

$én$ A processzor három műveletet hajt végre egyidőben:

adatok fogadása a -edik processzortól $(i-1)$
művelet végrehajtása
adatok átvitele az i-edik processzorhoz. $(i+1)$

Ez a művelet akár egy századmásodpercig is eltarthat. Ekkor a párhuzamosan és szinkronban kapcsolt processzorok olyan sebességgel működnek (hiszen csak három művelet van), ahol egy processzor egy művelet végrehajtásának sebessége. $N$ $v/3$ $v$

halmazokra oszlik. Az összes lehetséges kulcs halmaza nem átfedő részhalmazokra van felosztva. A processzorokkal rendelkező rendszer úgy sorolja fel a kulcsokat, hogy például a -edik gép felsorolja a kulcsokat a részhalmazból . A rendszer leáll, ha az egyik gép megtalálta a megfelelő kulcsot. De ha minden processzor nem az első lehetséges kulcstól kezdi el a számítást, akkor az iterációs idő megnőhet, de az algoritmus egyszerűsödik. A kijelölések átlagos száma ebben az esetben , ahol a kulcskészlet elemeinek száma, és a processzorok száma. $K$ $K$ $én$ $K_{i},i=1...Q$ $|K|/Q$ $K$ $K$

A "nyers erő" által elkövetett támadások visszafordítása

A fordított brute force támadás során egyetlen (általában megosztott) jelszót tesztelnek több felhasználónévvel. Ebben az esetben a párhuzamosítás is érvényesül, de a processzoroknak ellenőrizniük kell, hogy más felhasználónak van-e ilyen jelszava. Egy ilyen stratégia során a támadó általában nem próbálja meg feltörni egy adott felhasználó fiókját. A fordított támadások ellen jelszószabályt vezetnek be, amely tiltja az azonos jelszavak használatát.

Példa a jelszókitalálás időtartamára

A táblázat a jelszavak brute-force keresésének becsült idejét mutatja, azok hosszától függően. Feltételezzük, hogy 36 különböző karakter használható a jelszóban ( egy kisbetű latin betűi + számok), és a brutális erő sebessége 100 000 jelszó másodpercenként ( B támadási osztály , jellemző a Windows gyorsítótárból történő jelszó-helyreállításra ( .PWL fájlok) a Pentium 100 -on ) [16] .

Karakterek száma	Opciók száma	Bátorság	Keresési idő
egy	36	5 bites	kevesebb mint egy másodperc
2	1296	10 bites	kevesebb mint egy másodperc
3	46 656	15 bites	kevesebb mint egy másodperc
négy	1 679 616	21 bites	17 másodperc
5	60 466 176	26 bites	10 perc
6	2176782336	31 bites	6 óra
7	78 364 164 096	36 bites	9 nap
nyolc	2,821 109 9x10 12	41 bites	11 hónap
9	1,015 599 5x10 14	46 bites	32 év
tíz	3656 158 4x10 15	52 bites	1162 év
tizenegy	1,316 217 0x10 17	58 bites	41 823 év
12	4.738 381 3x10 18	62 bites	1 505 615 év

Így a legfeljebb 8 karakter hosszú jelszavak általában nem biztonságosak. A modern számítógépeknél ez a szám sokkal magasabb. Tehát egy 64 bites kulcs (jelszó) egy modern számítógépen körülbelül 2 év alatt megoldódik, és a keresés könnyen szétosztható sok számítógép között.

Támadási eszközök

A modern személyi számítógépek lehetővé teszik a jelszavak brutális erőszakos feltörését a fenti táblázatban bemutatott hatékonysággal. A párhuzamos számításokon alapuló nyers erő optimalizálással azonban a támadás hatékonysága jelentősen növelhető [18] . Ehhez többszálú számítástechnikára alkalmas számítógép használatára lehet szükség . Az elmúlt években széles körben elterjedtek a GPU -kat használó számítástechnikai megoldások , mint például az Nvidia Tesla . Amióta az Nvidia 2007-ben megalkotta a CUDA architektúrát , számos olyan megoldás jelent meg (lásd például Cryptohaze Multiforcer , Pyrit Archived 2012. november 20. a Wayback Machine -nél ), amelyek lehetővé teszik a kulcsok gyorsítását olyan technológiák segítségével, mint a CUDA, FireStream , OpenCL .

Rute-force támadásokkal szembeni ellenálló képesség

A brute force támadással kapcsolatos információbiztonsági rendszer fejlesztése során két fő irányt lehet megkülönböztetni:

fokozott követelmények a védett információkhoz való hozzáférési kulcsokkal szemben;
a biztonsági rendszer összes elemének megbízhatóságának növelése.

Így lehetetlen magas szintű védelmet elérni e paraméterek közül csak egy javításával [19] . Vannak példák arra, hogy az optimális jelszó-bonyolultságon alapuló hitelesítési rendszer sebezhetővé vált az adatbázisnak a támadó helyi számítógépére való másolásával szemben, majd brute force támadásnak vetették alá helyi optimalizálás és számítási eszközök segítségével, amelyek nem elérhetők távoli kriptoanalízis [20] . Ez az állapot arra késztetett néhány számítógép-biztonsági szakértőt, hogy kritikusabb megközelítést javasoljanak a szabványos biztonsági gyakorlatokhoz, például a lehető leghosszabb jelszavak használatához [21] . Az alábbiakban felsorolunk néhány gyakorlati módszert [22] [23] [24] a kriptorendszer megbízhatóságának növelésére a nyers erő támadásokkal kapcsolatban:

Adatbázis másolásvédelem .
Jelszó -kivonatolás webszerveren [23] .
Megfelelően konfigurált tűzfal , például iptables [24] használata .
Más eszközök, amelyek megakadályozzák a gyors kulcsellenőrzést , például a Captcha , valamint a felhasználói hitelesítés megtagadása vagy időtúllépése .

Brute force optimalizálási módszerek

Elágazás és kötés módszer

A felsorolás felgyorsítása érdekében az elágazó és kötött módszer a megvalósítható megoldások azon részhalmazainak kiiktatását használja, amelyek nyilvánvalóan nem tartalmaznak optimális megoldásokat [25] .

Számítások párhuzamosítása

A kulcskiválasztás sebességének növelésének egyik módja a számítások párhuzamosítása . A párhuzamosításnak két megközelítése van [26] :

Az első megközelítés egy csővezeték építése [26] . Legyen az arányalgoritmus a legegyszerűbb műveletek (műveletek) láncaként ábrázolva: . Vegyük a processzorokat , állítsuk be a sorrendjüket, és tételezzük fel, hogy a processzor három műveletet hajt végre egyidőben: $E_{k}\ (x)=y$ ${O_{1}\ ,O_{2},...,O_{N}}$ $N\$ ${A_{1}\ ,A_{2},...,A_{N}}$ $én\$
1. adatok fogadása a -edik processzortól; $(i-1)\$
2. művelet végrehajtása ; $O_{i}\$
3. adatok átvitele a következő i-edik processzorra. $(i+1)\$
Ekkor a sorosan kapcsolt, párhuzamosan és szinkronban működő processzorok pipeline a sebességgel működik , ahol egy processzor egy művelet végrehajtásának sebessége. $N\$ $v/3\$ $v\$
A második megközelítés szerint az összes lehetséges kulcs halmazát nem átfedő részhalmazokra osztjuk [26] . A gépek rendszere úgy sorolja fel a kulcsokat, hogy - a gép számba veszi a kulcsokat a készletből . A rendszer leáll, ha az egyik gép megtalálta a kulcsot. A legnehezebb a kulcskészlet felosztása. De ha minden processzor valamilyen tetszőleges kulccsal kezdi a számítást, akkor a tartózkodási idő megnő, és a séma jelentősen leegyszerűsödik. A lépések átlagos száma ebben az esetben , ahol a kulcskészlet elemeinek száma, és a processzorok száma. $K\$ ${K_{1}\,K_{2},...,K_{N}}$ $Q\$ $én\$ $K_{i}\ ,i=1..Q$ $|K|/N\$ $|K|\$ $N\$

Szivárvány asztalok

. megjelenésének előfeltételei

A hitelesítéshez jelszavakat használó számítógépes rendszereknek valamilyen módon meg kell határozniuk, hogy a megadott jelszó helyes-e. Egy triviális megoldás erre a problémára, ha minden felhasználóhoz listát vezetünk az összes érvényes jelszóról, de ez a megközelítés nem mentes az adatbázis-szivárgástól. Az alapszivárgás elleni védelem egyszerű, de helytelen módja a kriptográfiai hash függvény kiszámítása a jelszóból.

A módszer helytelen, mivel lehetséges előzetes keresést végezni, és amikor fel kell törni a jelszót, nézze meg az eredményt. A szivárványtábla ennek a módszernek az optimalizálása [27] . Legfőbb előnye a felhasznált memória mennyiségének jelentős csökkenése [28] [27] .

Használat

A szivárványtábla a lehetséges jelszavak láncainak felépítésével jön létre. Minden lánc egy véletlenszerű lehetséges jelszóval kezdődik, majd egy hash függvénynek és egy redukciós függvénynek van alávetve. Ez a függvény a hash függvény eredményét valamilyen lehetséges jelszóvá alakítja (például ha feltételezzük, hogy a jelszó 64 bites, akkor a redukciós függvény lehet a hash első 64 bitjének felvétele, az összes 64 bit bitenkénti hozzáadásával a hash blokkjai stb.) . A lánc közbenső jelszavakat a rendszer eldobja, és csak a láncok első és utolsó eleme kerül a táblázatba. Az ilyen táblák létrehozása több időt igényel, mint a hagyományos keresőtáblák létrehozása, de sokkal kevesebb memóriát (akár több száz gigabájtot, a szokásos N szóból álló táblázatok térfogata mellett a szivárványos táblázatokhoz csak körülbelül N 2/3 ) [28 ] . Ugyanakkor, bár több időre van szükségük (a hagyományos módszerekhez képest) az eredeti jelszó visszaállításához, a gyakorlatban jobban megvalósíthatóak (egy 6 karakteres, bájt karaktereket tartalmazó, szabályos tábla létrehozásához, 256 6 = 281 474 976 710 656 memóriablokkra lesz szükség, míg a szivárványhoz csak 256 6 ⅔ \u003d 4 294 967 296 blokk.

A jelszó visszaállításához ezt a hash értéket lecsökkentjük, és megkeressük a táblázatban. Ha nem található egyezés, akkor a hash függvény és a redukciós függvény ismét alkalmazásra kerül. Ez a művelet addig folytatódik, amíg egyezést nem talál. Az egyezés megtalálása után az azt tartalmazó lánc visszaállításra kerül, hogy megtalálja az eldobott értéket, amely a kívánt jelszó lesz.

Az eredmény egy táblázat, amely nagy valószínűséggel rövid időn belül vissza tudja állítani a jelszót [29] .

Incidensek

Bár egy információs rendszer védelmének mindenekelőtt megbízhatónak kell lennie a brutális erőszakos támadásokkal kapcsolatban, meglehetősen gyakoriak az esetek, amikor a behatolók sikeresen használják ezt a támadást.

Enigma attack

Az 1918-ban feltalált Enigma titkosítógépet 1929-től széles körben használta a német haditengerészet. A következő néhány évben a rendszert módosították, és 1930 óta a második világháború idején a német hadsereg és kormány aktívan használta [31] .

Az Enigma kóddal titkosított üzenetek első lehallgatása 1926-ból származik. Az üzeneteket azonban sokáig nem tudták elolvasni. A második világháború során a lengyel és a német kriptográfusok konfrontációja folyt. A lengyelek, akik újabb eredményt értek el a német kriptorendszer feltörésében, új nehézségekkel néztek szembe, amelyeket az Enigma rendszert folyamatosan frissítő német mérnökök vezettek be. 1939 nyarán , amikor nyilvánvalóvá vált a Lengyelország elleni invázió elkerülhetetlensége, az Iroda átadta munkája eredményét a brit és francia hírszerzésnek [32] .

A további betörési munkákat a Bletchley Parkban szervezték meg . A kriptoanalitikusok fő eszköze a Bomba visszafejtő gép volt . Prototípusát lengyel matematikusok alkották meg a második világháború előestéjén a lengyel védelmi minisztérium számára. E fejlesztés alapján és alkotóinak közvetlen támogatásával egy „fejlettebb” egységet terveztek Angliában.

A munka elméleti részét Alan Mathison Turing [33] készítette . Az Enigma rejtjelező gépben megvalósított algoritmus kriptográfiai elemzésével kapcsolatos munkája a gép korábbi verzióinak korábbi kriptográfiai elemzésén alapult , amelyet 1938-ban Marian Rejewski lengyel kriptoanalitikus végzett el . A Turing által kifejlesztett dekódoló működési elve az volt, hogy felsorolja a rejtjelkulcs lehetséges opcióit, és megpróbálja visszafejteni a szöveget, ha ismert volt a visszafejtendő üzenet szerkezete vagy a nyílt szöveg egy része [34] .

Modern szempontból az Enigma titkosítás nem volt túl megbízható, de csak ennek a tényezőnek a kombinációja számos elfogott üzenet, kódkönyvek, hírszerzési jelentések, a katonai erőfeszítések eredményei és még a terrortámadások jelenlétével tette lehetővé, hogy " nyissa meg" a titkosítást [32] .

A háború után Churchill biztonsági okokból elrendelte ezeknek a gépeknek a megsemmisítését.

A WPS protokoll sebezhetősége

2007-ben a Wi-Fi Alliance szervezet tagjaként működő vállalatok egy csoportja elkezdte az otthoni hálózatok számára az új Wi-Fi Protected Setup szabványt támogató vezeték nélküli berendezések értékesítését. Az ezt a technológiát támogató vezeték nélküli útválasztók gyártói között voltak olyan nagy cégek, mint a Cisco/Linksys , a Netgear , a Belkin és a D-Link . A WPS szabvány célja az volt, hogy nagymértékben leegyszerűsítse a vezeték nélküli hálózat létrehozásának folyamatát és annak használatát olyan személyek számára, akik nem rendelkeznek széles körű ismeretekkel a hálózatbiztonság területén. 2011 végére azonban megjelentek a WPS súlyos sebezhetőségeiről szóló információk, amelyek lehetővé tették a támadó számára , hogy néhány óra alatt kitalálja egy vezeték nélküli hálózat PIN-kódját [35] , egy átlagos személyi számítógép számítási erőforrásaival [36]. ] .

A CERT Koordinációs Központ jelenleg nem javasolja a gyártóknak, hogy adjanak ki új, ezt a technológiát támogató berendezéseket. [37]

Otthoni hálózatok tömeges feltörése WASP-n keresztül

2010-ben a DEFCON18 konferencián bemutattak egy pilóta nélküli légi járművet, a WASP -t , amelyet az otthoni Wi-Fi hálózatokról szóló statisztikák tömeges gyűjtésére terveztek. Az UAV egy BackTrack Linuxot futtató kompakt fedélzeti számítógéppel van felszerelve, melynek egyik jellemzője a vezeték nélküli hálózati jelszavak automatikus feltörése volt nyers erő alkalmazásával [38] [39] .

Lásd még

Jegyzetek

↑ Ried & Knipping, 2010 , p. 133.
↑ 1 2 3 Cormen, 2001 , p. 372.
↑ 1 2 Cormen, 2001 , Mátrixláncok terméke, pp. 370-372.
↑ Cormen, 2001 , p. 377.
↑ Cormen, 2001 , 4. rész. Oszd meg és uralkodj, pp. 65-67.
↑ 12. Cormen , 2001 , p. 65.
↑ Cormen, 2001 , p. 66.
↑ Knuth, 1972 , Selected Research Problems in Combinatorics .
↑ Cormen, 2001 , Az LCS-probléma : a leghosszabb közös részsorozat megtalálása, p. 392.
↑ Cormen, 2001 , A legközelebbi pontpár megkeresése, 1. o. 1039.
↑ SchneierOnSecurity , Ütközések az SHA-1 kivonatoló algoritmusban.
↑ Nyers erő . A Kaspersky Lab enciklopédiája. Letöltve: 2018. november 21. Az eredetiből archiválva : 2018. november 21.. (határozatlan)
↑ Paar, 2010 , p. 7.
↑ Corman, 2001 .
↑ Knuth, 1972 .
↑ www.lockdown.co.uk , Jelszó-helyreállítási sebesség.
↑ Tesla , Tesla C2075 paraméterei a gyártó honlapján.
↑ Ku , Brute-force támadás végrehajtása Nvidia és AMD grafikus kártyákkal .
↑ Mark Pothier . Kérjük, ne változtassa meg jelszavát (2010. április 11.). Archiválva az eredetiből 2011. június 28-án. Letöltve: 2011. május 25. "A jelszó megváltoztatása időpocsékolás lehet az információbiztonság felé vezető úton."
↑ Weiss , Az "erős" jelszó relatív fogalom.
↑ Cormac, 2009 , Rational Security Refusal.
↑ Gil , Mi az a Brute Force Hack ?.
↑ 1 2 McGlinn , PHP Jelszókivonat .
↑ 1 2 Zernov , Bruteforce elleni védelem iptables használatával.
↑ Land, 1960 , Automatikus módszer diszkrét programozási problémák megoldására .
↑ 1 2 3 Voevodin, 2002 , Párhuzamos számítástechnika.
↑ 12 Oechslin , 2003 , p. egy.
↑ 1 2 Hellman, 1980 , p. 401.
↑ Hellman, 1980 , p. 405.
↑ Harper , brit bomba-helyreállítási projekt.
↑ Larin-shankin, 2007 , II. világháború a levegőben: Az Ultra hadművelet néhány vonatkozása.
↑ 1 2 chernyak, 2003 , Az Ultra projekt titkai.
↑ Ellsbury , "Enigma" és "Bomb".
↑ groteck.ru , Turing Bombe gép.
↑ Liebowitz1 , Az otthoni vezeték nélküli útválasztók brute force támadásnak vannak kitéve.
↑ Ray, 2011 , A WPS protokoll elégtelen biztonsága.
↑ CERT , a WPS brute force hatálya alatt áll.
↑ Greenberg , A repülő drón feltöri a vezeték nélküli jelszavakat.
↑ Humphries , WASP: Repülő felderítő drón, amely feltöri a Wi-Fi hálózatokat.

Irodalom

Reid, D. A. és munkatársai. Bizonyítás a matematika oktatásában: kutatás, tanulás és tanítás . - John Wiley & SSense Publishers, 2010. - P. 266. - ISBN 978-9460912443 .
Paar, Christof et al.,. A kriptográfia megértése: Tankönyv diákok és gyakorló szakemberek számára . - Springer, 2010. - P. 1292. - ISBN 3-642-04100-0 .
Thomas H. Cormen et al.,. Bevezetés az algoritmusokba. - MIT Press, 2001. - P. 1292. - ISBN 978-0-262-03384-8 .
V. Chvatal et al.,. Válogatott kombinatorikus kutatási problémák. — Műszaki jelentés STAN-CS-72-292. — A Stanford Egyetem Számítástechnikai Tanszéke, 1972.
Schneier, Bruce . Hazugok és kívülállók : A társadalom számára szükséges bizalom megteremtése. - John Wiley & Sons, 2012. - ISBN 978-1-118-14330-8 .
Voevodin V.V. és mások. Párhuzamos számítástechnika . - Szentpétervár. : BHV-Petersburg, 2002. - 608. o . — ISBN 5-94157-160-7 .
Land, A.H. et al.,. Automatikus módszer diszkrét programozási problémák megoldására // Econometrica : Journal. - 1960. - 1. évf. 28 , sz. 3 . - P. 497-520 . - doi : 10.2307/1910129 .
Hellman, M.E. Kriptoanalitikus idő-memória kompromisszum // IEEE Transactions on Information Theory : folyóirat. – IEEE, IT-26:401–406, 1980. – Iss. Előadásjegyzetek számítástechnikából .
Oechslin, Philippe. Gyorsabb kriptanalitikai idő-memória kompromisszum létrehozása // Advances in Cryptology: Proceedings of CRYPTO : Journal. - 23rd Annual International Conference on Cryptology , Santa Barbara (Kalifornia) , USA: Springer, 2003. - Iss. Előadásjegyzetek számítástechnikából . — ISBN 3-540-40674-3 . Archiválva az eredetiből 2007. szeptember 26-án.
Larin, D. A., Ph.D. satöbbi.,. II. világháború a levegőben: Az Ultra hadművelet néhány vonatkozása // Információvédelem. Belül : magazin. - 2007. Archiválva : 2014. január 20. (Orosz)
Csernyak, Leonyid. Az Ultra Project titkai // Nyílt rendszerek : Journal. - 2003. - No. 07-08 . (Orosz)
Hurley, Cormac . So Long, And No Thanks for the Externalities: The Rational Rejection of Security Advice by Users (angol) // New Security Paradigms Workshop : a collection. - Microsoft Research ACM 978-1-60558-845-2/09/09, 2009.
Ray, Bill . A Wi-Fi Protected Setup könnyen feloldható biztonsági hiba miatt // The Register : portál. – 2011.

Linkek

A Brute Force algoritmus . Catania Egyetem (2007). — Az algoritmus eredeti megvalósítása C nyelven . Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1.. (határozatlan)
Zernov, Vlagyimir bruteforce védelem iptables segítségével . OpenNET (2010. június 9.). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. október 16.. (Orosz)
Schneier, Bruce . Az SHA-1 kriptoanalízise (angol) . schneier.com (2005. február 18.). - "új kriptoanalitikai eredmény - az első támadás, amely gyorsabb, mint a nyers erő az SHA-1 ellen ". Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Weiss, Aaron . Lehetséges , hogy az „erős” jelszavak nem mindenek, amelyeket feltörtek . esecurityplanet.com (2010. április 27.). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Harper, John. The British Bombe: The Rebuild Project (angolul) (nem elérhető link) (2008). Az eredetiből archiválva : 2012. december 19.
Ellsbury, Graham. The Enigma and the Bombe (angolul) (nem elérhető link) (2007). Az eredetiből archiválva : 2012. december 19.
A brit rajongók újra létrehozták az Enigma dekódert (hozzáférhetetlen link) (2006. szeptember 13.). Az eredetiből archiválva : 2012. június 29. (Orosz)
Ku, Andrew. Nvidia Versus AMD: Brute-Force Attack Performance . Tom's Hardware (2011. június 20.). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
McGlin, James. Jelszókivonatolás . _ PHP Security Consortium (2005). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Sebezhetőségi megjegyzés VU#723755 (angol) (lefelé irányuló kapcsolat) . CERT Koordinációs Központ (2011. december 27.). - "WiFi Protected Setup (WPS) PIN brute force sebezhetősége". Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
A Nyúl-lyuk . - A WASP projekt hivatalos weboldala, ahol a drón otthoni összeszereléséhez találsz instrukciókat Hozzáférés dátuma: 2012. november 30. Archiválva : 2012. november 26.
Greenberg, Andy . A repülő drón képes feltörni a Wi-Fi hálózatokat, lesni a mobiltelefonokat . Forbes (2011. július 28.). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Humphreys, Matthew . WASP: Linux - alapú repülő kém drón, amely feltöri a Wi-Fi- és GSM-hálózatokat . www.geek.com (2011. július 29.). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Tassi, Mike ; Perkins, Rick . Vezeték nélküli légi felügyeleti platform . www.defcon.org (2011). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. október 25..
Liebowitz, Matt. Otthoni Wi-Fi útválasztók, amelyek sebezhetőek a Brute-Force Hack miatt (angol) (nem elérhető link) . SecurityNewsDaily (2011). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Liebowitz, Matt. A repülő drón Wi-Fi jelszavakat lop, mobiltelefonokat tör fel (angolul) (a link nem érhető el) . SecurityNewsDaily (2011). Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Gil, Paul . Mi az a „Brute Force” hackelés? (angol) . about.com . Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Jelszó- helyreállítási sebességek . 2009_ _ - Jelszó helyreállítási sebesség. - "Meddig marad fenn a jelszava?" Letöltve: 2012. november 30. Az eredetiből archiválva : 2012. december 1..
Még gyorsabb grafika és vizualizáció . Nvidia . — A Tesla c2075 paraméterei a gyártó honlapján Letöltve : 2012. november 30. Archiválva : 2012. december 1.