Paar väikest nalja räsifunktsioonide teemal

cryptography0Olles natuke räsifunktsioonide üle mõtisklenud, jõudsin järgneva 2 mõtteni.

Mõte 1 Kui vanade räsifunktsioonide peamine probleem seisneb selles, et ründaja oskab räsist tuletada andmeid, mille peale räsifunktsioon antud räsi tagastab, peenemalt öeldes, ründaja oskab leida kollisioone, siis üks viis, kuidas vanu, “mitte-liiga-puruks”, räsifunktsioone ikkagi kasutada saab, on selline:

sõne_1="See tekst on varjatav, näiteks parool"
sõne_2="avalikult teada olev muinasjutt".concat(sõne_1)
sõne_3="mõni teine avalikult teada olev muinasjutt".concat(sõne_1)
kollisioonide_hulk_1 = leia_kollisioonid(murtud_räsifunktsioon, sõne_1)
kollisioonide_hulk_2 = leia_kollisioonid(murtud_räsifunktsioon, sõne_2)
kollisioonide_hulk_3 = leia_kollisioonid(murtud_räsifunktsioon, sõne_3)
tugev_räsifunktsioon(sõne_1) =
=murtud_räsifunktsioon(sõne_1).concat(
murtud_räsifunktsioon(sõne_2)).concat(
murtud_räsifunktsioon(sõne_3))

Mõte seisneb selles, et kollisioonide hulkade 1,2,3 ühisosa ei pruugi peale sõne_1’st koostatud sõnede ühisosi omadagi. Eeldus on, et murtud_räsifunktsioon siiski ei ole nii murtud, et funktsioon leia_kollisioonid(…) oma vastuse mõne minuti jooksul tagastab. Kui NSA arvutuskeskus peab funktsiooni leia_kollisioonid(…) ühekordse käivitamise korral kulutama 1h ja aastas on 365*24h=8760h, siis see ~9k-räsi üksteise otsa panna, sundides No-Such-Agency nimelisi asutusi terve aasta megavattidest arvutatud elekri-arveid tasuma, on juba päris suur võit.

Mõte 2

Mis puutub paroolide räsidesse, siis kuni 15 tähemärgini, võimalik, et paarikümne tähemärgini, rääkimata sõnaraamatutest automaatselt kombineeritud tähemärgijadade komplektist, on No-Such-Agency nimelistel asutustel tõenäoliselt räisid juba ette ära arvutatud ning ma üldse ei imestaks, kui erinevad valitsused “luurealase koostöö raames” neid tabeleid omavahel ka jagavad, umbes nagu enne arvutite kasutuselevõttu logaritmide tabeleid paber-raamatutena publitseeriti. Sellise ründe üheks vastumeetmeks võib proovida midagi sellist:

sõne_P1="parool".concat(
"vähemalt 100 märgine pikk, avalik, muinasjutt").concat(
kasutajanimi)
serveris_salvestatav_parooliräsi=veel_mittemurtud_räsifunktsioon(sõne_P1)

Sedasi tuleb Agentuuridel veel_mittemurtud_räsifunktsioon’i tabelid iga kasutaja jaoks eraldi arvutada ning tänu pikale, avalikule, muinasjutule, peaksid senised sõnaraamatutest koostatud tabelid, ideaal-juhul, muutuma suht kasutuks.

 Mõte 3, pealkirjaga “HashTXOR”

Teatavasti “one-time-pad”‘‘i korral on matemaatiliselt tõestatud, et see on põhimõtteliselt murdmatu krüptoalgoritm. “One-time-pad” eripära on, et võtit kulub sama palju, kui on andmeid ning võtit ei tohi korduv-kasutada. Niiöelda “turvalise räsifuntsiooni” ehk veel_mittemurtud_räsifunktsioon’i eripära on, et tema väljundist ei ole võimalik hetkel teada olevate meetodite ja riistvaraga sisendit tuletada. Neid 2 asja kokku pannes:

N=avalik, positiivne, täis-arv, 0,1,2,3,4, … sisuliselt massiivi indeks

muinasjutt_1=”Avalik, pikk, kuid pseudojuhuslik, muinasjutt, mis võib sisaldada näiteks muinasjutu genereerimise kuupäeva, päeva kõige ülbeima poliitiku tiitli pälvinud poliitiku nime, ilm.ee andmestikku, jne.”

salajane_võti=”Vähemalt 10KB suurune tekst”

võtmetükike_N=veel_mittemurtud_räsifunktsioon(toString(N).concat(muinasjutt_1).concat(salajane_võti))

krüptoteksti_tükike_N=XOR(võtmetükike_N,avatekstitükike_N)

Kürptotekst koosneb päisest, milleks on muinasjutt_1, ning krüptoteksti tükikeste massiivist. Kui XOR’i asemel kasutada minut.ee’s varemgi jutuks olnud funktsiooni TXOR, siis on võimalik kirjutada selline demo.

Tänan lugemast. :-)

2 arvamust “Paar väikest nalja räsifunktsioonide teemal” kohta

  1. Kõigepealt tänan toimetajat õnnestunud pildivaliku eest. :-)

    Artikkel oli küll pea-asjalikult räsifunktsioonidest, mille korral on oluline, et räsist ei oleks võimalik tuletada räsifunktsiooni sisendit, peenemalt öeldes, kujutisest ei õnnestu tuletada originaali, kuid programmeerimiskeeltes kasutatavate paisktabelite realisatsioonide korral pole selline omadus oluline. Paisktabelite (Java Map liidesega klassid, PHP massiiv, jne.) realisatsioonis on hoopis olulisim omadus kiirus, “vähene” (mida iganes see tähendab) mälukasutus ning asjaolu, et üks ja sama räsi ei vastaks “liiga paljudele” sisenditele.

    Kui mõelda, et praktiliselt kõigis programmeerimiskeeltes on paisktabelid kui andmestruktuurid laialdaselt kasutusel, isegi C++ stdlib toetab 2014. aastal paisktabeleid, siis rakendused muutuksid ilmselgelt oluliselt kiiremaks, kui CPU-d pakuks paisktabelitele massiivide sarnast riistvaralist tuge. Üheks niiöelda klassikaliseks linna-legendiks on, et riistvara areneb meeletu kiirusega ning tarkvara lohiseb järel. Hetkel näen, et pigem on asi vastupidi: praktiliselt kõik programmeerimiskeeled, kui ehk assembler välja arvata, kasutavad paisktabeleid, kuid parim, mida riistvara pakub, on mõne konkreetse krüptoalgoritmi kiirendi (Ubuntu: apt-get install tpm-tools) ning võibolla mõned SIMD käsud.

    Vanasti CPU-d ujukoma-arvudega liitmist-lahutamist riistvaraliselt ei toetanud. Kasutati spetsiaalset ujukoma-arvude lisa-protsessorit. Umbes aastal 2004 (ma täpselt ei mäleta, keskkooli lõpetasin aastal 2000 ja siis ei teadnud ma IT-st veel suurt midagi) ekstrapoleerisin ujukoma-arvude lisa-protsessoriga toimunut tulevikku, märgates, et ujukoma-arvude korral oli alguses eraldi seisev riistvara, lisa-protsessor, mis integreeriti CPU-koosseisu, ning graafika-kaart on samuti praktiliselt igas arvutis kasutusel, mistõttu osaliselt GPU-põhiste arvutuste laiema kasutuselevõtu tingimustes integreeritakse graafikakiirendi CPU-sse. Nagu näha, mu ennustus läks täppi. Samas vaimus jätkates ennustan, et tulevikus integreeritakse CPU-sse ka mõni umiversaalsem versioon hetkel pea-aegu igas arvutis emaplaadil olemas olevast, eraldi seisvast, krüpto-kiibist ning üks esimesi seltskondi, kes sellise lahenduse kasutusele võtab, on just tahvel-arvutite ja mobiiltelefonide tootjad, sest programmeerimiskeeltes laialt kasutusel olevate paisktabelite riistvaraline toetamine võimaldab rakendustarkvara sama elektri-tarbe ning CPU-taktide koguse korral oluliselt kiiremini jooksutada kui see ilma sellise riistvaralise kiirenduseta võimalik on.

    Tänan lugemast. :-)

    P.S. Palun öelge mulle, kus ma eksin. :-D

  2. Seoses ühe oma veidra asjatamisega sattusin telefonikõnede pealt-kuulamisest 10 minutiks natuke mõtisklema ning jõudsin mõttele, et kuna korraliku räsi-funktsiooni räsi välja-arvutamine on niivõrd arvutusmahukas, et 2014. aasta telefonid seda oma tava-CPU-ga reaal-ajas teha ei jõua, siis võib lahendus olla selline, et siin lõimes eelnevalt mainitud HashTXOR võtit võiks telefon ette välja arvutada ajal, mil ühtegi telefonikõnet ei toimu.

    Nii kui nii moodustavad telefonikõned telefoni elu-ajast imeväikese osa, mis tähendab, et telefonikõnede vahelisel ajal võtme ette välja arvutamiseks on aega küll ja küll. Kui inimesed on harjunud, et telefoniga lõputult rääkida ei saa, sest aku saab tühjaks, siis võiks ette-arvutatud võtme otsa saamisest tulenev piirang talutav olla. Erinevatele kontaktidele võib aga võitit ette arvutada telefonis endas oleva kõnede statistika järgi: neile, kellega rohkem räägitakse, arvutatakse rohkem, pikem jupp, võtit ette kui ülejäänutele. Enamik telefonikõnesid on nii kui nii vaid 3 minutit ning tänapäeval saab umbes 7GiB suuruse klass-10 (lugeda: salvestamisel-lugemisel kiire) mälukaardi umbes 7€ eest, mistõttu kogu telefoniraamatu jagu ette-arvutatud võtmete hoidmiseks võiks ruumi jaguda.

    Lühiarvutus

    Vanamoodses GSM’is oli, kui ma nüüd ei eksi, kõne parameetriteks 1B ja 4kHz ehk Nyquist’i teoreemi järgi 8kHz diskreetimis-sagedust kasutades:

    8B*8kHz=64kB/s
    Arvestades, et GSM’i helikvaliteet on paras käkk, siis MP3 failide helikvaliteeti ja ZIP’i tulemusi natuke intuitiivselt aluseks võttes,

    192kbps = (192k/8)B/s = 24kB/s ~ 24KB/s
    ffmpeg tegi ~9MiB suurusest, ~6min=6*60s=360s pikkusest, MP3-failist ligikaudu 32MiB suuruse WAV-faili, mille bzip2 suutis kokku pakkida ligikaudu 22MiB suuruseks failiks. Programm nimega xz suutis erinevate sõnaraamatu-suurustega luua antud WAV-failist samuti ligikaudu 23MiB suuruse faili, mistõttu väide, et piisab andme-edastus- ning krütpimis-kiirusest 9MiB 6 minuti kohta, on üpris kuhjaga optimistlik. Teisest küljest, 9MiB on 32MiB’st ligikaudu 35% ehk kui võtta andmemahuks 36MiB 6 minuti kohta ehk ~6MiB/minutis, siis kuluks 400 telefoniraamatus oleva inimese jaoks 3min. kõne-aja võtmete salvestamiseks

    400inimest * 6MiB/minutis * 3minutit * 5B-korralikku-räsi-1B-avateksti-kohta = 36000MiB ~35.2GiB

    ~59GiB suurune, klass-10, mälukaart maksab 2014_05 seisuga ligikaudu 50€.

    Tänan lugemast. :-)

Kommenteerimine on suletud