True Random Generator mit STM32F0

[Schnitzgi (Gast)]

Ciao Zämä

Die STM32F0 Serie bietet leider keinen Hardware random generator. Man 
kann den aber implementieren, ist nur etwas langsam (100µs pro Zahl oder 
so). Dazu nimmt man rauschen des internen Temperatursensors und zieht 
das durch den Hardware CRC Generator: basierend auf diesem Eintrag 
http://www.gniibe.org/memo/development/gnuk/rng/pqrng.html
hab ich mal den Code geschrieben, in einer Funktion echte Zufallszahlen 
(32bit) zu generieren. Das ganze könnte man sicher noch etwas 
optimieren, vorschläge willkommen. Das Ergebnis einiger tausend Zahlen 
sind im Graph angehängt.
Die Zahlen sind einiges besser als einfach direkt das rauschen vom ADC 
zu verwenden, dort gibt es Häufungen einiger Bitfolgen.

Hier der code, geschrieben für den STM32F030:

uint32_t getTrueRandomNumber(void) {

  ADC_InitTypeDef ADC_InitStructure;

  //enable ADC1 clock
  RCC_APB2PeriphClockCmd(RCC_APB2Periph_ADC1, ENABLE);

  // Initialize ADC 14MHz RC
  RCC_ADCCLKConfig(RCC_ADCCLK_HSI14);
  RCC_HSI14Cmd(ENABLE);
  while (!RCC_GetFlagStatus(RCC_FLAG_HSI14RDY))
    ;

  ADC_DeInit(ADC1);
  ADC_InitStructure.ADC_ContinuousConvMode = DISABLE;
  ADC_InitStructure.ADC_DataAlign = ADC_DataAlign_Right;
  ADC_InitStructure.ADC_Resolution = ADC_Resolution_12b;
  ADC_InitStructure.ADC_ScanDirection = ADC_ScanDirection_Backward;
  ADC_InitStructure.ADC_ExternalTrigConvEdge = ADC_ExternalTrigConvEdge_None;
  ADC_InitStructure.ADC_ExternalTrigConv = ADC_ExternalTrigConv_T1_TRGO; //default
  ADC_Init(ADC1, &ADC_InitStructure);

  //enable internal channel
  ADC_TempSensorCmd(ENABLE);

  // Enable ADCperipheral
  ADC_Cmd(ADC1, ENABLE);
  while (ADC_GetFlagStatus(ADC1, ADC_FLAG_ADEN) == RESET)
    ;

  ADC1->CHSELR = 0; //no channel selected
  //Convert the ADC1 temperature sensor, user shortest sample time to generate most noise
  ADC_ChannelConfig(ADC1, ADC_Channel_TempSensor, ADC_SampleTime_1_5Cycles);

  // Enable CRC clock 
  RCC_AHBPeriphClockCmd(RCC_AHBPeriph_CRC, ENABLE);

  uint8_t i;
  for (i = 0; i < 8; i++) {
    //Start ADC1 Software Conversion
    ADC_StartOfConversion(ADC1);
    //wait for conversion complete
    while (!ADC_GetFlagStatus(ADC1, ADC_FLAG_EOC)) {
    }

    CRC_CalcCRC(ADC_GetConversionValue(ADC1));
    //clear EOC flag
    ADC_ClearFlag(ADC1, ADC_FLAG_EOC);
  }

  //disable ADC1 to save power
  ADC_Cmd(ADC1, DISABLE);
  RCC_APB2PeriphClockCmd(RCC_APB2Periph_ADC1, DISABLE);

  return CRC_CalcCRC(0xBADA55E5);
}

[Steffen L. (slo)]

Hallo,

was genau ist in der Grafik zu sehen?
Welche Einheiten haben Abszisse und Ordinate?

Zeigt die Grafik die Häufigkeit mit der Werte vorkommen?
Oder hast du die Werte aus dem Zufallszahlengenerator nach Zahlenwert 
geordnet und der Reihen nach in den Grafen eingetragen, so dass auf der 
Abszisse die Anzahl der (sortierten) Zufallszahlen gezählt werden?

Grüße.

[D. S. (schnitzgi)]

Hallo Steffen,

sorry für die fehlende Beschreibung. Ich habe den Graphen so gemacht:
- alle erzeugten zahlen nach Grösse sortiert
- als Linie in excel geplottet

Also genau so, wie du das beschrieben hast.
Es gibt so also eine art 'Häufigkeit'. Häufen sich zahlen einer 
bestimmten grösse, gibt es dort eine weniger starke Steigung in der 
kurve, man sieht also 'dellen' bei Häufungen.
Man kann noch ein paar kleine 'dellen' erkennen, diese sollten aber bei 
genügend grosser Zahlenmenge verschwinden. Ich glaub ich hab hier um die 
3000 Punkte geplottet.
Das verfahren ist nicht ganz perfekt aber es kommt der Sache einer 
echten Zufallszahl schon sehr nahe.

[Gerd E. (robberknight)]

Die Frage ist warum Du einen "True" Random Generator brauchst und es 
nicht auch ein Pseudozufallsgenerator tut, z.B. rand() aus der 
C-Standardbibliothek. Den srand()-Aufruf zur Initialisierung am Anfang 
könntest Du ja mit ein paar ge-XORten Werten aus dem Temperatursensor 
machen.

Wenn Du es wirklich true random sein soll, dann wäre ich wegen den 
"Dellen" sehr skeptisch.

Ne ganz einfache Alternative dazu:
http://www.jtxp.org/tech/xr232usb.htm
Hier natürlich nur den Schaltungsteil mit dem LM393, den FTDI und µC 
brauchst Du natürlich nicht. Der zusätzliche Hardwareaufwand und 
Platinenplatz hält sich mit einem LM393 und etwas Hühnerfutter sehr in 
Grenzen.

Wenn wirklich hohe Qualitätsansprüche an die Zufallszahlen gestellt 
werden, würde ich das hier umsetzen:
https://github.com/waywardgeek/infnoise

[D. S. (schnitzgi)]

Gerd E. schrieb:
> Den srand()-Aufruf zur Initialisierung am Anfang
> könntest Du ja mit ein paar ge-XORten Werten aus dem Temperatursensor
> machen.

selbstberständlich. Dazu will man aber einen guten seed, was man mit der 
Funktion auch bekommt.

> Wenn Du es wirklich true random sein soll, dann wäre ich wegen den
> "Dellen" sehr skeptisch.

Du darfst den code gerne testen und die 'dellen' charakterisieren.

> Hier natürlich nur den Schaltungsteil mit dem LM393, den FTDI und µC
> brauchst Du natürlich nicht. Der zusätzliche Hardwareaufwand und
> Platinenplatz hält sich mit einem LM393 und etwas Hühnerfutter sehr in
> Grenzen.

Du meinst zusätzliche hardware einbauen, nur um ein paar random zahlen 
zu generieren? Niemals!

> Wenn wirklich hohe Qualitätsansprüche an die Zufallszahlen gestellt
> werden, würde ich das hier umsetzen:
> https://github.com/waywardgeek/infnoise

Ich würde dann einfach eine MCU klasse höher wählen, die grösseren STM32 
haben nämlich einen TRNG in hardware.

Du hast den zweck des codes etwas missverstanden. Es geht nicht darum, 
möglichst viele, möglichst perfekte Zufallszahlen zu erzeugen. Er zeigt 
nur, dass man auch mit einem STMF0 hinreichend gute Zufallszahlen 
hinbekommt.

[ante (Gast)]

Danke für's Teilen deiner Lösung, auch wenn gleich wieder 3x "... aber" 
kommt.

Das True stört mich und andere hierbei nämlich. Die Zahlen sollten 
erstmal Tests durchlaufen und für RNGs gibt es einige Verfahren nach 
deren Ergebnis die Güte des getesteten RNGs angegeben werden kann.

[ante (Gast)]

Achja, der größere STM32 hat keinen TRNG, sondern einen PRNG.

[D. S. (schnitzgi)]

ante schrieb:
> Achja, der größere STM32 hat keinen TRNG, sondern einen PRNG.

Stimmt, da hat du recht.
Ich denke mit genügend Iterationen der obigen Funktion sollten 'true' 
random zahlen aber möglich sein. Wie im text erwähnt ist er so noch 
nicht perfekt und ich hab es auch nicht ausführlich getestet. Die 
funktion hab ich geschrieben, dann aber doch nicht verwendet. Ich wollte 
random ID's generieren, hab dann aber rausgefunden, dass man dazu auch 
die unique chip-ID verwenden kann :)

[Bluemind (Gast)]

> sorry für die fehlende Beschreibung. Ich habe den Graphen so gemacht:
> - alle erzeugten zahlen nach Grösse sortiert
> - als Linie in excel geplottet

Wenn ich es richtig verstehe, dann sind die Zahlen doch gut verteilt.

Erzeuge doch einmal 100.000 Zahlen und hänge sie hier an.

[Daniel H. (Firma: keine) (commander)]

Schnitzgi schrieb:
> Das Ergebnis einiger tausend Zahlen
> sind im Graph angehängt.

Einen ähnlichen Graphen würde aber auch der folgende "TRNG" erzeugen 
(wenn man genügend viele "Zufallszahlen" anfordert):

uint32_t getRandom()
{
    static uint32_t i = 0ul;

    i++;

    return i;
}

Ich würde über den Output mal einen geeigneten Test wie z.B. Diehard 
laufen lassen, damit kriegt man dann eine bessere Abschätzung bzgl. der 
Qualität des erzeugten Zufalls.

https://en.wikipedia.org/wiki/Diehard_tests
http://www.phy.duke.edu/~rgb/General/dieharder.php

[Steffen R. (steffen_rose)]

Schnitzgi schrieb:
> rauschen des internen Temperatursensors

Für mich wäre interessant, welche Abhängigkeit die Zufallszahlen mit der 
Temperatur haben. (Abhängigkeit des Rauschens von der Temperatur)

[Daniel H. (Firma: keine) (commander)]

Hallo,

da mich das Thema sehr interessiert habe ich den RNG heute mal auf einem 
STM32F051R8 implementiert und mir anschließend 85.353.728 Bit generieren 
lassen (Diehard fordert >= 80.000.000 Bit). Anschließend habe ich dann 
Diehard (alle Tests) auf den so gesammelten Zufall losgelassen.

Diehard berechnet für jeden (Sub-)Test einen p-Wert, der zwischen 0 und 
1 liegt. Die berechneten p-Werte sollten bei einem guten RNG im 
Intervall 0 bis 1 gleichverteilt auftreten, d.h. dass z.B. 5% aller 
p-Werte zwischen 0.0 und 0.05 liegen sollten, 10% aller p-Werte zwischen 
0.0 und 0.1, 5% aller p-Werte zwischen 0.05 und 0.1 usw.. Abweichungen 
nach oben und unten sind natürlich möglich und in Grenzen tolerierbar.

Leider treten bei dem hier vorgestellten RNG starke Abweichungen auf wie 
die folgende Tabelle zeigt:

  p-Wert          Beobachtete             Erwartete
 Intervall     Wahrscheinlichkeit     Wahrscheinlichkeit
-----------   --------------------   --------------------
 0.0 - 0.1             5.0                   10.0
 0.1 - 0.2             9.0                   10.0
 0.2 - 0.3             5.0                   10.0
 0.3 - 0.4             6.1                   10.0
 0.4 - 0.5             5.0                   10.0
 0.5 - 0.6             5.3                   10.0
 0.6 - 0.7             6.1                   10.0
 0.7 - 0.8            10.0                   10.0
 0.8 - 0.9            11.1                   10.0
 0.9 - 1.0            37.4                   10.0

Insbesondere fällt auf, dass p-Werte > 0.9 mit einer Wahrscheinlichkeit 
von 37.4% auftreten, was signifikant vom Erwartungswert abweicht. Von 
243 gemessenen p-Werten hatten zudem 26 exakt den Wert 1.0. Der Test 
vermerkt hierzu:

When a bit stream really FAILS BIG, you will get p's of 0 or 1 to six or more places.

Ein Grund dürfte sein, dass der Temperatursensor einfach nicht genügend 
Entropie liefert, da die Temperatur im Regelfall recht stabil ist.

Viele Grüße
Daniel

[Clemens L. (c_l)]

Daniel H. schrieb:
> Ein Grund dürfte sein, dass der Temperatursensor einfach nicht genügend
> Entropie liefert

Diese Funktion liefert einen 32-Bit-Wert für 8 ADC-Werte; das setzt 4 
Bits Entropie pro Messung voraus. Es sollte rein theoretisch kein 
Problem sein, die for-Schleife anzupassen.

[D. S. (schnitzgi)]

Vielen Dank an Daniel fürs Testen.

Hatte genau denselben Gedanken wie Clemens: einfach die Schlaufe länger 
laufen lassen. Anfangs hatte ich versucht, 16 Durchgänge zu machen (ohne 
CRC) und jeweils zwei LSB zum Endresultat hinzugefügt mittels 
bit-shifts, die methode mit dem CRC hat aber bessere Resultate 
geliefert. Anscheinend noch nicht gut genug.

@Daniel: verbessert sich der Algorithmus, wenn man z.b. 32 
Schlaufendurchläufe anstatt nur deren 8 macht?

[Gerd E. (robberknight)]

Was man noch probieren könnte wäre die Sampling-Time runterzusetzen. Das 
dürfte noch mehr Rauschen in die Messung bringen.

[D. S. (schnitzgi)]

ADC_SampleTime_1_5Cycles ist schon das minimum, wie im Kommentar in der 
Zeile darüber bereits erwähnt.
Eventuell könnte man den clock noch erhöhen, indem man den vollen 
Busclock auf den ADC loslässt. Ich weiss jetzt nicht auswendig was die 
möglichen Optionen sind, aber mit dem Befehl
RCC_ADCCLKConfig(XXX);
kann man auch den Busclock nehmen.

[Daniel H. (Firma: keine) (commander)]

D. S. schrieb:
> @Daniel: verbessert sich der Algorithmus, wenn man z.b. 32
> Schlaufendurchläufe anstatt nur deren 8 macht?

Ich werde das mal testen und auch weiter mit rumspielen, finde ich 
extrem spannend :)

[Daniel H. (Firma: keine) (commander)]

D. S. schrieb:
> @Daniel: verbessert sich der Algorithmus, wenn man z.b. 32
> Schlaufendurchläufe anstatt nur deren 8 macht?

Interessanterweise scheint es mit Erhöhung der Schleifendurchläufe eher 
schlechter zu werden:

  p-Wert          Beobachtete             Erwartete
 Intervall     Wahrscheinlichkeit     Wahrscheinlichkeit
-----------   --------------------   --------------------
 0.0 - 0.1             5.5                   10.0
 0.1 - 0.2             5.9                   10.0
 0.2 - 0.3             1.9                   10.0
 0.3 - 0.4             4.1                   10.0
 0.4 - 0.5             7.6                   10.0
 0.5 - 0.6             6.4                   10.0
 0.6 - 0.7             8.5                   10.0
 0.7 - 0.8             6.8                   10.0
 0.8 - 0.9             9.9                   10.0
 0.9 - 1.0            43.4                   10.0

Ich probiere mal was passiert, wenn man die Durchläufe verringert. 
Außerdem werde ich mal einen kryptographisch sicheren PRNG 
implementieren und testen um sicherzustellen, dass mein Diehard nicht 
buggy ist.

[D. S. (schnitzgi)]

Interessant. Ich kenn mich zwar damit nicht aus aber gäbe es ein 
besseres CRC polynom?

[Daniel H. (Firma: keine) (commander)]

Hi,

ich glaube mittlerweile, dass der Diehard-Test den ich verwendet habe 
nicht ganz korrekt arbeitet, ein AES-OFB-basierte PRNG fiel ebenfalls 
durch.

Ich habe mir daraufhin die Dieharder-Testsuite installiert, allerdings 
benötigt diese Unmengen an Daten (je nach Test einige hundert MB bis 
einige hundert GB), die natürlich erst einmal generiert werden wollen.

Viele Grüße
Daniel

[Gerd E. (robberknight)]

Das CRC wird doch hier fürs Whitening verwendet.

Soweit ich das verstanden habe, sollte man die dieharder-Tests auf die 
rohen, nicht durchs Whitening gelaufenen, Zufallszahlen loslassen. Denn 
durch das Whitening kann ein Fehler im TRNG vor dieharder kaschiert 
werden. Gute PRNGs bestehen ja auch die dieharder-Suite.

Zur Evaluation würde ich daher auch einen raw-Modus implementieren den 
man bei Bedarf (=dieharder) aktivieren kann.

[Daniel H. (Firma: keine) (commander)]

Hallo,

der CRC ist hier aber Teil des RNG, da die Verarbeitung in 
getTrueRandomNumber() stattfindet. Betrachtet man diese Funktion als 
Blackbox dann sieht der Anwender von außen nur, dass diese einen TRNG 
darstellen soll und 32-bit Zufallszahlen liefert. Will er die Qualität 
des RNG beurteilen muss er also basierend auf diesen Zufallszahlen 
entsprechende Tests laufen lassen, da er von außen die rohen ADC-Werte 
gar nicht sieht. Somit stellen die ausgegebenen Zahlen auch die Rohdaten 
dar, welche an Diehard(er) gegeben werden müssen.

Letztendlich ist das Whitening sogar ein erwünschter Effekt um Fehler 
oder Unzulänglichkeiten in TRNGs zu kaschieren. Die neue NIST SP 800-90C 
schlägt hierfür explizit zwei Konstrukte vor, XOR und Oversampling, 
welche voraussetzen, dass TRNGs gemäß NIST SP 800-90B und PRNGs gemäß 
NIST SP 800-90A verwendet werden.

Beim XOR-Konstrukt wird zunächst ein PRNG mit Hilfe eines TRNG geseedet. 
Bei Anforderung einer Zufallszahl erzeugen beide dann je eine 
Zufallszahl, welche anschließend miteinander ver-XOR-ed werden, das 
Ergebnis ist dann die Zufallszahl, die ausgegeben wird, d.h.:

Init:
1. PRNG(TRNG())

Get Random:
1. r1 = TRNG()
2. r2 = PRNG()
3. r = r1 XOR r2

Beim Oversampling wird ein PRNG bei jeder neuen Anforderung einer 
Zufallszahl mit dem TRNG neu geseedet, die darauf folgende Ausgabe des 
PRNG ist dann die Zufallszahl, die ausgegeben wird, d.h.:

Init:
1. PRNG(TRNG())

Get Random:
1. PRNG(TRNG())
2. r = PRNG()

In beiden Fällen führt ein Ausfall bzw. ein Fehler im TRNG nicht zu 
einer unmittelbaren Reduzierung der Entropie, da der PRNG nach wie vor 
genügend Entropie liefert. Erkannt werden kann das nur, wenn es einem 
Angreifer gelingt den Zustand des RNG vollständig zurückzusetzen (z.B. 
durch einen Reset), da im Falle eines Ausfalls / Fehlers des TRNG dann 
natürlich immer mit dem gleichen Wert geseedet wird und der PRNG somit 
auch die gleiche Sequenz erzeugt.

Im hier vorliegenden Fall würde ich den RNG als Oversampling-Konstrukt 
betrachten, der TRNG ist dabei der ADC und der PRNG der CRC. Was 
natürlich im Umkehrschluss noch lange nicht bedeutet, dass der so 
konstruierte RNG kryptographisch sicher gemäß NISt SP 800-90C ist.

Viele Grüße
Daniel

[Clemens L. (c_l)]

D. S. schrieb:
> gäbe es ein besseres CRC polynom?

Nicht in Hardware.

Bessere CRCs (zur Fehlererkennung): 
https://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
Aber da das CRC wird hier wie ein Hash verwendet wird, kann man dann 
auch irgendeinen anderen Algorithmus nehmen.

Gerd E. schrieb:
> Das CRC wird doch hier fürs Whitening verwendet.

Nein, als Entropie-Extraktor.

> Soweit ich das verstanden habe, sollte man die dieharder-Tests auf die
> rohen, nicht durchs Whitening gelaufenen, Zufallszahlen loslassen.

Die rohen ADC-Werte wären nicht 100% zufällig.

[Gerd E. (robberknight)]

Daniel H. schrieb:
> der CRC ist hier aber Teil des RNG, da die Verarbeitung in
> getTrueRandomNumber() stattfindet. Betrachtet man diese Funktion als
> Blackbox dann sieht der Anwender von außen nur, dass diese einen TRNG
> darstellen soll und 32-bit Zufallszahlen liefert.

klar.

Aber er kann aus einer Blackbox heraus nicht mehr abschätzen, wie gut 
der TRNG-Anteil ist und wie oft die Whitening-Funktion einschreiten 
musste, um Defizite des TRNGs zu kaschieren.

So kann man die Qualität des echten Zufalls nicht beurteilen. Das ist 
ein wesentlicher Kritikpunkt an vielen kommerziell erhältlichen TRNGs.

> Letztendlich ist das Whitening sogar ein erwünschter Effekt um Fehler
> oder Unzulänglichkeiten in TRNGs zu kaschieren.

Das ist klar. Für die normale Anwendung nimmst Du natürlich das 
Whitening. Aber zur Beurteilung des TRNGs brauchst Du die Rohdaten.

[Gerd E. (robberknight)]

Clemens L. schrieb:
> Die rohen ADC-Werte wären nicht 100% zufällig.

Ein Bias ist für Dieharder kein Problem.