Kellon toistuvaan lukuun perustuva satunnaislukugeneraattori -ohjelma

Abstract

Opinnäyte esittelee kellon vaihteluihin perustuvan satunnaislukugeneraattorin, Ressun. Siinä kerrotaan mitä nämä vaihtelut ovat. Lisäksi käydään läpi ressun toiminnot, jaetaan se palasiin ja esitellään niiden toimintaa. Lopuksi tutkitaan hiukan ongelmia, ja esitellään tilastollisia testejä satunnaisuudelle.

Ressu koostuu kahdesta toistorakenteesta, joista ensimmäisessä (~kellon luku ja bittien järjestely) puskuriin luetaan täyteen kellon merkkejä, ja vaihdetaan puskurin ylin bitti alas ja siirretään alimpia bittejä 1 bitti ylöspäin. Toisessa toistorakenteessa (~puskurin merkkien sekoitus) vaihdetaan jokainen puskurin merkki toisen puskurin merkin kanssa. Näitä kahta toistorakennetta toistetaan b kertaa. Ensimmäinen toistorakenne takaa että kellon alin bitti koskee kaikkia puskurin bittejä ja toinen kierros takaa että vierekkäin luetut bitit ovat eri paikoissa puskurissa ja että jokainen kellobitti vaikuttaa ~jokaiseen puskurin bittiin.

Työn aikana listasin mahdollisia ongelmia: kello ainoa satunnaisuudenlähde, muuteltu kellofunktio, käsitelty kellojono muodostaa hyökkääjän haluaman puskurin, hyökkääjä arvaa kellojonon, hyökkääjä arvaa puskurin, laitteistoerot, laitteiston kuormitus, kello ei ole riittävän tarkka, kello on liian säännöllinen, kellon sarjat ovat liian pitkiä, bittigeneraattori on tunnistettavissa, bittigeneraattori ei tuota uniikkia tietoa.

Ongelmat, joissa kellosarjaa on muuteltu ei katsota olennaiseksi, koska jos hyökkääjä voi muokata kellosarjaa, hän voi tehdä mitä tahansa muutakin, esimerkiksi lähettää generaattorin tuottaman puskurin itselleen.

Satunnaislukugeneraattorin arvaamiseen generaattori ei anna mitään vihjeitä (jos b on riittävän suuri), joten en pidä sitäkään olennaisena.

Ongelma jossa bittigeneraattori ei tuota uniikkia tietoa, ei johdu generaattorin rakenteesta, vaan ajatuksesta että jos generaattori tuottaa samanlaisia puskureita, kellosta luettavat bitit eivät riitä koko puskurin sisällöksi. Puskuriin saadaan lisää bittejä kasvattamalla kutsun b muuttujan arvoa.

Työ esittelee tilastollisia testejä, joilla voidaan testata lukujonon satunnaisuutta, testeistä mukana ovat monobit, poker 2, poker 4, runs ja runs8.

Raportin liitteenä on työn aikana tehdyt ohjelmat kellon vaihtelujen havainnollistamiseen, tilastojen laskemiseen,varsinainen satunnaislukugeneraattori, ja kutsuvat rutiinit, jos haluat sen heti käyttöön (tässä b on toivoakseni ylimitoitettu niin ettei pitäisi tulla ongelmia). Raportissa suositellaan kuitenkin että tätä ei käytetä ainoana generaattorina.

This thesis presents random number bit stream generator based on variances reading the clock, Ressu. The thesis shows what these variances are, shows how Ressu works, divides it into pieces, and analyses the parts. The last part of the thesis lists the problems discovered during writing and shows some statistical tests for randomness.

Ressu contains two repeat structures. The first (~reading clock and moving bits) structure fills the buffer with clock bytes and moves the highest bit to lowest and the lowest bits one step up. The second structure (~shuffling buffer characters) swaps every character in buffer with random character in buffer. These repeat structures are repeated 8*b times. The first repeat structure guarantees that the lowest bit in the clock touches every bit of the buffer. The second structure guarantees that the bits read next to each other are in different parts of the buffer, and that every bit of the clock affects ~every bit of the buffer.

While working on the thesis I listed some possible problems in the generator: clock is the only source for bits, corrupted clock function, corrupt clock gives buffer wanted by attacker, attacker guesses clock stream, attacker guesses the buffer, hardware differences, hardware load, clock not accurate enough, clock is too regular, clock series are too long, attacker is able to identify generator, or generator does not provide unique buffers.

Problems where clock is corrupted are not considered relevant, as if an attacker can change clock stream he can send buffer containing collected random bits to himself.

The generator does not give any hints to guessing clock stream or clock series (if b is large enough), this is not considered relevant either.

The problem that random bit generator does not give unique buffers is not about the structure of the generator, but it is about the thought that if the generator returns duplicate buffers, we don’t have enough randomness in clock stream. We get more random clock bits to buffer by increasing b.

The thesis gives statistical tests that can be used to test randomness of bit stream. Included are monobit-, poker 2-, poker 4-, runs- and runs8 -tests.

The programs written during the work are attached to the thesis. There are programs to show these variances, programs for statistical tests, and for finding b values that return unique buffers. The generator itself is in attachment 2. Also, there is a program to use the program right now, it has hopefully conservative enough buffer size and b.