Na úspěšný „hack“ byl dán časový limit 30 dní, během kterých Milne postupně dával do oběhu nápovědu v podobě prvních slov seedu. Toho využil bitcoinový vývojář John Cantrell (stojí za relativně nedávno představeným messaging protokolem Juggernaut pro Lightning Network) a za pomoci propůjčeného cloudového výkonu prověřil přes bilion kombinací, než se mu skutečně podařilo adresu odemknout a bitcoin vybrat.
Naštěstí pro nás celý postup poměrně důkladně zdokumentoval v rámci svého blogu na serveru Medium, takže po celé události naštěstí nezůstaly jen bulvární titulky a výkřiky na Twitteru.
The private keys to the 1BTC wallet at: 3HX5tttedDehKWTTGpxaPAbo157fnjn89s were generated from a 12-word mnemonic seed
— Alistair Milne (@alistairmilne) May 28, 2020
Over the next ~30 days I will be releasing the words (or a clue to a word) on my various social media pages
Milne počínaje 28. květnem pravidelně zveřejňoval nápovědu, pomocí které se dalo odvodit některé z prvních 12 slov seedu (seed phrase) podle BIP39. Kdokoliv, kdo by tyto nápovědy rozluštil, měl šanci s pomocí seedových slov, které zná, a těch, která si například útokem hrubou silou dohledá, odemknout obsah peněženky.
Hra končí v okamžiku, kdy Milne zveřejní poslední slovo seedu. Aby to ale nebylo tak jednoduché, protože brute force útok při třech kombinacích již není nijak nereálný, plánoval Milne poslední tři slova zveřejnit najednou. Ani tento trik ale nakonec nestačil, Cantrell, který k prolomení útok hrubou silou použil, si vystačil se znalostí pouhých 8 slov, aby uhodl ta zbývající a po jejich seřazení do správného pořadí získal přístup k privátnímu klíči a bitcoin si převedl.
Zatímco většině bitcoinových matadorů přišlo, že výzva vzhledem k relativně nízké odměně ani nestojí za to, Cantrell se začal hned připravovat. Podle odhadu, který spočítal, by se znalostí 8 slov ze seedu potřeboval prověřit zhruba 1,1 bilionu kombinací (2⁴⁰), čehož není tak úplně nereálné dosáhnout. Situaci usnadňuje fakt, že počet možných slov pro vygenerování seedu je omezený na 2048 (každému slovu je přitom přiřazeno jedno číslo). To teoreticky znamená 204812 = 2132 kombinací, v praxi jich ale je o něco méně, neboť ne všechna data v rámci BIP39 fráze jsou generována úplně náhodně.
Na druhé straně situaci komplikuje fakt, že je potřeba celý útok provést v několika krocích. Cantrell si spočítal, že k otestování jedné jediné fráze potřebuje vygenerovat seed z nápovědy, z něho odvodit master private key a z master key pak samotnou adresu. Po napsání programu, který tento proces automatizuje, a otestování na několika benchmarcích na železe, které měl Cantrell doma k dispozici, se ukázalo, že je schopný otestovat pouze 1250 kombinací za vteřinu, tedy 108 milionů za den, takže prolouskání se přibližně jedním bilionem kombinací, které je potřeba ověřit (za předpokladu, že skutečně zná 8 předcházejících slov a jejich pořadí), by trvalo plus minus 25 let.
Dlužno ovšem podotknout, že doma programátor využíval k počítání CPU MacBooku, což rozhodně není pro podobný úkol ideální nástroj. Při použití GPU výkon poměrně rapidně narostl, a to na 143 000 variací za sekundu, což znamená, že by se celková doba zkrátila na přibližně 83 dní, než se zkontroluje všech 2⁴⁰ možných (v nejhorším scénáři).
Naštěstí již poměrně dlouhou dobu není problém si krátkodobě pronajmout potřebný výpočetní výkon online, a to na volném trhu za velmi kompetitivní ceny. Cantrell si proto pronajal menší množství GPU jednotek a kapacitu v rámci cloudové platformy Microsoft Azure. Pro tu pak napsal v OpenCL C software, který distribuuje práci ve várkách pro jednotlivá GPU.
Dle jeho vlastních slov mu celá příprava zabrala tolik času, že v polovině testování měl již Milne zveřejněno 8 slov ze seedu a závod s časem vypukl naplno. V době největší zátěže GPU ověřovala 40 miliard kombinací za hodinu. Na projití potřebného bilionu kombinací tak bylo třeba 25 hodin času (byť statisticky mnohem méně). „Zpravidla by měla stačit polovina času,“ popisuje na blogu Cantrell.
To se ovšem v jeho případě nenaplnilo. Po testování 85 % kombinací totiž situace vypadala stejně jako na začátku a Cantrell začal pochybovat o tom, jestli má vůbec Milnem odhalená slova ve správném pořadí. Pokud by tomu tak nebylo, měl by na krku dalších 8! (faktoriál) možností a celý plán by se sesypal jako domeček z karet. Na konci dne bez výsledku byl údajně Cantrell rozhodnutý experiment zastavit, ale neměl to srdce jej ukončit, když už se dostal tak daleko. Nechal tedy GPU i nadále počítat poslední zbývající kombinace a ke svému překvapení v okamžiku, kdy jich zbývalo již jen 8 %, se skutečně vynořilo správné řešení. Trvalo to nakonec oproti odhadu 25 hodin téměř 30 hodin času a 1 000 710 602 752 pokusů.
V okamžiku, kdy Cantrell na řešení přišel, vystřídala pocit bezmoci naopak paranoia, co když stejný nápad mělo víc lidí a on byl jen o pár vteřin či minut rychlejší. Rozhodl se proto zatím stále neutracenou transakci co nejrychleji poslat na svoji vlastní peněženku. Aby byla vytěžena z mempoolu skutečně prioritně, obětoval na to z celé částky 0,01 BTC na transakční poplatek (v přepočtu 2222 Kč při současném kurzu, v době transakce byl ale kurz vyšší).
Následně Milne potvrdil, že někdo skutečně bitcoin z adresy poslal pryč, okomentoval to slovy: „Tušil jsem, že hraji závod s časem, ale většina lidí by čekala, že prolomení 4 seedových slov bude spíš záležitost pár víkendů než dne.“
Co to znamená pro bezpečnost
Když se lze během útoku hrubou silou, který je s poměrně únosnými náklady možné zrealizovat formou krátkodobého pronájmu výpočetní kapacity, možné během 30 hodin prolomit bitcoinovou peněženku, zůstává Bitcoin bezpečný? To je otázka, která po experimentu začala vrtat hlavou řadě lidí.
Mnohé můžeme vyčíst mezi řádky už ze samotného popisu útoku a jeho úskalí, které by šance srážely k nule (exponenciální nárůst obtížnosti s každým chybějícím slovem, nebo například taková drobnost jako neznalost správného pořadí známých slov). To ostatně dokládá i sám Cantrell, který později na Twitteru říká, že jediným důvodem, proč dokázal za 30 hodin útok úspěšně realizovat, bylo to, že znal díky Milnemu prvních osm slov a jejich posloupnosti. Stejný útok na celý seed by na shodném systému dle jeho vlastních slov trval 837 milionů tisíciletí. Když k tomu připočteme fakt, že dnes se běžně používají seedy s 24 slovy, jsme už úplně v říši teorie.
Great, now you can brute force mnemonics in 1 day if you know as few as 5 words.
— John Cantrell (@JohnCantrell97) June 19, 2020
To brute force all 12 words (just to break even on your $100B investment, assuming you can actually liquidate all the BTC) still takes 422 TRILLION YEARS. /6
Samozřejmě je zde možnost, že by si případný hacker pronajal řádově vyšší výpočetní výkon, to ale naráží jak na úzká hrdla, tak to nedává příliš smysl byznysově, neboť náklady stoupají neproporciálně k získané výhodě (od určitého okamžiku s enormními náklady navíc získáme jen nepatrné zlepšení výkonu) a reálně se tak nemohou vrátit.
Jinak by situace mohla vypadat s plnohodnotným obecným kvantovým počítačem, jak jej v našem rozhovoru popisuje Gilles Brassard, jenže o něm si můžeme nechat (včetně Google a IBM) zatím jenom zdát. BIP39 ale podle všeho poskytuje stejnou, nebo velmi podobnou bezpečnost jako samotné privátní klíče, a to je rozhodně dobrá zpráva.
