Die Quantencomputer kommen! Ist das Bitcoins Ende? (Teil 1)

Regelmäßig berichten Journalisten über die Gefahr, die Quantencomputer für Bitcoin und viele andere Kryptowährungen bedeuten sollen. Doch wie dramatisch ist diese Bedrohung wirklich? Dieser Artikel diskutiert am Beispiel Bitcoin das Thema Quantencomputer.

Dr. Philipp Giese
Teilen

Ein Blick in den virtuellen Blätterwald zeigt, dass Quantencomputer als Bedrohung von Bitcoin und anderen Kryptowährungen dargestellt werden. Wann immer Updates zum aktuellen Entwicklungsstand dargestellt werden, weisen die jeweiligen Autoren darauf hin, was diese Entwicklung für Verschlüsselungen bedeuten würde.

Das Bild fällt dystopisch aus: Alle Verschlüsselungen können dem Quantencomputer zum Opfer fallen, unsere Konten und damit unsere Privatsphäre seien dem Diebstahl anonymer Hacker oder der NSA schutzlos ausgeliefert. Mit Blick auf die Gefährdung der RSA-Verschlüsselung mag das sogar stimmen.

In jüngster Zeit verbindet man diese Angst mit dem Trend der Kryptowährungen: Mit Quantencomputern würde Bitcoin am Ende sein, die Wallets könnten geleert werden und das ganze System würde untergehen – so oder so ähnlich stellen manche Kreise Cryptogeddon dar.

Die Sorge ist nicht ganz unbegründet und hat dazu geführt, dass verschiedene Projekte schon heute Verschlüsselungsalgorithmen verwenden, die quantum resistant sind. Sie versprechen also, dass die Wallets selbst für Quantencomputer unhackbar sind.

In der Hinsicht ist verständlich, dass viele Bitcoin-Investoren sich fragen, warum Bitcoin nicht aktiv wird. Um diese Frage zu beantworten, soll in diesem Artikel die Gefährdung Bitcoins durch Quantencomputer eingeschätzt werden.

Was kann ein Quantencomputer?

Um die Gefahr von Quantencomputern korrekt einzuschätzen, ist es wichtig, die Möglichkeiten und Grenzen derselben zu verstehen. Als erstes möchte der Artikel deshalb skizzieren, was ein Quantencomputer ist.

Klassische Computer sind Digitalrechner, die Informationen über Nullen und Einsen verarbeiten. Ein Bit kann entweder 0 oder 1 sein. Komplexere Information wird über mehr Bits, Verarbeitung derselben über logische Schaltungen realisiert. Beispielsweise ergibt eine UND-Schaltung eine 1 nur dann, wenn über beide Eingänge eine 1 gesendet wird. Für eine UND-Verknüpfung ergeben sich also vier mögliche Kombinationen, die im schlimmsten Fall alle durchgerechnet werden müssen, um zur 1 zu gelangen:

0 UND 0 ergibt 0
1 UND 0 ergibt 0
0 UND 1 ergibt 0
1 UND 1 ergibt 1

Ein Quantencomputer speichert Information in sogenannten Qubits ab. Diese machen sich Phänomene der Quantenmechanik zunutze. Manche Leser werden das Gedankenexperiment „Schrödingers Katze“ kennen: Ein Psychopath sperrt eine Katze in eine Kiste, in die er eine sich zufällig öffnende Kapsel Blausäure gelegt hat. Öffnet sich diese, stirbt die Katze. So lange die Kiste nicht geöffnet ist, kann die Katze als gleichzeitig tot und lebendig beschrieben werden. Übertragen auf Qubits bedeutet das, dass diese nicht 0 oder 1, sondern als 0 und 1 gleichzeitig beschrieben werden können. Man kann sich entsprechend vorstellen, dass in einem ähnlichen Prozess wie der obigen UND-Verknüpfung nicht mehrere Prozesse durchgerechnet werden müssen, sondern alle gleichzeitig errechnet werden.

Was für Angriffe sind mit Quantencomputern möglich?

Nach oben Genanntem kann man sich verstehen, dass Quantencomputer deshalb die Laufzeit von Algorithmen dramatisch senken können. Und das ist nicht rein spekulativ: Auch ohne Quantencomputer haben Wissenschaftler schon Algorithmen entwickelt, die für die Sicherheit von Bitcoin eine gewisse Relevanz besitzen. Der Shor-Algorithmus hat zum Ziel, große Zahlen zu faktorisieren, was für viele kryptographische Prozesse relevant ist. RSA basiert beispielsweise darauf, dass Faktorisierungsverfahren eine extrem hohe Laufzeit besitzen – und entsprechend durch Quantencomputer indirekt gefährdetwerden.

Neben dem Shor-Algorithmus ist noch der Grover-Algorithmus bekannt: Hier geht es um die Suche innerhalb einer unsortierten Datenbank beziehungsweise um die Invertierung einer Funktion. Der Grover-Algorithmus erlaubt also bei einer Funktion f(x) = y das x für ein gegebenes y zu berechnen. Da es sich bei f(x) um eine Verschlüsselungs- oder Hashingfunktion handeln kann, ist dieser Algorithmus ebenfalls eine Gefahr für verschiedene kryptographische Funktionen.

Wie ist der aktuelle Stand von Quantencomputern?

Verschiedene Unternehmen und Institutionen haben ihrer Aussage nach schon Quantencomputer entwickelt. So soll das Unternehmen D-Wave Systems inzwischen vier Computer entwickelt haben. D-Wave 2000Q soll mit insgesamt 2048 Qubits arbeiten. Man kann jedoch verschiedene kritische Stimmen hören, die die von D-Wave Systems beworbenen Eigenschaften in Frage stellt. Außerdem soll laut Edward Snowden die NSA an einem auf Kryptographie fokussierten Quantencomputer arbeiten. Als nachweisbares Maximum kann man den 70 Qubit-Quantencomputer von Google sehen.

Aussagen der Form „das ist frühestens in 20 Jahren so weit“ hat die Realität des dritten Jahrtausends oft widerlegt. Deshalb soll vom „worst case“ ausgegangen werden: Verborgene Hacker oder die NSA könnten schon jetzt Quantencomputer nutzen.

Kann man mit Quantencomputern Bitcoins Private Key knacken?

Ein oft angesprochenes Problem ist, dass ECDSA-Verschlüsselung mittels dieses Shor-Algorithmus via Quantencomputer knackbar ist. Das ist ein sehr großes Problem, da man über die ECDSA-Verschlüsselung aus dem Private Key den Public Key generiert. Um eine ECDSA-Verschlüsselung zu knacken, würde sich mithilfe des Shor-Algorithmus der rechnerische Aufwand zur Ermittlung eines Private Keys aus einem Public Key um einen Faktor 10^-34 reduzieren. Selbst ein sehr langsamer Rechner, der eine Berechnung pro Sekunde durchführen kann, würde nicht einmal zwei Tage zum Finden des Private Keys benötigen.

Ist dann tatsächlich alles unsicher?

Was viele jedoch oft übersehen ist, dass im Fall von Bitcoin zwischen dem Angreifer und dem Private Key zwei Verschlüsselungen liegen. Dass man aus einem Public Key einen Private Key ermitteln muss, ist bekannt. Das kann wie dargestellt über den Shor-Algorithmus geschehen. Der Angreifer wird jedoch im Normalfall nicht den Public Key selbst, sondern seinen Hash sehen. Dieser Hash ist die Wallet-Adresse.

Konkret greifen folgende kryptographische Prozesse ineinander: Aus dem Private Key mit 256 Bit kann man über ECDSA-Verschlüsselung einen 512 Bit Public Key generieren. Diesen verwandelt ein SHA256-Algorithmus in eine Prüfsumme, die man ihrerseits in die Wallet-Adresse umwandeln kann. Der Angreifer muss also nicht nur den Private Key aus dem Public Key ermitteln. Er muss zuerst aus der Wallet-Adresse den Public Key generieren.

Hacker können zwar prinzipiell SHA256 über den Grover-Algorithmus knacken. Über diesen Algorithmus erreicht man jedoch lediglich eine quadratische Beschleunigung. Das bedeutet, dass ein Angriff auf einen durch SHA256 generierten Hash ungefähr 2^128 beziehungsweise 3,4*10^38 Rechenzyklen benötigt. Aktuell können die Supercomputer der Welt ungefähr 10^17 Rechenoperationen pro Sekunde verarbeiten. Diese Menge sei als obere Schranke angenommen. Prinzipiell ist nicht davon auszugehen, dass man in derart kurzen Zeitabständen nach erfolgten Messprozessen einen sogenannten verschränkten Zustand wieder präparieren kann. Ein Quantencomputer mit derart vielen Qubit-Operationen pro Sekunde würde statt 4*10^52 Jahren nur noch 107,9 Billionen Jahre zum Finden des Public Keys benötigen. Das ist weiterhin deutlich größer als das Alter des Universums!

Zugegegebenermaßen existiert ein weiterer Algorithmus, der eine kubische Laufzeitoptimierung verspricht. Mit diesem könnte ein Quantencomputer, im Fall von 10^17 Qubit-Operationen pro Sekunde, die Verbindung zwischen Wallet-Adresse und Public Key in 15 Jahren knacken.

Selbst unter der Annahme eines Supercomputers, der aktuell physikalisch nicht möglich ist, und unter Nutzung eines vergleichsweise unbekannten Algorithmus, würde der Aufwand des Hacks den Nutzen dramatisch übersteigen.

Was macht Bitcoin und was kannst du tun?

Es zeigt sich: Bitcoin ist vergleichsweise quantum safe. Natürlich gilt das nur solange niemand einen besseren Algorithmus als Grover für das Finden des Public Keys entwickelt. Deshalb ist es weiterhin interessant, ob Bitcoin-Developer sich überhaupt dieser Frage annehmen.

Frei nach dem Motto „Be your own bank” wäre es außerdem wünschenswert, wenn der einzelne Bitcoin-Nutzer nicht nur krypto-fit, sondern quantum safe ist. Im Teil zwei dieser Artikelreihe diskutieren wir deshalb, was für Möglichkeiten wir zur besseren Absicherung unserer Bitcoins haben.

BTC-ECHO

Du willst Helium (HNT) kaufen oder verkaufen?
Wir zeigen dir in unserem Leitfaden, wie und wo du einfach und seriös Helium (HNT)) Token/Coins kaufen kannst.
Helium kaufen