Raaka voima

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. lokakuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 11 muokkausta .

Täydellinen luettelointi (tai "raaka voima" -menetelmä , eng. brute force ) - menetelmä matemaattisten ongelmien ratkaisemiseksi . Viittaa menetelmäluokkaan, jonka avulla voidaan löytää ratkaisu käyttämällä kaikki mahdolliset vaihtoehdot . Kattavan haun monimutkaisuus riippuu ongelman kaikkien mahdollisten ratkaisujen määrästä. Jos ratkaisuavaruus on erittäin suuri, tyhjentävä haku ei välttämättä anna tuloksia useisiin vuosiin tai jopa vuosisatoja.

Mikä tahansa luokan NP ongelma voidaan ratkaista kattavalla haulla. Samaan aikaan, vaikka tavoitefunktion laskenta kustakin tietystä mahdollisesta ongelman ratkaisusta voidaan suorittaa polynomiajassa , kaikkien mahdollisten ratkaisujen lukumäärästä riippuen, tyhjentävä luettelointi voi vaatia eksponentiaalisen suoritusajan.

Salaustekniikassa tyhjentävän haun laskennallista monimutkaisuutta käytetään salausten kryptografisen vahvuuden arvioimiseen . Erityisesti salauksen sanotaan olevan turvallinen, jos ei ole olemassa "krakkausmenetelmää", joka on huomattavasti nopeampi kuin raakavoimahaku . Raakavoimaiset salaushyökkäykset ovat monipuolisimpia, mutta myös pisimpiä.

Exhaustion Method

Terminologia

Englannin kielessä tässä artikkelissa käsitelty termi " raaka voima " viittaa yleensä hakkerihyökkäysten luokkaan . Samaan aikaan yleisempi käsite, matemaattinen menetelmä käyttää kaikki mahdolliset vaihtoehdot ratkaisun löytämiseksi ongelmaan, vastaa termiä " todistaminen loppuun ".

Kuvaus

"Ummentumismenetelmä" sisältää koko luokan erilaisia menetelmiä. Yleensä ongelmalauseessa otetaan huomioon tietyn loogisen järjestelmän äärellinen määrä tiloja loogisen lauseen totuuden tunnistamiseksi kunkin tilan riippumattoman analyysin avulla [1] . Väitettä todistava menetelmä koostuu kahdesta osasta:

Todiste mahdollisuudesta tyhjentää järjestelmän kaikki tilat. On osoitettava, että mikä tahansa järjestelmän tietty tila (esimerkiksi todistettavan loogisen lausekkeen arvo) vastaa vähintään yhtä harkituista ratkaisuehdokkaista.
Jokaisen vaihtoehdon tarkistaminen ja sen osoittaminen, että harkittava vaihtoehto on tai ei ole ratkaisu ongelmaan.

Tyypilliset ongelmat ratkaistaan tyhjentävällä luettelolla

Vaikka tyhjentävää hakua ei käytetä käytännössä useimmissa sovelletuissa ongelmissa (etenkään ei liity salausten rikkomiseen ), on olemassa useita poikkeuksia. Erityisesti silloin, kun tyhjentävä haku kuitenkin osoittautuu optimaaliseksi tai edustaa algoritmin kehittämisen alkuvaihetta , sen käyttö on perusteltua. Esimerkki tyhjentävän haun optimaalisuudesta on matriisien ketjutulojen laskenta-ajan estimointialgoritmi, jota ei voida kiihdyttää "raakavoima"-menetelmään perustuvaan algoritmiin verrattuna [2] . Tätä algoritmia käytetään dynaamisen ohjelmoinnin klassisen ongelman ratkaisemiseen - prioriteettien määrittämiseen seuraavan muodon matriisitulojen laskemiseksi: . ${\displaystyle A_{1}A_{2}A_{3}\cdots A_{n))$

Esimerkki tyhjentävän luettelon käytöstä

Lähtötehtävänä on laskea annettu ketju (matriisitulo) mahdollisimman lyhyessä ajassa. On mahdollista toteuttaa triviaali peräkkäinen algoritmi, joka laskee halutun tuotteen. Koska matriisitulo on assosiatiivinen operaatio , ketjutulo voidaan laskea valitsemalla mielivaltaisesti ketjun elementtipari ja korvaamalla se tuloksena olevalla matriisilla . Jos toistat kuvatut toimenpidekerrat , jäljelle jäävä tuloksena oleva matriisi on vastaus: . Tämä kaava voidaan havainnollistaa seuraavasti. Harkitse matriisiketjua: . On olemassa 5 tapaa laskea tätä ketjua vastaava tuote : $(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 {Tilenpunainen}(}A_{3}A_{4}{\väri {Tilenpunainen}) }{\color {BurntOrange})}{\color {Violet})},

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

{\color {Violet}(}{\color {Tilenpunainen}(}A_{1}A_{2}{\väri {Tilenpunainen})}{\väri {BurntOranssi}(}A_{3}A_{4 }{\color {BurntOrange})}{\color {Violet})},

{\color {Violet}(}{\color {BurntOrange}(}A_{1}{\color {Tilenpunainen}(}A_{2}A_{3}{\väri {Tilenpunainen})}{\väri {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})}.

Valitsemalla oikean laskentajärjestyksen voit saavuttaa huomattavan kiihtyvyyden laskelmissa. Nähdäksesi tämän, harkitse yksinkertaista esimerkkiä 3 matriisin ketjusta. Oletetaan, että niiden koot ovat vastaavasti yhtä suuret . Vakioalgoritmi kahden matriisin kertomiseksi koolla vaatii laskenta-aikaa, joka on verrannollinen määrään (laskettavien sisätulojen lukumäärä) [3] . Siksi, arvioimalla merkkijono järjestyksessä , saamme laskettavat pistetulot sekä lisäpistetulot toisen matriisitulon laskemiseksi. Skalaaritulojen kokonaismäärä: 7500. Laskentajärjestyksen erilaisella valinnalla saadaan plusskalaaritulot , eli 75000 skalaarituloa [3] . $10 \ kertaa 100 100 \ kertaa 5,5 \ kertaa 50$ $p\ kertaa q, q\ kertaa 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$

Siten tämän ongelman ratkaisu voi vähentää merkittävästi matriisiketjun laskemiseen käytettyä aikaa. Tämä ratkaisu voidaan saada tyhjentävällä luettelolla: on otettava huomioon kaikki mahdolliset laskentasarjat ja valita niistä se, joka ketjua laskettaessa vie vähiten skalaarituloja. On kuitenkin otettava huomioon, että tämä algoritmi itsessään vaatii eksponentiaalista laskenta-aikaa [2] , joten pitkillä matriisiketjuilla voitto ketjun laskemisesta tehokkaimmalla tavalla (optimaalinen strategia ) voi menettää kokonaan sen ajan kuluessa. löytää tämä strategia [4] .

Suhde "hajoita ja hallitse" -käsitteeseen

Algoritmien teoriassa on useita laajalti sovellettavia yleiskäsitteitä . Raaka voima -menetelmä on yksi niistä. Itse asiassa tyhjentävää hakua voidaan käyttää niissä tapauksissa, kun kyseessä on diskreetti deterministinen järjestelmä, jonka tilat ovat helposti analysoitavissa [5] .

Toinen loistava esimerkki algoritmien teorian peruskäsitteestä on " hajota ja hallitse " -periaate. Tätä käsitettä voidaan soveltaa, kun järjestelmä voidaan jakaa useisiin osajärjestelmiin, joiden rakenne on samanlainen kuin alkuperäisen järjestelmän rakenne [6] . Tällaisissa tapauksissa osajärjestelmät ovat myös erotettavissa tai ne ovat triviaaleja [6] . Tällaisissa järjestelmissä alun perin esitetty ongelma on triviaali. Siten "hajoita ja hallitse" -käsitteen toteutus on rekursiivinen .

Rekursio puolestaan on eräänlainen tyhjentävä haku. Joten rekursio on sovellettavissa vain diskreeteille järjestelmille [7] . Tämä vaatimus ei kuitenkaan koske tietyn järjestelmän tiloja, vaan sen alirakennetta . Kaikkien tasojen johdonmukainen huomioiminen antaa tyhjentävän ratkaisun koko diskreetille järjestelmälle esitettyyn ongelmaan.

Muihin täydellisen numeroinnin esimerkkeihin verrattuna rekursiomenetelmän ominaisuus on, että lopullinen ratkaisu perustuu useampaan kuin yhteen triviaaliin osajärjestelmään. Yleensä ratkaisu muodostetaan kokonaisen osajärjestelmän perusteella.

Seuraavissa esimerkeissä klassisista hajota ja hallitse -ongelmista raaka voima on joko ainoa tunnettu ratkaisu tai alkuperäinen toteutus, jota on edelleen optimoitu:

Suurimman alijonon löytäminen [8] [9]
Matriisien ketjutulo [2]
Ongelma lähimmän naapurin löytämisessä [10]
Hajautusfunktioiden törmäystunnistus [11]

Brute force attack

Salaustekniikassa brute-force kryptografinen hyökkäys tai brute force [12] ( eng. Brute-force attack ) perustuu brute force -hyökkäykseen - salasanan murtamiseen etsimällä kaikki mahdolliset avainvaihtoehdot. Sen ominaisuus on kyky käyttää sitä mitä tahansa käytännössä käytettyä salausta vastaan [13] ( poikkeukset eli tietoteorian kannalta tietoturva , katso myös salausalusta ja Tietoteoreettinen turvallisuus ). Tämä mahdollisuus on kuitenkin olemassa vain teoreettisesti, mikä vaatii usein epärealistisia aika- ja resurssikustannuksia. Jos päätöstila on liian suuri, tämäntyyppinen hyökkäys voi epäonnistua useita vuosia tai jopa vuosisatoja. Raakavoimahyökkäyksen käyttö on oikeutetuimmin tapauksissa, joissa hyökkäyksen kohteena olevasta salausjärjestelmästä ei ole mahdollista löytää heikkoja kohtia (tai kyseessä olevassa salausjärjestelmässä ei ole heikkoja kohtia). Kun tällaisia puutteita havaitaan, kehitetään krypta -analyysitekniikoita niiden ominaisuuksien perusteella, mikä auttaa yksinkertaistamaan hakkerointia.

Raakavoiman vastustuskyky määrittää salausjärjestelmässä käytettävän salausavaimen . Joten avaimen pituuden kasvaessa tällä menetelmällä tapahtuvan murtamisen monimutkaisuus kasvaa eksponentiaalisesti. Yksinkertaisimmassa tapauksessa N - bittinen salaus rikkoutuu, pahimmassa tapauksessa 2 N :ään verrannollisessa ajassa [14] [15] . Keskimääräinen hakkerointiaika on tässä tapauksessa kaksi kertaa lyhyempi ja on 2 N -1 . On olemassa tapoja lisätä salauksen vastustuskykyä "raakaa voimaa" vastaan, esimerkiksi salattujen tietojen hämärtäminen ( obfuskaatio ), mikä tekee salatun tiedon erottamisesta salaamattomasta tiedosta epätriviaalia.

"Raaka voima" -menetelmään perustuvat kryptografiset hyökkäykset ovat monipuolisimpia, mutta samalla hitaimpia. Käyttää pääasiassa aloittelevia hakkereita . Tehokas yksinkertaisille salausalgoritmeille ja jopa 64 bitin pituisille avaimille. Nykyaikaisille avaimille, joiden pituus on vähintään 128 bittiä (joskus avaimelle kerrotaan suuri määrä 200 numeroa), ne ovat tehottomia. Mikä tahansa salasana voidaan arvata kattavalla haulla. Samaan aikaan, vaikka tavoitefunktion laskenta kustakin tietystä mahdollisesta ongelman ratkaisusta voidaan suorittaa polynomiajassa, kaikkien mahdollisten ratkaisujen lukumäärästä riippuen hyökkäys voi vaatia eksponentiaalisen suoritusajan.

Laskentatoimien rinnakkaisuus

Näppäinvalinnan nopeuttamiseksi käytetään laskelmien rinnastamista. Rinnakkaisua on kahta tyyppiä:

algoritmin rakentaminen. Esitetään algoritmi yksinkertaisten toimien (operaatioiden) ketjuna. Antaa olla prosessorien määrä, jossa järjestys on ohjelmoitu. Prosessorit tekevät työn: $N$

$i$ Prosessori suorittaa kolme toimintoa samaan aikaan:

vastaanottaa tietoja -: nnelta prosessorilta $(i-1)$
suorittaa operaatiota
siirtää tietoja i:nnelle prosessorille. $(i+1)$

Tämä toimenpide voi kestää vain sekunnin sadasosan. Sitten rinnakkain ja synkronisesti kytketyt prosessorit toimivat nopeudella (koska operaatioita on vain kolme), missä on yhden toiminnon suorittamisen nopeus yhdellä prosessorilla. $N$ $v/3$ $v$

jakautuminen sarjoihin. Kaikkien mahdollisten avainten joukko on jaettu ei-päällekkäisiin osajoukkoon. Prosessoreilla varustettu järjestelmä luettelee avaimet siten, että esimerkiksi -. kone luettelee avaimet osajoukosta . Järjestelmä lakkaa toimimasta, jos yksi kone on löytänyt oikean avaimen. Mutta jos kukin prosessori ei aloita laskentaa ensimmäisestä mahdollisesta avaimesta, iterointiaika voi pidentyä, mutta algoritmi yksinkertaistuu. Keskimääräinen valintojen määrä tässä tapauksessa on , jossa on elementtien lukumäärä avainjoukossa ja on prosessorien lukumäärä. $K$ $K$ $i$ $K_{i},i=1...Q$ $|K|/Q$ $K$ $K$

Käänteiset hyökkäykset "raa'alla voimalla"

Käänteisessä brute force -hyökkäyksessä yksi (yleensä jaettu) salasana testataan useilla käyttäjätunnuksilla. Tässä tapauksessa myös rinnakkaistoiminto pätee, mutta prosessorien on tarkistettava, onko toisella käyttäjällä tällainen salasana. Tällaisessa strategiassa hyökkääjä ei yleensä yritä murtautua yhden tietyn käyttäjän tiliin. Käänteisiä hyökkäyksiä vastaan on laadittu salasanakäytäntö, joka kieltää identtisten salasanojen käytön.

Esimerkki salasanan arvauksen kestosta

Taulukossa näkyy arvioitu aika salasanojen raa'an voiman etsimiseen niiden pituuden mukaan. Oletetaan, että salasanassa voidaan käyttää 36 eri merkkiä ( yhden tapauksen latinalaiset kirjaimet + numerot), ja raa'an voiman nopeus on 100 000 salasanaa sekunnissa ( hyökkäysluokka B , tyypillinen salasanan palautukselle Windowsin välimuistista ( .PWL- tiedostot) Pentium 100 : ssa ) [16] .

Merkkien määrä	Vaihtoehtojen määrä	Rohkeus	Hakuaika
yksi	36	5 bittiä	alle sekunti
2	1296	10 bittiä	alle sekunti
3	46 656	15-bittinen	alle sekunti
neljä	1 679 616	21 bittiä	17 sekuntia
5	60 466 176	26-bittinen	10 minuuttia
6	2176782336	31-bittinen	6 tuntia
7	78 364 164 096	36-bittinen	9 päivää
kahdeksan	2.821 109 9x10 12	41 bittinen	11 kuukautta
9	1,015 599 5x10 14	46-bittinen	32 vuotta
kymmenen	3.656 158 4x10 15	52 bittiä	1162 vuotta
yksitoista	1.316 217 0x10 17	58-bittinen	41 823 vuotta
12	4 738 381 3x10 18	62 bittiä	1 505 615 vuotta

Näin ollen enintään 8 merkin pituiset salasanat eivät yleensä ole turvallisia. Nykyaikaisissa tietokoneissa tämä luku on paljon suurempi. Joten 64-bittinen avain (salasana) selviää nykyaikaisella tietokoneella noin 2 vuodessa ja haku voidaan helposti jakaa useiden tietokoneiden kesken.

Hyökkäyskeinot

Nykyaikaiset henkilökohtaiset tietokoneet mahdollistavat salasanojen murtamisen raa'alla voimalla yllä olevan taulukon mukaisella tehokkuudella. Rinnakkaislaskentaan perustuvalla raakavoiman optimoinnilla hyökkäyksen tehokkuutta voidaan kuitenkin lisätä merkittävästi [18] . Tämä saattaa edellyttää monisäikeiseen laskemiseen mukautetun tietokoneen käyttöä . Viime vuosina grafiikkasuoritteita käyttävät laskentaratkaisut , kuten Nvidia Tesla , ovat yleistyneet . Sen jälkeen kun Nvidia loi CUDA - arkkitehtuurin vuonna 2007, on ilmestynyt monia ratkaisuja (katso esimerkiksi Cryptohaze Multiforcer , Pyrit arkistoitu 20. marraskuuta 2012 Wayback Machinessa ), jotka mahdollistavat nopeutetun avainten arvauksen käyttämällä teknologioita, kuten CUDA, FireStream , OpenCL . .

Kestävyys raa'an voiman hyökkäykselle

Tietoturvajärjestelmän parantamisprosessissa raa'an voiman hyökkäyksen suhteen voidaan erottaa kaksi pääsuuntaa:

lisääntyneet vaatimukset suojattujen tietojen pääsyavaimille;
turvajärjestelmän kaikkien osien luotettavuuden lisääminen.

Näin ollen on mahdotonta saavuttaa korkeaa suojaustasoa parantamalla vain yhtä näistä parametreista [19] . On esimerkkejä siitä, kuinka optimaaliseen salasanan monimutkaisuuteen perustuva todennusjärjestelmä osoittautui alttiiksi kopioida tietokanta hyökkääjän paikalliselle tietokoneelle, minkä jälkeen se joutui raa'an voiman hyökkäykseen käyttämällä paikallisia optimointeja ja laskentatyökaluja, jotka eivät ole käytettävissä etäsalausanalyysi [20] . Tämä tilanne on saanut jotkin tietoturva-asiantuntijat suosittelemaan kriittisempää lähestymistapaa turvastandardien käytäntöihin, kuten mahdollisimman pitkiin salasanoihin [21] . Alla on luettelo käytännön menetelmistä [22] [23] [24] kryptojärjestelmän luotettavuuden lisäämiseksi suhteessa raa'an voiman hyökkäykseen:

Tietokannan kopiosuojaus .
Salasanan hajautus verkkopalvelimella [23] .
Käyttämällä oikein määritettyä palomuuria , kuten iptablesia [24] .
Muut keinot, jotka estävät nopean avaimen vahvistuksen , kuten Captcha , sekä käyttäjän todennuksen kieltämisen tai aikakatkaisun .

Raakavoiman optimointimenetelmät

Branch and Bound Method

Laskennan nopeuttamiseksi haara ja sidottu menetelmä eliminoi toteutettavissa olevien ratkaisujen osajoukot, jotka eivät ilmeisesti sisällä optimaalisia ratkaisuja [25] .

Laskentatoimien rinnakkaisuus

Yksi tapa nopeuttaa avainten valintaa on laskelmien rinnakkaistaminen . Rinnakkaisussa on kaksi lähestymistapaa [26] :

Ensimmäinen lähestymistapa on rakentaa putki [26] . Esitetään suhdealgoritmi yksinkertaisimpien toimien (operaatioiden) ketjuna: . Otetaan prosessorit , asetetaan niiden järjestys ja oletetaan, että - prosessori suorittaa kolme toimintoa samaan aikaan: $E_{k}\ (x)=y$ ${O_{1}\ ,O_{2},...,O_{N}}$ $N\$ ${A_{1}\ ,A_{2},...,A_{N}}$ $minä\$
1. vastaanottaa dataa -: nnelta prosessorilta; $(i-1)\$
2. toiminnan suorittaminen ; $O_{i}\$
3. siirtää tiedot seuraavalle i:nnelle prosessorille. $(i+1)\$
Tällöin sarjaan kytkettyjen, rinnakkaisten ja synkronisesti toimivien prosessorien liukuhihna toimii nopeudella , jossa on yhden prosessorin yhden toiminnon suorittamisen nopeus. $N\$ $v/3\$ $v\$
Toinen lähestymistapa on, että kaikkien mahdollisten avainten joukko jaetaan ei-päällekkäisiin osajoukkoon [26] . Konejärjestelmä luettelee avaimet siten, että - th kone luettelee avaimet joukosta . Järjestelmä lakkaa toimimasta, jos jokin koneista on löytänyt avaimen. Vaikein osa on avainsarjan jakaminen. Mutta jos jokainen prosessori aloittaa laskennan jollakin mielivaltaisella avaimella, viipymäaika kasvaa ja järjestelmä yksinkertaistuu huomattavasti. Keskimääräinen vaiheiden lukumäärä tässä tapauksessa on , jossa on avainjoukon elementtien lukumäärä ja prosessorien lukumäärä. $K\$ ${K_{1}\,K_{2},...,K_{N}}$ $Q\$ $minä\$ $K_{i}\ ,i=1..Q$ $|K|/N\$ $|K|\$ $N\$

Rainbow-pöydät

Edellytykset

Tietokonejärjestelmien, jotka käyttävät salasanoja todentamiseen , on jotenkin määritettävä, onko syötetty salasana oikea. Triviaali ratkaisu tähän ongelmaan on pitää luettelo kaikista kelvollisista salasanoista jokaiselle käyttäjälle, mutta tämä lähestymistapa ei ole immuuni tietokantavuodoille. Yksinkertainen mutta virheellinen tapa suojautua perusvuodolta on laskea salaushajautusfunktio salasanasta.

Menetelmä on virheellinen siinä mielessä, että on mahdollista suorittaa haku etukäteen, ja kun haluat murtaa salasanan, katso tulosta. Sateenkaaritaulukko on tämän menetelmän optimointi [27] . Sen tärkein etu on käytetyn muistin määrän merkittävä väheneminen [28] [27] .

Käyttö

Sateenkaaritaulukko luodaan rakentamalla mahdollisten salasanojen ketjuja. Jokainen ketju alkaa satunnaisella mahdollisella salasanalla, jonka jälkeen sille suoritetaan hash- ja vähennystoiminto. Tämä funktio muuntaa hajautusfunktion tuloksen joksikin mahdolliseksi salasanaksi (esim. jos oletetaan, että salasana on 64 bittiä pitkä, niin pelkistysfunktio voi ottaa tiivisteen ensimmäiset 64 bittiä, bittikohtaisesti kaikki 64-bitit hash-lohkot jne.) Ketjun välissä olevat salasanat hylätään ja vain ketjun ensimmäinen ja viimeinen elementti kirjoitetaan taulukkoon. Tällaisten taulukoiden luominen vaatii enemmän aikaa kuin tavallisten hakutaulukoiden luominen, mutta paljon vähemmän muistia (jopa satoja gigatavuja, kun tavallisten N sanan taulukoiden tilavuus, sateenkaaritaulukot tarvitsevat vain noin N 2/3 ) [28 ] . Samaan aikaan, vaikka ne vaativat enemmän aikaa (perinteisiin menetelmiin verrattuna) alkuperäisen salasanan palauttamiseen, ne ovat käytännössä toteuttamiskelpoisempia (tavallisen taulukon rakentaminen 6-merkkiselle salasanalle tavumerkeillä, 256 6 = 281 474 976 Tarvitaan 710 656 muistilohkoa, kun taas sateenkaarelle - vain 256 6 ⅔ \u003d 4 294 967 296 lohkoa).

Salasanan palauttamiseksi tätä hash-arvoa pienennetään ja se etsitään taulukosta. Jos vastaavuutta ei löydy, hajautustoimintoa ja vähennystoimintoa käytetään uudelleen. Tämä toiminto jatkuu, kunnes osuma löytyy. Kun osuma on löydetty, sen sisältävä ketju palautetaan etsimään hylätty arvo, joka on haluttu salasana.

Tuloksena on taulukko, joka voi suurella todennäköisyydellä palauttaa salasanan lyhyessä ajassa [29] .

Tapahtumat

Vaikka kaiken tietojärjestelmän suojauksen tulee ennen kaikkea olla luotettavaa raa'an voiman hyökkäyksessä, tapaukset, joissa tunkeilijat käyttävät tätä hyökkäystä onnistuneesti, ovat melko yleisiä.

Enigma attack

Vuonna 1918 keksittyä Enigma-salauskonetta käytti laajalti Saksan laivasto vuodesta 1929 lähtien. Seuraavien vuosien aikana järjestelmää muutettiin, ja vuodesta 1930 lähtien Saksan armeija ja hallitus käytti sitä aktiivisesti toisen maailmansodan aikana [31] .

Ensimmäiset Enigma-koodilla salattujen viestien sieppaukset ovat peräisin vuodelta 1926. He eivät kuitenkaan pystyneet lukemaan viestejä pitkään aikaan. Koko toisen maailmansodan ajan puolalaisten ja saksalaisten kryptografien välillä oli vastakkainasettelu. Puolalaiset, jotka saivat toisen tuloksen murtaessaan saksalaisen kryptojärjestelmän, kohtasivat uusia vaikeuksia, jotka saksalaiset insinöörit esittelivät, jotka jatkuvasti päivittivät Enigma-järjestelmää. Kesällä 1939 , kun Puolan hyökkäyksen väistämättömyys kävi selväksi, toimisto luovutti työnsä tulokset Britannian ja Ranskan tiedustelupalveluille [32] .

Lisämurtotyötä järjestettiin Bletchley Parkissa . Kryptanalyytikkojen päätyökalu oli Bomba- salauksenpurkukone . Sen prototyypin loivat puolalaiset matemaatikot toisen maailmansodan aattona Puolan puolustusministeriölle. Tämän kehityksen perusteella ja sen tekijöiden suoralla tuella Englannissa suunniteltiin "edistyneempi" yksikkö.

Työn teoreettisen osan teki Alan Mathison Turing [33] . Hänen työnsä Enigma-salauskoneeseen toteutetun algoritmin kryptografisessa analyysissä perustui tämän koneen aikaisempien versioiden aiempaan kryptoanalyysiin, jonka puolalainen kryptanalyytikko Marian Rejewski suoritti vuonna 1938 . Turingin kehittämän salauksenpurkulaitteen toimintaperiaate oli luetella mahdollisia salausavaimen vaihtoehtoja ja yrittää purkaa tekstiä, jos salauksen purkamisen tai osan selkeästä tekstistä tiedettiin [34] .

Nykyajan näkökulmasta Enigma-salaus ei ollut kovin luotettava, mutta vain tämän tekijän yhdistelmä monien siepattujen viestien, koodikirjojen, tiedusteluraporttien, sotilaallisten ponnistelujen tulosten ja jopa terrori -iskujen kanssa mahdollisti " avaa" salaus [32] .

Sodan jälkeen Churchill määräsi turvallisuussyistä tuhoamaan nämä koneet.

WPS-protokollan haavoittuvuus

Vuonna 2007 joukko yrityksiä, jotka ovat Wi-Fi Alliance -organisaation jäseniä, alkoi myydä kotiverkkoihin tarkoitettuja langattomia laitteita, jotka tukevat uutta Wi-Fi Protected Setup -standardia. Tätä tekniikkaa tukevien langattomien reitittimien valmistajien joukossa olivat sellaiset suuret yritykset kuin Cisco/Linksys , Netgear , Belkin ja D-Link . WPS-standardin tarkoituksena oli yksinkertaistaa huomattavasti langattoman verkon perustamisprosessia ja sen käyttöä ihmisille, joilla ei ole laajaa tietoa verkkoturvallisuudesta. Vuoden 2011 loppuun mennessä kuitenkin julkaistiin tieto WPS:n vakavista haavoittuvuuksista, joiden ansiosta hyökkääjä pystyi arvaamaan langattoman verkon PIN-koodin [35] vain muutamassa tunnissa, kun hänellä oli tavallisen henkilökohtaisen tietokoneen laskentaresurssit [36] . ] .

Tällä hetkellä CERT-koordinointikeskus ei suosittele valmistajia julkaisemaan uusia tätä tekniikkaa tukevia laitteita. [37]

Kotiverkkojen joukkohakkerointi WASP:n kautta

Vuonna 2010 DEFCON18- konferenssissa esiteltiin miehittämätön ilma -alus WASP , joka on suunniteltu laajaan tilastojen keräämiseen kodin Wi-Fi-verkoista. UAV on varustettu kompaktilla ajotietokoneella, jossa on käytössä BackTrack Linux.Yksi sen ominaisuuksista oli kyky murtaa langattoman verkon salasanat automaattisesti raa'alla voimalla [38] [39] .

Katso myös

Muistiinpanot

↑ Ried & Knipping, 2010 , s. 133.
↑ 1 2 3 Cormen, 2001 , s. 372.
↑ 1 2 Cormen, 2001 , Matriisiketjujen tuote, s. 370-372.
↑ Cormen, 2001 , s. 377.
↑ Cormen, 2001 , jakso 4. Divide and Conquer, s. 65-67.
↑ 12 Cormen , 2001 , s. 65.
↑ Cormen, 2001 , s. 66.
^ Knuth, 1972 , Selected Research Problems in Combinatorics .
↑ Cormen, 2001 , LCS-ongelma : pisimmän yhteisen osasekvenssin löytäminen, s. 392.
↑ Cormen, 2001 , Lähimmän pisteparin löytäminen, s. 1039.
↑ SchneierOnSecurity , Törmäykset SHA-1-hajautusalgoritmissa.
↑ Raaka voima . Kaspersky Labin tietosanakirja. Haettu 21. marraskuuta 2018. Arkistoitu alkuperäisestä 21. marraskuuta 2018. (määrätön)
↑ Paar, 2010 , s. 7.
↑ Corman, 2001 .
↑ Knuth, 1972 .
↑ www.lockdown.co.uk , Salasanan palautusnopeus.
↑ Tesla , Tesla C2075 -parametrit valmistajan verkkosivuilla.
↑ Ku , Suorittaa raa'an voiman hyökkäys Nvidian ja AMD :n näytönohjainkorteilla .
↑ Mark Pothier . Älä vaihda salasanaasi (11. huhtikuuta 2010). Arkistoitu alkuperäisestä 28. kesäkuuta 2011. Haettu 25. toukokuuta 2011. "Salasanan vaihtaminen voi olla ajanhukkaa tielläsi tietoturvaan."
↑ Weiss , "Vahva" salasana on suhteellinen käsite.
↑ Cormac, 2009 , Rational Security Refusal.
↑ Gil , Mikä on Brute Force Hack ?.
↑ 1 2 McGlinn , PHP Salasanan hajautus .
↑ 1 2 Zernov , Suojaus bruteforcea vastaan iptablesin avulla.
↑ Land, 1960 , Automaattinen menetelmä diskreettien ohjelmointiongelmien ratkaisemiseksi .
↑ 1 2 3 Voevodin, 2002 , Parallel Computing.
↑ 12 Oechslin , 2003 , s. yksi.
↑ 1 2 Hellman, 1980 , s. 401.
↑ Hellman, 1980 , s. 405.
↑ Harper , British Bomb Recovery Project.
↑ larin-shankin, 2007 , World War II on Air: Jotkut Ultra-operaation näkökohdat.
↑ 1 2 chernyak, 2003 , Ultra-projektin salaisuudet.
↑ Ellsbury , "Enigma" ja "Bomb".
↑ groteck.ru , Turing Bombe kone.
↑ Liebowitz1 , Kodin langattomat reitittimet raa'an voiman hyökkäykselle.
↑ Ray, 2011 , WPS-protokollan riittämätön suojaus.
↑ CERT , WPS on raa'an voiman alainen.
↑ Greenberg , Lentävä drone murtaa langattomat salasanat.
↑ Humphries , WASP: lentävä tiedusteludroni, joka murtaa Wi-Fi-verkkoja.

Kirjallisuus

Reid, D.A. et ai.,. Todiste matematiikan koulutuksessa: tutkimus, oppiminen ja opettaminen . - John Wiley & SSense Publishers, 2010. - S. 266. - ISBN 978-9460912443 .
Paar, Christof et ai.,. Kryptografian ymmärtäminen: oppikirja opiskelijoille ja harjoittajille . - Springer, 2010. - S. 1292. - ISBN 3-642-04100-0 .
Thomas H. Cormen et ai.,. Johdatus algoritmeihin. - MIT Press, 2001. - P. 1292. - ISBN 978-0-262-03384-8 .
V. Chvatal et ai.,. Valitut kombinatoriset tutkimusongelmat. — Tekninen raportti STAN-CS-72-292. — Tietojenkäsittelytieteen laitos, Stanfordin yliopisto, 1972.
Schneier, Bruce . Valehtelijat ja ulkopuoliset : Yhteiskunnan tarvitseman luottamuksen mahdollistaminen kukoistaakseen. - John Wiley & Sons, 2012. - ISBN 978-1-118-14330-8 .
Voevodin V.V. ja muut. Rinnakkaislaskenta . - Pietari. : BHV-Petersburg, 2002. - s . 608 . — ISBN 5-94157-160-7 .
Land, A.H. et ai.,. Automaattinen menetelmä diskreettien ohjelmointiongelmien ratkaisemiseen // Econometrica : Journal. - 1960. - Voi. 28 , ei. 3 . - s. 497-520 . - doi : 10.2307/1910129 .
Hellman, M.E. Kryptusanalyyttinen aika-muisti kompromissi // IEEE Transactions on Information Theory : Journal. — IEEE, IT-26:401–406, 1980. — Iss. Tietojenkäsittelytieteen luentomuistiinpanot .
Oechslin, Philippe. Nopeamman kryptaanalyyttisen aikamuistin kompromissi // Advances in Cryptology: Proceedings of CRYPTO : Journal. - 23rd Annual International Conference on Cryptology , Santa Barbara (Kalifornia) , USA: Springer, 2003. - Iss. Tietojenkäsittelytieteen luentomuistiinpanot . — ISBN 3-540-40674-3 . Arkistoitu alkuperäisestä 26. syyskuuta 2007.
Larin, D. A., Ph.D. jne.,. Toinen maailmansota on Air: Jotkut Ultra-operaation näkökohdat // Tietojen suojaaminen. Sisällä : lehti. - 2007. Arkistoitu 20. tammikuuta 2014. (Venäjän kieli)
Chernyak, Leonid. Ultra-projektin salaisuudet // Open Systems : Journal. - 2003. - Nro 07-08 . (Venäjän kieli)
Hurley, Cormac . Niin kauan, ja ei kiitos ulkoisuuksista: Käyttäjien rationaalinen turvallisuusneuvonnan hylkääminen (englanniksi) // New Security Paradigms Workshop : kokoelma. - Microsoft Research ACM 978-1-60558-845-2/09/09, 2009.
Ray, Bill . Wi-Fi Protected Setup avataan helposti suojausvirheen takia // The Register : portaali. – 2011.

Linkit

Brute Force -algoritmi . Catanian yliopisto (2007). — Algoritmin alkuperäinen toteutus C -kielellä . Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012. (määrätön)
Zernov, Vladimir bruteforce-suojaus iptablesilla . OpenNET (9. kesäkuuta 2010). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 16. lokakuuta 2012. (Venäjän kieli)
Schneier, Bruce . SHA-1:n kryptoanalyysi (englanniksi) . schneier.com (18. helmikuuta 2005). - "uusi kryptanalyyttinen tulos - ensimmäinen hyökkäys nopeampi kuin raakavoima SHA-1 :tä vastaan ". Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Weiss, Aaron . " Vahvat " salasanat eivät välttämättä ole kaikkea, mitä ne murretaan . esecurityplanet.com (27. huhtikuuta 2010). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Harper, John. The British Bombe: The Rebuild Project (englanniksi) (linkki ei saatavilla) (2008). Arkistoitu alkuperäisestä 19. joulukuuta 2012.
Ellsbury, Graham. The Enigma and the Bombe (englanniksi) (linkki ei saatavilla) (2007). Arkistoitu alkuperäisestä 19. joulukuuta 2012.
Brittiharrastajat ovat luoneet uudelleen Enigma-dekooderin (pääsemätön linkki) (13. syyskuuta 2006). Arkistoitu alkuperäisestä 29. kesäkuuta 2012. (Venäjän kieli)
Ku, Andrew. Nvidia Versus AMD: Brute-Force Attack Performance . Tom's Hardware (20. kesäkuuta 2011). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
McGlin, James. Salasanan hajautus . PHP Security Consortium (2005). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Haavoittuvuushuomautus VU#723755 (englanniksi) (downlink) . CERT-koordinointikeskus (27. joulukuuta 2011). - "WiFi Protected Setup (WPS) PIN brute force haavoittuvuus". Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Kanin reikä . - WASP-projektin virallinen nettisivu, josta löytyy ohjeet dronin kokoamiseen kotona Pääsypäivämäärä : 30.11.2012. Arkistoitu 26.11.2012.
Greenberg, Andy . Lentävä drooni voi murtaa Wi-Fi-verkkoja, snoop on matkapuhelimia . Forbes (28. heinäkuuta 2011). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Humphreys, Matthew . WASP : Linux-käyttöinen lentävä vakoojadrone, joka murtaa Wi-Fi- ja GSM-verkot . www.geek.com (29. heinäkuuta 2011). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Tassi, Mike ; Perkins, Rick . Langaton antennivalvontaalusta . www.defcon.org (2011). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 25. lokakuuta 2012.
Liebowitz, Matt. Kodin Wi-Fi-reitittimet, jotka ovat alttiita Brute-Force Hackille (englanniksi) (linkki ei saatavilla) . SecurityNewsDaily (2011). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Liebowitz, Matt. Lentävä drone varastaa Wi-Fi-salasanat, hakkeroi matkapuhelimia (englanniksi) (linkki ei ole käytettävissä) . SecurityNewsDaily (2011). Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Gil, Paul . Mitä on brute Force -hakkerointi? (englanniksi) . about.com . Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Salasanan palautusnopeudet . 2009_ _ - Salasanan palautusnopeus. - "Kuinka kauan salasanasi pysyy pystyssä." Haettu 30. marraskuuta 2012. Arkistoitu alkuperäisestä 1. joulukuuta 2012.
Saat entistä nopeamman grafiikan ja visualisoinnin . Nvidia . — Tesla c2075 -parametrit valmistajan verkkosivuilla Haettu 30. marraskuuta 2012. Arkistoitu 1. joulukuuta 2012.

Raaka voima

Exhaustion Method

Terminologia

Kuvaus

Tyypilliset ongelmat ratkaistaan ​​tyhjentävällä luettelolla

Esimerkki tyhjentävän luettelon käytöstä

Suhde "hajoita ja hallitse" -käsitteeseen

Brute force attack

Laskentatoimien rinnakkaisuus

Käänteiset hyökkäykset "raa'alla voimalla"

Esimerkki salasanan arvauksen kestosta

Hyökkäyskeinot

Kestävyys raa'an voiman hyökkäykselle

Raakavoiman optimointimenetelmät

Branch and Bound Method

Laskentatoimien rinnakkaisuus

Rainbow-pöydät

Tapahtumat

Enigma attack

WPS-protokollan haavoittuvuus

Kotiverkkojen joukkohakkerointi WASP:n kautta

Katso myös

Muistiinpanot

Kirjallisuus

Linkit

Tyypilliset ongelmat ratkaistaan tyhjentävällä luettelolla