A High-Throughput DSP-Free PRNG for FPGA based on Xoshiro128** and Integer Chaotic Mixing

In de digitale wereld vertrouwen veel systemen op reeksen getallen die er volkomen willekeurig uitzien om correct te kunnen functioneren. Deze reeksen zijn essentieel voor het beveiligen van communicatie, het simuleren van complexe fysieke systemen en het draaien van cryptografische protocollen. Echter, echte willekeur is moeilijk te genereren met een machine, daarom gebruiken ingenieurs algoritmen om "pseudo-willekeurige" getallen te creëren. Dit zijn deterministische reeksen die willekeurig lijken voor een waarnemer, maar die in werkelijkheid worden geproduceerd door een specifieke set regels beginnend bij een initiële zaadwaarde (seed). De uitdaging voor hardwareontwerpers is om deze reeksen snel en efficiënt te creëren zonder te veel stroom te verbruiken of te veel ruimte in te nemen op een computerchip. Wanneer deze generatoren worden ingebouwd in gespecialiseerde chips genaamd FPGA's, die reconfigureerbare hardware zijn die vaak worden gebruikt in embedded systemen, is het doel om een hoge snelheid te bereiken terwijl het ontwerp klein en energiezuinig blijft, waarbij kostbare, stroomverslindende componenten die typisch gereserveerd zijn voor zware wiskundige berekeningen worden vermeden.

Een team onderzoekers van universiteiten in Iran heeft een nieuwe manier ontwikkeld om een dergelijke generator te bouwen die op een FPGA draait. Hun werk richt zich op het creëren van een apparaat dat een enorme stroom willekeurig ogende getallen produceert zonder gebruik te maken van de standaard hoogwaardige rekeneenheden die op de meeste chips te vinden zijn. In plaats van te vertrouwen op deze gespecialiseerde componenten, die vaak beperkt in aantal zijn en aanzienlijk veel stroom verbruiken, ontwierp het team een systeem dat alleen basis logische poorten en standaard geheugenregisters gebruikt. Het resultaat is een generator die gegevens kan produceren met een snelheid van 5,82 gigabit per seconde, een snelheid die wedijvert met veel complexere ontwerpen, terwijl het een zeer kleine hoeveelheid van de middelen van de chip gebruikt en minimaal stroom verbruikt.

De kern van dit nieuwe ontwerp is een hybride aanpak die drie verschillende methoden van het mengen van getallen combineert. De primaire motor is een bekend algoritme genaamd Xoshiro128**, dat fungeert als de hoofdbron van de reeks. Deze motor is efficiënt en heeft een zeer lange cyclus voordat hij zich herhaalt, maar het heeft een voorspelbare wiskundige structuur die door een bekwame aanvaller geëxploiteerd zou kunnen worden. Om dit te verhelpen, voegden de onderzoekers twee extra lagen van menging toe. De eerste laag maakt gebruik van een eenvoudig additief proces dat waarden verschuift op een manier die een ander soort patroon creëert. De tweede laag gebruikt een "tent map", een methode die de getallen uitrekt en vouwt, vergelijkbaar met hoe een bakker deeg vouwt, hoewel het vouwen in dit geval gebeurt door middel van eenvoudige gehele getal-wiskunde in plaats van fysieke manipulatie. Deze lagen zijn ontworpen om samen te werken om de voorspelbare patronen van de hoofdmotor te doorbreken, waardoor de uiteindelijke output veel moeilijker te achterhalen is via reverse-engineering.

De onderzoekers bouwden dit systeem met behulp van een high-level synthesetool, die automatisch een softwarebeschrijving van de logica vertaalt naar de fysieke lay-out van de chip. Ze testten het ontwerp op een specif kind van een chip dat bekend staat als de Xilinx Zynq-7000. De implementatie was succesvol op elke relevante metriek voor embedded toepassingen. Het uiteindelijke ontwerp nam slechts 934 kleine logische blokken op de chip in beslag en gebruikte 1.071 registers, wat een zeer compacte voetafdruk is. Cruciaal is dat het nul gespecialiseerde digital signal processing slices en nul blokken toegewezen geheugen gebruikte, wat bewijst dat hoogwaardige willekeurige getalgeneratie mogelijk is zonder deze zware middelen te gebruiken. Het systeem draaide op een frequentie van 181,82 megahertz, wat de eerder genoemde hoge doorvoer leverde. Wat betreft het vermogen verbruikte de chip slechts 29 milliwatt aan dynamisch vermogen tijdens de werking, een cijfer dat een ondergrens schatting vertegenwoordigt en suggereert dat het ontwerp extreem energiezuinig is.

Om te waarborgen dat de geproduceerde getallen willekeurig genoeg waren voor serieus gebruik, onderwierp het team de output aan een batterij van rigoureuze statistische tests. Deze tests, die standaard suites bevatten die worden gebruikt door overheidsinstanties en onafhankelijke onderzoekers, controleren op patronen, biases en correlaties die zouden duiden op een gebrek aan willekeur. De generator slaagde voor elke test, inclusief de meest veeleisende tests die zoeken naar subtiele gebreken in de reeks. De onderzoekers analyseerden ook hoe gevoelig het systeem was voor veranderingen in de begincondities. Ze ontdekten dat het veranderen van zelfs maar één bit in de initiële opstelling ervoor zorgde dat de output volledig uiteenliep, een eigenschap die bekend staat als gevoeligheid voor begincondities. Dit zorgt ervoor dat twee apparaten die met licht verschillende zaadwaarden beginnen, geheel verschillende reeksen produceren, wat essentieel is voor de beveiliging.

De studie bevatte ook een gedetailleerde uitsplitsing van wat elk deel van het systeem bijdroeg. De onderzoekers vonden dat de hoofdmotor, Xoshiro128**, op zichzelf al statistisch sterk genoeg was om de tests te doorstaan. De toegevoegde lagen verbeterden de statistische kwaliteit van de getallen niet, maar ze deden iets anders belangrijks: ze verwijderden de lineaire wiskundige structuur die de hoofdmotor voorspelbaar maakte. Door deze lagen toe te voegen, maakten de onderzoekers het aanzienlijk moeilijker voor een aanvaller om de interne staat van de generator te achterhalen door enkel naar de output te kijken. Terwijl de hoofdmotor alleen relatief snel te reverse-engineeren was, vereist het volledige hybride systeem een veel complexere en tijdrovendere inspanning om te breken, wat de generator effectief beveiligt tegen bepaalde soorten aanvallen zonder dat dit ten koste gaat van de snelheid of efficiëntie.

Dit werk suggereert dat het mogelijk is om hoogwaardige willekeurige getallengeneratoren te bouwen voor omgevingen met beperkte middelen zonder te vertrouwen op zware hardwarecomponenten. Het ontwerp biedt een praktische afweging, waarbij snelheid, hulpbronnengebruik en beveiliging in balans worden gebracht. Hoewel de onderzoekers opmerken dat de wiskundige stappen die worden gebruikt in de vouwlaag algebraïsch niet complex zijn, creëert hun combinatie met de andere lagen een robuust systeem. De bevindingen wijzen erop dat deze aanpak zeer geschikt is voor embedded systemen waar ruimte en vermogen schaars zijn, en biedt een betrouwbare bron van willekeur die kan worden geïntegreerd in een breed scala aan apparaten. De onderzoekers hebben hun code en gegevens beschikbaar gesteld zodat anderen de resultaten kunnen verifiëren en erop kunnen voortbouwen, wat ervoor zorgt dat de resultaten gereproduceerd kunnen worden en het ontwerp kan worden aangepast aan toekomstige behoeften.