Entropie und Zufälligkeit

Neugier

1. Was unterscheidet wahre Zufälligkeit von menschlicher Intuition?
2. Wie führte ein Softwarefehler in einer Linux-Distribution dazu, dass Tausende von Schlüsseln für Brute-Force-Angriffe zugänglich wurden?
3. Warum steht eine Phrase aus zwölf Wörtern für genau 128 Bit Entropie plus eine Prüfsumme?

Erkunden

1. Ein privater Bitcoin-Schlüssel ist eine zufällige ganze Zahl zwischen 1 und n−1, wobei n die Ordnung des Generators der Kurve secp256k1 ist. Dieser Raum umfasst etwa 1,158 × 10^77 mögliche Werte. Um 128 Bit Sicherheit gegen Angriffe über den diskreten Logarithmus zu erreichen, muss der Schlüssel gleichverteilt aus diesem Bereich gewählt werden. Ist das Auswahlverfahren vorhersagbar oder verzerrt, sinkt die effektive Entropie, und der Aufwand für einen Angreifer schrumpft auf einen Bruchteil des theoretischen Maximums.
2. Entropie misst Unsicherheit in Bit. Eine BIP39-Mnemonic aus zwölf Wörtern kodiert 128 Bit echter Zufälligkeit plus eine aus SHA-256 abgeleitete 4-Bit-Prüfsumme. Eine Phrase aus vierundzwanzig Wörtern enthält 256 Bit. Das letzte Wort dient teilweise der Fehlererkennung; zufällige Wörter ergeben selten eine gültige Phrase, weil die Prüfsumme fehlschlägt. Diese Struktur verringert unbemerkte Übertragungsfehler, vorausgesetzt, die zugrunde liegende Entropie war echt.
3. Von Menschen erzeugte Zufälligkeit ist bekanntermaßen schwach. Von Menschen gewählte Phrasen enthalten weit weniger Entropie, als es den Anschein hat, weil Menschen vertraute Wörter, Zitate und Muster bevorzugen. Angreifer nutzen dies mit Wörterbuchangriffen auf Schlüssel aus, die aus einprägsamen Phrasen abgeleitet sind, sogenannten „Brain Wallets“. Vasek, Bonneau et al. (2016) dokumentierten, wie solche Wallets regelmäßig geleert wurden, oft sehr kurz nach der Einzahlung, weil Angreifer riesige Listen wahrscheinlicher Phrasen durchprobieren konnten.
4. Fehler in Softwareimplementierungen haben die Schlüsselerzeugung wiederholt kompromittiert. Eine Änderung von Debian an OpenSSL (im Einsatz 2006–2008, offengelegt in DSA-1571) ließ die Prozess-ID als nahezu einzige Variationsquelle übrig, sodass es für jeden Schlüsseltyp und jede Schlüsselgröße nur etwa 32.768 mögliche Schlüssel gab. Im August 2013 führte ein Fehler in Androids SecureRandom dazu, dass einige Bitcoin-Wallets Signatur-Nonces wiederverwendeten, wodurch private Schlüssel offengelegt und Diebstähle möglich wurden. Diese Vorfälle zeigen, dass Entropiequellen kryptografisch sicher und vom Systemzustand unabhängig sein müssen.
5. „Randstorm“, 2023 von Unciphered offengelegt, zeigte, dass Web-Wallets aus der BitcoinJS-Ära (ca. 2011–2015) schwache Zufallszahlengeneratoren verwendeten und ihre Nutzer damit Angriffen zur Schlüsselwiederherstellung aussetzten. Moderne Hardware-Wallets sammeln bei der Initialisierung Entropie aus mehreren internen Quellen und zeigen die resultierende Mnemonic Wort für Wort an. Sobald diese Wörter aufgeschrieben sind, bilden sie die alleinige Verfügungsgewalt über die Guthaben; wer sie verliert, verliert dauerhaft den Zugriff.
6. Gute Entropie stammt aus den kryptografischen Zufallszahlengeneratoren des Betriebssystems (CSPRNGs), aus Hardware-RNGs oder aus physikalischen Prozessen wie Würfelwürfen (mit Vorbehalten wegen möglicher Verzerrung). CSPRNGs mischen Rauschen aus Systemereignissen und Hardwaresensoren, um unvorhersagbare Bits zu erzeugen. Liegt die Ausgabe zwischen 1 und n−1, wird sie zu einem gültigen privaten Schlüssel; andernfalls versucht der Generator es mit neuen Zufallsdaten erneut. Diese Schleife gewährleistet eine gleichmäßige Verteilung über die gesamte Kurvenordnung.

Kernfakten

Übung neun, sechs, drei, eins

Faktcheck

Datumsangaben, Zahlen und Behauptungen wurden mit den unten aufgeführten veröffentlichten Quellen abgeglichen.

• Debian Security Advisory DSA-1571: openssl - insufficient randomness in key generation (2008)
• Bitcoin.org, 'Android Security Vulnerability' (11 August 2013)
• Unciphered, 'Randstorm: You Can't Patch a House of Cards' (2023)
• M. Vasek, J. Bonneau et al., 'The Bitcoin Brain Drain: Examining the Use and Abuse of Bitcoin Brain Wallets' (2016)
• M. Palatinus, P. Rusnak, A. Voisine & S. Bowe, 'BIP-0039: Mnemonic code for generating deterministic keys' (2013)