Nyligen rapporterade Google att de uppnått s.k. quantum supremacy vilket är uttrycket för att en kvantdator lyckats lösa ett problem som vanliga datorer inte har någon praktisk möjlighet att kunna lösa. Google hävdade att problemet som deras kvantdator nu löst skulle ha tagit 10 000 år att lösa för en av världens snabbaste superdatorer, något som IBM dock snabbt ifrågasatte och istället påstod inte skulle ta mer än ett par dagar. Hur som helst så är det uppenbarligen ännu ett steg framåt mot praktisk användning av kvantdatorer som Google har tagit.
Vad är en kvantdator?
I en vanlig klassisk dator brukar man kalla den mest grundläggande informationsenheten för en “bit”, vilket är något som antingen kan anta värdet 0 eller 1. Allt en dator gör kan egentligen uttryckas med dessa nollor och ettor även om vi människor oftast väljer att presentera det på sätt som är lättare för oss att förstå. Additionen 5 + 2 = 7 blir t.ex. i nollorna och ettornas värld 101 + 010 = 111.
Inom den smått magiska kvantfysiken finns något som kallas superposition vilket innebär att partiklar kan anta flera olika tillstånd samtidigt, t.ex. befinna sig på flera ställen samtidigt. Det låter förstås väldigt märkligt och det blir ännu svårare att förstå eftersom vi inte kan observera det här direkt. Försöker man observera det här fenomenet så “kollapsar” nämligen superpositionen och vi ser bara ett av de möjliga tillstånden. Det här skulle vara svårt att tro på om man inte faktiskt hade kunnat visa på faktiska sätt att utnyttja de här märkliga egenskaperna, något som man gör med t.ex. kvantdatorer. I en kvantdator kallas informationsenheten inte för “bit” utan för “qubit” och är något som kan anta en superposition av värdena 0 och 1, alltså “båda värdena samtidigt”.
Med qubits kan vi (på sätt och vis) utföra massor av uträkningar samtidigt eftersom dessa speciella bitar på samma gång antar både värdet 0 och värdet 1. Det är dock inte helt enkelt att utnyttja denna egenskap eftersom ett försök till observation av svaren gör att man, enligt vad vi nämnde tidigare, endast kommer att se ett specifikt svar. Däremot har smarta personer klurat ut att man trots detta kan få ut viss information ur beräkningen utan att observera de enskilda svarsbitarna. Exakt hur detta går till är för komplicerat för den här artikeln men slutsatsen är att man för att kunna utnyttja kraften hos en kvantdator behöver väldigt specifika algoritmer som konstruerats just för kvantdatorer och det går heller inte att hitta sådana algoritmer för alla typer av problem.
Att knäcka kryptering
En mycket populär form av kryptering idag är RSA, vilket är en form av s.k. asymmetrisk kryptering där olika nycklar används för kryptering (publik nyckel) respektive dekryptering (privat nyckel). Sådan kryptering baserar sig på det faktum att om du tar två stora primtal så är det enkelt att multiplicera dessa men mycket svårt/tidskrävande att gå åt andra hållet, alltså att utifrån produkten få fram vilka två tal som behöver multipliceras. För detta specifika problem har den amerikanske matematikern Peter Shor kommit på en algoritm som skulle kunna användas av kvantdatorer och därmed göra krypteringen helt värdelös. För en djupare förståelse av hur algoritmer för kvantdatorer fungerar rekommenderas denna video som förklarar Shors algoritm.
Bitcoin
Bitcoin använder inte RSA men väl en annan form av asymmetrisk kryptering (eller i Bitcoins fall signering) kallad Elliptic Curve Digital Signature Algorithm (ECDSA) och Shors algoritm kan faktiskt användas även för det bakomliggande problemet även här. Så vad innebär då detta för Bitcoin? Låt oss titta på hur Bitcoin använder ECDSA. Vid en enkel transaktion där Person A skickar bitcoin till Person B så kommer, lite förenklat, följande att hända:
- Person A skapar en transaktion som säger att X antal bitcoin ska skickas till Person B:s bitcoinadress. En bitcoinadress är en publik nyckel som hashats två gånger, först med algoritmen SHA-256, sedan med algoritmen RIPEMD-160. Notera här att Person B:s publika nyckel alltså inte exponeras när bitcoin skickas till motsvarande bitcoinadress.
- När B ska skicka dessa bitcoin vidare måste B bevisa att hen innehar den privata nyckeln som motsvarar bitcoinadressen i förra steget, vilket görs genom att använda ECDSA för att signera transaktionen med den privata nyckeln. Nu måste också den publika exponeras eftersom den ska kunna användas för att verifiera signaturen. Vem som helst kan sedan verifiera att signaturen är giltig och att den publika nyckeln motsvarar bitcoinadressen i fråga.
Om man med en kvantdator lyckas knäcka ECDSA så kommer det att vara möjligt att gå från en publik nyckel till en privat nyckel. Dock är det inte möjligt att gå från en bitcoinadress till en publik nyckel eftersom det inte finns något sätt att vända hashningarna. Det innebär alltså följande:
- Om du bara tagit emot bitcoin till en adress men inte skickat dem vidare så kan inte kvantdatorn komma åt dem. Detta eftersom den publika nyckeln inte är känd.
- När du väljer att skicka dina bitcoin vidare så finns en period innan din transaktion kommit med i ett block (i snitt 10 minuter) då din publika nyckel är känd och en angripare skulle kunna knäcka den privata nyckeln och använda den för att skapa en alternativ transaktion och därmed stjäla dina bitcoin.
I praktiken
I videon nedan kommenterar Andreas Antonopoulos vilka konsekvenser Googles framsteg har för Bitcoin och han fokuserar framförallt på två saker. Det första är att Google fortfarande har mycket långt kvar till att kunna knäcka RSA eller ECDSA, bl.a. eftersom den kvantdator man nu demonstrerat inte använder s.k. “error correction” vilket kommer att vara en nödvändighet för att den ska vara praktiskt användbar. Andreas har helt rätt förstås och det är mycket osannolikt att en praktiskt användbar kvantdator som skulle knäcka krypteringsalgoritmerna ser dagens ljus inom ett decennium. Dock ska man vara medveten att det här är ett område där det är mycket svårt att avgöra hur snabbt utvecklingen kommer att gå. Jämför t.ex. med machine learning där många trodde att en dators möjlighet att slå världens bästa Go-spelare var ett decennium bort när Google plötsligt åstadkom det.
Det andra Andreas fokuserar på är att det är skillnad på att knäcka signeringsalgoritmen och att knäcka hashningen vilket vi också var inne på tidigare. Så länge “bara" signeringsalgoritmen har knäckts och man inte återanvänder sina bitcoinadresser så finns bara det där 10-minutersfönstret tillgängligt för en angripare. Något motsvarande Shors algoritm finns inte för att knäcka hashfunktionerna (även om det forskas även på detta). Hela det här argumentet är dock lite vilseledande eftersom det är svårt att se en situation där ECDSA har knäckts men man ändå fortsätter använda Bitcoin som vanligt. Några saker som är relevanta i praktiken:
- Det handlar inte så mycket om ett “race” att hinna göra vissa saker (upptäcka transaktionen, knäcka privata nyckeln, skapa en ny transaktion) inom 10 minuter där man kan tänka att det är “osannolikt” att det skulle hända ens egen transaktion. Antingen finns tekniken för att göra detta under 10 minuter eller inte. Finns den så kan t.ex. en miner attackera alla transaktioner. Uppstår ett scenario där den här typen av attacker sker så förlorar Bitcoin hela sin trovärdighet.
- Trots rekommendationen att inte återanvända adresser så finns många publika nycklar exponerande och det gäller bl.a. en stor del av de tidiga coins som tros tillhöra Satoshi, p.g.a. en tidig feature i Bitcoin där man kunde skicka direkt till en IP-adress, vilket exponerade den publika nyckeln. Så mycket som 36% av alla bitcoin kan för tillfället vara åtkomliga för en kvantdator-attack. Även om många av dessa skulle hinna flyttas innan det blir ett problem så kommer många gamla bortglömda coins att vara utsatta.
Andreas diskuterar hur man kommer att kunna byta till kvantsäkra signaturer innan problemet blir aktuellt men vi måste alltså ändå förhålla oss till alla dessa förlorade/bortglömda bitcoin. Hur ser vi på att den som är först till kvarn med en kraftfull kvantdator får tillgång till alla dessa? Antingen är vi OK med det eller så får vi konstruera en icke-bakåtkompatibel lösning där alla coins måste flyttas för att fortsätta vara giltiga. Ingen av dessa lösningar känns klockrena. Det är också värt att nämna att de kvantsäkra signeringsalgoritmer som finns idag har nackdelar, som att de är långsamma och att signaturerna är större. Det är alltså ett område där det behöver göras framsteg för att Bitcoins övergång ska kunna bli smidig.
Sammanfattning
Kvantdatorer som kan knäcka Bitcoins signeringsalgoritm är med stor sannolikhet fortfarande långt borta och inget vi behöver oroa oss för i närtid. Om det är på väg att ske så är det möjligt att byta den nuvarande signeringsalgoritmen mot en som är kvantsäker (under förutsättning att någon som är tillräckligt snabb/kompakt finns tillgänglig). Vi måste dock förhålla till problemet med coins där den publika nyckeln nu är exponerad och som kanske är förlorade eller bortglömda. Ska vi låta en angripare lägga beslag på alla dessa eller ska vi göra en fork där dessa coins för alltid är oåtkomliga?