Diehard ist der Name einer „Testbatterie“ (auch: „Testsuite“ oder „Testsortiment“) zur Prüfung der Zufälligkeit einer gegebenen Zeichenfolge, beispielsweise aus Ziffern und/oder Buchstaben oder aus Bytes.

Das englische Wort diehard hat mehrere Bedeutungen und kann hier, als Adjektiv aufgefasst, vielleicht am treffendsten mit „unermüdlich“ übersetzt werden.Eintrag diehard im PONS-Wörterbuch, abgerufen am 8. März 2024. Die erste Silbe die separat betrachtet bedeutet „Würfel“ und kann zusammen mit hard () auch als Wortspiel interpretiert werden.

Erzeugung von Zufallsfolgen mini|300px|Beispiel eines Zufalls­textes aus Groß­buchstaben (hier gruppiert in Fünfer­gruppen) Der amerikanische Mathematiker und Informatiker George Marsaglia (1924–2011) interessierte sich ab den 1960er-Jahren mehrere Jahrzehnte lang sehr für das Phänomen „Zufall“, insbesondere für die Erzeugung von möglichst zufälligen Zahlen („Zufallszahlen“) oder zufälligen Buchstabenfolgen („Zufallstexten“), wie sie beispielsweise in der Kryptologie benötigt werden, und stellte sich selbst die Frage, wie sich „Zufälligkeit“ messen lässt.

Man wusste bereits, dass es alles andere als trivial ist, mithilfe von Algorithmen „gute“ Zufallsfolgen zu erzeugen. Mit „gut“ sind hier Zeichenfolgen gemeint, die sich von „echten“ Zufallsfolgen nicht unterscheiden lassen, also, die keinerlei Gesetzmäßigkeiten erkennen lassen und deren statistische Kenngrößen, wie beispielsweise Mittelwert oder Varianz, keine Auffälligkeiten zeigen. Man spricht hier von Pseudozufall.

Zwar gibt es eine Reihe von Zufalls­zahlen­generatoren, die mehr oder weniger „gute“ Zufallsfolgen erzeugen können, beispielsweise Pseudo­zufalls­folgen für Test­signale, die für spezielle Zwecke durchaus „hinreichend“ zufällig sein können. Letztlich handelt es sich dabei in der Regel jedoch um deterministische Zeichenfolgen, da sie mithilfe gewisser mathematischer Vorschriften berechnet werden. Daher werden diese als Pseudo­zufallszahlen­generatoren bezeichnet.

Für kryptographisch sichere Zufalls­zahlen­generatoren, die „möglichst echten“ Zufall erzeugen sollen, also unvorhersehbare nicht­deterministische Zufalls­zahlen­folgen, nutzt man zumeist physikalische Zufalls­zahlen­generatoren, beispielsweise Rauschgeneratoren. Zuweilen nimmt man auch menschliche Aktionen oder Reaktionen her, beispielsweise Bewegungen der Computermaus oder Zeiten in Millisekunden zwischen Tastendrücken, um daraus Zufallswerte abzuleiten. Allerdings zeigt sich, dass auch diese Ereignisse nicht wirklich zufällig sind, sondern ebenfalls nur quasizufällig. Folglich weisen auch die auf diese Weise erzeugten Zufallszahlen eine mehr oder weniger gute Qualität auf, beispielsweise sind sie zumeist noch nicht einmal gleichverteilt. Marsaglia konnte mithilfe seiner Testbatterie zeigen, dass auch die mithilfe von beispielsweise physikalischen Rauschgeneratoren erzeugten Zufallszahlen nicht alle Tests bestehen, im Gegenteil: „They fail many of the tests in DIEHARD“ ().George Marsaglia: Instructions for using DIEHARD – a battery of tests of randomness. Diehard.doc, 7. Januar 1997, S. 3 (englisch).

Daher gab Marsaglia die explizite Empfehlung, zur Erzeugung von „guten“ Zufallsfolgen am besten mehrere – möglichst unterschiedliche – Verfahren zu benutzen und deren Ergebnisse anschließend mithilfe eines Mischers miteinander zu kombinieren. Dabei geht er von dem Grundsatz aus, dass das Ergebnis der Kombination von zwei oder mehreren Zufallsfolgen niemals weniger zufällig ist als jede einzelne, was er empirisch belegen konnte.George Marsaglia: Instructions for using DIEHARD – a battery of tests of randomness. Diehard.doc, 7. Januar 1997, S. 3 (englisch). Marsaglia stellt in einer ZIP-Datei (siehe auch: Diehard.zip unter Weblinks) eine Vielzahl von Pseudo­zufalls­zahlen­generatoren in Form einer EXE-Datei namens Makewhat.exe („Mach was“) zur freien Verfügung sowie auch eine Meld.exe („Verschmelze“) zum Mischen zweier Zufallsdateien.

Messung der Zufälligkeit Interessanterweise zeigt sich, dass ähnlich wie die Erzeugung von Zufall auch ein Test auf Zufälligkeit alles andere als trivial ist. Niemand kennt eine einfache Methode, mit der man zuverlässig feststellen kann, ob eine gegebene Zeichenfolge wirklich zufällig ist oder nicht. Allerdings gibt es diverse statistische Kenngrößen, die man überprüfen kann, und die ein Maß für die „Qualität des Zufalls“ ergeben.

Beispiel Mittelwert mini|Spielwürfel als physikalischer Zufalls­zahlen­generator Ein ganz simpler und durchaus nützlicher Test auf Zufälligkeit ist die Berechnung des Mittelwerts. Beispielsweise könnte man damit die Qualität eines Spielwürfels überprüfen. Ein perfekter Würfel sollte jede Zahl zwischen 1 und 6 gleich häufig erzeugen. Wirft man ihn tausend Mal und addiert alle Ergebnisse, dann sollte sich eine Summe von etwa 3500 ergeben, da ja im Mittel bei sechs Würfen 1+2+3+4+5+6 = 21, also pro Wurf im Mittel 21/6 = 3,5 erzeugt wird. Eine große Abweichung im Ergebnis, beispielsweise 4000, würde den Würfel verdächtig erscheinen lassen. Umgekehrt wäre ein perfekter Mittelwert jedoch keinerlei Garantie für einen einwandfreien Würfel. Ein defekter Würfel könnte beispielsweise sehr häufig die Zahlen 1 und 6 ergeben, und diese beiden möglicherweise gleich häufig, hingegen selten oder nie die anderen Zahlen. Auch dann wäre der Mittelwert jedoch 3,5. Das heißt, der Mittelwert-Test würde solch einen defekten Würfel nicht entlarven.

Beispiel Gleichverteilung Ein alternativer und ebenso simpler Test wäre die Prüfung der Gleichverteilung. Hiermit würde der obige defekte Würfel sofort erkannt. Ein anderer „fiktiver Würfel“, hier durch einen Algorithmus realisiert, der nacheinander stets die Folge 1, 2, 3, 4, 5, 6 erzeugt, würde den Gleichverteilungs-Test glänzend bestehen und auch den Mittelwert-Test. Dennoch wäre natürlich solch eine Folge keineswegs zufällig, sondern in höchstem Maße deterministisch, also völlig unbrauchbar.

Testbatterie Wie sich zeigt, genügt kein einzelner Test, um die „wirkliche“ Zufälligkeit einer Zeichenfolge zu überprüfen. Ähnlich wie bei einer Batterie beim Militär, bei der mehrere Kanonen eingesetzt werden, um eine möglichst große Wirkung zu entfalten, hatte Marsaglia die Idee, eine Testsuite, also ein Sortiment von Tests zu benutzen, um die Zufälligkeit zu messen oder abzuschätzen. Er nutzte hierfür den Begriff einer „Testbatterie“. Erstmals im Jahr 1995 veröffentlichte er seine Diehard Battery of Tests of Randomness, . Sie erschien auf einer CD-ROM zusammen mit Dateien, die große Mengen (viele Megabyte) an Zufallszahlen bereitstellten. Im Jahr 2006 wurden diese ursprünglichen Diehard-Tests durch Robert G. Brown von der Duke University zu Dieharder-Tests erweitert.

Im Folgenden werden die von George Marsaglia in den 1990er-Jahren vorgeschlagenen Diehard-Tests kurz beschrieben. Details können seiner Textdatei entnommen werden (siehe auch: test.txt in Diehard.zip unter Weblinks). Die meisten Tests ergeben einen p‑Wert, der das Ergebnis der Untersuchung zusammenfasst und zwischen Null und Eins liegt. Falls ein Test nicht bestanden wird, die Zufallsfolge also als „schlecht“ erkannt wird, dann ist der p‑Wert sehr nahe bei 0 oder bei 1. Bei einer als „gut“ bewerteten Folge liegt er dazwischen, jedoch nicht zwingend bei 0,5 in der Mitte. Im Einzelfall können p‑Werte nahe 0 oder 1 „durch Zufall passieren“. Über alle Tests gesehen, sollten sie näherungsweise gleichverteilt zwischen 0 und 1 liegen.

Geburtstagsabstände (Birthday Spacings) Die Bezeichnung ist angelehnt an das Geburtstagsparadoxon. Der Test wählt abhängig von der zu prüfenden Folge zufällige Punkte in einem großen Intervall, ähnlich wie Geburtstage innerhalb eines Jahres. Dazu werden systematisch unterschiedliche, spezifische Bits aus der Folge ausgewählt und diese als Zeitpunkte interpretiert. Die Abstände zwischen den Zeitpunkten (Geburtstagen) sollten asymptotisch einer Poisson-Verteilung entsprechen.

Überlappende Permutationen (Overlapping Permutations) Hier werden jeweils fünf aufeinanderfolgende ganze Zahlen (Integers oder Bytes) betrachtet. Logischerweise gibt es für fünf unterschiedliche Elemente 5! (Fakultät), also 120 denkbare Anordnungen (Permutationen). Diese sollten im statistischen Mittel in der Folge mit gleicher Wahrscheinlichkeit auftreten.

Ränge von 31×31-Matrizen (Binary Rank Test) Hierzu werden der zu prüfenden Folge systematisch einzelne Bits entnommen und damit eine Matrix der Größe 31×31 binär aufgefüllt. Anschließend wird der Rang der Matrix bestimmt, der theoretisch zwischen 0 und 31 liegen kann, wobei jedoch Ränge kleiner als 28 vergleichbar selten auftreten sollten. Die Ergebnisse von 40.000 Versuchen werden mithilfe des Chi-Quadrat-Tests mit dem Erwartungswert verglichen.

Ränge von 32×32-Matrizen Dieser Test entspricht dem vorherigen, jedoch hier mit Matrizen der Größe 32×32.

Ränge von 6×8-Matrizen Hier werden jeweils sechs Bytes, also 6×8 Bits, der Folge entnommen und diese in eine Matrix geschrieben. Auch hier werden die Ränge der Matrizen bestimmt, wobei Ränge kleiner als 4 entsprechend selten auftreten sollten.

Bitfolge (Bitstream Test) Die Zufallsfolge wird überlappend bitmäßig betrachtet und aus jeweils 20 aufeinanderfolgenden Bits wird ein „Wort“ (aus Nullen und Einsen) gebildet. Das Vorkommen aller denkbaren 220, also 1.048.576 möglichen „Wörter“ wird geprüft und speziell das Nicht-Vorkommen von Wörtern gezählt. Im Idealfall sollten diese normalverteilt sein.

Affentests mini|Wenn nur ausreichend lange zufällig auf einer Schreibmaschine getippt wird, dann entstehen so auch sinnvolle Texte. Grundlage ist das Theorem des endlos tippenden Affen, das besagt, dass ein Affe, der unendlich lange zufällig auf einer Schreibmaschine herumtippt, irgendwann auch jedes beliebige Buch schreiben wird.

Überlappende Paare Hier werden jeweils zehn Bit aus der Folge entnommen und als ein „Buchstabe“ aus einem „Alphabet“ mit 210 also 1024 möglichen Buchstaben aufgefasst. Zwei solcher Buchstaben als Paar ergeben ein „Wort“. Auf diese Weise werden systematisch nacheinander insgesamt 221 gleich 2.097.152 Wörter gebildet. Anschließend wird geprüft, wie viele Wörter nicht ein einziges Mal aufgetreten sind.

Überlappende Quadrupel Dasselbe wird statt mit Buchstabenpaaren, also Wörtern der Länge zwei, auch mit Wörtern der Länge vier durchgeführt, also Buchstaben-Quadrupeln.

Überlappende DNAs Drittens werden jeweils zwei Bit aus der Folge entnommen und als ein DNA-Baustein Adenin (A), Guanin (G), Thymin (T) oder Cytosin (C) interpretiert. Man könnte auch sagen, als ein Buchstabe aus einem Alphabet mit nur vier Buchstaben. Jeweils zwanzig Bits können nun als ein Wort aus zehn dieser Buchstaben aufgefasst werden. Hier sind 410 unterschiedliche Wörter möglich, deren statistische Verteilung durch den Test überprüft wird.

Zähl die Einsen für eine Bytefolge (Count-The-1s) Nacheinander wird jedes einzelne Byte der Folge betrachtet. In jedem Byte können zwischen null und acht binäre Einsen auftreten, wobei diese neun Fälle unterschiedlich häufig sind (1, 8, 28, 56, 70, 56, 28, 8, 1). Für die Extremfälle (null Einsen und acht Einsen) gibt es nur jeweils eine Möglichkeit; jedoch für vier Einsen gibt es 70 Möglichkeiten. Mithilfe des Chi-Quadrat-Tests wird die Erfüllung des Erwartungswerts überprüft.

Zähl die Einsen für spezielle Bytes Innerhalb eines 32-bit-Datenworts werden acht Bit ausgewählt und die Anzahl der Einsen gezählt. Anschließend werden die einzelnen Zählergebnisse in Buchstaben umgesetzt, wobei null bis zwei Einsen den Buchstaben A ergeben, drei ein B, vier ein C, fünf ein D und sechs bis acht Einsen ein E. Somit ergeben sich Wörter aus fünf Buchstaben mit unterschiedlichen Wahrscheinlichkeiten der Buchstaben von 37, 56, 70, 56 und 37 aus 256 Fällen. Geprüft wird die Auftretenshäufigkeit aller Wörter im Vergleich zu den einzelnen Erwartungswerten.

Parkplatztest (Parking Lot Test)