G1234! - Optimizations for Bitcoin Key Cracking

our speaker is Ryan Costello gee thanks so these slides are live now if anybody wants to follow along and the video will go up whenever b-sides releases it that's probably gonna be three or four weeks so at Def Con 23 two years ago I gave a talk called cracking cryptocurrency brain wallets as part of this talk I released a tool called brain flare which cracks Bitcoin private keys that were generated by using sha-256 of a password or passphrase this this found a rather shocking amount of stuff but that's not really what this talks about directly what I want to talk to you today about is how to make this really fast and how to make it even faster for

some other types of weak keys so since since Def Con 23 I have added a bunch of new modes to brain flare special case optimizations I added support for a bunch of hardened algorithms it has a theory M support now beta script hash supports raw private key input so that you can write external tools that generate keys and feed that in you can feed raw beta script hash scripts in there and bitcoins gotten a little bigger so the bloom filter has actual false positives now so there's a feature for making sure that those false positives are caught in ignored so let's talk a little bit about Bitcoin keys Bitcoin uses of the elliptic curve digital signature algorithm with curve

parameters called SEC P 256 K 1 this is from standards from standards for efficient cryptography which is a document that sort of come put out a while ago that standardized a bunch of elliptic curve parameters the P stands for prime fields 256 it's a 256 bit field and K is Colpitts type of curve and I don't actually know how that is special but bitcoin is the only application that widely uses one of these curves with this curve you have points represented on a curve that satisfy the equation y squared equals x cubed plus seven in a finite field over a large prime it's slightly larger than to the 256 and then private keys are integers

in a different finite field you don't need to know that number really and then public keys are formed by multiplying a private key with what's known as the base point this is the also the point that you get for a private key with integer value 1 and if you want to go from public key to private key you need to have an algorithm that can efficiently find the discrete logarithm this is supposed to be very hard without a quantum computer to run Shor's algorithm on there's some stuff in Bitcoin that makes it so that this is a limited risk even if somebody does have a big quantum computer and wants to crack Bitcoin I don't have time to go

super into detail on how I looked at carefully cover key works there's a paper linked at the bottom of this slide that you can read this is what bitcoins curve looks like plotted over real numbers it's actually run over a finite field so it looks like noise but this will be important in a minute for key generation you can basically just generate an arbitrary 256 doubt without value and it'll work 32 random bytes it works fine unless with most software unless you choose 0 or n which is that long number that ends in 4141 hacks this makes it really easy for people to write applications that generate keys with weak randomness or do clever things like brain wallets Bitcoin

uses something called Bitcoin script when you send a payment in Bitcoin you were sending a payment to whoever can redeem a program whoever can provide inputs to a program written in the Bitcoin scripting language that makes it return true there's a couple of really common scripts that are used Bitcoin has addresses to represent these you have the addresses starting with one that just represent payment to a hash of a public key this ripe AMD 160 of a sha 256 of some value it's what Bitcoin calls hash 160 this is interesting because if you pay to one of these addresses and the recipient never reuses it even if quantum computers are around the public key isn't revealed until it's

spent so unless the quantum computer can crack it in about an hour it'll still be okay this is also paid a script hash where you are sending to a hash of a script don't worry too much about that if there am uses the least significant bits of the output of KISS check which is the hash algorithm that became sha-3 with slightly different initialization parameters because if there iam was released a little bit just as that was being standardized and Bitcoin actually has two different representations of public keys there's uncompressed which has both the X&Y coordinate and compressed which has the x coordinate and a header byte that indicates whether it was even or odd which is equivalent

to indicating whether it was positive or negative if you recall the graph you saw that it had two points at each x-value so you need to yeah you need to know whether it's the top or bottom point on the curve but once you know that you can compute the Y value I have a lot of general optimizations in brain flare most of it is pretty boring standard C optimization minimize memory copies inline functions allocate all of the memory at startup because now it is slow statically initialized buffers for values that don't change much or that are partially used I decided I wouldn't bother implementing any sort of threatening because message passing is a pain in the

ass so to make sure it was still efficient there's external data files you load in that have for various purposes and those get mapped with shared memory which if you run this on Linux will ensure all processes trying to access that file just get pointed at the same chunk of memory so you can run however many copies they're all loading 20 gigs of files into RAM but it takes 20 gigs regardless of how many copies you run shot 256 for brain wallets is important it's also used in anything that's looking at Bitcoin addresses so Intel put out a bunch of assembly implementations of sha-256 using instruction set extensions on Intel processors there's actual sha-256 instructions on some of the newer

processors and then there's the avx2 AVX and ssse3 instruction sets which are also faster and there's fallback to see implementation only the transform function is implemented and you can't incrementally fill in the hash because none of the stuff the brain player doesn't need to do that I would love to find optimized versions of ripe NP 160 and sha 3 check that I have not yet so hash padding hopefully some of you know how hash padding works but in short you have your data you follow it with a 1 bit and a bunch of 0 bits and then the length of the input of the hash this is so that if you have two similar values

that differ only in that they have a bunch of nulls at the end of them you get different hash values so there's a bunch of static buffers in brain flavor that have that all computed already and then to speed things a little more sha-256 output is written directly into the precomputed buffers for right Humpty 160 so no copying is required there here's what one of those buffers looks like for write MD 160 which is little-endian whereas Schatzi 56 is big and which is kind of annoying and then here's what this looks like in use and then here's one where it's doing hash 160 supporting and arbitrary length but the caller has to take care of all

of the padding and then here's what that looks like with a compressed public key you get the you have padding and you put the hat the public key in there and you feed it into this and it works great other fun things you can attack multiple cryptocurrencies at once if you if you want to do that you need to post process them because there's nothing in the data structure that will indicate which cryptocurrency it came from but I've played around with getting addressed dumps for a hundred random all coins and feeding them all and together it works perfectly fine if you have ones that use different public or different address formats like aetherium you can still do that you can reuse the

public key computations but if you wanted to do say brain wallets on aetherium aetherium nobody really used shot 256 they used to kiss check instead so the public keys you calculate aren't going to be helpful but if you wanted to say search for keys matching a bad random number generator you could do that if you wanted to incremental e search for all the keys starting with 1 you could do that too and so as far as public keys go brain flares got a flag that lets you specify which transforms you want these are storage function pointers with the type identifier uncompressed here's an example this is I'm compare key it's just hashing the public key for

compressed public key there's a little bit of bit twiddling to extract out whether why was caught where why whether why was even or odd and again just gets fed into the hash Assyrian uses Scheck instead we take the last 160 digits that's the address the other one is truncated x coordinates which are interesting if you want to look at the signature nonces a bitcoin signature has as inputs a nonce value which must not be reused otherwise bad stuff and the private key the essentially the x-coordinate of a public key created using the nonce as the private key is one component of the signature and then there's another component and don't worry about it too much then if you want to look for pay

descript hash stuff you can do that really is that is that a driller we're getting out okay [Music] [Applause]

great carry on here all right before we get into some of the nastier bits here let's I wanted to briefly mention that there are some pretty serious differences in speed between the different operations you can do on on an elliptic curve adding two field elements super fast multiplying two field elements pretty fast doubling a point fast adding two points together it's alright inverting a field element kind of slow multiplying an integer by a point which is deriving a public key that's about the slowest part so let's talk about point multiplication the naive method is just too with its this is if you can read that great but otherwise I just want to make sure it is yeah we I yeah screens gonna

flicker I guess sorry right so you start out with the base point you add it to an accumulator if your bit is one double its its the next bit is one you add again and so forth this is pretty standard but this can be made a lot faster with a partial pre-computation again here's here's what that looks like in in a academic paper and here's what I came up with after staring at the explanation in the paper and the code for a while you set up a 2d array of points you fill the 0th column with the points for 0 through 2 to the n minus 1 the 0 point is not actually the 0 point it's the

infinity points but when you add it to something you don't change the value I I don't know why this is but it works and then you fill out the rest of the row by multiplying it out as necessary so this turns your your point multiplied into basically a bunch of lookups and adds memory usage is about as you would expect the code I've currently got takes 88 bytes per entry so that's that's that and this is limited in large part by Ram speed rather than CPU speed because you're gonna be missing every cache you're gonna be missing the cache every time lib SEC P 256 K 1 which is the elliptic curve library for this curve

that was written by a bunch of the Bitcoin people does this already with a four bit window which which is fine it only takes up a little bit of memory brain flare when it starts up does a 16-bit window which is significantly faster most of my actual testing I do with a 24-bit window which takes about 6 16 gigs of RAM and yields a 2.5 X feet up bigger windows use more ram you quickly hit diminishing returns there's a paper - about how this works and a grad student named song at University College London wrote this code for me and I integrated in this brain flare and you can read the paper there ok so next thing is a fine versus

Jacobian coordinates a fine is the simple XY representation of a point Jacobian adds the Z value and uses this Z value to do tricky things that make the math faster this is all well and good but the Z value does not stay 1 and so when you want to convert you have to divide and well dividing in finite fields is actually kind of tricky let's I'm gonna go very quickly through these slides because we were interrupted and it's not super important so 1 plus 1 is 2 2 plus 2 is 4 3 plus 3 is 1 because modular arithmetic if you want to look up finite field arithmetic or modular arithmetic please do so I don't have

time to explain it the tricky part is division so the way we do envision division is instead we multiply it by the reciprocal or as it's generally called when doing this sort of math the inverse the multiplicative inverse so given if you want to divide you don't if you want to divide or if you want the inverse of X given X you find Y so that X times y equals 1 so in our five by in our five elements toy field this is the table and don't divide by zero because that's bad here's some examples so to convert our Jacobian coordinates back to a fine we need to do division to do division we need to find

the inverse of the Z value finding the inverse is very slow but we can cheat with algebra so instead we take a bunch of Z values we batch them together and we do one inversion for the entire group plus three multiplications per Z this is a lot faster in brainwallet mode it's a 1.7 X feet up if you're doing incremental mode it's actually 16 X speed-up so very much worth doing it took me a while to understand this very well but some here's here's a quick example so we have four values we're batching we multiply them together keeping keeping each progressive one because we'll need them in a moment then we calculates one inverse of our

last value then we know that's like that slightly messed up that three is supposed to be at the end of the first line I don't know how that happened so now we cancel some stuff out so we want the inverse of Z 3 so we take Z zero times Z 1 times the zoo and divide it by the inverse of Z zero Z 1 Z 2 Z 3 and everything except for the 1 over Z 3 cancels out then we cancel out the Z 3 term in our temporary variable and then we repeat this to get all of the inverses right helpful other thing that we can do to make things faster is just not give a

about side channels older versions of the library didn't put much effort into avoiding side channels because nobody was supposed to use it for anything real and then they went back later and fixed all of this stuff up so I just use the old version that is faster but completely unsafe to use for any real work so on my to-do list is to actually implement all of the all of the algorithms that I can't implement in timings unsafe ways to make things faster can also do some special cases brain flares got an incremental mode which takes advantage of the fact that key pairs are hormone Norfolk for addition but what that means is if we take the pub key of if we take the pub

key of the sum of two private keys that's the same as the sum of the public keys of those two private keys and adding public points together is much faster so if we want to go through one of them instead of incrementing the private key computing a new public key we compute a starting private key and then we take the equivalent public key for one and just add it over and over again really fast and then the most recent fun thing that I did was keys from a byte stream so if you've got a shitty random number generator say say somebody decided that a good way to generate random Keys was to use the JavaScript math dot random function and

turn it into a byte and call that 32 times well if you wrote something to generate that key stream you could feed it in this way it's about twice as fast as feeding in raw raw private keys the way this works is we built two tables one for subtracting the most significant bytes and then another for adding the least significant and we go through subtract and subtract the most significant byte multiplied by 256 by doubling eight times there's a morph is slightly more efficient way to do this where I can just multiply by 256 but it's a pretty marginal improvement and I haven't had time and then we once we've done that we can add in the new

byte there is a bunch of tricky special cases that have to be done for this there's some invalid private keys that if you're say doing a forensic search of Bitcoin keys from a ram dump or a harddrive dump you'll get lots of strings of zeros which are invalid keys so that has to be detected and fix-ups must be done or if you get all one bits that's it's a little weird and you can't keep adding like this but it's not really a big deal I actually found some really weird things dumping my hard drive into this there's a lot a lot of random Linux binaries that have sha-256 is of random strings embedded in them

for some reason also for some reason a sha-256 of some default picture that comes with Windows 7 was in there I have no idea why that was there either I have I have some more examples that I will go through at the talk I'm giving with Murray later where we analyze terrible brain wallets and the people who steal from them anyway so this is a little easier to understand with an example perhaps so here's a starting key just ignore the fact that this is not the right size and is only one value just pretend that this pretend that this has a corresponding the public point okay so we have the value we subtract off the

top byte we multiply by 250 add in the new bottom bite and then do this again over and over again speaking through whatever it is you're looking at so in order to do searching brain flare uses a bloom filter there's there's a couple hundred million addresses that have been used in Bitcoin since the beginning of time bloom filter is the data structure that allows you to check for set membership efficiency our set membership efficiently as long as you're okay with the occasional false positive it's pretty quick the way this works is you have you have hashes of some input value that are used to turn on a bit in a large bitmap and then to check you

just check and see if all of the bits that correspond to your input are already said and if so you have a hit or maybe a false positive and you can calculate the odds of a false positive for a given data set the thing is though we're looking at hashes of Bitcoin public keys and public keys themselves and these are pretty randomly distributed so we can just take different combinations of that and splice it together and call that a hash and that actually works fine so here's here's some ugly macros that do the whole thing in this particular the way this particular algorithm works is it takes the public key as an array of five

32-bit values there's a couple of hashes that are just taking page take one of the values and others that take certain parts of one of the values that shift them around and or them together and again this works perfectly fine except for that now Bitcoin now the Bitcoin has about I think last time I checked it was getting close to 300 million dresses since the beginning of time the the 32-bit bloom filter with twenty hashes it starts to have a lot of false positives so I am writing some new code that works around this problem which looks like this I wrote a Python script that actually generated this I didn't type all of this out by hand but I went

through and found combinations of shorts 16-bit values out of the hash value that I could combine together into a 48-bit value and the 48 bit value is nice because now I can use a bigger bloom filter and as long as the bloom filter is still a power of two all I have to do is and and ask out the extra bits that I don't want and as far as false positives go here's what it looks like today this is about a one in a thousand false positive rates so that if we're searching I think I think the current performance if I'm doing brain wallets is about on my PC is about 550,000 per second so there's 550 false positives

per second so we need an efficient way to find those and nots not spam with them so normally if you want to if you've got an array that's ordered you use a binary search right because the binary search is log in and that's pretty efficient if you don't know what a binary search is here's here's a quick walkthrough of one you seek to the middle that was too high so we'll seek to the middle of the first half that's too low so we seek to the middle of the second quarter and that's too high and then we seek to the beginning of the third eight we said this and we get a hit that's that's for operations that's

pretty good right but if you get huge huge lists of these that's that's still kind of at it at almost 300 million that's gonna give you what 18 yeah about 18 heads so instead there's another algorithm algorithm called inter and interpolation search which works really well if you have a unified distribution within your search range which tends to happen when you have a bunch of hashes so this does have the disadvantage of if somebody is able to pass you crafted inputs that are specifically designed to ruin your day you will be very very slow but as long as that doesn't happen it's log log in which instead of 18 operations would be four or five to search all nearly 300

million addresses in practice it's a little bit worse than that because there tend to be it tends to be front weighted but overall it works pretty good and so here's what that looks like oh another good way to explain it interpolation search is say you're you've got a phone book and you're looking for someone whose last name is Williams you're not gonna just look right in the middle because you know they're closer to the end so you enter that you you open the phonebook towards the end and refined from there and that's how an interpolation search works so here it's gonna estimate based on the list if we're looking for 5-1 it should maybe be it out there and the algorithm

will say oh well that's slightly too high let's try jumping back a little bit and and it gets it on to hit two two guesses instead of four okay I have a little more time than I thought so does anybody want me to revisit the finite field arithmetic and actually explain the head yeah alright that's a little quicker than I thought I was gonna get through this but um any questions I can go into detail on other stuff if people are curious get a question over there oh I also wanted to I really hope this is obvious to most people but cracking Bitcoin addresses and taking the money if it's not yours is kind of a dick move and probably

illegal although I talked to a bunch of lawyers about this and all of them had a different opinion on which law it broke so yeah let's see I had conversion trespass to chattels Computer Fraud and Abuse Act and a couple of other things but yeah if you do something and it's obviously it should be bad and you get caught you'll probably have a bad time anyway question have you thought of using minimal perfect hash functions excuse is that you yeah yeah for instead of the bloom filter it requires a lot of work yeah you should submit a patch scoob's the exact yeah I I the bloom filter works it's reasonably fast if somebody wants to give me some other code that is

faster I would be happy to accept it yes I was just curious if you had any I thought you'd have graphs showing how much you've actually sped up I understand you know the basic stuff you're describing but I was just curious what did it actually work out to be if you had you know test data yeah so I've done some benchmarks but the problem is a lot of these are mode dependent and it's and a lot of times the optimizations will you're you'll get a speed increase from the optimization but the thing you optimized may be sped up 50 times but your overall performance only went up only increased by 10 or 20% because of all this other stuff you're

doing like week that's why it's for example when I put in the assembly implementations of sha-256 and tweaked that stuff to use pre pathing and all that stuff I only got another two or three percent because the calculation time was dominated by generating the public keys so and the other thing is the the speed ups are not in isolation so like the pre computed multiplication plus the batched the batch defined conversions don't necessarily when used together have the same effect as as as you would compute from both of them in isolation if that makes any sense so yeah I don't I don't have great graphs I'm sorry so the as far as performance goes the

original cracker I wrote back in 2013 using open SSL and no tricks whatsoever did about 10,000 per second on my computer then the first version of brain flavor I wrote did 130,000 and my current code does 550,000 keys per second and this is all this is all Bitcoin with sha-256 brain while it's checking both the compressed and uncompressed version cool that would have been a real pretty graph sorry questions anyone

what's your opinion on what based Wallet generators my bid address that would tire fire yeah what's the most secure way to generate a wallet then offline or otherwise I it depends I mean it's it's the key generation is very simple you can there are tools where you roll a bunch of dice and hash the dice output and that gives you a private key that is probably reasonably safe but really random number generators are actually pretty secure you can trust them there's offline wallet tools like electrum which will give you a 128 bits seed represented as 12 words you can memorize that nobody's gonna crack that although if somebody wanted to they could certainly try it is deterministic

but yeah and and bid address which you specifically mentioned like they use decent crypto libraries to power that thing it uses browsers now have actual cryptographic number generation built into them via the get random values API that's pretty secure it also mixes it like it has you we wiggle your mouse around on the screen before generating anything and that helps to but I don't know major web browsers probably okay don't recommend but probably okay and then there's a lot of weird web browsers and I've actually even seen I think it was like it was it was some some video game console web browser I was playing around with I got two different ones to generate the same value

with the cryptographic random API so don't generate the cling keys on a game console thank you questions questions questions

hi I was just wondering um does brain flare get impacted in any weight with a bit 148 that's coming out the which bit 148 no so there's no sig would support if that's what you're asking about yeah I honestly haven't really looked into segregated with witness and cracking that I haven't seen any software that generates keys that work with segregated witness in a stupid way but I'm sure somebody will eventually figure out how to do that I tend to add stupid key generation schemes to brain flare as I find them actually when I was checking into some things to make this slide I found another one from a cerium that they did something dumb which I'm gonna implement

probably next week not all by the way not all of the not all of the stuff I've mentioned in these slides is in the version that is currently on github but I will have that out by next week there's there was an attack Iran that found a wallet that had a balance that's currently worth about $1,500 in it and I was advised not to include details on how I did that in the talk and so I am ripping that code out yeah if if anybody has a wallet with 0.64 Bitcoin in it that they generated awhile back and has my weird-ass Bitcoin address with no uppercase letters or numbers other than the leading one in there yeah you should

move your bitcoins because I'm yeah yes that that that will work wait now thank you it's a lot no sleep for either huh I get some sleep

I remember you talking a different talk about repeat k and other things yeah so brain flare can crack can crack bad nan says the K is the nonce value I briefly mentioned this but you have 256 bits value that if you reuse it you can compute the private key there were some bad wallets out there for a while that poorly generated K values which led to reuse but it's clear that there's probably other issues that could be replicated with it that could perhaps be used to break some keys but some 99% of the stuff I try to to find queues I will crack keys and then find that somebody else already ran that attack because I

think there are a bunch of dudes out there who have just decided that their job will be stealing Bitcoin from people with bad keys again I think those people are but they're they're very busy I guess and I'm sure some of them have gpu-accelerated tools that are way faster than mine that they will not release anyone else but what are your plans for future improvements so I would really like to learn how to do GPU coding and get that nice acceleration done that's the main one right now there's also as I mentioned like the incremental node is not or not incremental the key stream search mode is not completely done I want to try some silly stuff like what if I feed it

are see for with a blank key okay that actually came back up on the screen it's silly stuff like that really the bloom filter implementation needs to be replaced there's maybe something more efficient that I can do besides a bloom filter no no

how much money do you estimate you've saved from hackers that's that's really hard to to say and that's mostly the subject of the talk that Marie and I are giving I think 2 p.m. today 2 p.m. is that the one in 14 minutes that's the one at 2:00 p.m. according to the schedule how many talks are you getting just I mean it's mostly her talk I I just cracked a bunch of passwords and provided data or will there be charts in that talk yes there will be charts in that pod so everyone go to the 2 p.m. one yeah I don't know so the talk I gave at Def Con got this site brainwallet org

which was kind of infamous also because there have been allegations that the guy who ran that site was actually cracking brain wallets himself and he refused patches to improve the security of this system and really like and that was that was the site that used math dot random as key generation for a while so there were all sorts of sketchy things about that and did that got shut down for my talk and that has probably saved some people I've I've seen a few posts on reddit like oh I saw this talk I moved my knee out of brainwallet the there's also the guy I found brain wallets that clearly weren't pilfered and that's that's always interesting but some of those

were from before my talk because I was definitely not the first person in the security industry to say this was a terrible terrible idea and I'm I'm disappointed that some of those mistakes got repeated it aetherium I had a conversation with somebody I think sometime last year he had an ethereal wallet that had 46,000 ether in it which at the time that I talked to him was worth half a million dollars and currently I think if theorems about $200 a piece so as that is that eight million dollars yeah is yeah that the key was a guy brush from Monkey Island that was that was the password all lowercase i I don't even know like I feel really bad

for that guy probably what are some of your favorite passwords that you found well so there's a woodchuck on my shirt because one of the passwords I found was one of the first things I found was how much wood could a woodchuck chuck if a woodchuck could chuck wood which when I found it had 250 Bitcoin in it and I actually managed to find the owner of that and explained to him why this was a terrible idea and he was very grateful any questions yeah I was yeah we have another talk in ten minutes in this room sorry not in ten minutes okay it's at 2:00 okay so is there anybody that gave you a

bounty you told them that their wallet was insecure gave him a pointer and then they gave you a tip yes the the woodchuck guy gave me two bitcoins and I gave them to a friend as a wedding gift and I if I recall correctly he said he eventually sold them for $1,700 very nice anyone else last chance all right best practices to protect yourself from this sort of attack use the standard software and not some random dudes website that says it's totally secure because it's probably a trap I think that's pretty good general advice - yeah all right well thank you everyone yeah thank you [Applause]