Bitturmixolás: véletlenszámok, titkosítás és hash függvények

Tudjuk, hogy a számítógép a programokban adott műveleteket determinisztikusan végzi el. Azaz ugyanazoknál a bemenő adatoknál ugyanaz a program ugyanazt a kimenő adatot állítja elő. Kérdés az, hogy akkor hogyan tudunk véletlenszámokat gyártani? Mert ilyesmire rendszeresen szükségünk van. Például ha kártyajátékot írunk, a programnak tudnia kell véletlenszerű leosztásokat kitalálni.

Két lehetőségünk van. Az egyik út az, hogy valamilyen fizikai folyamat alapján állítunk elő véletlenszámot. Mondjuk az elektronok véletlenszerű, ide-oda mozgása okozta zajt érzékeljük. (Ilyen zajt hallhatunk, ha a rádiót két csatorna közé állítjuk, ahol nincs semmilyen adó.) Ehhez azonban célhardver szükséges. (A mai számítógépek tartalmaznak hasonlót.) Azt is csinálhatjuk, hogy megkérjük a felhasználót, hogy gépeljen be egy mondatot – és közben nem a beírt betűket figyeljük, hanem a billentyűlenyomások között eltelt időt. Az is elég véletlenszerű, csak hát nem állíthatjuk meg mindig a programot, ha épp véletlenszámokra van szükségünk.

A másik út, hogy imitáljuk a véletlenszámokat. Fogunk egy kiindulási számértéket, osztjuk, szorozzuk, hozzáadunk valamennyit, megcseréljük néhány bitjét, invertáljuk másikakat – az így kapott számot pedig kikiáltjuk véletlenszerűnek. Bár biztosan nem az, ha ügyesek vagyunk, mégis úgy tűnhet, hogy az. Ezek az álvéletlenszámok, vagy más néven pszeudo-véletlenszámok. Ha elindulunk ezen a gondolatmeneten, kiderül, hogy az ilyen bitmágiából érdekes és hasznos dolgokat lehet kihozni.

A legtöbb C függvénykönyvtár szabványos rand() függvénye egy ún. lineáris kongruencia generátor. Ezek a véletlenszámokat egy szorzással, egy összeadással és egy maradékképzéssel imitálják. A Microsoft C függvénykönyvtára például ezt a megvalósítást tartalmazza:

#include <stdio.h>
#include <stdint.h>
 
int main(void) {
    uint32_t allapot = 1;                       /* kiindulás */
 
    for (int x = 0; x < 10; x += 1) {  /* 10 véletlenszám */
        allapot = allapot * 214013 + 2531011;
        uint32_t szam = (allapot >> 16) & 32767;
        printf("%d\n", szam);
    }
    
    return 0;
}

Mit csinál ez? Fog egy allapot nevű változót, amelyet az 1-es kezdeti értékről indít. Megszorozza egy számmal, hozzáad egy másikat – ez lesz az allapot következő értéke. Ezután kivágja ennek a változónak a 31-16. bitjeit, és az így kapott számot nevezi véletlenszámnak. A számítás részletei nem is lényegesek annyira, de egy biztos: ez minden, csak nem véletlenszám. Ha elindítjuk a programot, a kiírt számok mégis eléggé annak tűnnek. Többször indítva viszont azt látjuk, hogy mindig ugyanazt a számsort kapjuk. Ezen úgy segíthetünk, hogy az allapot változó tartalmát, a kiindulási értéket (angolul: seed) más számról indítjuk: éppen ezt teszi az előadáson is említett seed() függvény.

A reprodukálhatóság hasznos tulajdonság tud lenni! Kisorsolhatjuk ugyanazt a kártyaleosztást vagy ugyanazokat a kockadobásokat. Ha egy számítógépes hálózat forgalmát szimuláljuk programunkban, akkor elő tudjuk állítani ugyanazt a forgalomeloszlást. Ha a játékunkban véletlenszerű események történnek, akkor is tudunk könnyedén visszajátszást mutatni a játékosnak arról, hogyan teljesítette a pályát: ehhez elég rögzíteni a lépéseit, a véletlenszerű időpontokban bekövetkezett eseményeket pedig újra kisorsoljuk ugyanattól a számtól indítva a generátort.

Az ilyen, szorzunk-hozzáadunk elven működő véletlenszám-generátorokat lineáris kongruencia generátornak nevezzük a maradékos osztás miatt, ami itt túlcsordulásba van elrejtve (az allapot nevű változó 32 bites). A kódban szereplő konstansok megválasztásának számelméleti alapjai vannak: pl. a hozzáadott szám és a moduló osztója relatív prím kell legyen.

Ha van egy csomó véletlenszerű bitünk, akkor könnyű egy adattitkosító algoritmust csinálni. Az XOR (kizáró VAGY) függvény egy érdekes tulajdonsággal rendelkezik, amit ehhez felhasználhatunk: ugyanis ez a függvény önmaga inverze. Ha egy tetszőleges A számot bármilyen B számmal kizáró VAGY kapcsolatba hozunk kétszer egymás után, akkor visszakapjuk A-t. Ez azért van, mert az XOR függvény az adott biteket invertálja, és a kétszeri invertálás visszaadja az eredetit. Ezt könnyű bizonyítani is:

A titkosítás egyszerű: a titkosítandó szövegben véletlenszerűen invertáljuk a biteket. Fogjuk az üzenetünket, és elkezdünk mellé véletlenszámokat generálni. Az üzenet n-edik bitjét XOR kapcsolatba hozzuk a véletlen bitsorozat n-edik bitjével: így kapjuk a titkosított adatfolyamot. A visszaalakítás ugyanígy történik. A titkosított üzenet n -edik bitjét XOR-oljuk ugyanazon véletlen bitsorozat n-edik bitjével, visszaforgatva az invertált biteket eredeti állapotukba.

A titkosításnak – nagy örömünkre – kulcsa is van, a véletlenszám generátor kiindulási értéke. Ha nem ismerjük a kulcsot, akkor nem leszünk képesek ugyanazt a bitsorozatot előállítani, és ezért a titkosított üzenetet visszafejteni sem, mert nem tudjuk, melyik biteket kell invertálni. Mivel a véletlen bitsorozatban elvileg 50% a valószínűsége mind a 0-k, mind az 1-ek megjelenésének, a titkosított bitsorozatra ugyanez lesz igaz, és egyáltalán nem fog rajta látszani az eredeti bemenetből semmi.

Ezt az algoritmust az alábbi programmal lehet megvalósítani C-ben, az egyszerűség kedvéért a beépített rand() függvényt használva:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char uzenet[] = "Hello, vilag!";

    /* ez megmondja a szöveg hosszát: string-length. */
    int hossz = strlen(uzenet);

    /* eredeti üzenet */
    printf("Eredeti üzenet: ");
    for (int i = 0; i < hossz; i++)
        printf("%c", uzenet[i]);
    printf("\n");

    /* titkosított üzenet */
    srand(12345);                           /* ez a kulcs */
    for (int i = 0; i < hossz; i++)
        uzenet[i] ^= rand() & 0xff;         /* 8 random bit */
    printf("Titkosítva: ");
    for (int i = 0; i < hossz; i++)
        printf("%c", uzenet[i]);
    printf("\n");

    /* újra az eredeti */
    srand(12345);                           /* ugyanaz a kiindulás megint */
    for (int i = 0; i < hossz; i++)
        uzenet[i] ^= rand() & 0xff;         /* 8 random bit */
    printf("Megint az eredeti: ");
    for (int i = 0; i < hossz; i++)
        printf("%c", uzenet[i]);
    printf("\n");

    return 0;
}

Fontos megjegyezni, hogy az egyes C implementációk között a rand() függvény működése eltérő lehet. A szabvány nem írja elő a beépített álvéletlenszám-generátor konkrét működési elvét. Az egyes fordítók által használt rand() függvények legtöbbje egy lineáris kongruencia generátor, de más konstansokat használnak. Ezért ha egy konkrét géptípuson, bizonyos fordító által készített programmal kódolunk egy szöveget, másik gépen vagy másik fordítóval esetleg nem tudjuk dekódolni azt, mert az ottani rand() eltérő számokat generál! Ha szükségünk van pontosan ugyanarra a véletlen számsorra, jobban tesszük, ha beépítünk a programba egy saját generátort.

Egy profibb véletlenszám-generátor beépítésének további indítékai is lehetnek. Ugyanis az egyszerű generátorok bár gyorsak, rendelkeznek néhány nem kívánatos tulajdonsággal. Például ha szabályosság van a kimenetében, akkor a fenti módszerrel titkosított üzenetünkben is lesz szabályosság.

Az írás elején bemutatott algoritmus például a 30546-odik véletlenszámnak ugyanúgy a 41-et hozza ki, mint az elsőnek, és onnantól kezdve a sorozat ismétlődik. Ez nem csak azt jelenti, hogy a periódusa túl rövid: a szemfülesek észrevehetik, hogy a 30546 kevesebb, mint a 32767 (a legnagyobb szám, amit kisorsol). Szóval kell lennie olyan számnak a 0 és a 32767 között, amelyet ez a generátor soha nem állít elő! Sőt azt sem mondhatjuk, hogy egyenletes a generátor kimenete. Ha az előállított számok legalsó bitjét használjuk „fej vagy írás” pénzfeldobásnak…

#include <stdint.h>
#include <stdio.h>
 
int main(void) {
    uint32_t allapot = 1;

    int fej = 0;
    int iras = 0;
    for (int x = 0; x < 30545; x += 1) {
        allapot = allapot * 214013 + 2531011;
        uint32_t szam = (allapot >> 16) & 32767;
        if ((szam & 1) == 0)    /* a legalsó bit */
            fej += 1;
        else
            iras += 1;
    }
    
    printf("%d fej, %d iras.\n", fej, iras); 
    
    return 0;
}

Az eredmény: 15188 fej, 15357 írás. Ez nem pénzfeldobás, hanem inkább egy vajaskenyér: szeret a vajas oldalára esni.

A lineáris kongruencia generátoroknál sokkal jobb eredményt érhetünk el pl. a Mersenne Twister nevű algoritmussal. Ez igen meggyőző tulajdonságokkal rendelkezik: pl. a periódusa 219937-1. Ez egy 6000 számjegyből álló szám! Ha másodpercenként egymilliárd számot generálunk, akkor is 5985 évig tart, mire elölről kezdődik a számsor. Talán a világ összes számítógépén futó összes Mersenne Twister függvényét összesen nem hívták még meg ennyiszer 1997 óta, amikor kitalálták ezt az algoritmust.

A lenti C nyelvű kód ennek megvalósítása. A programban egy 624 elemű, 32 bites számokból álló tömb van, ez tárolja a generátor állapotát. Minden 624-edik véletlenszám kérés után megkeveri ezt a tömböt, egymással invertálva, léptetve, összeadva a benne lévő értékeket. Az előállított számok ebből a tömbből származnak, további léptetésekkel és invertálásokkal „utókezelve”.

#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint32_t mt[624];

    mt[0] = 0;            /* itt lehet állítani a kiindulási értéket */
    for (int i = 1; i < 624; i += 1)
        mt[i] = 0x6c078965 * (mt[i-1] ^ (mt[i-1] >> 30)) + i;

    unsigned index = 0;
    for (int j = 0; j < 10; j += 1) {
        /* 624 kérésenként egy új tömböt keverünk ki*/
        if (index == 0) {
            for (int i = 0; i < 624; i += 1) {
                uint32_t y = (mt[i] & (1 << 31)) | (mt[(i+1) % 624] & ~(1 << 31));
                mt[i] = mt[(i + 397) % 624] ^ (y >> 1);
                if ((y % 2) != 0)
                    mt[i] = mt[i] ^ 0x9908b0df;
            }
        }

        /* a tömbből kivett számokat még tovább kavarjuk */
        uint32_t y = mt[index];
        y ^= (y >> 11);
        y ^= (y << 7) & 0x9d2c5680;
        y ^= (y << 15) & 0xefc60000;
        y ^= (y >> 18);
        index = (index + 1) % 624;

        /* az előállt véletlenszám, 0..(1<<32)-1 */
        printf("%08x\n", (unsigned) y);
    }

    return 0;
}

Látható, hogy ez is álvéletlenszámokat generál csak. Nem csinál mást, csak turmixolja ide-oda a biteket: a cél csak annyi, hogy a kimenet minél véletlenszerűbbnek tűnjön. A műveletek persze úgy vannak megkonstruálva, hogy a szabályosság minél kisebb legyen. Az algoritmus több dimenzióban biztosítja a számok egyenletes eloszlását. Vagyis nem csak az egyes számok eloszlása egyenletes nagyjából, hanem ha az egymás melletti számokat (x;y) koordinátáknak használjuk a síkon, akkor az így kapott pontok is közel egyenletesen fedik le a négyzetet, ahova esnek. (Tehát kockadobásnál nem lesznek olyasmi szabályosságok, mintha pl. 6-os után gyakrabban jönne 3-as.) Sőt ha az egymás melletti számhármasokat (x;y;z) koordinátáknak használjuk, akkor a pontok a kocka alakú teret egyenletesen töltik ki, és így tovább, bizonyíthatóan legalább 624 dimenzióig.

Ha egy, a fenti véletlenszám-generátorhoz hasonló algoritmust úgy módosítunk, hogy az egyes számok előállítása közben folyton újabb számokkal „zavarjuk fel benne a vizet”, akkor egy ún. hash függvényt kapunk.

A Wikipedia a következőket írja a hash függvényekről. A kriptográfiában (titkosításban) használt hash függvények bemenetét általában üzenetnek (message), a kimenetét pedig kivonatnak (digest) nevezzük. Az üzenet tetszőleges hosszúságú adat lehet, a kivonat viszont egy fix hosszúságú bitsorozat. És itt jön a lényeg: a függvény biztosítja azt, hogy az üzenet megváltoztatása nagyon nagy valószínűséggel megváltoztatja a kivonatot is.

Egy ideális hash függvény az alábbi tulajdonságokkal rendelkezik:

• bármilyen bemenetre könnyű meghatározni a kimenetet,
• nagyon nehéz olyan üzenetet alkotni, aminek a kivonata előre adott,
• nagyon nehéz úgy módosítani az üzenetet, hogy a kivonata ne változzon,
• nagyon nehéz két különböző üzenetet találni, amelyek kivonata megegyezik.

Röviden: odafelé nagyon könnyű, visszafelé nagyon nehéz. A „nagyon nehéz” azt jelenti, hogy beláthatatlanul sok időbe, például évtizedekbe vagy évszázadokba telik elvégezni a feladatot még akkor is, ha száz vagy ezer számítógépet állítunk rá a feladatra.

Egy ismert hash függvény, az SHA-1 sémája látható a lenti ábrán. Itt a <<< körbeforduló bitenkénti eltolást jelent (vagyis azt, hogy az egyik oldalon kitolt bitek a másik oldalon bejönnek), Wt az üzenet bitjeit, Kt a konstansokat, a piros + a 32 biten túlcsorduló összeadást, az F függvény pedig egy olyan bitművelet-sorozatot, amely minden huszadik lépés után változik. Az algoritmus egy körben a bemenetből 512 bitet dolgoz fel, ezért a bemenet bitjeinek száma 512-vel osztható kell legyen. Ha ennél rövidebb, akkor nullákkal töltik fel a művelet előtt, és a végére az üzenet hosszát is hozzáveszik (hogy a csupa nullákból álló, de különböző hosszúságú üzenetek kellően különbözzenek egymástól). Egy kör legbelső ciklusa valahogy így néz ki:

for (int i = 0; i < 80; i += 1) {
    if (0 <= i && i <= 19) {
        F = (B & C) ^ (~B & D);
        K = 0x5A827999;
    } else if (20 <= i && i <= 39) {
        F = B ^ C ^ D;
        K = 0x6ED9EBA1;
    } else if (40 <= i && i <= 59) {
        F = (B & C) ^ (B & D) ^ (C & D);
        K = 0x8F1BBCDC;
    } else if (60 <= i && i <= 79) {
        F = B ^ C ^ D;
        K = 0xCA62C1D6;
    }

    temp = E + F + forgat(A, 5) + W[i] + K;
    E = D;
    D = C;
    C = forgat(B, 30);
    B = A;
    A = temp;
}

Ez hasonló az előző algoritmushoz: a felismerhetetlenségig kavarja a bemeneti biteket és a beépített konstansokat. A hash függvényeknél ezeket a konstansokat egészen máshogy határozzák meg, mint a véletlenszám-generátoroknál. Mivel ezekkel digitális aláírásokat gyártanak, és jelszavakat tárolnak segítségükkel, fontos az, hogy biztosan ne legyen a konstansokban semmi elrejtve. Az algoritmusok megtervezői ezt úgy szokták biztosítani, hogy ún. „nothing up my sleeve”, azaz „semmi sincs az ingujjamban” számokat választanak. Például a π 2-es számrendszerbeli ábrázolásának első 128 bitjét, hiszen az tőlük biztosan független, nem ők találták ki. Az SHA-1 fent látható négy konstansa a 2, 3, 5 és 10 számok négyzetgyökeiből keletkezett.

A forgat() függvény által jelképezett körforgó léptetésre a processzoroknak szokott lenni beépített utasítása. A C-nek nincs beépített operátora erre a feladatra. Viszont meg lehet írni egy ilyet két szokásos léptetés segítségével is, amelyeknél nullák jönnek be. 32 bites számok esetén:

Vagyis a körforgó balra léptetésre az alábbi C függvényt írhatjuk. Az ilyesmit a legtöbb fordító felismeri, és a megfelelő gépi utasítást építi be helyette a lefordított kódba.

uint32_t forgat(uint32_t mit, int hanyszor) {
    return (mit << hanyszor) | (mit >> (32-hanyszor));
}

Az alábbi táblázat néhány rövid szöveget, és azoknak SHA-256 kivonatát tartalmazza. A kivonat az SHA-256-nál 256 bites, amely itt 16-os számrendszerben látható. Ez éppen 256/4=64 hexadecimális számjegyet jelent. Látszik, hogy mind a négy üzenetnek nagyon különbözik a kivonata. Azoké is, amelyek maguk is nagyon különböznek, hosszban és tartalomban is, mint a „hello, vilag!” a „jelszo001”-től. De azoké is, amelyek csak egyetlen bitben, h→H és 0→1. (A h és a H betű karakterkódja csak az 5. biten, a 0 és az 1 karakterkódja pedig csak a 0. biten tér el egymástól.)

Amikor jelszavakat tárolunk, az „üzenet” a jelszó maga. A felhasználók adatait tároló adatbázisban nem ez, hanem csak ezek kivonata szerepel. A hash függvények fentebb említett tulajdonságai adják a lehetőséget a biztonságos tárolásra:

• „Könnyen kiszámolható a bemenetből a kimenet”: egy feljogosított felhasználó könnyen azonosítani tudja magát. Ha megmondja a jelszót, azt csak meg kell etetni a hash függvénnyel, és ha a kivonat megegyezik az eltárolttal, hihetünk neki.
• „Nehéz két különböző üzenetet találni, amelyek kivonata megegyezik”: vagyis nehéz olyan karaktersorozatot alkotni, amely nem azonos az eredetivel, de mégis ugyanazt a kivonatot adja. Ezért van az, hogy bár az eredeti jelszó nem tárolódik, mégis valószínűtlen, hogy helyette egy teljesen más jelszót elfogadna a rendszer.
• „Lehetetlen olyan üzenetet kitalálni, amelynek a kivonata előre adott”: ez azt jelenti, hogy hiába tudja meg valaki az adatbázisban tárolt hash értéket, nem fogja tudni (épeszű időn belül) kitalálni a hozzá tartozó jelszót. Még az adatbázist közvetlenül látó adminisztrátornak sem mehet ez, hiába látja a kivonatokat.

Ezért van az, hogy „rendes helyeken” nem tudják megmondani a jelszót, ha a felhasználó elfelejtette azt. Legfeljebb egy másikat tudnak beállítani. Az InfoC admin portál például egy ilyen rendes hely, a jelszavakat mi is hashelve tároljuk. Ha valaki elfelejti, mi sem tudjuk megmondani, csak újat állítani neki.

Egy jó hash függvény használható ellenőrzőösszegek előállítására is. Ha egy hosszú üzenetet (pl. fél megabájtot) etetünk meg a függvénnyel, kidob egy viszonylag rövid számsort, amelyet küldésnél az üzenet mellé tehetünk. Ez olyan, mint egy ujjlenyomat: bár vannak olyan üzenetek (fájlok), amelyek kivonata egyforma, nagyon nehéz ilyeneket találni. Ha a címzett előállítja a fogadott üzenet kivonatát, ellenőrizheti az üzenet integritását. Ha a két kivonat egyezik, az üzenet szinte biztosan ép.

A digitális aláírásként történő használat egyszerűsített gondolatmenete a következő. Van egy üzenet, amit a megalkotója alá szeretne írni. Kitalál ehhez egy jeligét, hozzácsapja az üzenethez, és a kettőt együtt adja a hash függvénynek. Ezáltal keletkezik egy kivonat, amely a bizonyíték. Ezt titokban tartja. Ha bárki azt kéri tőle, hogy igazolja, tényleg ő írta az üzenetet, nincs más dolga, mint elárulni a jeligét. Az ellenőrzéshez fogni kell az üzenetet, hozzátenni a jeligét, és újra meghatározni a kivonatot. Ha az üzenet tartalma nem változott, és a jelige is helyes, ugyanazt a kivonatot kell kapni. Így nem csak az aláíró személye ellenőrizhető, hanem az üzenet tartalma is: hogy tényleg pontosan az volt-e az üzenet, amit ő aláírt.

Bár egy ismert kivonathoz „nagyon nehéz” üzenetet találni, ez nem jelenti azt, hogy lehetetlen, csak azt, hogy belátható időn belül nem lehetséges. A mai számítógépek elég gyorsak már ahhoz, hogy a néhány karakterből álló jelszavakat kitalálják. Egyszerűen próbálgatással: indulunk a rövid szavaktól a hosszabbak felé, és kipróbáljuk az összes betűkombinációt. Ha csak az angol ábécé kisbetűit használjuk, és pontosan hat betűs jelszavakat feltételezünk, nincs is olyan sok lehetőség: 266 = 308 millió jelszót kell végigpróbálni. Pár perc.

Ezért szörnyen nagy hülyeség az, hogy „komoly helyek” azt várják a felhasználóktól, hogy tegyen írásjeleket is a jelszavába. 6 karakter, kisbetű, nagybetű és számjegyek: ez 62-féle írásjel, vagyis 626 = 56 milliárd kombináció. Ha az előbbi egy percig tartott, akkor ez 180 percig fog tartani. Három óra. Kivárható. Viszont ha mondjuk négy darab ötbetűs szót választunk, csak kisbetűket használva, az

lehetőség. Erről meg is emlékezett az xkcd, de hiába, valószínűleg még éveket kell várnunk, mire nem megjegyezhetetlen, hanem erős jelszót fog várni tőlünk a netbankunk.

A legtöbb hash függvénynek egyébként idővel az a sorsa, hogy találnak a kimenetében valami szabályosságot. Ilyenkor annak használata már nem ad elfogadható biztonságot, mert ez azt jelenti, hogy a lehetőségek végigpróbálása nélkül, vagy inkább: jóval kevesebb lehetőség végigpróbálásával válik lehetségessé egy adott kivonathoz tartozó üzenetet kitalálni.

Így jártak a manapság már nem nagyon használt MD4 és MD5 függvények is. Ezek kimenetében lévő szabályosságok miatt már olyan algoritmust is találtak, amely néhány másodperc alatt képes ütközéseket (azaz két különböző üzenetet ugyanazzal a kivonattal) találni.

Az SHA-1 algoritmust éveken keresztül használták jelszavakhoz, de manapság már ezt sem szabad: 2017 tavaszán az Amszterdami Egyetem és a Google kutatócsoportjai közösen, elő tudtak állítani két különböző PDF fájlt, amelyek SHA-1 ellenőrzőösszege megegyezett, a tartalmuk viszont eltért: SHAttered.