Niektóre wysokiej klasy mikroprocesory wbudowane mają rzeczywiste generatory liczb losowych, jednakże większość niedrogich mikrokontrolerów pozbawiona jest takich modułów. Inżynierowie mają w rękawie kilka asów - sztuczek - pozwalających na quasi-losową inicjalizację programowego generatora. Zazwyczaj jest on inicjalizowany ziarnem generowanym przez licznik, zatrzymany zdarzeniem zewnętrznym (np. naciśnięciem przycisku). Oczywiście takie coś funkcjonuje całkiem nieźle, ale nie jest pozbawione wad. Po pierwsze, istnieje szansa, że licznik zsynchronizuje się z częstotliwością pracy skanera portów wejściowych układu. Po drugie, czas pomiędzy uruchomieniem licznika a naciśnięciem przycisku jest zazwyczaj krótki, co powoduje, że ziarno jest bliskie początkowej wartości licznika, a przez to dosyć przewidywalne. Po trzecie, w niektórych aplikacjach nie da się zaimplementować wejścia zewnętrznego, więc trzeba znaleźć inny sposób inicjalizacji generatora.
Niezależnie od tego, co się mówi, większość mikrokontrolerów ma wbudowane źródło całkiem niezłych liczb losowych. Jakkolwiek nie jest on doskonały i może nie nadawać się do aplikacji typowo kryptograficznych, to generuje on dostatecznie dużo entropii, aby nadawać się do wykorzystania w grach, symulacjach, gadżetach itp.
Niezainicjalizowana pamięć RAM
Hakerzy i zaawansowani inżynierzy często wykorzystują hardware w sposób nieprzewidziany przez producenta, w tym przypadku ulotną pamięć RAM, nie jako pamięć, a jako źródło entropii. Gdy do mikrokontrolera dołączy się zasilanie, wewnętrzna pamięć RAM (ulotna) ma nieznaną i losową zawartość. Każdy przerzutnik w jej strukturze będzie wstępnie ustawiony jako 0 lub 1 - jest to konsekwencja odchyłek od idealnej struktury układu, zapadów pamięci zasilania oraz termalnego (i kwantowego) szumu. Z tego względu zawartość pamięci RAM jest inna przy każdym uruchomieniu układu.
Kilka lat temu firma Intel opracowała nowatorski sposób generacji losowych bitów, oparty o specjalnie skonstruowany przerzutnik. Został on ustawiony w stanie metastabilny, a następnie zwolniony do stabilnego 0 lub 1. Całość powtarza się z częstotliwością 3 MHz. Firma Intel planuje zaimplementować taki układ w nowej generacji swoich procesorów.
Póki co w mikrokontrolerach nie ma takich przerzutników, ale generalnie to jest ich sporo, a część z nich da się stroić. To, ile przerzutników ulotnej pamięci RAM potrzebne jest do stworzenia generatora liczb losowych, zależne jest od parametrów samej pamięci, więc aby dobrać ich ilość trzeba przeprowadzić szereg eksperymentów. Pozwoli to sprawdzić, ile bitów pamięci RAM zachowuje się nieprzewidzianie po załączeniu układu. Niestabilność, o którą nam chodzi, objawia się w wysoce symetrycznych przerzutnikach z dobrze zbalansowanymi tranzystorami. Potrzebujemy tych nieprzewidywalnych bitów do zbierania entropii, więc zebrać trzeba możliwie dużo danych, najlepiej sczytać całą pamięć RAM przed jej inicjalizacją.
Eksperymenty
Przyjrzyjmy się zawartości pamięci RAM typowego mikrokontrolera przed inicjalizacją. Poniższy obrazek zawiera początkowy stan 2048 bitów pamięci układu PIC18F2525. W każdym rzędzie jest 256 bitów (32 bajty). Jedynki są czerwone, a zera żółte.
Oczywiście jest o wiele mniej jedynek niż zer w pamięci, ale to nie ma znaczenia. Co innego jest interesujące. Czy jeżeli wzięlibyśmy inny układ, nawet z tej samej rodziny lub tej samej linii produkcyjnej, to ile bitów różniłoby się, względem zaprezentowanego obrazka?
Najpewniej łatwo się tego domyślić - każdy układ ma charakterystyczny dla siebie rozkład. Drugim, istotniejszym pytaniem jest to, ile bitów pamięci RAM będzie generowało losowe stany po włączeniu. Poniżej zaprezentowany wyniki kolejnego, prostego eksperymentu. Uruchomiono mikrokontroler (PIC18F2525) dwukrotnie, za każdym razem odczytując niezainicjalizowaną pamięć. Kolor biały to odczytane dwa zera, kolor szary dwie jedynki. Kolorem czerwonym oznaczono odczytanie najpierw zera, potem jedynki, a niebieskim sytuację odwrotną.
Po przeprowadzeniu pewnych eksperymentów widać, że na ogół te same bity pamięci RAM wykazują nieprzewidywalne zachowanie - o takie nam chodzi i one będą naszym źródłem entropii. Przetestowano mikrokontrolery z rodziny PIC18 i PIC24 (rezultaty znajdują się poniżej), ale każdy układ powinien zachowywać się w podobny sposób. Wyniki zaprezentowane tutaj uzyskano dla szybkiego narastania napięcia zasilającego, ale podobne zachowanie da się zaobserwować dla wolnego narastania napięcia zasilającego. Taka sytuacja powoduje generację pewnych wzorów w pamięci, ale przyczynia się to do zwiększenia niestabilnych bitów w pamięci.
Oprogramowanie
Zatem jeżeli potrzebujesz kilku losowych bitów (np. do inicjalizacji generatora programowego), pamięć RAM jest dobrym ich źródłem. Trzeba napisać procedurę, która będzie XORować (lub wykonywać ADD MOD 256) z bitami w blokach niezainicjalizowanej pamięci. Jeśli potrzebujemy np. 32-bitowego losowego ziarna, to 4K pamięci RAM PIC18F2525 dzielimy w cztery 1024-bitowe bloki i wykorzystujemy do wygenerowania czterech bajtów ziarna. Nawet jeśli część pamięci zostanie już zainicjalizowana, to nie powinno to mieć wpływu na całkowitą entropię otrzymanego ziarna.
Ograniczeniem opisywanej metody jest sytuacja, w której pamięć podtrzymywana jest napięciem z baterii lub gdy urządzenie jest usypiane, a nie wyłączane. Tym niemniej w większości mniej czułych na słabą entropię aplikacji, wystarczy moment wymiany baterii, aby wygenerować losowe ziarno starczające na bardzo długi czas działania programowego generatora liczb losowych.
Podczas tworzenia aplikacji wykorzystujących ten sposób generowania liczb losowych, pamiętać trzeba, że pamięć odczytywać trzeba przed jej inicjalizacją, od razu po włączeniu układu. Dodatkowo warto zwrócić uwagę, aby układ, w którym to realizujemy, nie miał zbyt wielkiej pojemności filtrującej zasilanie, gdyż CMOS RAM potrzebuje naprawdę niewiele prądu do podtrzymania zapisu. W takiej sytuacji, kiedy wyłączamy układ tylko na chwilę i następuje zasadniczo jedynie zapad napięcia z uwagi na ładunek zgromadzony w kondensatorze filtrujący mikrokontroler zresetuje się, ale pamięć RAM pozostanie w dużej mierze nietknięta.
Istnieje kilka możliwych podejść do realizacji takiego układu, pozwalających na poprawienie jakości liczb losowych generowanych przez układ. Nie należy nigdy inicjalizować całej pamięci RAM, jedynie potrzebny jej fragment. Nie można także używać zbyt dużych pojemności filtrujących, zasilanie najlepiej odłączać zamiast usypiać układ.
Jednostka eksperymentalna
Pierwsze rezultaty eksperymentalne okazały się być bardzo obiecujące, więc autor zdecydował się na konstrukcję trzech prototypów generujących strumień losowych bitów.
1. Dwa układy PIC18F2525s komunikującej się poprzez 8-bitową szynę równoległą. Podległy mikrokonstroler generuje 16 losowych bitów, każdy z nich oparty o 248 bitów pamięci RAM. Master (po środku na schemacie) odbiera te bity i wysyła do komputera PC poprzez interfejs RS232. Po odebraniu 16 bitów, układ sterujący odłącza podległe mu mikrokontrolery na 200 ms, co powinno zresetować układ i zapełnić RAM losową zawartością. Dalej całość się powtarza - realizowane jest 625 tysięcy cykli, aby zebrać 10 MB danych, potrzebnych do testów losowości. Całość trwa około 50h.
2. W tym prototypie master jest ten sam, ale podległe ma dwa układy 24EP512GP202. W tym przypadku strumień ma 192 bity w pakiecie, więc 10 Mb danych generuje się przez 5,5 h.
3. W ostatnim przykładzie wykorzystany jest tylko mikrokontroler 24EP256GP710A z 4 megabitami zewnętrznej pamięci SRAM CY62177EV30. Pamięć SRAM jest odłączana od zasilania i odczytywana w podobny sposób jak wewnętrzna pamięć układów w poprzednich przypadkach. Jedyną zaletą tego podejścia jest duża pojemność pamięci RAM, co oznacza, że generacja generacja 10 Mb danych jest szybka - zajmuje jednie 19 minut.
Test losowości
Dwa zestawy testów zrealizowane zostały dla prezentowanych prototypów - Diehard i ENT. Pierwszy prototyp przeszedł wszystkie testy, a dwa pozostałe oblały część testów ENT - najczulsze z testów losowości. Wyniki testów losowości zawarte są w poniższej tabeli:
| Żródło entropii | 1. (8 bitowy mikrokontroler) | 2. (16 bitowy mikrokontroler z programowym generatorem liczb losowych) | 3. (zewnętrzna pamięć RAM z programowym generatorem liczb losowych) |
| Entropia (bits/byte) | 7.999982 | 7.999982 | 7.999982 |
| Kompresja zredukowała wymiar o | 0% | 0% | 0% |
| Wartość chi² dla rozkładu losowego przekroczona przy: | 47.47% | 34.29% | 42.24% |
| Średnia arytmetyczna (127.5 = wartość w pełni losowa) | 127.4936 | 127.5478 | 127.4937 |
| Błąd wartości liczby π wyznaczonej metodą Monte Carlo | 0.03 | 0.05 | 0.00 |
| Szeregowy współczynnik korelacji (0.0 = wartości nieskorelowane) | 0.000206 | 0.000434 | 0.000104 |
Testy typu Diehard wymagają o wiele obszerniejszego opisu. Ich wynik umieszczono na stronie www.voja.rs/rndtests.htm wraz z plikami binarnymi wygenerowanymi w eksperymencie.
Podsumowanie
Podsumowując, po drobnych modyfikacjach, wszystkie przedstawione prototypy przechodzą poprawnie testy losowości, którym czasami nie mogą sprostać nawet komercyjne (i drogie!) rzeczywiste generatory liczb losowych. Te układy DIY można złożyć za mniej niż 10 dolarów.
Pamiętać trzeba oczywiście, że działanie powyższych urządzeń oparte jest o nieudokumentowane działanie mikrokontrolerów. W ten sposób także nie da się osiągnąć poziomu losowości i bezpieczeństwa potrzebnego w poważnych aplikacjach kryptograficznych, jednakże niezainicjalizowany RAM jest doskonałym źródłem losowych liczb do mniej wymagających aplikacji, a przede wszystkim - przedstawiona metoda jest prosta, jej implementacja jest darmowa i zasadniczo nie powoduje zwiększenia powierzchni PCB ani poboru dodatkowego prądu przez układ.
Źródło:
http://hackaday.com/2015/06/29/true-random-number-generator-for-a-true-hacker/
Fajne? Ranking DIY
