“Das weiß ja keiner. Einige behaupten das, weil sie die Alternative ängstigt …”

Der Large Bitcoin Collider (LBC) versucht, per Brute Force Bitcoin-Adressen zu knacken. In den letzten Wochen hat das Projekt die ersten Erfolge verkündet. Sind Bitcoins nun nicht mehr sicher? Sind sie, im kryptographischen Kern, kaputt? Rico, der Kopf hinter dem LBC, erklärt uns im Interview ausführlich, was hier gerade passiert.

Wer bist du denn und warum heißt deine Webseite cryptoguru.org?

Ich bin gestandener Informatiker. Die Domain cryptoguru.org und etwas Hardware-Infrastruktur habe ich für einen kleinen Bitcoinbetrag jährlich gemietet. Mir hat der Domainname gefallen, aber er war schon registriert. Glücklicherweise haben die Eigentümer dafür aktuell keine Verwendung, also wurden wir uns einig.

„Weil jeder gesagt hat, es sei unmöglich, hat es niemand richtig versucht.“

Du betreibst den Large Bitcoin Collider (LBC), mit dem du Kollisionen von Bitcoin-Adressen suchst. Wie kamst du auf diese Idee bzw. was willst du damit beweisen?

Im Juli 2016 bin ich über die Webseite directory.io gestolpert, die angeblich alle privaten Schlüssel auflistet. Ich fand das eine lustige Idee. Die Message war, sinngemäß: „Sind da auch meine Adressen drin? Ja, aber Niemand wird die je finden. Weil … Mathematik.“ Das hat mich an ähnliche Fälle aus der Informatik erinnert (z.B. dass in der Kreiszahl PI u.a. alle Werke Shakespeares kodiert sind).

Ich habe ein wenig rumgeforscht und bin auf bitcointalk.org darauf gestossen, dass Leute tatsächlich versucht haben directory.io zu scrapen und die Adressen auf „Inhalt“ abzuklopfen. Da dachte ich mir, das sollte auch besser zu machen sein. Zunächst war das ein reines Gedankenkonstrukt, aber als ich so darüber nachdachte, und mir klar wurde, dass man überhaupt nicht den gesamten 256bit Suchraum anschauen müsste, sondern nur 160bit, war die Kollisionsidee geboren. Da dachte ich: „Mal schauen was geht!“

Beweisen möchte ich eigentlich nur, dass sich manchmal auch viele Menschen irren können, wenn sie behaupten, etwas sei unmöglich. Wir wissen ja, dass das vorkommt und ich glaube, dass das auch in diesem Fall zutrifft.

Weil jeder gesagt hat, es sei unmöglich, hat es niemand richtig versucht. Aber ein „Beweis“ ist für mich nicht die Motivation. Schon eher motiviert mich nicht bereits ausgetrampelte Pfade zu begehen.

Der LBC ist, wenn ich es richtig verstehe, ein Brute-Force-Angriff auf beliebige Bitcoin-Adressen. Kannst du erklären, was da genau passiert?

Fangen wir damit an, wie eine Bitcoin-Adresse entsteht: Man nimmt einen privaten Schlüssel (eine zufällige Zeichenfolge einer bestimmten Länge). Aus diesem errechnet man mithilfe von Koordinaten auf einer Elliptischen Kurve einen öffentlichen Schlüssel. Den hasht man mit SHA256, und das Ergebnis davon jagt man nochmal durch einen RIPEMD160 Algorithmus. Jetzt hat man eine hash160, was eigentlich schon die Bitcoin-Adresse ist. Um sie besser lesen zu können, wird das mit Base58 kodiert, womit wir die beliebten Bitcoin-Adressen haben (1irgendwas …).

Die Clients des Large Bitcoin Colliders (LBC) kennt nun alle hash160-Adressen, auf denen mehr als 0 BTC sind. Er zählt einfach die privaten Schlüssel hoch – uns interessieren 2¹⁶⁰ – und berechnet daraus besagten hash160. Den vergleicht er mit den Adressen, auf denen Bitcoins sind.

Wie wahrscheinlich oder unwahrscheinlich ist es, eine Adresse zu finden, die bereits benutzt wurde?

Da gibt es natürlich viele Hochrechnungen, aber je mehr man sich damit beschäftigt, desto mehr unbekannte Variablen erkennt man. Irgendwann sieht das dann aus wie die Drake-Gleichung, die schätzen will, wieviele intelligente Zivilisationen es in der Milchstraße gibt, und man muss feststellen: Nichts genaues weiß man nicht.

Aber mal so als Beispiel: Es gibt nur maximal 2¹⁶⁰ mögliche Adressen und nicht 2²⁵⁶ wie viele glauben. Und die 2¹⁶⁰ auch nur dann, wenn RIPEMD160 surjektiv ist, also den gesamten Möglichkeitsbereich auch wirklich abdeckt. Was wir vermuten hoffen, aber nicht wissen…

Es gibt derzeit etwa 15 Millionen Adressen mit einem Guthaben (2^23,8). Wenn wir davon ausgehen, dass diese gleichmäßig über den Suchraum verteilt sind, dann bedeutet das, dass im Schnitt von 2^136,2 Adressen EINE ein Guthaben hat.

Wenn wir jetzt annehmen, dass man 2^36,2 Adressen je Sekunde absuchen kann, dann braucht man 2¹⁰⁰ Sekunden, mithin 40196936841331 Milliarden Jahre, bis man diese eine Adresse findet.

So gesehen ist es ziemlich unwahrscheinlich, dass es gelingt. Wir haben aber schon 3 gefunden. Hm?

„Das Ergebnis sind, derzeit: 5,5 mio keys/s pro CPU Kern.“

Laut deiner Webseite erzeugt ihr 587 Megakeys je Sekunde. Das ist schon ziemlich viel. Welche Hardware steckt dahinter?

Das war gestern. Zu dem Zeitpunkt, zu dem ich diese Antwort schreibe, hat der Pool gerade 1196,22 Mkeys/s (Beim Korrekturlesen: 1238,53 Mkeys/s). Das meiste sind CPUs und ein paar GPUs. Die Frage nach der Hardware ist aber viel weniger relevant als die nach der Software.

Oben habe ich über Leute berichtet, die directory.io mit einem Skript Seite-für Seite geholt haben um die dann weiter zu parsen und analysieren. Die haben so 20-30 Sekunden pro Seite gebraucht. Auf einer Seite sind 128 Schlüssel, mithin 256 Adressen (uncompressed, compressed). Sie haben also mit 6 keys je Sekunde begonnen.

Ich habe versucht, das besser zu machen. Mit ein wenig Herumexperimentieren konnte ich die Rate von Keys je Sekunde extrem erhöhen.

Zuerst habe ich vanitygen benutzt, womit ich 100 keys je Sekunde geschafft habe. Dann habe ich die Quellen von directory.io geholt und direkt geparst, womit ich auch 13.000 keys je Sekunde kam. Daraufhin dachte ich mir, warum Base58, wenn hash160 auch reicht. Und siehe da: 40.000 keys/s. Als mir Ryan Castellucci sagte, dass sein Brainflayer viel schneller sei, habe ich es damit versucht, und tatsächlich: ich war bei 520.000 keys/s.

Dannach habe ich mich so richtig in die Materie eingearbeitet. SHA256 studiert, RIPEMD160 studiert, meine C Kenntnisse wieder aufpoliert. Langsam aber stetig habe ich Brainflayer zu HRD-Core umgebaut und bin bei 720.000 keys/s gelandet.

Zu dem Zeitpunkt hatte ich die schnellste RIPEMD160 CPU Implementierung. Aber es war noch nicht schnell genug. Also habe ich mir den secp256k1 Code vorgenommen und versucht, GPUs zu verwenden. Da aber niemand je eine GPU Anpassung schreiben wollte oder konnte, habe ich ihn von 0 auf entwickelt. Das war noch nicht perfekt, hat mich aber auf 2,2 Millionen Keys / Sekunde gebracht.

Aber es geht noch weiter: Der User „arulbero“ auf Bitcointalk machte einige Vorschläge, wie man die Elliptic Curve Arithmetik verbessern kann, und hat an seiner eigenen Bibliothek dafür gearbeitet. Ich habe in der Zwischenzeit noch mehr Operationen auf die GPU gebracht, und 25.3.2017 kam es zur Scheidung und Hochzeit: Wir haben die libsecp256k1 aus dem Code geschmissen und durch die arulbero-EC Arithmetik ersetzt.

Das Ergebnis sind, derzeit: 5,5 mio keys/s pro CPU Kern. Der Pool des LBC ermöglicht es nun, dass im Prinzip jeder seine Hardware für die Suche bereitstellen kann, da sich diese Suche perfekt parallelisieren lässt. Es dürften also ein paar hundert CPU-Kerne sein, die bei uns mitmachen.

Auf der Seite mit euren Statistiken steht, dass die Wahrscheinlichkeit 0,0000000-irgendetwas beträgt, dass ihr im Lauf der nächsten 24 Stunden eine 50-Prozent-Chance auf eine Kollision hat. Bedeutet das, dass ihr 1.000 Jahre (oder so) nichts finden werdet?

Du kennst sicher die Geschichte von den Seerosen und dem Teich.

• Tag 1: Eine Seerose
• Tag 2: 2 Seerosen
• Tag 3: 4 Seerosen. usw.

Nach 27 Tagen ist der halbe See voll mit Seerosen. Nach wie vielen Tagen ist der ganze See voll?
Du schreibst 0,000irgendwas. Sehen wir uns doch mal die Zahlen genauer an:
0.00000000000000000045% (17.9.2016)
0.00000000000000200548% (23.9.2016)
0.00000000002801022860% (28.3.2017)
0.00000000016406321697% (04.4.2017)


Ich glaube, es kann sich jeder ein Bild davon machen, ob wir hier über einen Zeitraum von 1000 Jahren in die Zukunft nachdenken müssen.

Kürzlich sind euch ja einige Kollisionen mit Wechselgeld-Adressen gelungen. Warst du überrascht?

Ich war zu 50% überrascht 🙂

Wie kann es sein, dass das auch noch mehrfach geschehen ist? Waren die Adressen speziell, etwa mit zu wenig Entropie erzeugt?

Das weiß ja keiner. Einige behaupten das, weil sie die Alternative ängstigt. Andere haben Zweifel vorgebracht, ob das denn tatsächlich Funde sind oder ob das nicht „wir“ platziert haben. Ich kann jedem versichern, dass das echte Funde sind. Ob nun schlechte Entropie oder die erste Hälfte einer Kollision – wir wissen es einfach noch nicht.

„Nüchtern betrachtet stimmen die Zahlen vorne und hinten nicht.“

Auf den Adressen waren nur Minimal-Beträge. Was machst du, wenn ihr mal aus Zufall die Schlüssel für die Wallet von BitStamp findet?

Wieviel ist da drauf?

Spaß beiseite: Die Standard-Vorgehensweise sollte die gleiche sein wie bei den bisherigen Funden: Auf eine Verwahrungsadresse transferieren und den Fund öffentlich machen. Der „rechtmäßige Eigentümer“, kann dann in einem Zeitraum von derzeit 6 Monaten die Rückgabe beantragen: Einfach seinen anderen Key vorweisen. Wir haben unsere Kollision und er hat seine Bitcoins.

Ihr habt schon mehrere „Trophäen“ aus einer „Puzzle“-Transaktion gefunden. Was hat es damit auf sich?

Auf die Puzzle-Transaktion hat mich Ryan Castellucci aufmerksam gemacht. So wie es aussieht handelt es sich dabei um ein knapp 33BTC teures Vorwarnsystem, das jemand aufgesetzt hat um zu sehen, wie sicher Bitcoin P2PKH Adressen sind.

Hierbei wurden pro Bit Entropie des privaten Schlüssels 0,001 Bitcoin deponiert. Bis Nr. 50 wurden alle bereits 2015 leergeräumt. Man sollte also tunlichst keine 50 bit Schlüssellänge verwenden. #51 haben wir erst vor kurzem gefunden.

Es gibt eine Grafik mit einer Sonne, und darunter steht, dass selbst dann, wenn man die ganze Oberfläche der Sonne mit perfekten Prozessoren bedecken und die ganze Energie der Sonne verbrennen würde, kaum eine Chance hätte, eine Bitcoin-Adresse zu bruteforcen. Ist das nur Marketing?

Ja. Das Pathos dieser Grafik hat ja auch auf mich einen Eindruck gemacht, als ich es das Erste mal gesehen habe, aber nüchtern betrachtet stimmen die Zahlen vorne und hinten nicht.

Bitcoin ist geschützt – vorerst sage auch ich: „sehr gut sogar“. Aber nicht so gut, wie das diese Grafik (und andere) mystifizieren.

Könnte ein Cluster von Supercomputern Bitcoin-Adressen ausräumen? Wäre es möglich, einen Asic zu bauen, der auf diese Weise Bitcoins mined?

Bitcoin-Adressen ausräumen kann ich ohne Taschenrechner. Wenn ich die zugehörigen privaten Keys habe. Kann ein Cluster von Supercomputern private Keys finden? Ja.

Könnte ein ASIC das machen, was momentan CPU/GPU mit unserer Software machen? Ja. Wenn das Ende der Fahnenstange bei GPU erreicht ist, werde ich mir FPGAs ansehen.

Ich bin selbst oft überrascht, wie viele Gemeinsamkeiten es zur Evolution des Bitcoin-Mining gibt. Wir durchlaufen diese aber schneller.

Würde ein Quantencomputer helfen, Kollisionen zu finden?

Möglich, aber da will ich nicht spekulieren. Nur soviel: Noch vor den Quantencomputern sehe ich eine andere Technologie, die möglicherweise P2PKH/P2PSH Adressen wesentlich schneller angreifbar machen würde. Aber das muss als Teaser reichen. Details gibt es von mir keine.

Wie kann sich ein User vor Kollisionen schützen? Gibt es eine Möglichkeit, sie unwahrscheinlicher zu machen?

Bedauerlicherweise ist gerade die (vermutete) richtige Funktionsweise von SHA256 und RIPEMD160 dafür verantwortlich, dass ich diese Frage mit „Nein“ beantworten muss.

Es wurde eine Möglichkeit diskutiert, P2PKH Adressen speziell vor dem LBC zu schützen. Das wäre die Verwendung eines privaten Keys aus dem Bereich 2¹⁵⁹ + rand(2¹⁵⁸) – für diese Keys ist die Wahrscheinlichkeit für Kollisionen mit anderen Keys in den ersten 160bit Suchraum am geringsten, und die Wartezeit „bis da der LBC vorbeischaut“ am längsten.

Ein bisschen beunruhigend ist es ja schon. Würdest du derzeit große Werte in Bitcoin speichern?

Ja, ich habe einige Bitcoins und der LBC ändert da auch nichts daran. Was ich persönlich sicher nicht machen würde: Manche Adressen haben 100.000 Bitcoins drauf. Das ist aus meiner Sicht zu riskant und zwar unabhängig vom LBC. Den Gegenwert von über 100 mio US$ einer Folge von 160 Nullen und Einsen anzuvertrauen – das würde ich nicht machen.