Was zeichnet gute Pseudozufallszahlen aus?

Dr. Werner Schindler, BSI

Viele kryptographische Anwendungen benötigen Zufallszahlen. Ungeeignete Zufallszahlen können grundsätzlich starke kryptographische Mechanismen entscheidend schwächen. Daraus ergibt sich die Notwendigkeit, Zufallszahlengeneratoren zu bewerten. Seit Dezember 1999 ist die AIS 20 ("Funktionalitätsklassen und Evaluationsmethodologie für deterministische Zufallszahlengeneratoren") in Kraft.

Die Gesamtheit der Zufallszahlengeneratoren kann man grob in drei Klassen einteilen, nämlich in Pseudozufallszahlengeneratoren, physikalische Zufallszahlengeneratoren (physikalische Rauschquellen) und "Hybridverfahren". Während Pseudozufallszahlen algorithmisch erzeugt werden, nutzen physikalische Zufallszahlengeneratoren nicht vorhersagbare physikalische Prozesse aus; etwa thermisches Rauschen einer in Sperrichtung geschalteten Zener-Diode. Hybridverfahren sind im Wesentlichen deterministische Zufallszahlengeneratoren, denen regelmäßig "echter Zufall" (Tippgeschwindigkeit oder Mausbewegung des Nutzers, aktuelle Inhalte des Arbeitsspeichers etc.) zugeführt wird. Beispielsweise nutzt SSL ein Hybridverfahren zur Generierung zufälliger Sessionkeys. Im Folgenden werden die Pseudozufallszahlen genauer betrachtet.

Klassische Anwendungsbereiche für Pseudozufallszahlen sind stochastische Simulationen und Monte-Carlo-Integrationen. Mit Hilfe stochastischer Simulationen kann man Näherungslösungen für Fragestellungen erhalten, die von zufälligen Einflüssen mit bekannter Wahrscheinlichkeitsverteilung abhängen, in ihrer Gesamtheit für exakte analytische Lösungsansätze aber zu komplex sind. Der gesamte Ablauf wird auf einem Rechner vielfach "durchgespielt", wobei die Pseudozufallszahlen die partikulären zufälligen Einflüsse repräsentieren. Aus den Simulationsergebnissen wird die gesuchte Näherungslösung abgeleitet. Die Palette möglicher Anwendungen ist vielfältig ([AL], [Kn], [Sch1] etc.).

Mit der Entdeckung und der raschen Verbreitung der Public-Key-Kryptographie hat sich in den letzten zwei Jahrzehnten ein weiteres, ständig wachsendes Anwendungsfeld eröffnet; man denke etwa an Challenge-Response-Protokolle, das Erzeugen zufälliger Sessionkeys oder an Zero-Knowledge-Protokolle.

Anwendungsabhängige Bewertung von Pseudozufallszahlen

Pseudozufallszahlen sind deterministisch erzeugte Zahlen, oder allgemeiner, deterministisch erzeugte Werte, die ähnliche Eigenschaften aufweisen sollen wie Ausgabefolgen. Da Pseudozufallszahlen deterministisch von einem Anfangszustand (seed) abhängen, kann ein deterministischer Zufallszahlengenerator – anders als physikalische Rauschquellen – durch das Erzeugen neuer Zufallszahlen die Gesamtentropie der Zufallszahlenfolge nicht über die Entropie des Seed hinaus erhöhen. Folgen deterministisch erzeugter Zufallszahlen können daher nicht "zufällig" im eigentlichen Sinn sein, sondern sie können sich bestenfalls im Hinblick auf bestimmte Eigenschaften ähnlich wie "echte", d.h. wirklich zufällige Folgen verhalten. Der Vorteil der Pseudozufallszahlengeneratoren gegenüber physikalischen Zufallszahlengeneratoren bzw. Hybridverfahren liegt vor allem im Preis bzw. der Geschwindigkeit, mit der Zufallszahlen erzeugt werden können.

Vor allem im Zusammenhang mit stochastischen Simulationen sind in der Literatur verschiedenste Ansätze zur Charakterisierung "guter" Zufallszahlenfolgen vorgeschlagen und untersucht worden; typischerweise mittels statistischer Tests oder komplexitätstheoretischer Überlegungen (siehe z.B. [Kn]). Im Kontext kryptographischer Anwendungen verdienen vor allem [FI140] (4.11.1) und [IEP] (G.4.5) Erwähnung. Während die erste Referenz statistische Tests formuliert, die "gute" Zufallszahlenfolgen passieren sollten, macht die zweite (wenngleich äußerst vage!) die Eignung eines deterministischen Zufallszahlengenerators (Pseudozufallszahlengenerators) an der praktischen Unvorhersagbarkeit der von ihm erzeugten Zufallszahlenfolgen fest.

Zurück zu den drei kryptographischen Anwendungsbeispielen aus dem ersten Abschnitt. In den Protokollspezifikationen ist normalerweise von Zufallszahlen, zufälligen Schlüsseln o.ä. die Rede. Wie man die Zufallszahlen oder zufällige Schlüssel indes erzeugen soll, darüber schweigen sich die Spezifikationen üblicherweise allerdings aus.

Welche Eigenschaften müssen diese zufälligen Werte erfüllen? Bei Challenge-Response-Protokollen genügt es normalerweise, dass die erzeugten Werte paarweise verschieden sind, um das Wiederverwenden alter Nachrichten zu verhindern. Zero-Knowledge-Protokolle basieren darauf, dass die Zufallswerte unvorhersagbar sind, und zufällige Sessionkeys dürfen selbst dann nicht erratbar sein, falls ein potenzieller Angreifer eine Teilfolge von Vorgänger- oder Nachfolgerschlüsseln kennt; etwa weil er bei diesen Kommunikationsverbindungen (z.B. im Rahmen einer e-commerce-Anwendung) selbst der legitime Kommunikationspartner war.

Schon die oberflächliche Analyse dieser drei Beispiele zeigt, dass verschiedene (kryptographische) Anwendungen unterschiedliche Anforderungen an die benötigten Zufallszahlen stellen. Da deterministisch erzeugte Zufallszahlen sich ohnehin nur in Bezug auf bestimmte Kriterien wie "echte" Zufallszahlen verhalten können, legt dies den Gedanken nahe, die Eignung deterministischer Zufallszahlengeneratoren in Abhängigkeit von der bzw. den avisierten Anwendungen zu bewerten. Retrospektiv sollte der Titel demnach eigentlich weniger griffig "Was zeichnet Pseudozufallszahlen aus, die für bestimmte Anwendungen geeignet sind?" lauten.

Bewertung von Pseudozufallszahlengeneratoren

Ganz offenkundig können ungeeignete Zufallszahlen sicherheitskritische Anwendungen mit, für sich allein betrachtet, starken kryptographischen Mechanismen entscheidend schwächen. Daher ist eine Bewertung von Zufallszahlengeneratoren im Rahmen von IT-Produktevaluierungen unbedingt erforderlich. Dennoch liefern Evaluationshandbücher hierzu keine Hinweise.

In [Sch2] wurde der Gedanke einer anwendungsabhängigen Bewertung aufgegriffen und als Konsequenz ein 4-Klassen-Modell formuliert. In Abstimmung mit den akkreditierten Prüfstellen entwickelte sich hieraus das Dokument "W. Schindler: Funktionalitätsklassen und Evaluationsmethodologie für deterministische Zufallszahlengeneratoren" in [AIS 20]. Für deterministische Zufallszahlengeneratoren (Pseudozufallszahlengeneratoren) schließt die AIS 20 die oben angesprochene Lücke in der Evaluationsmethodologie. Sie ist verbindlich, falls ein Hersteller ein deutsches IT-Sicherheitszertifikat anstrebt. Inzwischen ist die AIS 20 ins Englische übersetzt und über DIN bei ISO eingereicht.

Der Grundgedanke besteht darin, die Eignung deterministischer Zufallszahlengeneratoren in Abhängigkeit von den kryptographischen Anwendungen zu beurteilen, in denen sie eingesetzt werden. [AIS 20] definiert klassenspezifische Eigenschaften, legt die notwendigen Angaben des Antragstellers fest und beschreibt die Aufgaben des Evaluators. Die Praktikabilität der Evaluationskriterien wird an Beispielen demonstriert. Nachfolgend wird das Grundkonzept erläutert, und die klassenspezifischen Eigenschaften werden informell beschrieben. Außerdem werden zu jeder Funktionalitätsklasse typische kryptographische Anwendungen angegeben.

Das vollständige Dokument ist beim BSI, Referat II 2 erhältlich. Zur Zeit befindet es sich samt englischer Übersetzung außerdem auf der Internetseite des BSI, und zwar unter  http://www.bsi. de/aufgaben/ii/zert/ais/ais.htm unter AIS 20 bzw. AIS 20 (engl.).

Evaluationsgegenstand ist nicht die technische Realisierung des Pseudozufallszahlengenerators, sondern ein 5-Tupel (S,R,φ,ψ,p_A), das die logische Struktur beschreibt. Im Einzelnen bedeuten

S

die (endliche) Menge aller möglichen inneren Zustände des Pseudozufallszahlengenerators,

R

die Menge der möglichen Ausgabewerte (Zufallszahlen),

φ: S → S

die Zustandsfunktion,

ψ: S → R

die Ausgabefunktion,

p_A

ein Wahrscheinlichkeitsmaß, das die Verteilung des seed angibt.

In Schritt n≥1 wird zunächst der innere Zustand mittels s_n := φ(s_n-1) ∈ S erneuert, und anschließend wird eine Zufallszahl r_n := ψ(s_n) ∈ R berechnet und ausgegeben.

Obwohl die Auswahl des Anfangszustands nicht im eigentlichen Sinn zur Beschreibung eines Pseudozufallszahlengenerators gehört, ist die dadurch induzierte Wahrscheinlichkeitsverteilung (beschrieben durch p_A) für viele Anwendungen keineswegs unerheblich (siehe unten). Der Antragsteller muss daher eine nachvollziehbare und plausible Begründung abgeben, weshalb der von ihm gewählte Auswahlmechanismus die Verteilung p_A induziert.

Pseudozufallszahlengeneratoren, in [AIS 20] als DRNGs (deterministic random number generator) bezeichnet, werden in Klassen K1, K2, K3 und K4 mit aufsteigenden Anforderungen eingeteilt. Nachfolgend werden die klassenspezifischen Anforderungen informell beschrieben, die die jeweilige Klasse zusätzlich zu der darunterliegenden Klasse verlangt.

K1: Eine aus Zufallszahlen r₁,r₂,... gebildete Folge von Zufallsvektoren (r₁,...,r_c),(r_c+1,...,r_2c),...,(r _M-c+1,...,r_M) soll mit hoher Wahrscheinlichkeit nur paarweise verschiedene Elemente enthalten.

Bemerkung: Statistische Eigenschaften der erzeugten Zufallsvektoren sind ohne Belang. Der Parameter c hängt im Wesentlichen von den avisierten Anwendungen ab und wird vom Antragsteller ebenso angegeben wie die Quantifizierung des Terms "mit hoher Wahrscheinlichkeit". Durch die angestrebte Mechanismenstärke sind hierbei jedoch Grenzen gesetzt.

Beispiel: Challenge-Response-Protokolle.

K2: zusätzlich zur K1-Eigenschaft: Zufallszahlen r₁,r₂, ... und ihre Projektionen auf einzelne Bits passieren bestimmte statistische Tests.

Denkbare Anwendungen: Von Schieberegistern gesteuerte Stromchiffre, deren Anfangsbelegungen sich aus geheimgehaltenen Langzeitschlüsseln und einem Spruchschlüssel ergeben, wobei Letzterer zu Beginn der Kommunikation offen übertragen wird; offen übertragene, nichtkonstante Initialisierungsvektoren

K3: zusätzlich zu den K2-Eigenschaften: Es ist einem Angreifer nicht praktisch möglich, zu einer ihm bekannten Zufallszahlenteilfolge r_i,r_i+1,...,r_i+j Vorgänger, Nachfolger oder gar einen inneren Zustand zu errechnen. Die Ratewahrscheinlichkeit soll bestenfalls vernachlässigbar über der ohne Kenntnis der Teilfolge liegen. Letztere muss so klein sein (Seedauswahl!), dass hieraus kein reales Risiko erwächst.

Bemerkung: Das dem Angreifer zugebilligte Angriffspotenzial hängt von der Mechanismenstärke ab.

Denkbare Anwendungen: Erzeugung von Signaturschlüsselpaaren, Spruchschlüsselerzeugung, pseudozufällige Paddingbits, Zero-Knowledge-Proofs.

K4: zusätzlich zu den K3-Eigenschaften: Es ist einem Angreifer nicht praktisch möglich, aus Kenntnis eines inneren Zustands s_i Vorgängerzufallszahlen oder gar einen inneren Vorgängerzustand zu errechnen. Die Ratewahrscheinlichkeit soll bestenfalls vernachlässigbar über der ohne Kenntnis von si liegen

Bemerkung: Die K4-spezifische Anforderung berücksichtigt das Szenario, dass sich ein Angreifer in den Besitz der technischen Realisierung des DRNGs bringt und in der Lage ist, den inneren Zustand des DRNG zu rekonstruieren. Das dem Angreifer zugebilligte Angriffspotenzial hängt von der Mechanismenstärke ab.

Denkbare Anwendungen: Erzeugung von Signaturschlüsselpaaren, Spruchschlüsselerzeugung, pseudozufällige Paddingbits.

© BSI, D-53133 Bonn,
© SecuMedia-Verlags-GmbH, D-55205 Ingelheim,
KES 3/2000, Seite 57

Zurück zum Inhalt