Jūsų failų pirštų atspaudų paėmimas

Trys Stenfordo universiteto kriptografai neseniai sugalvojo protingą nuolatinės tapatybės vagystės internete problemos sprendimą. Apsukrūs įsilaužėliai Rusijoje, Kinijoje ir kitose šalyse siunčia krūvas el. pašto žinučių, atrodančių, lyg būtų gautos iš kokios nors finansinės institucijos, tokios kaip „Citibank“ ar „Paypal“. Milijonai vartotojų gauna šiuos pranešimus, kuriuose yra įterptos HTML nuorodos, kurios nukelia nieko neįtariantį gavėją į panašias svetaines, veikiančias tolimose vietose. Būsite paraginti įvesti vartotojo vardą ir slaptažodį, tada įsilaužėlis turi jūsų banko sąskaitos raktus.

Tačiau geri naudotojų vardai ir slaptažodžiai, įvesti blogose svetainėse, nėra vienintelė tokia grėsmė, su kuria susiduria vartotojai. Galbūt didesnė problema yra ta, kad daugelis žmonių naudoja tą patį vartotojo vardo ir slaptažodžio derinį keliose svetainėse. Tai palengvina įsiminimą, tačiau tai reiškia, kad nesąžiningas svetainės operatorius gali paimti vartotojų vardų ir slaptažodžių sąrašą iš, tarkime, internetinių loterijų svetainės ir panaudoti jį bandydamas įsilaužti į internetines banko sąskaitas.

Taigi Stanfordo kriptografai Blake'as Rossas, Danas Bonehas ir Johnas Mitchellas sukūrė protingą „Internet Explorer“ papildinį, kuris išsprendžia šią problemą, koduodamas tai, ką įvedėte į slaptažodžio lauką, kad kiekviena svetainė matytų skirtingą slaptažodžio slaptažodį, kuris priklauso nuo to, ką įvedėte. ir pačios svetainės domene.

Dabar daugelis žmonių naudoja tam tikrą šios strategijos variantą. Jų „Hotmail“ slaptažodis gali būti „nosmis-hotmail“, o „Yahoo!“ Asmeninis slaptažodis yra nosmis-Yahoo! Tačiau bet kokią tokią strategiją iššifruoti gana paprasta. Slaptažodžių kodavimo metodas, kurį sukūrė Stenfordo trijulė, yra pagrįstas matematine funkcija, vadinama kriptografine maišos rūšimi, vienpuse funkcija, kuri vartotojo įvestą informaciją paverčia skaičių ir raidžių kratiniu tokiu būdu, kurio negalima pakeisti. Kadangi Stanfordo sistema apskaičiuoja ir svetainių domeno, ir vartotojų slaptažodžio kriptografinę maišą, įsilaužėlis gauna skirtingus slaptažodžius nei teisėti. (Spustelėkite čia Norėdami sužinoti daugiau apie šį protingą sprendimą.)

Viena įmonė, kuri labai viešai naudoja kriptografines maišas, yra Yahoo! Praėjusiais metais Yahoo! perkūrė prisijungimo prie savo svetainės procesą, kad jis būtų apsaugotas nuo kvapo. Standartinis būdas tai padaryti yra naudoti šifravimą. Tačiau šifravimas gali būti lėtas, ypač kai naudojate vieną iš populiariausių interneto svetainių.

Taigi ką Yahoo! Vietoj to jis pakeitė savo prisijungimo puslapį, kad būtų naudojama vadinamoji iššūkio atsako sistema, pagrįsta kriptografine maiša. Kai bandote prisijungti, „Yahoo!“ serveris į jūsų naršyklę atsisiunčia kriptografinę maišos funkciją, parašytą „JavaScript“. Kartu su šia funkcija yra iššūkis trumpa raidžių ir skaičių seka. Kai įvedate slaptažodį prisijungimo ekrane, jūsų naršyklė paima jūsų slaptažodį, prideda šiuos „Yahoo!“ pateiktus simbolius ir apskaičiuoja gautos eilutės kriptografinę maišą. Tada naršyklė siunčia gautą reikšmę atgal į Yahoo!, šifravimo nereikia. Net jei esate kibernetinėje kavinėje, kur jūsų žiniatinklio srautą užuodžia Belgijos įsilaužėliai, blogi vaikinai negali paimti gautos maišos reikšmės ir išvesti jūsų pradinį slaptažodį.

Ši sumani iššūkių ir reagavimo sistema taip pat yra „Mobil Speedpass“ sistemos pagrindas: dėl to „Speedpass“ radijo dažnio identifikavimo (RFID) žymą taip sunku klonuoti. Kitos RFID sistemos nenaudoja iššūkio atsako, todėl jas užpulti yra gana lengva.

Bet kas yra ši kriptografinė maišos funkcija?

Neįtikėtinai naudinga maiša

Kriptografinės maišos funkcijos yra vienas iš pagrindinių šiuolaikinės skaitmeninės ekonomikos elementų. Nepaisant to, jie daugeliu atžvilgių lieka paslaptimi juos kuriantiems kriptografams ir plačiajai visuomenei, kuri jas naudoja kiekvieną dieną.

Maišos funkcijos kartais vadinamos pirštų atspaudų funkcijomis, nes jas galima naudoti norint sukurti unikalų skaitmeninio failo piršto atspaudą. Pirštų atspaudai paprastai yra 128 bitų arba 160 bitų skaičiai, kurie rodomi kaip šešioliktainių skaitmenų seka. Pavyzdžiui, mano vardo piršto atspaudas naudojant MD5 sistemą yra c55bbe0f3ba258f5b1cb6d5b62b0b360. Maišos funkcijos sukurtos taip, kad bent jau teoriškai dviejų failų maišos vertė nebus tokia pati.

Kad galėtumėte suprasti, kaip veikia šios pirštų atspaudų funkcijos, toliau įdėjome JavaScript pagrįstą MD5 skaičiuotuvą. Tiesiog įveskite tekstą ir pamatysite MD5 maišą. Pastebėkite, kaip ji visiškai pasikeičia kiekvieną kartą, kai pridedate, pašalinate ar pakeičiate raidę. Pirštų atspaudų pasikeitimo būdas iš tikrųjų yra nenuspėjamas, jei galėtume numatyti, kaip jis pasikeis, failų pirštų atspaudai nebūtų labai naudingi.

Įveskite savo tekstą žemiau:

MD5 yra:

Dauguma šiandien naudojamų maišos funkcijų yra pagrįstos MIT profesoriaus Rono Rivesto devintajame dešimtmetyje sukurta technika. (Rivest tikriausiai geriausiai žinomas kaip RSA šifravimo algoritme, viešojo rakto šifravimo algoritme, kuris yra praktiškai kiekvienoje žiniatinklio naršyklėje.) Tuo metu Rivest ir kiti matematikai tobulino pagrindinių kriptografinių operacijų, kurias mes atliekame, detales. dabar laiko savaime suprantamu dalyku. Maišos funkcijos buvo įsivaizduojamos kaip tam tikra kriptografinė glaudinimo sistema, leidžianti paimti didelį failą ir sutrumpinti jį iki trumpos raidžių ir skaičių eilutės.

Idėja buvo panaudoti šiuos pirštų atspaudus kaip savotišką pačių failų pakaitalą. Užuot pasirašę visą failą skaitmeniniu būdu, samprotavo Rivest ir kiti, galite skaitmeniniu parašu pasirašyti maišą. Kadangi viešojo rakto kriptografija apima daug sunkios matematikos, maišos funkcijos leidžia beveik taip pat greitai pasirašyti itin ilgą failą, kaip pasirašyti trumpą failą.

Vienas iš pagrindinių dalykų, kurį galite padaryti naudodami maišos funkciją, yra sužinoti, ar failas pasikeitė: tiesiog apskaičiuokite failo maišą ir užsirašykite. Vėliau dar kartą apskaičiuosite maišą. Jei maiša nepasikeitė, tada yra didžiulė tikimybė, kad failas taip pat nepasikeitė.

Pavyzdžiui, tarkime, kad savo smulkaus verslo finansus saugote naudodami „QuickBooks“ ir norite kelioms dienoms išvykti atostogų: žmonėms reikia naudotis jūsų kompiuteriu, bet jūs norite įsitikinti, kad niekas nekeičia „QuickBooks“ duomenų. Vienas paprastas dalykas, kurį galite padaryti, tai prieš išeidami apskaičiuoti failo kriptografinę maišą ir įrašyti numerį rodyklės kortelėje. Kai grįšite iš atostogų, tiesiog iš naujo apskaičiuokite maišą. Jei dvi reikšmės nesutampa, žinote, kad failas buvo sugadintas.

Žinoma, jums nereikia sustoti tik su vienu failu. Galite apskaičiuoti kiekvieno kompiuteryje esančio failo kriptografinę maišą ir sudėti juos į naują failo iškvietimą, kuris yra failas hashes.txt. Tada galite apskaičiuoti failo hashes.txt maišą ir įrašyti šį piršto atspaudą savo užrašų kortelėje. Pakartokite procesą, kai grįšite iš atostogų ir turėsite greitą būdą sužinoti, ar pasikeitė koks nors failas visame kompiuteryje. (Neturėsite jokio būdo žinoti, kuris failas pasikeitė, bet tai yra kita problema.)

Ši maišos maišos skaičiavimo idėja yra įsibrovimo aptikimo sistemos, vadinamos Tripwire, pagrindas, kurį 1990-ųjų pradžioje išrado Purdue universiteto kompiuterių mokslų profesorius Gene Spafford ir jo absolventas Gene Kimas. (Spaffordas ir aš kartu esame parašę penkias knygas apie kompiuterių mokslą.) Šiandien daugelis skirtingų programų naudoja šį Tripwire metodą, kad užtikrintų kompiuterių failų ir duomenų bazių vientisumą.

Maišos maišos skaičiavimas taip pat yra saugios laiko žymos paslaugos, kurią išrado Stuartas Haberis ir Scottas Stornetta, kai jiedu dirbo Bellcore 1990 m., pagrindas. Paslauga, vadinama Surety, leidžia sukurti kriptografiškai saugų ir nepakartojamą įrodymą, kad tam tikras dokumentas , nuotrauka ar kitas failas egzistavo tam tikru metu tam tikrą datą ir nuo to laiko jis nebuvo pakeistas.

Laidavimo technika veikia apskaičiuojant maišos medį pagal kiekvieno dokumento, pažymėto laiko žyma, maišos kodus. Tada medžio šaknis paskelbiama gerai žinomoje vietoje, ji gali būti, pavyzdžiui, atspausdinta klasifikuotame skelbime Niujorko laikas . Galite įrodyti, kad atitinkamą dieną jūsų dokumentas egzistavo, parodydami, kad jūsų dokumentų piršto atspaudas buvo reikalingas norint sukurti laikraštyje pasirodžiusius pirštų atspaudų atspaudus.

Kitos įmonės ir net JAV pašto tarnyba nuo tada sukūrė savo elektroninę laiko žymų paslaugą. Tačiau visos šios sistemos priklauso nuo organizacijos, kuri veikia kaip patikima trečioji šalis, kuri iš tikrųjų pasirašo jūsų dokumentą naudodama savo privatų raktą. Šio metodo problema yra ta, kad trečioji šalis turi būti visiškai patikima: jei ta trečioji šalis nusprendžia sukurti parašą su neteisinga data arba kokiam nors įsilaužėliui pavyksta pavogti trečiosios šalies privatų raktą, nėra jokio būdo atskirti apgaulingą parašą nuo galiojančio. Žinoma, taip pat galima sukurti apgaulingus laidavimo parašus, tačiau jums reikės arba grįžti į praeitį ir pakeisti tai, kas buvo išspausdinta Niujorko laikas , arba keliaukite po visą pasaulį, suraskite kiekvieną išspausdintą kopiją ir pakeiskite senus pirštų atspaudus nauju.

Kaip veikia maišos funkcijos

Štai kodėl maišos funkcijos yra naudingos. Dabar pažiūrėkime, kaip jie iš tikrųjų atrodo.

Tarp šiandien plačiausiai naudojamų maišos funkcijų yra vadinamoji MD5 (5 pranešimų santraukai). MD5 sukuria 128 bitų ilgio maišą, kuri paprastai rašoma kaip 32 šešioliktainių (16 bazinių) skaitmenų seka. Jei paimtumėte mano vardą ir apdorotumėte jį naudodami MD5, gautumėte šią iš pažiūros atsitiktinę eilutę:

c55bbe0f3ba258f5b1cb6d5b62b0b360

Arba matematiškesniu formalumu pasakyti:

MD5 (Simson Garfinkel) = c55bbe0f3ba258f5b1cb6d5b62b0b360

Kiekvienas iš tų šešioliktainių ženklų reiškia 4 bitus; mano vardo MD5 reikšmė iš tikrųjų yra:

1100010101011011101111100000111100111011101
0001001011000111101011011000111001011011011
010101101101100010101100001011001101100000

Dauguma žmonių dirba su šešioliktainiu vaizdavimu, nes gana lengva pažvelgti į dvi maišas ir pasakyti, ar jos yra vienodos, ar skirtingos.

MD5 veikia padalijant failą į daugybę mažų gabalėlių, o po to paimant kiekvieną iš tų dalių ir atliekant šimtus matematinių operacijų, kurios sumaišo, apverčia, perkelia ir kitaip apdoroja bitus į neatpažįstamą netvarką. Žodis neatpažįstamas šiame aprašyme yra pagrindinis. Pagrindinis geros maišos funkcijos reikalavimas yra tai, kad būtų neįmanoma nuspėti failo pirštų atspaudų, nesistengiant iš tikrųjų apskaičiuoti šio piršto atspaudo, neturi būti jokių trumpųjų klavišų. Jei būtų, galbūt galėtumėte paleisti maišos funkciją atgal ir sukurti failą, kuriame būtų tam tikra maiša, pavyzdžiui, kito failo maiša. Iš tiesų, visas maišos funkcijų saugumas visiškai sugenda, jei įmanoma sugeneruoti du failus, turinčius tą pačią maišą.

Maišos funkcijos grožis yra tas, kad net ir nedidelis įvesties pakeitimas dramatiškai pakeičia išvestį. Matematiškai funkcijos sukurtos taip, kad kiekvienas išvesties bitas turės 50 procentų tikimybę, kad pasikeis kiekvieną įvestyje pakeistą bitą.

Pažvelkime į kitą MD5 maišą, šiek tiek kitokį mano vardo atvaizdavimą:

MD5 (Simson L. Garfinkel) = df876e8e6f548d5be698fab7f06dd278

Vien tik pridėjus L. gaunama visiškai kitokia maiša. Jei palyginsite du maišus bitai po bitų, pamatysite, kad 63 iš 128 pozicijų pasikeitė iš 0 į 1 arba 1 į 0, o kitos 65 liko nepakitusios.

Deja, visa kriptografinių maišos funkcijų teorija turi didžiulę problemą. Šių funkcijų naudojimas reikalauja, kad nebūtų vadinamųjų susidūrimų. Netyčia ar tyčia neturėtų būti dviejų failų, turinčių tą patį kriptografinį pirštų atspaudą. Ir, kaip paaiškėjo, tai yra neįmanomas reikalavimas.

Priežastis gana paprasta. Failo pirštų atspaudai yra fiksuoto dydžio, o tai reiškia, kad galimų pirštų atspaudų skaičius yra ribotas. Kita vertus, failai gali būti bet kokio dydžio. Taigi galimų failų yra daugiau nei pirštų atspaudų, todėl turi būti bent vienas piršto atspaudas, kuris yra kelių failų pirštų atspaudas. Matematinis terminas tam yra „pieonhole“ principas. Iš tiesų, net jei apsiribojate failais, kurių ilgis yra tik devyni simboliai, galimų failų skaičius vis tiek yra 256 kartus didesnis už galimų pirštų atspaudų skaičių.

Priežastis, dėl kurios pagal „pieonhole“ principą maišos funkcijos nepadaro visiškai beprasmiškų, yra ta, kad galimų pirštų atspaudų yra stulbinančiai daug daugiau, nei failų planetoje. (Su MD5 galimi 2128 pirštų atspaudai. Dabar bendras kompiuterių standžiųjų diskų, kurie kada nors buvo pagaminti, skaičius yra tik apie 229. Jei kiekviename standžiajame diske būtų milijonas unikalių failų, o tai būtų pervertinta, vis tiek būtų tik 249 atskiri failai. Tai daug , daug, daug mažesnis skaičius nei 2128.)

SHA-1 ginčas

Mokymo tikslais naudojau MD5 maišos funkciją. Tačiau šiomis dienomis laikomas MD5 praeiti vietoj to dauguma pasaulio pereina prie JAV vyriausybių saugiojo maišos algoritmo, žinomo kaip SHA-1, standarto, kurį Nacionaliniai standartų ir technologijų institutai (NIST) priėmė dar 10-ojo dešimtmečio pradžioje.

Šiandien SHA-1 yra plačiai gerbiamas algoritmas, tačiau jo istorija yra sudėtinga. Dar 1993 metais JAV vyriausybė bandė priversti pramonę pritaikyti vadinamąją Clipper Chipa slaptą šifravimo sistemą, kurią sukūrė Nacionalinio saugumo agentūra. Per vadinamuosius kriptovaliutų karus, kurie siautėjo aplink Clipper, NIST pasiūlė JAV vyriausybei patvirtinti savo saugaus maišos algoritmą kaip dalį Federalinių informacijos apdorojimo standartų. Dėl techninių priežasčių maišos funkcijos turėtų turėti dvigubai daugiau bitų nei šifravimo algoritmai, su kuriais jos veikia. Clipper buvo 80 bitų šifravimo algoritmas, todėl standartas buvo sukurtas 160 bitų pirštų atspaudams gaminti.

Galima manyti, kad vyriausybės standartas su 160 bitų pirštų atspaudais būtų saugesnis nei 128 bitų MD5. Tačiau, kaip ir patį Clipper, SHA sukūrė Nacionalinė saugumo agentūra, o NIST ir NSA atsisakė paaiškinti principus, kurie buvo naudojami kuriant jį. Kai kurie žmonės svarstė, ar NSA galėjo paslėpti kažkokias užpakalines duris algoritme, kad agentūra galėtų generuoti susidūrimus pagal poreikį. Tokios užpakalinės durys galėtų būti naudojamos, pavyzdžiui, padirbtiems skaitmeniniams parašams gaminti, kas gali būti naudinga Centrinei žvalgybos agentūrai. Suklastotas skaitmeninis parašas gali būti naudojamas, pavyzdžiui, pasirašyti elektroninį įsakymą, suteikiantį JAV šnipui prieigą prie duomenų bazės užsienio šalyje.

Daugybė kriptografų ir kitų akademikų analizavo SHA algoritmą ir nerado nieko blogo. 1993 m. gegužės 11 d. NIST paskelbė, kad SHA yra saugaus maišos algoritmas. Tačiau rašalas vos išdžiūvo, kai NIST paskelbė, kad padarė klaidą. Dėl priežasčių, kurios tuo metu nebuvo atskleistos, NIST paskelbė modifikuotą Secure Hash Algorithm algoritmo, kurį dabar vadiname SHA-1, versiją.

Sąmokslo teoretikai kriptografijos bendruomenėje (o jų yra daug) turėjo lauko dieną. Ar SHA buvo tokia galinga, kad NSA nusprendė, kad ją reikia nutildyti? O gal NSA SHA pastatė užpakalines duris ir kažkas iš NIST tai sužinojo? Ar abu algoritmai buvo vienodai saugūs, o NSA kriptografai tiesiog maišėsi su žmonių protais?

1998 m. rugpjūčio mėn. pasaulis daugiau ar mažiau sužinojo atsakymą į SHA prieš SHA-1 mįslę. Florentas Chabaud ir Antoine'as Joux, du prancūzų kriptografai, sugalvojo teorinę ataką prieš pirmąją SHAan atakos versiją, nuo kurios SHA-1 tiesiog buvo apsaugotas. Beveik neabejotinai NSA žmonės žinojo apie šį išpuolį ir pasiūlė SHA-1 kaip atsakomąją priemonę. Įdomu tai, kad NSA kriptografai tikriausiai nežinojo apie ataką, kai SHA pirmą kartą buvo pasiūlyta 1993 m., o tai reiškia, kad geriausia pasaulyje kriptografijos agentūra tik penkeriais metais lenkė kriptografus akademinėje bendruomenėje.

Šiandien maišos funkcijos taip pat dažnai naudojamos generuoti pasikartojančius, bet nenuspėjamus atsitiktinius skaičius, konvertuoti įvestus slaptažodžius į reikšmes, tinkamas naudoti kaip šifravimo raktus. Vietoj to, kad slaptažodžiai būtų saugomi tiesiogiai, daugelis kompiuterių sistemų saugo slaptažodžio maišą. Tai neleidžia asmeniui, kuris įsilaužė į kompiuterį, sužinoti visų slaptažodžio.

Maišos funkcijos buvo pasiūlytos kaip būdas kovoti su šiukšlėmis ir kaip skaitmeninių grynųjų pinigų sistemų pagrindas. Matematikas Peteris Wayneris išleido knygą pavadinimu Permatomos duomenų bazės Prieš kelerius metus jis parodė, kaip maišos funkcijos gali būti naudojamos informacijos saugojimui duomenų bazėje tokiu būdu, kurį saugo duomenų bazę valdanti organizacija. Pavyzdžiui, kolegijos priėmimo skyrius galėtų saugoti studentų socialinio draudimo numerius duomenų bazėje, kad šie numeriai vis tiek galėtų būti naudojami kaip identifikatoriai prašymuose, bet kad niekas priėmimo skyriuje negalėtų atsisėsti prie terminalo ir gauti studentų sąrašo. ir jų numeriai. Tačiau iki šiol nė vienas iš šių metodų dar nepasirodė.

Apskritai, kriptografinės maišos yra viena įdomiausių ir naudingiausių matematinių metodų, kuriuos kriptografai sugalvojo per pastaruosius 20 metų ir vis dar ieškojo naujų jų panaudojimo būdų.

paslėpti