equalpastebin.com

IdentifyingKeyLeakageofBitcoinUsersMichaelBrengel(B)andChristianRossowCISPA,SaarlandUniversity,Saarbr¨ucken,Germany{michael.
brengel,rossow}@cispa.
saarlandAbstract.
Westudykeyleakageinthecontextofcryptocurrencies.
First,weconsidertheproblemofexplicitkeyleakageoccurringonopen-sourceintelligenceplatforms.
Todothis,wemonitorthePastebinfeedfromSep2017–Mar2018tondexposedsecretBitcoinkeys,reveal-ingthatattackerscouldhavestolen22.
40BTCworthroughly$178,000givencurrentexchangerates.
Then,wefocusonimplicitkeyleakagebyexploitingthewrongusageofcryptographicprimitivesandscanBitcoin'sblockchainforECDSAnoncereuse.
Wesystematicallyoutlinehowanattackercanuseduplicatervaluestoleaknoncesandsecretkeys,whichgoesbeyondthesimplecasewherethesamenonceandthesamekeyhavebeenusedinconjunctionmorethanonce.
OurresultsshowthatECDSAnoncereusehasbeenarecurringproblemintheBitcoinecosystemandhasalreadybeenexploitedbyattackers.
Infact,anattackercouldhaveexploitednoncereusetosteal412.
80BTCworthroughly$3.
3million.
1IntroductionCryptocurrencieshavebecomepopularentitiesinglobalnancialmarkets.
AprimeexampleofsuchacurrencyisBitcoin[17]withacurrentmarketcapital-izationofover$135billion[1]orEthereum[23]withacurrentmarketcapital-izationofover$44billion[2].
Assuch,itcomesasnosurprisethatmaliciousactorsconstantlytrytostealthosecurrencies,i.
e.
,changeownershipofcryp-tocurrencyassetswithoutconsentofthelegitimateowners.
Thedecentralizedandanonymous(oratleastpseudonymous)natureofthosecurrenciesmakessuchmaliciousactivitiesmoreattractive,astracebackandprosecutionbylawenforcementagenciesissignicantlyharderthanwithtraditionalcurrencies.
Intermsofstealingcryptocurrencyassets,thereareseveralpossibilities.
Acryptocurrencyisusuallybasedonacryptographicprotocol,whichusesseveralcryptographicprimitivessuchasellipticcurves[15]ordigitalsignatures[12],whichonecouldtrytoattack.
However,boththeprotocolandtheprimitivesareusuallywellstudiedandareeitherprovensecureintheory,orhavebeensubjecttoanauditingprocessbyexpertsintheeld.
Therefore,thebestattackerscanhopeforinthissettingareimplementationaws,whichareusuallyshort-livedduetotheopen-sourcenatureofcryptocurrencyimplementations.
ThemostprominentincidentofsuchanimplementationawhappenedinFebruary2014,whenattackersfoundavulnerabilityintheMt.
GoxBitcoinexchange,whichallowedthemtosteal850,000BTCwortharound$450millionatthattime.
cTheAuthor(s)2018M.
Baileyetal.
(Eds.
):RAID2018,LNCS11050,pp.
623–643,2018.
https://doi.
org/10.
1007/978-3-030-00470-5_29624M.
BrengelandC.
RossowWhiletheattackdidnotaecttheBitcoinprotocolitself,itexploitedtheinher-enttransactionmalleabilityofBitcointransactionstobreaksomeassumptionsoftheinternalaccountingsystemofMt.
Gox[11].
Whilesuchlarge-scaleincidentsarerare,amorecommonandthusalsosevereclassofattacksagainstcryptocurrenciesaimstoleakcryptographickeys.
Cryp-tocurrencyassetsarecryptographicallyprotectedbyacollectionofsecretkeys,whichiscalledawallet.
Ifthiswalletisstoredinaninsecuremanner,i.
e.
,inplainondiskwithoutanyadditionalprotection,thenmalwarecansimplyscanthediskforsuchwalletsandreportthemtotheattacker,whichinturncanusethemtostealassets.
Duetothepopularityofcryptocurrencies,attackershavemassivelydeployedmalwarethataimstoleaksuchsecretkeys.
Awell-knowncaseofsuchmalwarewasthePonyBotnet,whichoperatedfromSeptember2013toJanuary2014[18].
Themalwarescannedthevictim'smachineforvariouscondentialcredentialsincludingcryptocurrencykeys,whichresultedinnancialdamageof$220,000.
Modernwalletsnowusemoresophisticatedmeansofkeymanage-mentsuchasadditionalencryptionwithapassword,two-factorauthenticationorhardware-basedsecurity[13],whichprotectsagainstsuchlocalattacks.
Inthispaper,wetakeadierentperspectiveandstudywhetherremoteattackvectorsallowleakingcryptographickeysfromusers.
First,westudywhetherusers(accidentallyorknowingly)explicitlyleakcryptographickeys,thatis,postthempublicly.
Tothisend,weleveragethenotionofopen-sourceintelligence(OSINT)withrespecttocryptocurrencyleaks.
Asacasestudy,weconsiderBitcoinasitisthemostprevalentcryptocurrencycurrentlyused,butanyothercryptocurrencywouldbesuitableaswell.
AsanOSINTplatformweconsiderPastebin[3],whichisapopularinformation-sharingwebapplicationontheInternet,andhasalreadyproventoleakdierenttypesofprivacy-relatedinformation[16].
However,otherOSINTplatformssuchasTwitter,Reddit,Face-bookorGitHubwouldalsowork.
WeenvisionascenariowhereavictimusesPastebintoshareapieceofinformationincludingBitcoinsecretssuchasacodesnippetperformingatransactionorthedebugoutputofwalletsoftware.
Thevictimcreatesthispastetoprivatelysharetheinformation,notknowingthatitwillbepubliclyavailableinthePastebinfeed.
AnattackerthatmonitorsthisfeedcanthenscaneachnewpasteforBitcoinkeys,forexampleusingtheirwell-knownformat,andusethosekeystostealBitcoins.
Tosimulatethis,wehavemonitoredthePastebinfeedsinceSeptember2017forBitcoinsecrets.
Ourresultsshowthatanattackercouldhavestolen22.
40BTCduringthistimespan.
Wethenalsostudythepossibilityofimplicitkeyleakage,giventhatcryp-tocurrencyusers(orsoftwaredevelopers)maymisapplycryptographicprimi-tives.
Inparticular,keepingourfocusonBitcoin,westudytheincorrectuseoftheEllipticCurveDigitalSignatureAlgorithm(ECDSA),which,however,alsoappliestoothercryptocurrenciesthatarebasedonthisprimitive.
TosignamessagemusingECDSAwithasecretkeysk,onemustcomputeasignature,whichinvolvesarandomlychosennoncek.
Itiswellknownthatapartfromthesecretkey,thenoncemustalsobekeptsecret,asanattackercanotherwiseusethesignatureandktoretrievesk.
Similarly,ifonesignstwodistinctmessagesIdentifyingKeyLeakageofBitcoinUsers625m1andm2usingthesamekandthesamesk,thenanattackercanrecomputeskbasedonthestructureofthesignatureandtheknowledgethatboththekeyandthenoncehavebeenreused.
Whilesuchaduplicateoccurrenceshouldnothappeninpractice,asthesetofpossiblenoncesissucientlylarge,i.
e.
,almost2256inthecaseofBitcoin,suchduplicatescanstillappearforotherreasons.
Onesuchreasoncouldbetheuseofweakrandomnumbergenerators[4]orvul-nerablesoftwarethatisnotawareoftheimplicationsofnoncereuses.
Anotherscenariowhichcouldalsoberesponsibleforsuchduplicateoccurrencesiscloningorresettingavirtualmachine,whichcouldpossiblyresultinreusingthesameseedfortherandomnumbergenerator.
WhilethereisanecdotalevidenceforduplicatenoncesintheBitcoinblockchain,thereisnosystematicstudyontheactualimpactortheprevalenceofthisphenomenon,i.
e.
,thepotentialnancialdamagethatcanbecaused.
Tollthisgap,wescantheBitcoinblockchainforduplicatenoncesandsimulateanattackscenarioinwhichamaliciousactoractivelymonitorsincomingtransactionstolookforduplicatenonceoccurrencestoleakkeysandstealBitcoins.
Inparticular,wesystematicallyoutlinehowanattackercanuseduplicatenoncestoleaksecrets,whichhasnotbeenshownbeforeinsuchdetail.
Thisgoesbeyondna¨vecaseswherethesamekeyandnoncepairwasusedtwicetosigntwodistinctmessages.
Infact,weshowthatitisalsopossibletoleaksecretsbyexploitingcyclicdependenciesbetweenkeysandduplicatenonces.
Ourresultsshowthatanattackercouldhaveusedthismethodologytosteal412.
80BTC.
Tosummarize,ourcontributionsareasfollows:(i)WeassessthethreatofexplicitBitcoinkeyleaksusingOSINT.
Weinstantiatethisideabymonitor-ingthepublicfeedofPastebinforleakedsecretkeys.
Ourresultsdemonstratehowanattackerdoingthiscouldhavestolen22.
40BTC.
(ii)WesystematicallydemonstratehowattackerscanmonitorBitcointransactionstoscanforimplicitkeyleaks.
Wedevelopamethodologythatcanmapsignatureswithduplicatenoncestolinearequationsystemsusingabipartitegraphrepresentation.
(iii)WeassesstheimpactofimplicitkeyleaksinthecontextofBitcoin.
Thatis,weanalyzehowprevalenttheyareandhowmuchBitcoinsanattackercouldhavestolenbyexploitingthem.
Finally,westudyifsuchexploitationhashappenedinthepast.
Ourresultsshowthatanattackercouldhavestolen412.
80BTCandthatattackershaveexploitednoncereuseinthepasttostealBitcoins.
2BackgroundInthissection,weoutlinethepreliminariesrequiredforthescopeofthispaperinordertograspourideasusingtheBitcointechnology.
BlockchainandMining.
ThecentralcomponentoftheBitcoinprotocolistheBitcoinblockchain,whichisadistributedappend-onlylog,alsocalledaledger.
TheideaofthisledgeristokeeptrackofalltransactionsthathaveeveroccurredintheBitcoinnetwork.
Theledgerconsistsofasequenceofblocks,eachofwhichconsistsofasetoftransactions.
AddingsuchablocktotheblockchainrequiressolvingacomputationalpuzzleusingtheHashcashproof-of-worksystem[9].
The626M.
BrengelandC.
RossowprocessofaddingblockstotheblockchainiscalledminingandisrewardedwithBitcoins.
Transactionsandblocksarecreatedanddistributedbythepeersofthenetwork.
Beforetransactionsaremined,theyareputinatemporarybuercalledthemempool.
Miners,i.
e.
,thepeerswhichmineblocks,willthentaketransactionsfromthemempooltobuildandmineablockandnally,announceanewlyminedblocktothenetwork.
Transactions.
ABitcointransactionTconsistsofasequenceofinputsTi=[i1,im]andasequenceofoutputsTo=[o1,on]andisuniquelyidentiedbyatransactionID,whichisgeneratedbycomputingahashofthetransaction.
InputsandoutputsarethereforeuniquelyidentiedbytheIDofthetransactionwhichcontainsthemandtheirindexintheinputlistandoutputlist,respec-tively.
Anoutputoj∈Tocarriesavalue,whichisthenumberofsatoshisthatthisoutputisworth.
AsatoshiisdenedtobesuchthatoneBitcoin(BTC)equals108satoshis.
Thepurposeofatransactionistospendoutputsbycreatingnewones,whichrepresentsthemoneyow.
Todothis,everyinputij∈Tiuniquelyreferencesanoutputofanotherprevioustransaction,i.
e.
,theoneswhichwillbespent,andcreatesnewoutputsthatcanbespentbyfuturetransactions.
Anoutputcanonlybereferencedonce,andtheoutputsintheblockchainwhichhavenotbeenreferencedatanygivenmomentintimeiscalledthesetofunspentoutputs.
Everytransactioncarriesanimplicittransactionfee,whichisthedif-ferencebetweenthesumofthevaluesoftheoutputsandthesumofthevalueofthereferencedoutputs.
Transactionfeeswillbepaidtotheminers,whichthusprioritizetransactionsbasedontheirfees,i.
e.
,thehigherthefee,thefasterthetransactionwillbemined.
Sinceablockcanonlybe1MiBinsize,minerswillusuallyconsidertransactionfeesasafunctionofsatoshisperbyteofthetransaction,i.
e.
,thelargerthetransactionthelargerthenominalvalueofthefeeshouldbe.
TransactionfeesareanessentialeconomicalelementoftheBitcoinnetworkandchangeconstantlydependingonthenumberoftransactionsinthemempoolandhowmuchpeersarewillingtopaytheminers.
Specialtransactionswithoutanyinputsreferencingotheroutputsareso-calledcoinbasetransactionsandarecreatedwhenablockisminedtorewardtheminer,whichishowBit-coinsareinitiallycreated.
Thatis,beforeaminerminesablock,theywillrstcreateacoinbasetransactionwhichwillbeputintheblockandrewardsthemwithBitcoins.
Thisrewardisaxedamount,whichgetshalvedevery210,000blocks,plusthefeesofalltransactionsintheblock.
Scripts.
TransactionsintheBitcoinnetworkareveriedbyusingasmallstack-basedlanguage,theprogramsofwhicharecalledscripts.
Everyinputandoutputcontainsascript,whichisoftenreferredtoasscriptSigandscriptPubKey,respec-tively.
Thesescriptscanperformarithmetic,cryptography,owcontrolandsoon.
Inorderforatransactiontobevalid,onemustconcatenatethescriptSigofeachinputwiththescriptPubKeyofitsreferencedoutput,whichyieldsanewsetofscripts,i.
e.
,oneforeachinput.
Allofthesescriptsarethenevaluated,andforthetransactiontobevalid,theremustbeonlyoneelementonthestackafterevaluationandthiselementmustbeequaltotrue.
ThescriptPubKeycanthere-forebeconsideredameansofprotection,i.
e.
,onecanonlyredeemanoutputIdentifyingKeyLeakageofBitcoinUsers627iftheycanprovideacorrectscriptSig.
Thescriptinglanguagecontainsspecialinstructionsforellipticcurvecryptography,whichisusedwithinthisscriptingframeworktocryptographicallysecuretransactions.
Inthiscontext,everyuserhasasecretkeyskandapublickeypk.
ThemostprevalenttypeoftransactioniscalledaPayToPubkeyHash(P2PKH)transaction.
OutputsbelongingtosuchtransactionshaveascriptPubKeythatveriesthatthesenderofthetransactionpossessesthecorrectpublickeybycomparingitagainstahash.
Additionally,thescriptveriesasignature,whichmeansthataworkingscriptSigmustprovideboththepublickeypkaswellasavalidsignaturethatcanbeveriedwithpk,whichmeansthatthesendermustknowsk.
BitcoinAddresses.
ABitcoinaddressisaserializedhashofpk,whichisgen-eratedbyhashingthepublickeywiththeSHA-256andtheRIPMED-160hashfunctionsandappendingandprependingaversionbyteandchecksumbytes.
Thehashisthenserializedusingbase58encoding,whichisamorehuman-readability-friendlyversionofthebase64encodingandremovesambiguous-lookingcharac-ters(e.
g.
,zero("0")andcapitalo("O")).
Anexampleofsuchanaddressis16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM.
Beforehashing,pkmustbeserialized,forwhichtherearetwooptions,namelythecompressedpublickeyandtheuncompressedpublickey.
Weomitthetechnicaldetailshereastheyarenotrequiredforthescopeofthispaper.
Itisonlyimportantthatbothserializationoptionsyielddierentaddresses,whichmeansthateverypublickeypkcorre-spondstotwoaddresses,whichcanbeusedindependentlyofeachother.
Thismeansthatifanattackerleaksasecretkey,theygaincontroloverthebalancesoftwoaddresses.
WecandenethebalanceofaP2PKHaddressbyusingthepreviouslymentionedscripts.
Forinstance,wedeterminethatthebalanceofaP2PKHaddressencodingahashh,isthesumofthevaluesofallunspentoutputsthatcanberedeemedwiththepublickeypkthathisahashfor.
3ExplicitKeyLeaks:OpenSourceIntelligenceInthissection,wewilloutlinethemethodologythatweusetodiscoverexplicitBitcoinkeyleaks,i.
e.
,caseswhereusers(knowinglyornot)directlydisclosesensitiveBitcoinkeymaterialtothepublic.
Tothisend,wefollowthegeneralideaofopensourceintelligence(OSINT),inwhichanattackerharvestspubliclyavailableinformationtoderivesensitiveinformation.
ToevaluatethisideainthecontextofBitcoinsecrets,wechosePastebinasanOSINTplatform.
Givenitspopularity,weexpectthatBitcoinusersaccidentallyleaksecretinformationthere.
ExamplesofsuchleakswouldbeuserspublishingcodesnippetsdoingBitcointransactionsorthedebugoutputofsomewalletsoftwarewhichuserswanttoshareprivately,notknowingthatthesepastesarethenpubliclyvisibleinthePastebinfeed.
WemonitoredallpastesstartingfromSeptember2017andscannedeachpasteforBitcoinsecrets,i.
e.
,secretkeys.
628M.
BrengelandC.
Rossow3.
1FindingBitcoinSecretsToscanapasteforsecretBitcoinkeys,weleveragetheobservationthatBitcoinkeysareserializedusingawell-knownformat.
Asecretkeyisanintegersk,whichwewilldescribefurtherinSect.
4.
1.
Anagreed-uponformatforserializingthosekeysistheWalletImportFormat(WIF).
Toconvertasecretkeyskintothisformat,thefollowingprocedureisapplied.
First,skisconvertedtoa32-bytes-longbig-endianrepresentation,whichwecallb.
Then,0x80isprependedtobandoptionally0x01isappendedifthesecretkeywillcorrespondtoacompressedpublickey.
ThenSHA256isappliedtwiceonb,andwecallthelastfourbytesofthishashc.
TheWIFisdenedtobethebase58encodingofb||c.
Thelast4bytesinthisformatareachecksumfortheremainingbytes,whichisusedinpracticetoavoidcopyandpastemistakes.
However,thischecksumalsoallowsasystematicscanforinstancesofWIFstringsintextwithaverylowprobabilityoffalsepositives.
InourBitcoinmonitoringtool,wethusproceedforeachnewpasteasfollows.
First,wemoveaslidingwindowoverthecontentofthepastetodiscoverallvalidbase58encodedsubstringsofthepastewhichare51or52characterslongandstartwitheither"5","K"or"L".
Bothoftheseconstraintsareaconsequenceofthebase58encodingandthefactthatthexedbyte0x80isprepended.
Foreachstringwhichmatchesthesecriteria,wecomputeandverifythechecksumasdescribedabove.
Ifthechecksumveries,wehavefoundavalidWIFstringandwecancomputethecorrespondingsecretkeysk.
Finally,wecheckifthesecretkeyisinthevalidrange(cf.
Sect.
4.
1),andifthisisthecase,thenweconsiderthiskeyforfurtheranalysis.
3.
2ResultsToapplyourmethodology,wemonitoredandscannedallpublicpastesonPaste-binsinceSeptember2017.
Weidentied21,464secretkeys,whichcorrespondto42,936addresses,i.
e.
,2addressesperkeyasdescribedinSect.
2.
However,mostoftheseaddressesareunused,i.
e.
,thereisnotransactionintheblockchainwhichtransferredBitcoinsfromortotheseaddresses.
Asofnow,391(0.
91%)ofthoseaddressesheldabalanceatsomepointintime.
However,forstealingBitcoinsitisnotsucientthatanaddressheldabalanceatsomepointintime.
Instead,wealsohavetotakeintoaccountthattheaddressheldabalanceafterwehaveseenthecorrespondingsecretkeyinapaste.
Ifwerespectthisconstraint,wendthat165(0.
38%)addressesheldabalanceafterwehaveseentheirsecretkeyinapaste.
Thosekeyswerescatteredamongatotalof34pastes.
Summingupthosebalancesgivesatotalof326.
70BTC.
Itshouldbementioned,though,thatthisisstillnotaguaranteethatthisnumberofBitcoinscouldhavebeenstolen.
Thisisduetothefactthatwedeter-minethebalanceofanaddressatsomepointintimebasedontheblockchain,notthemempool.
Thatis,wetakethelatestblockthatwasminedbeforethepastewaspublishedandcheckthebalanceofanaectedaddressuptothisblock.
Itcouldbethecasethattherewasatransactioninthemeantimewhichredeemedoutputsfromthegivenaddress,i.
e.
,therecouldbeapendingtransactioninIdentifyingKeyLeakageofBitcoinUsers629themempool.
Inthiscase,anattackercouldnoteasilycreateatransactiontostealtheBitcoins.
Currentnetworkrulesdiscouragethedistributionoftrans-actionsthatdouble-spendoutputsunlessthetransactionisexplicitlymarkedasareplace-by-fee(RBF)transaction.
Anattackercouldtrytomineastealingtransactionthemselvesortrytodirectlyannouncethestealingtransactiontominingpoolswhichdonotfollowthesenetworkrules.
Alternatively,iftheblock-ingtransactionhasalowfee,theattackercouldwaituntilasignicantnumberofpeersdonothavethetransactionintheircopyofthemempoolanymore.
Thiswouldincreasethechancesthatthenewstealingtransactionwillbepushedtomorepeers,whichinturnwillincreasethechancesthatthestealingtransactionswillbemined.
However,noneofthesemethodsguaranteessuccess,andthereforetheamountof326.
70BTCisanupperlimit.
TogetamoreconservativeestimationoftheamountofstealableBitcoins,wehavetoconsiderpendingtransactions.
Thatis,weonlyconsideredcaseswheretherewasnotransactioninbetweenwhichwasnotmarkedasRBF.
Asitturnsout,thiswasthecasefor26addressesin119pastes.
Fortheremainingcases,therewasablockingtransactioninbetween,i.
e.
,thepastecontainingthesecretkeywaspublishedaftertheblockingtransactionwasdistributed.
Forexample,onepastecontainedanaddressholdingabalanceof40.
84BTCforwhichatransactionwasalreadyplacedinthemempool.
Intotal,wefoundthatanattackercouldhavestolen22.
40BTC.
Weexcludedtransactionfeesinthisanalysisastheyarehighlydynamicovertimeandthenumberofstealableoutputswassosmallthattheresultingfeeswouldnotbeasignicantfactor.
Thisdemonstratesthatanattackercancausesignicantnanciallosswithrelativelysimplemeans.
ThisisampliedbythefactthatanattackercouldexpandthismethodologytoothercryptocurrenciesandOSINTplatforms.
4ImplicitKeyLeaks:IncorrectlyUsedCryptographySeeingthatevenexplicitkeyleaksposeaproblemtoBitcoinusers,inthissection,wewillstudyhowusersimplicitlyleaksecrets.
Tothisend,wewillrstdescribethemostimportantcryptographicprimitiveinBitcoin,namelyECDSA.
Wethenshowhowtheincorrectuseofthisprimitiveopensseverevulnerabilities.
Thatis,wewillsystematicallydescribehowanattackermonitoringthetransactionsoftheBitcoinnetworkcanusenoncereusetostealBitcoins,andwhatamountofdamagecouldhavebeencaused(orwascaused)inthepastbyattackers.
4.
1EllipticCurveDigitalSignatureAlgorithm(ECDSA)BitcoinusestheEllipticCurveDigitalSignatureAlgorithm(ECDSA)tocryp-tographicallysecuretransactions.
TheschemeisbasedonthecomputationalinfeasibilityassumptionofsolvingtheEllipticCurveDiscreteLogarithmProb-lem(ECDLP),i.
e.
,giventwopointsQandQkonthecurve,thereisnopolynomial-timealgorithmforrecoveringk.
Bitcoinusesthesecp256k1curve,whichisbasedontheequationy2=x3+7overtheniteeldFpwiththe630M.
BrengelandC.
Rossow256-bitprimenumberp=225623229282726241.
Furthermore,secp256k1usesageneratorpointGwiththe256-bitgroupordern=22560x14551231950B75FC4402DA1732FC9BEBF,i.
e.
,nisthesmallestnumbersuchthatGn=0.
Tocreateandverifysignatures,weneedthenotionofasecretkeyskandapublickeypk.
Inthecontextofellipticcurvecryptography,skisarandomlychosenintegerfrom{1,n1}andthepublickeypkcanbederivedbymultiplyingthegeneratorGwithsk,i.
e.
,pk=Gsk.
Thisderivationisconsideredsecure,asrecoveringskfrompkwouldrequiresolvingECDLP.
TosignamessagemwithasecretkeyskusingECDSA,thefollowingpro-cedureisfollowed:Firstahashofthemessageh=H(m)iscreatedusingacryptographichashfunctionH.
Thehashhistheninterpretedasanumberandtruncatedsothatitdoesnotcontainmorebitsthanthegroupordern.
InthecaseofBitcoin,wehaveH=SHA2562,i.
e.
,applyingSHA256twice,whichmeansthathwillnotbetruncatedasnisa256-bitnumber.
Then,arandomnoncekischosenfrom{1,n1}.
Afterthat,thervalueiscom-puted,whichisthex-coordinateofthepointthatisyieldedbymultiplyingthegeneratorpointGwithk,whichwedenotebyr=(Gk)xmodn.
Finally,thevalues=k1(h+rsk)modniscomputedandthetuple(r,s)isreturnedasthesignature.
Ifr=0ors=0,thenthisprocedureisrepeateduntilbothrandsarenon-zero.
Toverifythat(r,s)isavalidsignatureforamessagemusingthepublickeypk,oneproceedsasfollows:Firstthehashh=H(m)iscreatedandtruncatedasbefore.
Then,thecurvepoint(x,y)=(Gh+pkr)s1iscalculatedandthesig-natureisconsideredvalidifx=r.
Thecorrectnessfollowsfromtheobservationthatpk=Gsk,whichimplies(Gh+pkr)s1=G(h+skr)s1=Gkss1=Gk.
Intermsofkeyornonceleakage,notethattheequations=k1(h+rsk)modncontainstwounknownsandthereforecannotbeusedtoleakthesecretkeyorthenonce.
Recoveringkfromr=(Gk)xwouldrequiresolvingECDLP,similartohowpk=Gskcannotbeusedtorecoversk.
4.
2UsingDuplicateNoncestoLeakKeysItisknownthatECDSAfailscatastrophicallyifnoncereuseoccurs.
Noncereusemeansthattherearemultiplesignaturesusingthesamenoncek,whichmightallowanattackertoleaksecretkeysundercertaincircumstances.
Forinstance,ifthesamek(andtherebythesamervalue)andskareusedtocreate2signatures(r,s1)and(r,s2)fortwodistinctmessagesm1andm2,thenwehave1:s1=k1(h1+rsk)s2=k1(h2+rsk),(1)Thisallowsleakingthesecretkeyskwith:s2h1s1h2r(s1s2)=h1h2+rh1skh1h2rh2skrh1+rskrh2rsk=rh1skrh2skrh1rh2=sk.
(2)1Notethatallcalculationsonsignaturesaredonemodulon,whichweomitforbrevity.
IdentifyingKeyLeakageofBitcoinUsers631Similarly,kcanbeleakedwith:h1h2s1s2=h1h2k1(h1h2+sk(rr))=k.
(3)However,noteverykindofnoncereuseleadstocaseswhereanattackercanleaksecrets.
Forinstance,considerthecasewhereanoncekisusedwithtwodierentkeyssk1andsk2tosigntwodistinctmessages,i.
e.
,:s1=k1(h1+rsk1)s2=k1(h2+rsk2).
(4)Itturnsoutthatitisnotpossibleinthiscasetoleakanysecrets.
Togetabetterunderstandingofthis,weneedtoconsiderthefundamentalunderlyingproblemthatconstitutestheactofleakingsecretsinthissetting.
IfwerewriteEq.
(1)tolookasfollows:s1krsk=h1s2krsk=h2itbecomesevidentthatthisisasystemoflinearequations.
Inparticular,thissys-temconsistsof2linearlyindependentequations,sinceh1=h2,and2unknowns,i.
e.
,kandsk,andisthereforeuniquelysolvable.
Ontheotherhand,Eq.
(4)con-sistsof2equationsand3unknowns,i.
e.
,k,sk1andsk2,andisthereforenotuniquelysolvableastherearemoreunknownsthanequations.
4.
3BeyondSingle-KeyNonceReuseInterestingly,insomecasessecretsleakeventhoughthenoncesarenotreusedwiththesamesecretkey.
Forexample,considerthefollowingcase,wheretwokeyssk1,sk2areusedwiththesamepairofnoncesk1,k2,i.
e.
,:s1,1=k11(h1,1+r1sk1)s1,2=k11(h1,2+r1sk2)s2,1=k12(h2,1+r2sk1)s2,2=k12(h2,2+r2sk2)Here,nononceisusedtwicebythesamekey,butnonceshavebeenreusedacrosskeys.
Thesystemthusconsistsof4linearlyindependentequationsand4unknownsandisthusuniquelysolvable.
Asolutionforsk2thatcanbecomputed,withGaussianeliminationforexample,wouldbe:sk2=r1s1,2(h2,2s2,1h2,1s2,2)r2s2,2(h1,2s1,1h1,1s1,2)r1r2(s1,2s2,1s1,1s2,2).
Ingeneral,wecanthinkofthisproblemasfollows.
AnattackerisgivenasetofsignaturesS={(h1,r1,s1,pk1)hn,rn,sn,pkn)},whichcanbeextractedfromtheBitcoinblockchain,forexample.
Eachtuple(hi,ri,si,pki)∈Scorrespondstoasignature(ri=(Gki)x,si=k1i(hi+rsk))wherepk=Gsk.
Thegoaloftheattackeristoleakasmanykeys(ornonces)aspossiblebysolvingsystemsoflinearequations.
Toachievethis,anattackerhastoidentifysubsetsofsolvablesystems.
Theycandosobyreducingthisproblemtographtheory.
632M.
BrengelandC.
RossowForinstance,webuildanundirectedbipartitegraphG=(Vpk∪Vr,E),whereVpk={pkipki)∈S},Vr={ri|(·,ri,S}andE={{ri,pki}|(·,ri,·,pki)∈S}.
ThegraphGconsistsoftwotypesofnodes,rvaluesriandpublickeyspki,eachofwhichcorrespondstoanunknown(anoncekiandasecretkeyski).
Anedge{r,pk}inthisgraphcorrespondstoasignature,whichinturncorrespondstoanequationinthesystemoflinearequationsthatSconstitutes.
Asapre-lteringstep,werstcollectallthervaluesandpublickeysthatappearatleasttwiceinconjunction,i.
e.
,wecollectF={r,pk||{(·,r,·,pk)∈S}|>1}.
Sincethiscorrespondstothesamenoncebeingusedbythesamekeyatleasttwice,itmeansthatwecanleaktheusedsecretskandskusingEqs.
(3)and(2)withtheappropriatesignatures.
Additionally,wecanleakallthesecretswhichcorrespondtothenodesthatarereachablebyeverypublickeyandnonceinF.
Tounderstandthis,assumewehaveanrvalueri∈F,whichmeansthatwecanleakthenoncekiasdescribed.
Nowassumethatthereisanodepkj∈Vpksuchthat{ri,pkj}∈E,whichimpliestheexistenceoftheequationsj=k1i(hj+rskj).
Sinceweknowki,wecanleakskjwithskj=sjkihjr.
Thesameisanalogouslytrueifweassumeapublickeypki∈Fandanrvaluerj∈Vrsuchthat{rj,pki}∈E.
Byapplyingthisargumentinductively,itbecomesevidentthatwecanleakthesecretsassociatedwithallnodesthatarereachablefromeveryri∈Fandeverypki∈F.
Inthenextstep,weneedtoidentifythenodesandedgeswhichcanbemappedtoasolvablesystemoflinearlyindependentequations.
Thiscanbeachievedbyndingnon-trivialcyclesinG,i.
e.
,distinctnodesr0,pk0,rn,pknforn>0suchthat{ri,pki}∈Eand{pki,ri+1modn}∈Efor0≤i≤n.
Suchacyclecontains2(n+1)nodes,i.
e.
,unknowns,and2(n+1)edges,i.
e.
,equations,andthusdirectlyimpliestheexistenceofasolvablesystemoflinearequations.
Hence,forallsuchcycleswecanleakthecorrespondingsecrets,and,asbefore,wecanalsoleakthesecretsofthereachablenodes.
TheoutputofthiswholeprocessistwosetsVpkVpkandVrVr,whicharethepublickeysandrvaluesforwhichwehaveleakedthesecretkeysandnonces,respectively.
IfweremovethenodesinVpk∪VrandtheiredgesfromG,theresultinggraphshouldnotcontainanynon-trivialcycles.
ThismeansthatnomoresecretscanbeleakedandhenceVpkandVrareoptimalwithrespecttotheirsize.
Thereis,however,alittletwisttothemethodologywedescribedhere.
Weconsidertwosignatures(r1,s1)and(r2,s2)acaseofnoncereuseifthervaluescoincide,i.
e.
,ifr1=r2.
Thisisnotstrictlytrue,asthervalueisonlythex-coordinateofGk.
SinceellipticcurvesarebasedonaWeierstrassequationoftheformy2=x3+bx+a,therearealwaystwononceskwhichleadtothesamervalue2.
Inparticular,ifwehaveGk=(x,y),thenwehaveG(k)=(x,y).
Thismeansthatifthervaluescoincide,weneedtotakeintoaccountthatonenoncemightbetheadditiveinverseoftheotherratherthanbeingequal.
Torespectthis,wemustconsiderforeverysignature(r,s)thesignature(r,s)aswell,whichisthesignaturethatisyieldedbynegatingk.
Foreachsuchcombinationwehavetosolvethesystemoflinearequationsandcheckifthe2Recallthatr=0(cf.
Sect.
4.
1).
IdentifyingKeyLeakageofBitcoinUsers633returnedsolutionsarecorrecttoleakthecorrectkeysandnonces.
Thiscanbedonebydouble-checkingthateachleakedsecretkeyskcorrespondstothegivenpublickeypk,whichcanbedonebyverifyingtheequalityGsk=pk.
4.
4ResultsWewillnowoutlineourresultsregardingnoncereuseintheBitcoinblockchain.
Toachievethis,wedownloadedacopyoftheBitcoinblockchainupuntilblock506071,whichwasminedon2018-01-2516:04:14UTC.
WeparsedallinputsfromallP2PKHtransactionstoextracttheirECDSAsignatures.
Table1.
The10mostfrequentrvaluesandtheirnumberofoccurrences.
rvalueOccurrences0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c632,276,7180x00006fcf15e8d272d1a995af6fcc9d6c0c2f4c0b6b0525142e8af866dd8dad4b7,8950x1206589b08a84cb090431daa4f8d18934a20c8fa52ad534c5ba0abb3232be1d92650x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f817982510x2ef0d2ae4c49c37703ba16a3126e27763e124ff3338fb93577ed7bd79ed0d19e910x06cce13d7911baa7856dec8c6358aaa1fb119b5a77d0e4d75d5a61acae05fcfb830xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1760x281d3da7518241cd8ee30cd57ae3173a1bd9ee5e3b02a46ba30f25cd5b4c6aa8680x8216f63d28f4dc0b6909a330d2af09b93df9dd3b853958c4d203d530328d8ed1640x5d4eb477760cf19ff00fcb4bab0856de9e1ce7764d829a71d379367684712be452Intotal,weextracted647,110,920signaturesandwefound1,068distinctrvaluesappearingatleasttwiceandusedby4,433keys.
Intotal,theseduplicatervaluesmakeupfor2,290,850(0.
35%)ofallrvalues.
InTable1,weshowthetop10mostfrequentduplicatervaluesalongwiththeirnumberofappearances.
Themostfrequentduplicatervalueappears2,276,671times,whichmakesup99.
38%ofallduplicateoccurrences.
Thisrvalueisspecial,asitisextraordinarysmall,giventhatits90mostsignicantbitsareall0.
Additionally,thecorrespondingnoncekforthisrvalueisk=12modn.
Asthisisunlikelytobeacoincidence,itisbelievedthatthedesignersofthesecp256k1curvechosethegeneratorpointGbasedonthesevalues.
Itisalsobelievedthatthisrvalueisusedonpurposebypeerstosavetransactionfees.
BitcoinusestheDERencodingtoserializesignatures,whichcancompresstheleadingbitsofthisrvalue,whichreducesthetransactionsizeandleadstosmallertransactionfees.
Ifpeersusethisnonceonlyforthe"last"transactionofanaddress,i.
e.
,thenaltransactionwhichremovesallfunds,thenthisshouldbesecureaslongasthetransactionismarkedasnon-replaceable.
Butsincethistransactionstillleaksthesecretkeyoftheaddress,thepeerneedstomakesurethattheywillneverusetheaddress634M.
BrengelandC.
Rossowagain.
Ouranalysisrevealedthatthisrvaluewasprimarilyusedintwotimeperiods.
Therstblockwhichcontainsthisvalueisblock364,767andthelastoneisblock477,411.
Intotal,weidentied1,550blockswhichcontainthisrvalue.
Wefoundthatthervaluewasusedexcessivelyin2timeperiods,whichisdepictedinFig.
1.
Wecanseethatbetweenblock365,000andblock366,000andbetweenblock374,000andblock375,000,thevalueisusedroughly1milliontimeseach,whichmakesupalmostallofitsappearances.
364000366000368000370000372000374000376000Block0500000100000015000002000000AccumulatedNumberofOcurrencesFig.
1.
Numberofoccurrencesofthemostprominentduplicatervalueovertime.
Inspectingtheotherduplicatervaluesabitmorecloselyrevealsfurtherinterestingcases.
Thesecondmostusedrvaluealsohas16leading0bits,whichisalsoanindicationthatthecorrespondingnoncewasnotchosenrandomly.
Thefourthmostusedrvaluecorrespondstothenoncek=1,whichisanindicationofeitherabrokenrandomnumbergeneratororahand-craftedtransactionwherethenoncewasnotrandomizedandthecreatorsimplytookthex-coordinateofG.
Anotherrvaluewefoundwasusingthenoncek=12345678,whichisalsoanindicationofanad-hocgeneratedtransactionusingaxednonceratherthanasecurerandomone.
Similarly,wefoundtwootherrvalueswherethecorrespondingnonceswheresuspiciouslysmall,i.
e.
,inonecasethenoncewask=0x80001fffandinanothercasethenoncealsohad74leading0bits.
Inanothercasethenoncewask=32i=016i,i.
e.
,0x0101.
.
.
01inhexadecimalnotation,whichlookslikeapatternthatahumanwouldproduce.
4.
5MeasuringtheImpactofWeakNoncesWewillnowassesshowmuchdamageanattackercouldhavecausedbyusingthepreviouslydescribedmethodologyforleakingkeysandnonces.
Todothis,weputourselvesinthepositionofanattackerwhomonitorsthetransactionsoftheblockchain.
Thatis,weuseourcopyoftheblockchaintocreateanorderedsequenceofsignatures[(Δ1,h1,r1,s1,pk1)Δn,hn,rn,sn,pkn)]whereΔiisIdentifyingKeyLeakageofBitcoinUsers635ablocknumbersuchthatΔi≤Δjfori≤jandtheremainingelementsarethecomponentsofasignaturefoundinatransactionofblockΔi.
Wethenprocesstheseentriesinorderasfollows.
Weaddeachsignaturesi=k1(hi+ri)forapublickeypkiinblockΔitoadatabase,whichallowsustoquicklyidentifyduplicatervaluesaswellastheirsignatures.
EachidentiedduplicatervalueriisthenaddedtothegraphGalongwiththeusedpublickeypki.
However,beforeaddingthese2nodestothegraph,wemakeafewchecks.
First,wecheckifwehaveleakedbothkiandski,inwhichcasewecancompletelydisregardboth,asaddingthemwillnotleadtonewleaks.
Second,wecheckifGalreadycontainstheedge{ri,pki},inwhichcasewecanleakbothkiandski.
Third,wecheckifwehavealreadyleakedeitherkiorski,inwhichcasewecanthenleakskiorki,respectively.
Inthelasttwocases,wecanalsoleakthesecretscorrespondingtoallthenodesreachablefrombothriandpkiasdiscussedpreviously.
Onlyifnoneofthesethreeconditionsapply,weaddtheedge{ri,pki}toG.
Afterprocessingallsignaturesofablock,welookforcyclesinGtoidentifysolvablesystemsoflinearequationsinordertoleaksecretsasoutlinedpreviously.
Wheneverwendanewleak,wemakesurethatweremovethecorrespondingsignaturesfromthedatabaseandthatweremovethecorrespondingnodesandtheiredgesfromG,aswewillotherwiseredundantlyreconsiderthesamervaluesandcycles.
100200300400500NumberofstealableBTC200400600800Numberofvuln.
addrs.
Fig.
2.
NumberofstealableBitcoins+numberofvulnerableBitcoinaddressesattributedtoECDSAnoncereuseovertime.
Usingthismethodology,wemanagedtoleak892outofthe1,550possiblenonces(57.
55%)and2,537outofthe4,433secretkeysthatwereusedinconjunc-tionwiththesenonces(57.
23%).
Intotal,thisgivesustheoreticalcontroloverthebalancesof5,074addresses,i.
e.
,twoaddressesperkey.
Duringthiswholeoperationweidentied23cyclesinthegraphandthelongestcycleconsistedof12nodes,whichrepresentsasystemof12linearequationsand12unknowns(6nonces+6secretkeys).
ThenalshapeofGdidnotcontainanymorecycles,whichmeansthatwehaveleakedthemaximumnumberofsecrets.
Figure2depictsthenumberofBitcoinsthatanattackercouldhavestolenatanypointintime,i.
e.
,theblockheight,aswellasthenumberofvulnerableaddressesateachmomentintime.
Weconsideranaddressatacertainblock636M.
BrengelandC.
Rossowvulnerableifwehaveleakedthekeyoftheaddressandifitheldabalanceatthatblock.
ThereareafewnotablespikesforboththenumberofstealableBit-coinsaswellasthenumberofvulnerableaddresses.
Therstsignicantspikeoccursroughlybetweenblock221,000andblock227,000,wherethepeaksteal-ablebalanceis533.
82BTC.
Interestingly,therewasonlyonevulnerableaddressduringthisspike.
Thenextspikeoccursroughlybetweenblock296,000andblock298,000withapeakstealablebalanceof20BTC,whichwasstealableforatimes-panof3blocksfromblock297283untilblock297285.
Fromblock297,261uptoblock297,304therewere90vulnerableaddresses,whichisalsothemaximumnumberofvulnerableaddressesofthespike.
Thenextspikeisslightlyshorterandhappensataroundblock333,300andlastsroughlyuntilblock333,600.
Duringthistimespan,anattackercouldhavestolenupto266.
73BTCatblock333,387andtherewere290peakvulnerableaddressesatblock333,393.
Thisisfollowedbytwosimilarlylong-lastingspikesbetweenblocks365,000and366,000andblocks374,000and375,000.
Intheformercase,11.
21BTCwasstealableandtherewere131vulnerableaddressesatsomepoint,andinthelattercase15.
41BTCwasstealableandtherewere769vulnerableaddressesfromblock374,386to374,386.
Thisisalsothelargestnumberofaddressesthatwerevulnerableatatimeoverthewholetimespan.
Finally,whilethenumberofvulnerableaddressessuddenlyjumpsto289atblock475,963,thereareonly0.
0064BTCstealableatthepeak.
Atthecurrentstateofourcopyoftheblockchain,thereare5vulner-ableaddressesholdinganaccumulatedbalanceof4002satoshis,i.
e.
,0.
00004002BTC,whichisunlikelytobestolengivencurrenttransactionfees.
0.
00.
20.
40.
60.
81.
0Balancethreshold360370380390400410StealableBTCFig.
3.
NumberofBitcoinsanattackercouldhavestolenbasedonabalancethreshold.
Toassesshowmuchanattackercouldhavestolenovertime,weconsidertwoscenarios.
First,weassumeanattackerwhichstealsthepeakbalanceofeachaddressovertime.
Thatis,wetakethesumofthepeakbalancesofeachaddress,whichgivesatotalof1021.
58BTC.
Here,weimplicitlyassumethattheownernoticesthefraudandthereforeweignoreallfuturefunds.
However,thisattackmodelrequiresanattackertoknowthepeakbalanceinadvance,IdentifyingKeyLeakageofBitcoinUsers637whichisunrealistic.
Therefore,weconsiderasecondmorerealisticattackingscenarioinwhichanattackerdenesabalancethreshold.
Inthissetting,anattackeronlystealsabalanceifitisequaltoorlargerthanandweassumeagainthatwecanonlystealoncefromanaddress.
Figure3plotsthenumberofBitcoinsthatanattackercouldhavestoleninthisscenariodependingon.
Weletrangebetween0and1BTCwith0.
001increments.
Theoptimalbalancethresholdaccordingtotheplottedfunctionis=0.
125,whichanattackercouldhaveusedtosteal412.
80BTC.
Notethateventhoughoneaddressalonehadabalanceof533.
82BTCatsomepoint,itdoesnotmeanthatanattackerinthissettingcanstealitcompletely.
Thisisbecauseweassumethatwecanstealonlyoncefromanaddressonceitsbalancesurpassesthebalancethreshold,afterwhichweconservativelyassumethattheowneroftheaddressbecomesawareoftheproblem.
Whilethismeansthatchoosingalargesuchas=500BTCwouldyieldalargerprotfortheattacker,webelievethatitisnotanoptimalchoice.
GiventhecurrentvalueofBitcoin,webelievethatitisunrealisticforasingleindividualtoholdsuchalargebalance.
Additionally,ifweassumethattherearemultiplecompetingattackers,thenwealsohavetotakethisintoconsiderationwhenchoosing.
Wethereforeletrangebetween0and1BTCaswebelievethatthisisagoodcompromisebetweenwhatiscurrentlypracticalandwhatisoptimalintheory.
Aftersaidoptimum,thenumberofBTCstartstodecreasesteeply,andfor=1,thereare359.
04stealableBitcoins,i.
e.
,13.
02%lessthanintheoptimalcase.
SimilartoourpreviousOSINTanalysisinSect.
3.
2,wealsoignoredtransactionfeeshereduetotheirnegligibleimpact.
Additionally,wealsodidnotconsiderblockingtransactionsinthiscase,asanattackermonitoringtransactionscancreatestealingtransactionsassoonaspossible.
4.
6IdentifyingPastAttacksGiventhatthephenomenonofECDSAnoncereuseisaknownproblem,wenowtrytoassessifithasbeenusedbyattackersinthepasttostealBitcoins.
Todothis,wetriedtoidentifyforeachofthe7spikesinFig.
2themomentintimewhenthenumberofstealableBitcoinssuddenlydropped.
Thenwetriedtondtransactions,whichwerecreatedduringthattimeandwhoseoutputsreferencedinputsofmanyvulnerableaddresses.
Inthecaseoftherstspike,itishardtoarguewhetheritwasusedbyanattackerasonly1addresswasvulnerableinthistimespan.
However,weidentiedseveralcaseswherethebalanceoftheaddresssuddenlydroppedbyover99.
99%,whichonecouldargueisanincidentwhereBitcoinshavebeenstolen.
Inthesecond,third,sixthandseventhspikewefoundcaseswherethenumberofstealableBitcoinsdecreasedsuddenlyandweidentiedinallcasesasingletransactionsreferencingalltheresponsiblevulnerableaddresses,whichmakesusbelievethatBitcoinswerestolen.
Inthecaseofthelastspike,however,only0.
00064BTCwerestolen.
Regardingthefourthandfthspike,wedidnotobserveasimilarsuspi-ciousdropregardingthenumberofBitcoins,butonlyregardingthenumberofvulnerableaddresses.
Toseethedierence,considerFig.
4,whichshowsandcomparesazoomedinviewofthesecondandthefthspike.
Intheformer,we638M.
BrengelandC.
Rossow296000296500297000297500298000Block0102030405060NumberofstealableBTC020406080Numberofvuln.
addrs.
373800374000374200374400374600374800375000375200Block0246810121416NumberofstealableBTC05101520Numberofvuln.
addrs.
Fig.
4.
ComparisonofaspikewhereBitcoinsmighthavebeenstolenduetoasuddendropinstealableBitcoins(left)andacasewhereweseeasmoothdecreaseindicatingthatnocoinsmighthavebeenstolen(right).
canseeasuddendropinthenumberofstealableBitcoins,i.
e.
,whilethereare7.
49stealableBTCatblock297,304,thereareonly0.
2BTCstealableatblock297,305.
WeidentiedasingletransactionwhichtransferredallthestealableBitcoins,indicatingatheft.
Thefactthatthenumberofvulnerableaddressesdidnotdecreaseto0atthesametimecanbeexplainedbyvariousreasons.
Forinstance,itcouldbepossiblethattheattackerwasnotawareoftheremainingvulnerableaddresses.
Or,itcouldbethecasethattheattackerusedabalancethresholdanddeterminedthattheremainingaddressesarenotworthstealingfrombasedonthisthreshold,becauseaswecansee,the0.
2BTCaresharedamong86vulnerableaddresses.
InthesecondspikeinFig.
4,weobserveasmoothandmonotonedecreaseovertimeregardingthenumberofstealableBitcoinsandthenasuddendecreaseofthenumberofvulnerableaddressesatthesametimethestealableBTCdrop.
Thisphenomenoncouldbeexplainedbythefactthatalltheaddressesbelongtothesameindividualandthatattheendalltheso-calledchangeaddressesareemptiedbythewallet.
Changeaddressesareaddresseswhichareusedtoaccumulateleftovertransactionoutputs.
Forexample,ifanaddressAwantstosend1BTCtoanaddressBusingasingleoutput,whichisworth5BTC,thentheresultingtransactionwillcreatetwooutputs,onethatisworth1BTCandcanbespentbyaddressBandonethatisworth4BTCandcanbespentbyachangeaddressthatbelongstotheownerofA.
Thenaltransactionofthewalletwillthenuseallaccumulatedoutputsofthechangeaddresses,whichcouldbeanexplanationforthesuddendrop.
5DiscussionInthissection,wewillconsidertheethicalaspectsofourworkanddescribehowtheproblemofkeyleakageofcryptocurrenciescanbetackled.
IdentifyingKeyLeakageofBitcoinUsers6395.
1EthicalConsiderationsGiventhatwesystematicallydescribehowattackerscanstealBitcoinsabusingleakedkeys,wehavetoaddresstheethicalaspectsthatcomealongwithsuchawork.
Ontheonehand,webelievethatraisingawarenessoftheseattackvectorsisfundamentalandimportanttoimprovethesecurityofthecryptocurrencyecosystem.
Ontheotherhand,onecouldarguethattheamountofdetailweputintooutliningthesemethodsisnotbenecialasitallowsforeasyreproducibilitybyattackers.
Yetwebelievethatthisistherightwaytotacklethisproblemas"securitybyobscurity"hasproveninthepasttobeaninsucientmeansintheareaofsecurity.
WealsonotethatECDSAnoncereuseisknowntobeaproblemandithasbeenreportedinforumpoststhatthisphenomenonhasoccurredintheBitcoinblockchain[5–7].
However,aswehaveshowninSect.
4.
4,thisapparentlyknownproblemstillregularlyoccursandisabusedbyattackers,withthelatestcaseofnoncereuseappearinginablockminedon2017-07-15.
Thisconstantrecurrenceleadsustobelievethatitwillhappenagain,unlessweemphasizethisproblembetter,whichiswhyweoutlinetheattackindetail.
Anotherethicalaspectofdealingwithattacksoncryptocurrenciesisthataresponsibledisclosureprocessintermsofnotifyingthevictimsisnottrivial.
AfundamentaldownsidehereisthatBitcoinitselfisdecentralizedbydesignandintendstoensuretheanonymity(orpseudonymity)ofthepeers.
Thismeansthat(i)wehavenodedicatedpointofcontact,whichwecouldinformaboutourndingsand(ii)wecannotreachouttothelegitimateownersofthevulnerableaddresses.
Wetriedtohandlethisproblemasresponsiblyaspossibleandrefrainfromdisclosingproblematicaddressesand/ortransactions.
Forexample,wedidnotmentionanyvulnerableaddressesorURLstopastescontainingthem,aswecannotbesurethattheownersofthoseaddressesareawareofthevulnerability.
WhileanattackercanreproduceourmethodologytondanyfuturevulnerableaddressesusingPastebin,itshouldnotbeeasilypossibletondtheaddresseswehavediscovered,sincethePastebinfeedonlyliststhemostcurrent250pastes.
WhilePastebincanbesearchedusingstandardsearchengineslikeGoogle,itshouldbeveryhardtodiscoverthepasteswehavefound,sincesearchenginesonlyoerakeyword-basedsearch,ratherthanaregex-basedsearchwhichwouldberequiredtondtheaddresses.
InourECDSAcasestudy,wealsodidnotmentionanyvulnerableaddresses.
However,anattackercanfullyreproduceourresultshere,astheBitcoinblockchaincontainsallthenecessaryhistoricalinformation.
Therefore,notmentioningvulnerableaddressesisnotaseectiveasinthecaseofourOSINTcasestudy.
Yetwealsodonotseeareasontodoso,asonecouldarguethatthismakesittooeasyforanattacker.
5.
2CountermeasuresExplicitlyleakingkeysisnotstrictlyatechnicalproblem,asusersseeminglypub-lishprivateinformationwithoutknowingtheconsequencesofdoingso.
However,therearesometechnicalsolutionsthatcouldbeappliedonOSINTplatforms.
Forexample,Pastebincouldincludeacheckintheirlogic,whichscanspastesfor640M.
BrengelandC.
RossowsecretssuchasBitcoinsecretkeysencodedintheWIFformat.
Infact,theycouldprovideimmediatefeedbacktousersaboutthesecurityimplicationsofpastingsuchcontent.
WehavethereforecontactedPastebinwithadetaileddescriptionofourwork,proposingtoadoptsuchamethodology.
ToavoidECDSAnoncereuse,thereareafewsolutionsthatcanbeapplied.
OnesuchsolutionproposedbyRFC6979[19]istochoosethenoncekdetermin-isticallybasedonthemessagemandthekeysk.
Asinputsdier,thisschemeprovidesuniquenoncesandhardensagainstnoncereuse.
However,sincethissolutionisbackwards-compatiblewiththeexistingECDSAscheme,italsomeansthatpeersdonothavetofollowthisproposal.
Inparticular,onecannotverifythatasignaturehasbeencreatedwiththedeterministicnoncechoiceasproposedbyRFC6979.
Anotherwayofdealingwiththisproblemistoincorporateadupli-catenoncecheckintotheBitcoinprotocol.
Forexample,acheckforduplicatervaluescouldbeincorporatedintothetransactionvericationprocess.
Eachpeerverieseachtransactionofablock,whichincludesverifyingthesignatureandothersanitychecks.
Here,theprotocolcouldalsosupportacheckforduplicatervalues,i.
e.
,checking,foreachrvalueofeachsignature,ifitalreadyoccursintheblockchain.
Fromaperformanceperspective,aBloomltercouldhelptoscalethisprocess.
Themorepeersfollowthis,thelesslikelyitwillbecomethatatransactioncontainingaduplicatervaluewillbeaddedtotheblockchain.
However,anattackermonitoringthemempoolinsteadoftheblockchainmightstillbeabletoobservetransactionscontainingduplicatervalues.
Therefore,onewouldneedtoadditionallyadaptthenetworkrulessuchthatanewruleisadded,whichdiscouragesthedistributionoftransactionswhichcontaindupli-catenonces.
Ifsuchatransactionreachesapeerwhichfollowsthisnewsetofrules,theduplicatervaluewillbedetectedandthetransactionwillnotberelayedfurther.
Additionally,thepeersendingthetransactionshouldbenotiedwithanerrormessageabouttheproblemtocreateawareness.
Themorepeersfollowthisnewsetofrules,thelesslikelyitbecomesthattransactionscontain-ingduplicatervaluesaredistributedamongthenetwork.
Intotal,webelievethattheadoptionofallproposals,i.
e.
,deterministicECDSAandadaptingthenetworkrulesaswellasthetransactionvericationprocess,aresucientmeanstoeliminatenoncereusefromcryptocurrencies.
6RelatedWorkInthissectionwediscussotherworkintheareasofOSINT,BitcoinkeyleakageandECDSAnoncereuse,andhowtheyrelatetoourwork.
OSINThasbeenappliedbeforetoexposeorharvestprivacy-relatedinforma-tion.
Maticetal.
[16]performedastudyinwhichtheymonitoredthePastebinfeedbetweenlate2011andearly2012todevelopaframeworkfordetectingsensitiveinformationinpastes.
Theydiscoveredalmost200,000compromisedaccountsofseveralwebsitesaswellaslistsofcompromisedserversorleakeddatabasedumps.
Inaslightlydierentvein,Sabottkeetal.
[20]designaTwitter-basedexploitdetectorthatcanpredictvulnerabilitiessuchascodeexecutionorIdentifyingKeyLeakageofBitcoinUsers641Denial-of-Serviceattackssolelybasedontweets.
Similarly,Zhuetal.
[24]showhowtheycanuseacademicsecurityliteratureasOSINTtoautomaticallyengi-neerfeaturesformalwaredetection.
WhilealloftheseworksshowthepotentialofOSINT,theyareonlyremotelyrelatedtoourworkasourusecaseisdierent.
IntermsofleakingBitcoinsecretstostealmoney,therehavebeenafewotherpaperstargetingthisproblem.
Vaseketal.
[22]haveoutlinedhowonecanattackpassphrase-basedwallets(brainwallets).
TheauthorsdevelopedatoolcalledBrainayer,whichusesbruteforceandadictionarytogenerateweakpassphrases,whichwouldhaveallowedanattackertostealBitcoinsworth$100,000atthattime.
Thisapproachissimilartooursinthesensethatanattackerexploitsthefactthatuserstreatsensitiveinformationwrongly,i.
e.
,passphrasesinthecaseofBrainayerandsecretkeysornoncesinourcase.
Incontrasttosearchingforweakpassphrases,weharvestOSINTandcryptographicprimitives.
MorerelatedareworksbyCastelluccietal.
[10]andValsorda[21],whichbothconsiderECDSAnoncereusewithrespecttoBitcoin.
However,bothonlycoverthebasiccase,whereanonceisusedinconjunctionwiththesamekeytwice.
Wegeneralizethisconcepttosystemsoflinearequationsandsystem-aticallyoutlinehowanattackercanuseagraph-basedapproachtoleaksecrets.
ThegeneralproblemofnoncereuseinrespecttoECDSA(orthecloselyrelatedDSAscheme)hasbeenstudiedinothercontexts.
Anotableincidentoccurredin2010,whenitwasdiscoveredthatSonyreusedthesamenoncetosignsoftwareforthePlayStation3gameconsole[8].
Furthermore,Heningeretal.
[14]studiedtheimpactofweakkeysandnoncereuseinthecaseofTLSandSSHservers.
Theauthorscollectedover9millionsignaturesandfoundthat0.
05%ofthesesignaturescontainedthesamervalueasatleastoneothersignature.
Additionally,theauthorsusedasubsetofthosesignatureswhereakeyandanonceappearinconjunctionatleasttwicetoleak281secretkeys.
Apartfromstudyingadierentusecase,i.
e.
,Bitcoin,ourworkisdierenthereinthatwesystematicallyoutlinehowanattackercanleakkeys,whichgoesbeyondthesimplecasewherethesamekeyandnonceisusedmorethanonce.
7ConclusionWehavestudiedtheproblemofimplicitandexplicitkeyleakageinthecontextofcryptocurrencies,whichshowshowanattackercanleverageOSINTorduplicatenoncestoleaksecretkeys.
Ourcasestudieshaveshownthepracticalrelevanceoftheseissues.
AnattackermonitoringPastebinorscanningtransactionsfornoncereusecouldhavestolenupto22.
40BTCand412.
80BTC,respectively.
Ourworkemphasizesaspectsthatareimportantforboththeusersandthedevelopersofcryptocurrencies.
Forinstance,ourPastebincasestudyshowstheimportanceofmakingusersawareofhowtodealwithcryptocurrencysecrets.
OurresultsregardingECDSAshowthatnoncereuseisarecurringproblemandhighlightthebenetsofincorporatingcountermeasuresontheprotocollevel.
Inthecasethatcryptocurrenciesbecomeevenmorepopular,itwillbecomemorelucrativeformiscreantstoperformkeyleakageattackssimilartotheoneswe642M.
BrengelandC.
Rossowdescribedhere.
Thishighlightstheimportanceofourresearch,whichapartfromcreatingawarenessoftheproblem,alsocanfosterfutureresearchonthetopicofexplicitandimplicitkeyleakageinthecontextofcryptocurrencies.
Acknowledgement.
ThisworkwassupportedbytheEuropeanUnion'sHorizon2020researchandinnovationprogramme,RAMSES,undergrantagreementNo.
700326.
References1.
https://coinmarketcap.
com/currencies/bitcoin/.
Accessed27Mar20182.
https://coinmarketcap.
com/currencies/ethereum/.
Accessed27Mar20183.
https://pastebin.
com.
Accessed27Mar20184.
https://bitcoin.
org/en/alert/2013-08-11-android.
Accessed27Mar20185.
https://bitcointalk.
org/index.
phptopic=581411.
0.
Accessed27Mar20186.
https://bitcointalk.
org/index.
phptopic=1118704.
0.
Accessed27Mar20187.
https://bitcointalk.
org/index.
phptopic=1431060.
0.
Accessed27Mar20188.
https://events.
ccc.
de/congress/2010/Fahrplan/attachments/178027c3consolehacking2010.
pdf(2010).
Accessed27Mar20189.
Back,A.
:Hashcash-adenialofservicecounter-measure(2002)10.
Castellucci,R.
,Valsorda,F.
:StealingBitcoinwithMath.
https://news.
webamooz.
com/wp-content/uploads/bot/osecmag/151.
pdf.
Accessed27Mar201811.
Decker,C.
,Wattenhofer,R.
:BitcointransactionmalleabilityandMtGox.
In:ProceedingsoftheEuropeanSymposiumonResearchinComputerSecurity(ESORICS)(2014)12.
Die,W.
,Hellman,M.
:Newdirectionsincryptography.
IEEETrans.
Inf.
Theory22,644–654(1976)13.
Eskandari,S.
,Barrera,D.
,Stobert,E.
,Clark,J.
:Arstlookattheusabilityofbitcoinkeymanagement.
In:ProceedingsoftheWorkshoponUsableSecurity(USEC)(2015)14.
Heninger,N.
,Durumeric,Z.
,Wustrow,E.
,Halderman,J.
A.
:MiningyourPsandQs:detectionofwidespreadweakkeysinnetworkdevices.
In:ProceedingsoftheUSENIXSecuritySymposium(USENIXSecurity)(2012)15.
Koblitz,N.
:Ellipticcurvecryptosystems.
Math.
Comput.
48,203–209(1987)16.
Matic,S.
,Fattori,A.
,Bruschi,D.
,Cavallaro,L.
:Peeringintothemuddywatersofpastebin.
ERCIMNews(2012)17.
Nakamoto,S.
:Bitcoin:apeer-to-peerelectroniccashsystem(2008)18.
Naware,A.
M.
:Bitcoins,itsadvantagesandsecuritythreats.
Int.
J.
Adv.
Res.
Comput.
Eng.
Technol.
(IJARCET)5,1732–1735(2016)19.
Pornin,T.
:Deterministicusageofthedigitalsignaturealgorithm(DSA)andellip-ticcurvedigitalsignaturealgorithm(ECDSA)(2013).
https://rfc-editor.
org/rfc/rfc6979.
txt20.
Sabottke,C.
,Suciu,O.
,Dumitras,T.
:Vulnerabilitydisclosureintheageofsocialmedia:exploitingTwitterforpredictingreal-worldexploits.
In:ProceedingsoftheUSENIXSecuritySymposium(USENIXSecurity)(2015)21.
Valsorda,F.
:ExploitingECDSAfailuresinthebitcoinblockchain.
In:ProceedingsofHackInTheBox(HITB)(2014)22.
Vasek,M.
,Bonneau,J.
,Castellucci,R.
,Keith,C.
,Moore,T.
:Thebitcoinbraindrain:examiningtheuseandabuseofbitcoinbrainwallets.
In:Grossklags,J.
,Preneel,B.
(eds.
)FC2016.
LNCS,vol.
9603,pp.
609–618.
Springer,Heidelberg(2017).
https://doi.
org/10.
1007/978-3-662-54970-436IdentifyingKeyLeakageofBitcoinUsers64323.
Wood,G.
:Ethereum:anext-generationsmartcontractanddecentralizedapplicationplatform(2018).
https://ethereum.
github.
io/yellowpaper/paper.
pdf.
Accessed27Mar201824.
Zhu,Z.
,Dumitras,T.
:FeatureSmith:automaticallyengineeringfeaturesformal-waredetectionbyminingthesecurityliterature.
In:ProceedingsoftheConferenceonComputerandCommunicationsSecurity(CCS)(2016)OpenAccessThischapterislicensedunderthetermsoftheCreativeCommonsAttribution4.
0InternationalLicense(http://creativecommons.
org/licenses/by/4.
0/),whichpermitsuse,sharing,adaptation,distributionandreproductioninanymediumorformat,aslongasyougiveappropriatecredittotheoriginalauthor(s)andthesource,providealinktotheCreativeCommonslicenseandindicateifchangesweremade.
Theimagesorotherthirdpartymaterialinthischapterareincludedinthechapter'sCreativeCommonslicense,unlessindicatedotherwiseinacreditlinetothematerial.
Ifmaterialisnotincludedinthechapter'sCreativeCommonslicenseandyourintendeduseisnotpermittedbystatutoryregulationorexceedsthepermitteduse,youwillneedtoobtainpermissiondirectlyfromthecopyrightholder.