Kuinka hajautus toimii?

Salaushajautusfunktiot ovat matemaattisia objekteja, joita voidaan kuvata ”suureksi sekoitukseksi ja sekoitukseksi” joidenkin bittien joukosta ”. Ne ottavat syötteenä bittisarjan (mahdollisesti hyvin pitkän) ja tarjoavat kiinteän koon. Karkeasti sanottuna he ovat niin sotkeutuneita, että vaikka heissä ei ole mitään salaisuutta (se on vain deterministinen koodi), kukaan ei pysty selvittämään, kuinka ne ”kääntää” (löytää vastaava tulo tietylle ulostulolle) paitsi nimeltään perusmenetelmä ”onni”: kokeile satunnaisia syötteitä, kunnes ottelu löytyy.

Kuinka tieteellisesti voi tapahtua, että hajautusfunktioita voi olla olemassa, on hyvä kysymys .

Hajautus ei ole salaus . Hajautuksessa ei ole salaisuutta eikä avainta.

Hash-toiminnoilla on monia käyttötarkoituksia; yksi niistä on ”salasanojen tallennus”. Hajautusfunktio näyttää hyvältä salasanan tallennuksessa. Emme halua tallentaa salasanoja suoraan (muuten hyökkääjän satunnainen kurkistus tietokantoihimme antaisi hänelle liikaa tietoa; katso tämä -blogiviesti keskustelusta) ; haluamme tallentaa salasanan vahvistustunnukset : jotain, joka sallii käyttäjän esittämän salasanan vahvistamisen, mutta ei paljasta itse salasanaa. Joten ajatus on: tallentakaamme salasanan hajautus. Kun salasana on vahvistettava, laskemme vain sen hash ja katsomme, vastaako se tallennettua arvoa. Mutta salasanan arvaaminen vain hash-arvosta on vaikeaa, koska hash-toiminto on joustava ”inversiota” vastaan (katso yllä).

Koska salasanat ovat erityistä dataa (tietoja, jotka ihmiset voivat muistaa), turvallisuuden takaamiseksi tarvitsemme ”vahvistetun” hash-toiminto:

• Haluamme erittäin hidas hash-funktion.
• Emme halua one hash-toimintoa, mutta monia erillisiä hash-toimintoja, joten jokainen salasana hajautetaan omalla hash-toiminnollaan; kyse on rinnakkaisten hyökkäysten estämisestä. Tätä prosessia, jolla yksi hash-funktio muutetaan moniksi muunnoksiksi, kutsutaan suolaksi .

Katso tämä vastaus salasanojen hajauttamisen aiheen perusteelliseen käsittelyyn.

Kommentit

• Anteeksi, mutta vaikka vastauksesi oli erittäin perusteellinen ja hyvin koottu, löysin toinen vastaus on enemmän kuin etsin.

Hajautus on joidenkin toiminto bittimerkkijono (yleensä vaihteleva pituus) toiseen bittimerkkijonoon (yleensä pienempi ja kiinteän pituinen).

Hajautusta käytetään tietokannoissa tietojen hakemiseen ja muistin sisäisissä tietorakenteissa, joita kutsutaan hash-taulukoiksi. Sen avulla voimme vähentää mielivaltaisen datan, kuten merkkijonon tai monimutkaisen objektin, jossa on useita kenttiä, binääriluvuksi, jota voidaan sitten käyttää suoraan hakemistona harvaan taulukkoon liittyvien tietojen noutamiseksi (joitain yksityiskohtia hashien käsittelystä) törmäykset).

Edellä mainitulla tavalla käytetyt hajautusfunktiot ovat salauksen hajautusfunktioiden ”serkkuja”. Ne on suunniteltu erilaisiin vaatimuksiin. Niiden on oltava nopeasti laskettavissa ja saavutettava hyvä jakelu.

Turvallisessa tietojenkäsittelyssä salaushajautuksia käytetään sulattamaan tiedot osaksi edustavaa, pientä bittijonoa. Salausfunktioilla on erilaiset vaatimukset. Ne on suunniteltu niin, että niitä on vaikea peruuttaa (”lukko-ovi” – tai ”yksisuuntainen” -toimintoiksi). Paitsi, mutta tärkeä vaatimus on, että tietylle teksti- ja tiiviste-arvolle on vaikea löytää toista tekstiä, joka tuottaa saman hashin.

Hajautusta voidaan käyttää paitsi salasanoissa, mutta tarkistussummana tietojen eheyden todentamiseksi ja osana digitaalisten allekirjoitusten toteuttamista. Suuren asiakirjan digitaaliseen allekirjoittamiseen joudumme yksinkertaisesti hajauttamaan asiakirjan, jotta saadaan ”tiivistelmä” (nimi, jota käytetään hajautusfunktion tulosteessa, kun jotain hyvin pitkää hajautetaan). Sitten juuri tämä tiivistelmä laitetaan julkisen avaimen salausjärjestelmän läpi allekirjoituksen tuottamiseksi. Siellä voit nähdä heikkouden: entä jos hyökkääjä onnistuu tuottamaan asiakirjan, jolla on sama katsaus? Tällöin näyttää siltä, että alkuperäisen asiakirjan päällä tuotettu alkuperäinen allekirjoitus on itse asiassa väärennetyn asiakirjan allekirjoitus: allekirjoituksen siirtoon liittyvä väärentäminen on tosiasiallisesti tapahtunut.

Salasanan hajautus antaa järjestelmille mahdollisuuden olla tallentamatta salasanan, mutta antaa heille mahdollisuuden tarkistaa, tietääkö käyttäjä, joka yrittää hakea merkintää, salasanan. Hajautus ei salli vain järjestelmien olla tallentamatta pelkkää tekstiä sisältäviä salasanoja (jotka on suojattava erittäin huolellisesti), mutta se antaa myös mahdollisuuden, että vaikka hajautusasiat ovat julkisesti alttiina, salasanat ovat silti turvallisia (samoin kuin julkisen avaimen salaus) järjestelmät pystyvät paljastamaan julkiset avaimet). Vaikka käytännössä hajautukset on silti suojattu yleisöltä: esimerkiksi /etc/shadow -tiedostot Unix-tyyppisissä järjestelmissä, täydentäen maailman luettavia /etc/passwd -tiedostoja .

Hajautusfunktio on kaikkea muuta kuin satunnainen. Satunnaistamista käytetään kuitenkin estämään hyökkääjät, jotka rakentavat suuria sanakirjoja salasanoista ja tiivisteistä, joiden avulla he voivat etsiä hajautuskoodin ja noutaa vastaavan salasanan.

Jos haluat hajauttaa salasanan turvallisemmin, voimme yksinkertaisesti lisätä joitain satunnaisia bittejä siihen, jota kutsutaan ”suolaksi”. Eri suolat, jotka lisätään samaan salasanaan, johtavat tietysti erilaisiin hajautuksiin (toivottavasti vain vähän tai ei lainkaan törmäyksiä).

Jos satunnainen suola on esimerkiksi 32 bittiä leveä, se tarkoittaa, että teoriassa yksi salasana voi hajauttaa yli neljällä miljardilla eri tavalla, minkä vuoksi on erittäin epäkäytännöllistä saada valmiiksi laskettu sanakirja kaikista mahdollisista hajautuksista suuresta joukosta salasanoja.

Kun käyttäjä todennetaan, hän ei tietenkään tiedä mitään tästä suolasta. Se on okei, koska suola tallennetaan hashin kanssa käyttäjän profiiliin (usein yhdessä hashin kanssa yhdeksi kompaktiksi bittijonoksi). Kun käyttäjän salasanan merkintää tarkistetaan, suola lisätään mihin tahansa salasanaan hän tuli sisään, niin että hajautus suoritetaan oikealla suolalla. Jos salasana on oikea, hash täsmää, koska käytetty suola on myös oikea, koska se on vedetty käyttäjän profiilista.

Joten satunnaisuus sisällytetään salasanan hajautukseen, samalla kun se antaa sen toimia.

Hajautuksia tekee vaikeiksi se, että ne on rakennettu ”trap door” – tai ”one way” -toiminnoista. Matematiikassa on monia esimerkkejä tällaisista asioista. Esimerkiksi , yksinkertainen lisäys on ansa-ovi. Jos lisäämme joitain kokonaislukuja summan tuottamiseksi, alkuperäisten numeroiden palauttaminen on mahdotonta, tietäen vain summan.

Salasanan hajautukset eivät ole salattuja salasanoja. Jos hyökkääjä on salasanan hajautus ja suola, ja sattuu arvaamaan salasanan, hän voi vahvistaa sen helposti, samalla tavalla kuin kirjautumistodennusohjelma: se suorittaa salasanan ja suolan hajautusfunktion läpi ja näkee, että oikea hash syntyy.

Kommentit

• Erinomainen kirjoitustaito ja todella helppo y ymmärtää vastauksen, joka on tosiasiallisesti oikea, mutta käsittelee kaikki kohdat ja säilyttää siihen luonnollisen virtauksen, joka tekee siitä paljon kattavamman. Se ’ ei ole helppo saavutus, kiitos vastauksestasi!
• erittäin informatiivinen. Katoit kaikki näkökohdat.

Yksi hajautusavaimista on, että se heittää pois tietoja. Et voi kääntää tiivistettä, koska tarvittava tieto on kadonnut. Tässä on muutama esimerkki toimivista (mutta melko arvottomista) hajautusfunktioista. Jos annat minulle salasanan, voisin tehdä jotain seuraavista:

• Laske vokaalien määrä
• Ota jokaisen kirjaimen ASCII-koodi ja XOR ne kaikki yhdessä
• Ota salasanan binaarisen esityksen CRC32-tarkistussumma (tämä on oikeastaan todellinen hash, vain ei salaus)

Kummassakin näistä tapauksista en voi ”kääntää prosessia. Sen sijaan minun on suoritettava prosessi uudelleen, kun annat minulle salasanan myöhemmin uudelleen, jotta voin nähdä, onko suorittamani laskelma yhteneväinen.

Esimerkki: Jos annat minulle salasanan ”apina”, voin tallentaa numeron 3 (3 vokaalia). Sitten myöhemmin, kun yritän todentaa salasanan ”lohikäärme”, suoritan saman tarkistuksen uudelleen ja keksin 2, joka ei vastaa 3. Joten tiedän, että annoit minulle väärän salasanan. Mutta jos annat minulle salasanan ”melissa”, oletan väärin, että kirjoitit oikean salasanan. Tämä on hash törmäys .

Sääntöjoukko, jota käytät keksiä numero, jonka edustaa annettua salasanaa, on hash-toiminto . Näitä pidetään yksisuuntaisina toimintoina, koska niitä ei pitäisi pystyä peruuttamaan. Laadukkaat hash-toiminnot on suunniteltu rajoittamaan mahdollisten törmäysten määrää, joten sinun ei tarvitse huolehtia tästä ongelmasta. Vaihe eteenpäin salauksen tiivistefunktiot on suunniteltu vaikeuttamaan tietyn ulostuloa mahdollisesti vastaavan merkkijonon keksimistä ja ehkä tarkoituksellisesti luoda törmäyksiä). Ne on myös suunniteltu rajoittamaan tietomäärää, jonka voit kerätä tietystä syötteestä vain hajautusulostulosta.

Tämän seurauksena ainoa tapa kertoa, mikä salasana vastaa tiettyä salaus hashia, on kokeilla kaikkia mahdollisuuksia, kunnes törmäät toimivaan. Lisävastatoimet (suola, BPKDF2 jne.) Tekevät tästä arvausprosessista vieläkin vaikeampaa, kun salasanaa arvaavan henkilön käydään läpi enemmän vanteita jokaista yritystä kohti.

Huomaa, että olen hämmentänyt täysin sitä, miten salauksen hajautusfunktio tekee siitä toimivan salasanan keksiminen on vaikeaa (vaikka se ei olisikaan alkuperäinen). Tätä kutsutaan ” preimage-hyökkäykseksi ”. Yllä olevassa triviaalissa esimerkissä” melissa ”keksiminen ehdokkaasalasanaksi, joka sisältää 3 vokaalia, on esimerkki tällaisesta hyökkäyksestä.

Salaushajautusfunktiot tekevät tämän yleensä suorittamalla syötteen vaikka useita” tietyn prosessin kierrokset ”, jossa jokaisen kierroksen tuloksesta tulee osa seuraavan prosessin tuloa.Ensimmäisen kierroksen panoksen selvittämiseksi sinun on selvitettävä toisen kierroksen tulo, mikä puolestaan vaatii sinua selvittämään kolmannen kierroksen panoksen jne., Mikä tarkoittaa, että kunkin komponentin kukin arvaus Thomas Porninilla on melko tyhjentävä selitys siitä, miten tämä vastus toimii; melko hyödyllinen lukeminen, jos haluat todella ymmärrä se.

1. Määritä z: n vakioarvo, joka täyttää tämän yhtälön: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Tarvitsetko apua? OK, x = 32. Eivätkö vieläkään pysty ratkaisemaan sitä? Sitten sinun ei pitäisi tietää vastausta ensinnäkin.

   Y: n arvo, joka pienentää tämän yhdeksi muuttujayhtälöksi, jolloin sen ratkaiseminen tälle yksittäiselle muuttujalle on triviaali kaikille 6. luokkalaisille (mahdollisesti tarvitsen laskinta), on salaisuus, jonka olen jakanut vain luotettavien ihmisten kanssa. Ilman sitä z voi olla mikä tahansa; sen arvo riippuu y: stä, joten sitä ei voida tyydyttävästi ratkaista ilman vakiota, tunnettua y: tä. Jos et ” en tiedä y arvoa, se johtuu siitä, että en ole luottanut sinuun tarpeeksi antamaan sitä sinulle yksityisesti.

   Tämä on salauksen perusperiaate; matemaattinen kaava tai muu deterministinen prosessi on hyvä -dokumentoitu, ja yhden tai useamman kaavan mahdollisista muuttujista saa myös olla julkisesti tiedossa, jolloin osapuolet voivat sopia tavasta asettaa salauksensa niin, että kumpikin voi purkaa salauksensa. pysy salaisena; jos tunnet yhden, voit löytää toisen. Yksi, jonka sinun pitäisi tietää, on avain ja yksi sinä voi löytää avaimella on viesti.

   Hajautusasiakirjassa se on hieman erilainen. Hajautus ei vaadi yhden salaisuuden säilyttämistä toisen säilyttämiseksi. Sen sijaan hajautustyö perustuu peruuttamattomaan matemaattiseen muunnokseen; minkään H (x) = y: n kohdalla ei tunneta H ^-1 (y) = x paitsi H (x): n kokeileminen kaikilla mahdollisilla x: llä, kunnes saat y: n. Yleensä tämä johtuu siitä, että useat yhtälön välitulokset ovat epäselvät; esimerkiksi positiivisen luvun neliöjuuren laskeminen tuottaa teknisesti molemmat positiivinen ja negatiivinen tulos, koska kumpikin luku voidaan kertoa itsestään tuloksen tuottamiseksi.Kerroin käänteinen on samalla tavoin epäselvä; x mod 3: n tuottaman luvun 1 olisi voinut tuottaa mikä tahansa x = 3k + 1. Tämäntyyppiset ”yksisuuntaiset” muunnokset yhdistetään siten, että käänteisen hajautusfunktion laskeminen yrittää tuottaa loputtomia mahdollisuuksia; helpoin (helpoin) tapa ratkaista ne on siis yksinkertaisesti kokeilla kaikkia mahdollisia syötteitä, kunnes yksi lähtö vastaa. kestää vielä kauan.

2. Hashes eivät ole satunnaisia. Kuten aiemmin totesin, hajautukset ovat seurausta peruuttamattomasta matemaattisesta operaatiosta. Tämän operaation on silti oltava deterministinen; vakiosyötöllä annetaan lähtö vakiona riippumatta siitä, kuinka monta kertaa toiminto suoritetaan. Satunnaisosaa ei ole.

   Missä olet saattanut olla hämmentynyt, on termi, jota hash simuloi, mikä on satunnainen oraakli . Kuvittele musta laatikko, jonka sisällä on pieni mies, jolla on valokuvamuisti ja jokin mystinen tapa tuottaa täysin satunnaisia lukuja. Kirjoitat jotain paperille ja työnnät sen aukon läpi, josta mies saa sen. Hän lukee sen, ja yksi kahdesta asiasta tapahtuu. Joko hän ei ole lukenut sitä aikaisemmin, jolloin hän luo uuden satunnaisluvun ja antaa sen sinulle sitouttamalla sekä viestisi että numerosi muistiinsa. Tai on lukenut tämän tarkan viesti ennen, jolloin hän muistaa ensimmäisen kerran luodun numeron ja antaa sinulle tht-numeron. Satunnaislukugeneraattori ei koskaan luo jo luomaa lukua, sillä on ääretön mahdollinen suuruus ja pikkumies muisti on rajaton ja erehtymätön. Siksi pieni ihminen ei koskaan ajattele lukevansa viestiä ennen, jos hän ei ole lukenut, älä koskaan unohda, että hän on lukenut viestin aiemmin, joten ei koskaan, koskaan, koskaan tuota kahta eri numeroa täsmälleen samalle viestille eikä samalle viestille numero kahdelle eri viestille.

   Tätä hash-toiminnot yrittävät simuloida. He eivät voi mallintaa tätä pientä miestä valokuvamuistilla, koska se vaatisi rajattoman tallennustilan ja rajattoman, yleisen saatavuuden, jopa laitteet, joita ei ole kytketty mihinkään muuhun laitteeseen millään muulla tavalla. Sen sijaan ne luottavat deterministiseen, mutta satunnaisesti etsivään laskelmaan, joka ”hajottaa” viestin hash-arvoonsa. Sama hash-toiminto, antaa saman viestin, tuottaa saman tiivistelmän; nämä toiminnot ovat kuitenkin rajoitettuja niiden hash-arvojen lukumäärässä, joita niiden sallitaan palauttaa. Tämä luo mahdollisuuden niin kutsutuille hash-törmäyksille; mahdollisia viestejä on enemmän kuin hash-arvoja, joten ennemmin tai myöhemmin (toivottavasti myöhemmin), kaksi minua ssages tuottaa saman hash-sanan.

3. Hashes voidaan murtaa kolmesta syystä.Ensinnäkin, koska matemaatikot (ja siten hyökkääjät) ovat viestinsä deterministinen, matemaattinen johdannainen, he löytävät lopulta matemaattisen suhteen viestin ja sen hashin välillä tai kahden viestin ja niistä johtuvien hashien välillä. Aikaisemmin satunnainen haku ei ole enää niin. Tämä mahdollistaisi useita hyökkäyksiä havaitun heikkouden luonteen perusteella; jos on olemassa algoritmisella tavalla annettu viesti ja sen hash, törmäysviestin luomiseksi, se on ongelma. Jos on tapa manipuloida viestiä ja ennustaa tuloksena oleva hash, se on erilainen ongelma. Jos tosiasiassa on tapa kääntää hajautus, tuottaa hajautusviestistä viesti, joka uudelleenhajautettuna tuottaa saman hajautusmerkin, että ”sa vakava ongelma.

   Toiseksi, koska hashilla on rajoitettu tiivistekoko, ennemmin tai myöhemmin kaksi viestiä tuottaa saman hashin. Tämä tarkoittaa, että hyökkääjän ei tarvitse löytää viestiä, jota käytät tietyn hashin tuottamiseen. ; hänen on vain löydettävä a viesti, joka tuottaa saman tiivisteen. Tämän todennäköisyydet ovat vähäiset, teoriassa yksi mahdollisuus monista mahdollisista hajautuksista, mutta silti parempi kuin yksi äärettömässä.

   Lopuksi, vaikka viestejä on paljon, on paljon pienempiä todennäköisten viestien määrä. Hajautustoiminnoille tyypillisesti antamillamme viesteillä on yleensä jonkinlainen rakenne (kielen, aiheen, sähköisen muotoilun ja tarkoituksen perusteella), mikä tarkoittaa, että tietyn osan viestistä voimme arvata tarkemmin sanoman muut osat. Informaatiotieteellisesti tämä tarkoittaa sitä, että hashiksi muunnetuilla viesteillä on usein alempi entropia kuin itse hash-funktiolla; selkeästi sanottuna hash-funktio, joka tuottaa 256-bittisiä pilkkuja, voi teoreettisesti tuottaa minkä tahansa permutaation näistä biteistä, 2 ^ 256. Jos kuitenkin on sanottuna vain 10000 mahdollista viestiä, jotka voidaan koskaan syöttää tähän hash-toimintoon hyökkäystä varten tutkittavan järjestelmän avulla, vain 10000 2 ^ 256 mahdollisesta hash-arvosta näkyy koskaan, ja mikä tärkeintä, hyökkääjän olisi pahimmassa tapauksessa vain kokeiltava kaikkia 10000 mahdollista syötettä löytääkseen etsittävän hash-arvon tuottavan.

Kommentit

• Ja tästä syystä rakastan IT-tietoturvaa ’ s pinonvaihtosivusto.
• Myös selityksesi / 1 on juuri sitä mitä tarvitsin. Minulla on kuitenkin kysymys. Vaikuttaa siltä, että ” hashit ” ovat kuin tietyn asian numeroversiot (tässä tapauksessa salasanat). Joten jos minulla on verkkosivusto ja 100000 ihmistä kirjautuu. Sitten 50% käyttää salasanaa ” salasana ” Pystyn säästämään tonnia tilaa tallentamalla vain ” salasana ” salasanan sijaan monta kertaa?
• No, jos ’ käyttää suojattua tiivistettä (> = 256-bittinen tiivistekoko) ja tallentaa sitten ” salasanan hajautetun arvon ” lisää tallennustilan kokoa. Lisäksi, jos hyökkääjä joskus huomaa, että 50 prosentilla käyttäjätileistä oli sama salasanan tiiviste, hän ’ tiesi tietävänsä, että kaikki hän ’ d täytyy vain murtaa yksi salasana ja hänellä on pääsy 50 prosenttiin käyttäjätileistä. Sinun tulisi olla ” suolattu ” salasanasi hajautus; menetelmiä on useita, mutta lopputulos on, että sama salasana, joka on tiivistetty samalla algoritmilla, tuottaa erilaisen tiivistelmän, koska jokaisella tilillä on ylimääräinen ainutlaatuinen suola-arvo.