Kleiner Seed-Raum in PRNG

Beschreibung

Kleiner Seed-Raum in PRNG ist eine Schwachstelle, die auftritt, wenn ein Pseudo-Zufallszahlengenerator (PRNG) mit einem Wert aus einem zu kleinen Raum geseedet wird, was ihn anfällig für Brute-Force-Angriffe macht. Da PRNGs deterministische Algorithmen sind, die vorhersagbare Ausgabesequenzen basierend auf ihrem Seed-Wert erzeugen, können Angreifer, die PRNG-Ausgaben sammeln können, versuchen, den Seed zu bestimmen, indem sie alle möglichen Seed-Werte gegen die beobachtete Ausgabe testen. Wenn der Seed-Raum begrenzt ist (z.B. ein 32-Bit oder 48-Bit Seed), können Angreifer erschöpfend alle möglichen Seeds in praktikabler Zeit testen. Selbst mit modernen CPUs, die Millionen von Seeds pro Sekunde testen, bleibt ein 128-Bit oder 256-Bit Seed-Raum rechnerisch nicht per Brute-Force durchsuchbar, während ein 48-Bit Seed in Stunden erschöpft werden kann.

Risiko

Ein kleiner Seed-Raum begrenzt grundlegend die Sicherheit jedes PRNG-basierten Mechanismus, unabhängig davon, wie die Zufallswerte verwendet werden. Javas java.util.Random verwendet nur einen 48-Bit Seed, was bedeutet, dass alle seine Ausgaben auf nur 2^48 (etwa 281 Billionen) mögliche Sequenzen beschränkt sind. Obwohl das groß klingt, ist es mit modernen Computerressourcen trivial durchsuchbar. Angreifer, die selbst eine kleine Menge PRNG-Ausgabe erfassen, können alle möglichen Seeds testen, um einen zu finden, der passende Ausgabe erzeugt, und dann alle zukünftigen Ausgaben vorhersagen. Dies ermöglicht Session-Hijacking, wenn Session-Tokens aus klein geseedeten PRNGs generiert werden, Anmeldedaten-Vorhersage für generierte Passwörter und kryptografische Schlüsselwiederherstellung. Die Schwachstelle ist besonders heimtückisch, weil die PRNG-Ausgabe zufällig erscheinen und statistische Tests bestehen kann, während sie vollständig vorhersagbar ist.

Lösung

Verwenden Sie gut geprüfte PRNG-Algorithmen mit angemessenen Seed-Längen. Ein Minimum von 256-Bit Seed bietet eine solide Grundlage für sicherheitsrelevante Anwendungen. Verwenden Sie kryptografisch sichere PRNGs (CSPRNGs), die mit angemessen großen internen Zustandsräumen konzipiert sind. In Java verwenden Sie SecureRandom anstelle von Random. In Python verwenden Sie das secrets-Modul oder os.urandom(). In C verwenden Sie RAND_bytes() von OpenSSL oder getrandom(). Stellen Sie sicher, dass der Seed aus hochwertigen Entropiequellen mit mindestens so viel Entropie abgeleitet wird, wie die Seed-Größe erfordert. Folgen Sie FIPS 140-2 oder FIPS 140-3 Richtlinien für zugelassene Zufallszahlengeneratoren. Kürzen oder reduzieren Sie niemals die effektive Größe von PRNG-Seeds.

Häufige Auswirkungen

Auswirkung	Details
Zugriffskontrolle	Umfang: Zugriffskontrolle Angreifer können alle möglichen Seeds aufzählen, um Authentifizierungs-Tokens, Session-IDs und Passwörter vorherzusagen und so Authentifizierungskontrollen zu umgehen.
Vertraulichkeit	Umfang: Vertraulichkeit Kryptografische Schlüssel, die aus klein geseedeten PRNGs generiert wurden, können durch Seed-Aufzählung wiederhergestellt werden und so verschlüsselte Daten kompromittieren.
Integrität	Umfang: Integrität Integritätsmechanismen, die PRNG-generierte Werte verwenden (CSRF-Tokens, Nonces), werden vorhersagbar und fälschbar.

Beispielcode

Anfälliger Code (Java/Python)

Die folgenden Beispiele demonstrieren Schwachstellen durch kleine Seed-Räume:

// Anfällig: Kleiner Seed-Raum in Java
import java.util.Random;

public class AnfälligerKleinerSeed {

    // Anfällig: java.util.Random hat nur 48-Bit Seed
    public String anfälligesToken() {
        // Anfällig: Nur 2^48 mögliche Sequenzen
        Random rand = new Random();
        byte[] bytes = new byte[32];
        rand.nextBytes(bytes);
        return bytesToHex(bytes);
    }

    // Anfällig: Expliziter 32-Bit Seed
    public String anfälligerKleinerSeed() {
        // Anfällig: Nur 2^32 mögliche Sequenzen
        int seed = (int) System.currentTimeMillis();  // 32-Bit
        Random rand = new Random(seed);
        return Long.toHexString(rand.nextLong());
    }

    // Anfällig: Kurzer Seed durch Abschneiden
    public String anfälligerAbgeschnittenerSeed() {
        // Anfällig: Auf 16 Bits abschneiden
        short seed = (short) System.nanoTime();  // Nur 2^16 Möglichkeiten!
        Random rand = new Random(seed);
        return Long.toHexString(rand.nextLong());
    }

    // Anfällig: RandomStringUtils mit schwachem Random verwenden
    public String anfälligerRandomString() {
        // Anfällig: org.apache.commons.lang.RandomStringUtils verwendet Random
        // das nur 48-Bit Seed hat
        return org.apache.commons.lang3.RandomStringUtils.randomAlphanumeric(32);
    }

    // Anfällig: Passwort aus schwachem Random
    public String anfälligesPasswort() {
        // Anfällig: Passwörter auf 2^48 Möglichkeiten begrenzt
        Random rand = new Random();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 16; i++) {
            sb.append(chars.charAt(rand.nextInt(chars.length())));
        }
        return sb.toString();
    }

    private String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

# Anfällig: Kleiner Seed-Raum in Python
import random

# Anfällig: random-Modul Seed (variiert, aber typischerweise 32-Bit auf vielen Systemen)
def anfällig_kleiner_seed():
    # Anfällig: System-Standard-Seeding kann begrenzte Entropie verwenden
    return random.getrandbits(256)  # Sieht sicher aus, aber durch Seed begrenzt

# Anfällig: Expliziter kleiner Seed
def anfällig_expliziter_kleiner_seed():
    import time
    # Anfällig: Nur 32 Bits Seed
    seed = int(time.time()) % (2**32)
    random.seed(seed)
    return format(random.getrandbits(128), '032x')

# Anfällig: Abgeschnittener Seed
def anfällig_abgeschnittener_seed():
    import os
    # Anfällig: Abschneiden von Entropie verfehlt deren Zweck
    volle_entropie = os.urandom(32)
    abgeschnitten = int.from_bytes(volle_entropie[:4], 'big')  # Nur 32 Bits!
    random.seed(abgeschnitten)
    return random.getrandbits(256)

# Anfällig: Seed aus begrenzter Quelle
def anfällig_begrenzte_quelle():
    import socket
    # Anfällig: Hostname hat sehr begrenzte Entropie
    hostname = socket.gethostname()
    random.seed(hash(hostname) & 0xFFFFFFFF)  # 32-Bit
    return format(random.getrandbits(128), '032x')

# Anfällig: Zähler-begrenzter Seed
class AnfälligerZählerSeed:
    zähler = 0

    @classmethod
    def generieren(cls):
        cls.zähler += 1
        # Anfällig: Zähler als Seed ist vollständig aufzählbar
        random.seed(cls.zähler & 0xFFFF)  # Nur 16 Bits!
        return random.getrandbits(128)

// Anfällig: Kleiner Seed-Raum in C
#include <stdlib.h>
#include <time.h>

// Anfällig: srand() nimmt nur 32-Bit Seed
void anfällig_srand() {
    // Anfällig: Nur 2^32 mögliche Sequenzen
    srand(time(NULL));
}

// Anfällig: Noch kleinerer Seed
void anfällig_kurzer_seed() {
    // Anfällig: 16-Bit Seed = 65536 Möglichkeiten
    unsigned short seed = (unsigned short)time(NULL);
    srand(seed);
}

// Anfällig: Benutzerdefinierter PRNG mit kleinem Seed
typedef struct {
    unsigned int state;  // Anfällig: Nur 32-Bit Zustand
} SchwacherPRNG;

void schwacher_prng_seed(SchwacherPRNG *prng, unsigned int seed) {
    prng->state = seed;
}

unsigned int schwacher_prng_next(SchwacherPRNG *prng) {
    // Anfällig: 32-Bit Zustand begrenzt alle Ausgaben
    prng->state = prng->state * 1103515245 + 12345;
    return prng->state;
}

// Anfällig: Gute Entropie abschneiden
void anfällig_abschneiden(unsigned char *output, size_t len) {
    unsigned char volle_entropie[32];
    // Angenommen wir haben hier 256 Bits gute Entropie

    // Anfällig: Auf 32 Bits für Seed abschneiden
    unsigned int seed = *(unsigned int*)volle_entropie;
    srand(seed);

    for (size_t i = 0; i < len; i++) {
        output[i] = rand() % 256;
    }
}

Korrigierter Code (Java/Python)

// Korrigiert: Angemessener Seed-Raum in Java
import java.security.SecureRandom;
import java.security.NoSuchAlgorithmException;

public class SichererAngemessenerSeed {

    // Korrigiert: SecureRandom hat großen internen Zustand
    public String sicheresToken() throws NoSuchAlgorithmException {
        // Korrigiert: SecureRandom verwendet 160+ Bit Seed aus System-Entropie
        SecureRandom sr = SecureRandom.getInstanceStrong();
        byte[] bytes = new byte[32];
        sr.nextBytes(bytes);
        return bytesToHex(bytes);
    }

    // Korrigiert: Explizit größer Seed
    public String sichererGroßerSeed() throws NoSuchAlgorithmException {
        // Korrigiert: 256-Bit Seed
        SecureRandom sr = new SecureRandom();
        byte[] seed = sr.generateSeed(32);  // 256 Bits
        sr.setSeed(seed);
        byte[] bytes = new byte[32];
        sr.nextBytes(bytes);
        return bytesToHex(bytes);
    }

    // Korrigiert: SecureRandom für Strings verwenden
    public String sichererRandomString(int lange) throws NoSuchAlgorithmException {
        // Korrigiert: SecureRandom statt Random
        SecureRandom sr = SecureRandom.getInstanceStrong();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < lange; i++) {
            sb.append(chars.charAt(sr.nextInt(chars.length())));
        }
        return sb.toString();
    }

    // Korrigiert: Sichere Passwortgenerierung
    public String sicheresPasswort(int lange) throws NoSuchAlgorithmException {
        // Korrigiert: Volle Entropie
        SecureRandom sr = SecureRandom.getInstanceStrong();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < lange; i++) {
            sb.append(chars.charAt(sr.nextInt(chars.length())));
        }
        return sb.toString();
    }

    // Korrigiert: Wenn Apache Commons benötigt, SecureRandom wrappen
    public String sichererApacheStyle(int lange) throws NoSuchAlgorithmException {
        // Korrigiert: RandomStringUtils nicht für Sicherheit verwenden
        return sichererRandomString(lange);
    }

    private String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

# Korrigiert: Angemessener Seed-Raum in Python
import secrets
import os

# Korrigiert: secrets-Modul verwenden (kein manuelles Seeding, verwendet System-CSPRNG)
def sicheres_token():
    # Korrigiert: System-Entropie, größer Zustand
    return secrets.token_hex(32)

# Korrigiert: Wenn Seeding von random nötig, volle Entropie verwenden
def sicher_geseedeter_random():
    import random
    # Korrigiert: 256-Bit Seed aus System-Entropie
    seed_bytes = os.urandom(32)
    # SystemRandom verwenden, das nicht auf Seed angewiesen ist
    return secrets.SystemRandom()

# Korrigiert: SystemRandom-Klasse verwenden
def sicherer_system_random():
    # Korrigiert: SystemRandom verwendet OS-Entropie direkt
    rng = secrets.SystemRandom()
    return format(rng.getrandbits(256), '064x')

# Korrigiert: Sichere Passwortgenerierung
def sicheres_passwort(lange=16):
    # Korrigiert: secrets-Modul
    chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*'
    return ''.join(secrets.choice(chars) for _ in range(lange))

# Korrigiert: Zähler mit sicherer Zufallskomponente
class SichererGenerator:
    def __init__(self):
        self.zähler = 0

    def generieren(self):
        self.zähler += 1
        # Korrigiert: Zähler ist nur Identifikator, Sicherheit kommt von secrets
        token = secrets.token_hex(16)
        return f"{self.zähler}:{token}"

# Korrigiert: Schlüssel mit voller Entropie
def sicherer_schlüssel():
    # Korrigiert: 256 Bits aus System-Entropie
    return os.urandom(32)

// Korrigiert: Angemessener Seed-Raum in C
#include <openssl/rand.h>
#include <string.h>

// Korrigiert: OpenSSL RAND verwenden, das großen internen Zustand hat
int sicherer_zufall(unsigned char *buffer, size_t len) {
    // Korrigiert: RAND_bytes verwendet großen Zustand aus System-Entropie geseeded
    return RAND_bytes(buffer, len) == 1 ? 0 : -1;
}

// Korrigiert: Ordnungsgemäßes Seeding mit voller Entropie
int sicher_init() {
    unsigned char seed[32];  // 256 Bits

    // Volle Entropie vom System holen
    if (RAND_bytes(seed, sizeof(seed)) != 1) {
        return -1;
    }

    // Zum Entropiepool hinzufügen (RAND_bytes bereits geseeded, dies fügt mehr hinzu)
    RAND_seed(seed, sizeof(seed));

    // Seed aus Speicher löschen
    OPENSSL_cleanse(seed, sizeof(seed));

    return 0;
}

// Korrigiert: Benutzerdefinierter PRNG mit großem Zustand (wenn benötigt)
typedef struct {
    unsigned char state[64];  // 512-Bit Zustand
    int position;
} SichererPRNG;

int sicherer_prng_init(SichererPRNG *prng) {
    // Korrigiert: Mit 512 Bits Entropie seeden
    if (RAND_bytes(prng->state, sizeof(prng->state)) != 1) {
        return -1;
    }
    prng->position = 0;
    return 0;
}

// Korrigiert: Entropie niemals abschneiden
int sicherer_schlüssel(unsigned char *key, size_t len) {
    // Korrigiert: Volle System-Entropie verwenden
    return RAND_bytes(key, len) == 1 ? 0 : -1;
}

// Korrigiert: getrandom mit angemessenem Puffer verwenden
#ifdef __linux__
#include <sys/random.h>

int sicher_getrandom(unsigned char *buffer, size_t len) {
    // Korrigiert: Volle Entropie vom Kernel
    ssize_t result = getrandom(buffer, len, 0);
    return result == (ssize_t)len ? 0 : -1;
}
#endif

Die Korrektur verwendet CSPRNGs mit großen internen Zustandsräumen (256+ Bits), die nicht per Brute-Force durchsucht werden können.

---

Ausgenutzt in der Praxis

Apache Commons RandomStringUtils (CVE-2019-10908)

Ein Produkt generierte Passwörter mit org.apache.commons.lang.RandomStringUtils, das intern java.util.Random mit nur einem 48-Bit Seed verwendet, was generierte Passwörter vorhersagbar machte.

• https://nvd.nist.gov/vuln/detail/CVE-2019-10908

Session-Token-Vorhersage

Zahlreiche Webanwendungen, die java.util.Random für Session-Tokens verwenden, wurden durch Seed-Aufzählungsangriffe ausgenutzt.

• https://owasp.org/

---

Tools zum Testen/Ausnutzen

• untwister — Kann Seeds aus beobachteter PRNG-Ausgabe wiederherstellen.

• Seed-Aufzählungsskripte — Brute-Force für 32-Bit und 48-Bit Seed-Räume.

• JavaSnoop — Kann Random-Verwendung in Java-Anwendungen beobachten.

---

CVE-Beispiele

• CVE-2019-10908 — RandomStringUtils verwendet 48-Bit geseedeten Random für Passwörter.

---

Referenzen

1. MITRE Corporation. "CWE-339: Small Seed Space in PRNG." Common Weakness Enumeration. https://cwe.mitre.org/data/definitions/339.html

2. NIST. "Recommendation for Random Number Generation." SP 800-90A. https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final

3. Java Documentation. "java.util.Random - Implementation Notes." https://docs.oracle.com/javase/8/docs/api/java/util/Random.html