Hardware RNG in elkaar zetten

[Boudewijn]

Hoi


Ik ben zelf bezig met wat x86-based embedded boards en wil daar wat cryptografische dingen op doen waarbij een random getal nodig is.

De in-kernel (linux en openBSD) random number generator (RNG) voldoet hiervoor niet.

Onze hardware (zowel embedded boards als een reguliere 1U server) komt in een server-ruimte te staan en daar is een hele berg leuke 'noise' door de al aanwezige spullen.

Nu leek het mij slim om die te gaan gebruiken voor RNG.
Hoe doe je dat nou? zelf zat ik aan een antenne te denken en een uProcje (picje of attiny) om dat te digitaliseren.

Hoe denken jullie hierover? Ik kan helaas weinig met google vinden.
Als leuke bijkomstigheid heb ik op de embedded boards een miniPCI (lijkt me erg lastig) interface en een I2C (leuker) en GPIO (programmeerbaar). Het gaat om een PC-Engines WRAP board.

Op de 'gewone' x86 hardware heb ik parallel en USB (maybe nog wat onboard, maar ga er niet vanuit).

Hoe maak je zoiets nou netjes? Het mag btw niet teveel stroom trekken en ik heb een 12V spanning bij de hand.


En is zoiets nou redelijk random?

[kluyze]

Je wil dus een externe bron (ruis) gebruiken voor een random getal, nu ja dit soort factoren zijn inderdaad meer random dan een pc of zo kan leveren.

Ik heb een tijdje terug ook wat gedacht aan dit soort van random getallen. Mijn gedacht was het volgende:

Neem verschillende externe factoren, best zoveel mogelijk verschillende sensoren.
- geluid
- licht
- temeratuur
- ...
Die dan ook zo mogelijk beinvloedbaar zijn door menselijk gedrag. voorbeeldje: je spreekt van een serverruimte daar komt dus niet dikwijls iemand stal dat daar 1 keer per dag iemand binnen komt, dat tijdstip is (meestal) niet exact te bepalen. Als je van dat tijdstip de seconden of zo neemt is het al redelijk random.

Als er mensen rondlopen is het nog beter, stemmen, geluid en licht op sensoren kan verschillend zijn en redelijk random.

Neem je dan al deze factoren en giet je die in een formule dan bekom je volgens mij een getal dat niet meer random KAN zijn.

Dat idee van jou lijkt trouwens ook wel iets, ik neem aan dat je het ruisniveau van rf signalen in de buurt wilt meten en dan het aantal pieken per seconde of gewoon het niveau op dat moment. Je kan dan ook nog wat versterkers er tussen gooien die nog wat ruis toevoegen liefst zo slecht mogelijke versterkers dan.
Het schijnt ook te zijn dat een weerstand die niet aangesloten is zelfs ruis (thermische of Johnson-ruis) ligt te maken, als de weerstands waarde hoog genoeg is kan je die spanning misschien versterken en die ruis binnen halen.

Nu ja is ooit een rare gedacht kronkel geweest.

[SA007]

Vind een octaal cmos invertor (of meerdere met minder poorten) en gooi dat op de datalijnen van je printerpoort.
Draden van verschillende lengtes aan de ingangen, geen peil aan te trekken, kan weinig meer randoms bedenken.

[ Voor 59% gewijzigd door SA007 op 31-05-2007 22:07 ]

[Mr_gadget]

of lees een sensor tot een groot aantal getallen achter de komma uit dan heb je de sensorruis die ook lastig te beïnvloeden is, hoewel AD convertor dan wel duur is.

[kluyze]

Hoezo ADC duur? Als je van het signaal van een sensor de gelijkspanning afgooit en dat signaal sterk versterkt dan heb je de ruis van de sensor plus de ruis die de versterker er bij gooit dan hoeft de AD niets speciaal te zijn.

[Boudewijn]

nou ik heb geen geluidskaart oid in mijn embedded hardware. Hier thuis heb ik een compleet vern**kt afgesteld radiootje (met antenne langs wat leuke voedingen) in de onboards geluidskaart hangen.
Prima random.


maar op die embedded bakjes lijkt me dat niet haalbaar ivm het feit dat ik daar geen nette interface voor heb.

Licht is niet haalbaar, de embedded boards verpakken we wss per 2 stuks in een 1U casing. Je kunt wel weer een switch nemen en daar een cam op zetten, maar dat is teveel custom werk.

Daarom die antenne, dat kan vrij makkelijk zonder van de situatie afhnakelijk te zijn.
Ik hoef het zelf niet te ontwikkelen op zich (vind het wel leuk , maar ben software-man) , maar een MBO-electro collega moet het kunnen maken.


Die RF zooi oppikken kan prima met wat microfonische staalbuisjes (ben er the hard way achter gekomen), maar profi is anders. Daarom stelde ik gewoon een 'antenne' voor, maar weet te weinig van RF enzo om dat soort crap bewust te krijgen.

[Boudewijn]

SA007 schreef op donderdag 31 mei 2007 @ 22:05:
Vind een octaal cmos invertor (of meerdere met minder poorten) en gooi dat op de datalijnen van je printerpoort.
Draden van verschillende lengtes aan de ingangen, geen peil aan te trekken, kan weinig meer randoms bedenken.

heb geen printerpoort op die embedded boards.
liever niet dus.

[SA007]

Wat voor interfaces heb je wel?

Meestal heb je wel uart, dan gooi je aan de RX van het ding een cmos invertor met een antenne eraan langs allemaal zooi, zet je hardware handshaking uit, geen stopbits, pak een redelijk hoge snelheid 9600baud oid.

[Boudewijn]

kijk eens in de startpost.

Ik heb een setje GPIO pinnen en een I2C bus. Ook miniPCI, maar die lijkt me niet echt handig voor DIY zaken (het gaat om een oplage van voorlopig max 50 RNGs).

Als gewone x86 hardware (de duurdere versie... ) draai ik een Intel mobo, daar kan ik met parallel of USB aan de slag.

[Anoniem: 4629]

Je gaat er nu wel vanuit dat die ruis random is. Terwijl hij in weze bestaat van een kakafonie van redelijk voorspelbare geluiden. Fans e.d. hebben een patroon. Ze oscilleren enz. Bepaalde frequenties komen in een bepaald tijdsbestek steeds terug. En zo is het met de meeste dingen. Als je daar goed naar kijkt kun je in iets wat random lijkt al snel deels een patroon gaan herkennen. Ik zeg niet dat je daarmee helemaal non-random bezig bent, want er zijn nog andere invloeden zoals idd de mensen die er rondlopen, maar als je geluid wat deels voorspelbaar als basis pakt voor een random nummer dan ben je niet goed bezig.

Evenzo moet je heel goed opletten wat voor transformaties je nog op je input toe gaan passen. Allerlei husselroutines en zo. Je zult de 1e niet zijn die een signaal wat daadwerkelijk nagenoeg random was ging versleutelen met een algoritme dat een patroon introduceerde in het signaal, waardoor het randomme er snel vanaf was.

[Boudewijn]

ja ik weet het.
Op zich wil ik de random meuk gaan gebruiken als seed voor de software RNG in Linux.
Sowieso zal er op 50Hz een heel leuk patroon zitten neem ik aan, maar heeft iemand anders een ander voorstel?

Dat van die RF meuk was puur bedoeld als gek idee, maar het maakt mij niet zoveel uit hoe ik het bereik als ik het maar bereik (de randomness dan). Liefst wel makkelijk te implementeren en tegen nette kosten.

Het wordt btw gebruikt voor certificaten (waaronder 802.1X dingen) en moet dus wel vrij stevig zijn.

[Nijn]

Wellicht is dit wel intresant voor je:
http://willware.net/hw-rng.html

Verder heb je misschien iets aan http://www.random.org/

[Anoniem: 167155]

Gewoon een weerstand nemen en een comperator. De ruis uit je weerstand is volkomen wit (helemaal evenreedig verdeeld over het spectrum)

Een comperator zorgt ervoor dat de output of 0 of 3.3V is

[Boudewijn]

Kan iemand mij deze uitleggen?


En is dit te combineren met witte ruis? (waar ik beetje bekend mee ben)
kan ik hier trouwens ook 12VDC in stoppen zonder issues?
lijkt me van wel, maar aangezien deze schakeling zich random gedraagt vind ik het lastig te beredeneren


weet iemand btw waar ik die 74ALS04 kan krijgen?
aantal toko's waar ik regelmatig shop hebben hem niet, of hebben ze hem uit het assortiment gedaan.

[ Voor 54% gewijzigd door Boudewijn op 03-06-2007 23:10 ]

[naftebakje]

Dat schema gaat om thermische ruis en lekstromen op de 1e transistor, waardoor je enigszins random omklappen krijgt nog voor de eerste condensator (lek op basis emitter van 1e transistor doet de 2e geleiden, daardoor wordt de basis weer laag getrokken en klapt ie weer om). De AC component van die primaire blokgolf gaat in de 1e inverter (door de condensator), door de 2,7K weerstand blijft die inverter nog wat naklepperen waardoor het nog wat meer random wordt. Hetzelfde voor de volgende inverter, de laatste inverter dient als buffer om de voorgaande schakeling niet te belasten.

[Boudewijn]

kan ik evt ook een 74LS04 ipv de 74als04 inzetten?
Deze kan ik namelijk wel krijgen. alleen farnell lijkt de als-versie te hebben.

[Sine]

Zo zou ik het in ieder geval doen, een transistor ( of inverse zener ) als ruis generator, en die sampelen.

En alle combinaties die daaromheen te bedenken zijn ( twee torren XOR-en ? )

Het geheel wel inblikken, de tor / diode zijn te beinvloeden door storing van buitenaf.

Experimenteer wat met de stroom door de tor, er is een vrij smalle sweet spot waar ze behoorlijk veel ruis naar buiten gooien, de beste ruiser die ik in mijn bakje had liggen was een metal can 2n2222A.

Hier nog wat meer over doe het zelf ruisgeneratoren :
http://www.hcrs.at/NOISE.HTM

En uitleg over een commercieele oplossing :
http://www.hcrs.at/ZYKLEN.HTM

Beetje duits kennis is handig

[ Voor 17% gewijzigd door Sine op 04-06-2007 02:21 ]

[BrennuS]

Leuk project maar sla je de plank niet mis...

je gaat een random getal creeren obv een externe sensor op dit getal ga je je beveiliging baseren.

Als ik de binnen wil komen moet ik alleen de sensor(s) beinvloeden of overstemmen. lijkt mij leuk om met parameters te schuiven en te kijken wat er aan de andere kant uitkomt.

Je krijgt het ongetwijfeld technisch voor elkaar. Ik zou het alleen niet gebruiken voor beveiliging.

[brute51]

Ik weet niet of je het graag zelf wilt bouwen, anders zou je is kunnen kijken naar een Via Epia moederboordje. De processor heeft zoiets ingebouwd zitten, de random nummergenerator ervan werkt op ongeveer zo'n manier. Maar een Epia presteert weer niet zo best als de meeste servers...

[Boudewijn]

BrennuS schreef op maandag 04 juni 2007 @ 08:46:
Leuk project maar sla je de plank niet mis...

je gaat een random getal creeren obv een externe sensor op dit getal ga je je beveiliging baseren.

Als ik de binnen wil komen moet ik alleen de sensor(s) beinvloeden of overstemmen. lijkt mij leuk om met parameters te schuiven en te kijken wat er aan de andere kant uitkomt.

Je krijgt het ongetwijfeld technisch voor elkaar. Ik zou het alleen niet gebruiken voor beveiliging.

nop, ik ga alleen de hardware rng de software rng laten beinvloeden. Over in de ruimte zitten : als je binnen bent heb je gewonnen. Dat is met elke server\service zo. Heel simpel... je boot naders gewoon in single-user mode en je hebt de jackpot.

Over via epia: is geen optie. We hebben in het project voor WRAP (en zo het nieuwe LX800 based board van pc-engines) gekozen.

[Wilf]

Ik ben ook betrokken bij het project. Wat ik begreep uit de tech specs van de LX800 zit er een TRNG al in geïntegreerd (zie ook de specs PDF), de vraag is of deze daadwerkelijk goed genoeg is voor de toepassing. Is er dus nog een meerwaarde aan de extra hardware RNG?

edit:
Voor de volledigheid:

De AMD True Random Number Generator genereert 32 bits random numbers. Deze is geïntegreerd in wat AMD "SB" noemt (Security Block), samen met 128 bit AES (CBC/ECB) maar is apart te adresseren.

[ Voor 24% gewijzigd door Wilf op 04-06-2007 11:12 . Reden: extra specs bijgevoegd ]

[BrennuS]

ik bedoel niet fysiek binnen maar in je systemen.

als ik van afstand de omgeving kan beinvloeden kan ik voorspellen wat het RNG gaat worden. ik weet het... duurt lang, is moeilijk, moet je erbij kunnen etc. maar je zou je eerste niet zijn. iemand die wil die hou je niet tegen.

[Wilf]

@ Brennus: daarom is het ook belangrijk de hardware RNG te integreren met de software RNG, zodat als de hardware RNG gecompromitteerd wordt er alsnog wel een vorm van random generation overblijft, hoe pseudo dit dan moge zijn.

Theoretisch kan je immers alle op sensor danwel RF gebaseerde hardware RNG's dusdanig bombarderen dat ze buiten hun bandbreedte treden (bijvoorbeeld bij een ADC-gebaseerde ruis een dusdanig voltage toebrengen dat er clipping ontstaat en er enkel maar FFFFFF gegenereerd wordt), dus dan is de extra security van een extra (P)RNG zeer welkom.

[Boudewijn]

nou de truc is dat de HW RNG de SW RNG voorziet van een stukje randomness (een seed dus).
als de hw rng uitvalt is de SW RNG altijd nog over

Hoe goed zou de LX800 RNG daarin presteren, en hoe meet je zoiets?

[sebastius]

Boudewijn, gewoon ongeveer 100000 miljard nummers nemen en kijken of het witte ruis benaderd?

[Boudewijn]

en hoe wil jij dat doen? ik ben informaticus, geen statisticus.
sowieso. 100.000 miljard is een eindige reeks

[ Voor 20% gewijzigd door Boudewijn op 04-06-2007 20:54 ]

[sebastius]

gewoon:

Elk getal heeft een veld in een tabel (bv 1 tot 10)

Als jij 1000 keer je RNG dan laat lopen, moet elk veld 100 hits hebben. En dan met 10.000 RN's ook weer. Hoe groter het aantal keer dat je de RNG laat lopen, hoe vlakker het resultaat moet zijn (dus alle cellen een gelijk aantal 'hits')

Zo kun je overigens ook checken of je RNG gecompromitteerd is.

[Boudewijn]

ja maar je bent wel erg voorspelbaar als je met een fixed lookup table werkt; dan kun je net zo goed de software RNG nemen lijkt me.
of mis ik iets?

[sebastius]

Ja je mist iets, dit is enkel een controle-middel. Puur statistiek gebruiken om te testen of je RNG goed is.

En software RNG kan ook behoorlijk random zijn hoor, neem de tijdstring, doe iets met XOR's enzo (als ik het me goed herinner), pak het XXde byte van je FAT table als seed en je RNG is best compleet denk ik. Compleet genoeg om door security testen heen te komen. Denk ik dan (geen feitelijke kennis aanwezig )

[ Voor 8% gewijzigd door sebastius op 05-06-2007 11:21 ]

[0fbe]

sebastius schreef op dinsdag 05 juni 2007 @ 10:02:
gewoon:

Elk getal heeft een veld in een tabel (bv 1 tot 10)

Als jij 1000 keer je RNG dan laat lopen, moet elk veld 100 hits hebben. En dan met 10.000 RN's ook weer. Hoe groter het aantal keer dat je de RNG laat lopen, hoe vlakker het resultaat moet zijn (dus alle cellen een gelijk aantal 'hits')

Zo kun je overigens ook checken of je RNG gecompromitteerd is.

Afwijking in aantallen haal je er zo inderdaad uit, regelmaat zal je door hits te tellen echter niet zien (123456890 heeft nog steeds van alles 1x)

[Boudewijn]

sebastius schreef op dinsdag 05 juni 2007 @ 11:20:
Ja je mist iets, dit is enkel een controle-middel. Puur statistiek gebruiken om te testen of je RNG goed is.

En software RNG kan ook behoorlijk random zijn hoor, neem de tijdstring, doe iets met XOR's enzo (als ik het me goed herinner), pak het XXde byte van je FAT table als seed en je RNG is best compleet denk ik. Compleet genoeg om door security testen heen te komen. Denk ik dan (geen feitelijke kennis aanwezig )

okay, maar wij willen marketing-technisch ook hw kunnen roepen