Entropiemangel und Fehler durch schwache Schlüssel

Entropiemangel tritt auf, wenn einem System genügend unvorhersehbare Eingaben fehlen, um seinen CSPRNG zu initialisieren. Dies geschieht bei frisch gestarteten eingebetteten Geräten, virtualisierten Servern oder Systemen ohne Benutzereingaben. Die Ausgabe des RNG wird vorhersehbar.

2006 entfernte ein Debian-Entwickler eine von Valgrind markierte Zeile: MD_Update(&m, buf, j). Diese Zeile war die Entropiequelle. Das Ergebnis: OpenSSL unter Debian wurde nur mit der PID initialisiert (maximal 32.768 Werte). Alle zwischen 2006 und 2008 erzeugten Schlüssel gehören zu einer Menge von 32.768 Möglichkeiten.

RSA-, DSA- und ECDSA-Schlüssel, SSH-Hostschlüssel, TLS-Zertifikate und SSL-VPN-Schlüssel, die 2006–2008 auf Debian-/Ubuntu-Systemen erzeugt wurden, waren kompromittiert. Betroffene Systeme: Debian Etch, Debian Lenny, Ubuntu 7.04–8.04. Sperrlisten wurden veröffentlicht und Zertifikate widerrufen.

VMs können mit identischem Festplattenzustand geklont werden. Wenn beide VMs Schlüssel aus demselben CSPRNG-Zustand erzeugen, produzieren sie dieselben Schlüssel. Hypervisoren fügen inzwischen über VirtIO RNG oder ACPI-Tabellen Entropie hinzu, aber unzureichend konfigurierte VMs sind beim Start weiterhin diesem Risiko ausgesetzt.

IoT-Geräte (Router, Kameras) erzeugen häufig beim ersten Start SSH-/TLS-Schlüssel, bevor sie genügend Entropie gesammelt haben. Studien haben ergeben, dass Millionen von Geräten einige wenige Tausend RSA-Schlüsselpaare gemeinsam verwendeten, weil sie alle aus demselben entropiearmen Startzustand initialisiert wurden.

Lenstra et al. (2012) sammelten 11,7 Millionen TLS-Zertifikate und berechneten paarweise den GCD. Dabei wurden 12.720 RSA-Schlüssel gefunden, die einen Primfaktor gemeinsam hatten – beide Schlüssel konnten also vollständig faktorisiert werden. 0,2 % aller öffentlichen Schlüssel waren gebrochen. Ursache: unzureichende Entropie beim Start.

ECDSA erfordert eine eindeutige zufällige Nonce k für jede Signatur. Wenn k wiederverwendet wird (oder schwach ist), kann der private Schlüssel sofort rekonstruiert werden: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n. Die PS3 von Sony verwendete k=constant – alle Spiele konnten mit dem wiederhergestellten Schlüssel signiert werden.

Java SecureRandom wurde unter Android 4.x unter bestimmten Bedingungen mit der Systemzeit initialisiert. Mehrere Bitcoin-Wallet-Apps erzeugten Signaturen mit derselben k-Nonce, wodurch private Schlüssel offengelegt wurden. Es wurden Bitcoin im Wert von Millionen Dollar gestohlen. Google korrigierte die Implementierung von SecureRandom.

Werkzeuge: ssh-vulnkey (prüft gegen die Debian-Sperrliste für schwache Schlüssel), badkeys (prüft TLS-Zertifikate auf bekannte schwache Primfaktoren), GCD-Batch-Algorithmus für die Prüfung großer Mengen von RSA-Schlüsseln. Certificate-Transparency-Protokolle ermöglichen Analysen im Maßstab der gesamten Population.

Verwenden Sie getrandom(GRND_RANDOM) bei der ersten Schlüsselerzeugung. Lesen Sie nach dem Warten auf die erste Initialisierung aus /dev/urandom (prüfen Sie, ob /proc/sys/kernel/random/entropy_avail > 128 ist). Verwenden Sie eine Hardware-RNG (RDRAND) als zusätzliche Entropiequelle. Erzeugen Sie niemals beim ersten Start ohne Verzögerung Schlüssel.

Persistieren Sie den CSPRNG-Zustand über Neustarts hinweg: Speichern Sie beim Herunterfahren 32 Bytes aus /dev/urandom in einer Seed-Datei; lesen Sie sie beim Start ein und führen Sie sie dem CSPRNG wieder zu. Dadurch bleibt die Entropie über Kaltstarts hinweg erhalten. Linux erledigt dies automatisch; eingebettete Systeme tun dies häufig nicht.

Was war die eigentliche Ursache des Debian-OpenSSL-Entropiefehlers?

Entropiemangel führt zu vorhersehbaren Schlüsseln. Beispiele für tatsächliche Sicherheitsbrüche: Debian OpenSSL (ausschließliche Initialisierung mit der PID), GCD-Angriffe auf IoT-Geräte, Wiederverwendung von ECDSA-Nonces bei der PS3 und Bitcoin-Wallets unter Android. Initialisieren Sie stets aus der Entropiequelle des Betriebssystems; prüfen Sie die Schlüsselerzeugung in eingebetteten Systemen sorgfältig. Als Nächstes: Schlüssel, Nonces und IVs sicher erzeugen.