>>I am Ryan Casataluche and I am
here today to talk about cracking brainwallets. A quick
disclaimer, just because someone's password is terrible
does not give you the right to steel their money. Please don't
do it. Don't blame the victim don't be a jerk. Pretending
people dont choose shitty passphrases doesnt help. So
brainwallets are not a good idea if you want to use something
that works like a brainwallet but is actually secure there is
this thing work wallet and it is a lot better and if you use it
with [indiscernible] words, it will be great. So don't use
brainwallets if you are using one please move you money out of
it. Someone lost $14,000 worth of bitcoin just last week.
Really quick overview about what a cryptocurrency is. Electronic
money using cryptography to secure it. We don't need a bank
or government to run one of these. Transfers work very
similarly to checks you sign the money over to somebody else
except for the ink on the paper it is cryptographic signatures
on the block chain. A big problem was to keep people from
spending the same money twice. The bitcoin solved this with a
public transaction log. Transfers are identified by
account. So super anonymous. Bitcoin like coin, dashcoin, at
DefCon we have DefCoin. And control of the private key, is
control of the money. A brainwallet is a little thing
built on top of this. You need a private key but you can't
memorize a private key really. Its a long string of hacks.
So you can turn a passphrase into a private key with a hash
and control of knowledge of the pass phrase becomes control of
the money. Why do people like this? The first thing they think
is plausible deniability. If no record on my computer or
anything of me making this thing then if somebody ask me a about
it I can say it doesn't exist. They can't prove me wrong. Well
thats not actually quite true. Because is pseudo
anonymous you can track the transactions. It is just tricky
and the other thing people say fifth amendment protection
against government seizure. Well sure, but you don't need a
brainwallet to do that. An encrypted wallet gives you the
same protection and its not more manageable and there is the
old meet is a better random number generator than silicon
because you can't back door meet but you don't need to back door
meet because it comes up with a shitty passwords and pass
phrases. So this doesn't really work very well. So remember that
cryptocurrency transactions are public. People are working on
adding privacy to do that not there yet and brainwallet
addresses show up on the transaction. And the same
password always gives you the same address so if you look at
addresses you can check them to see if there is a matching
brainwallet so a weak -- password can be guessed. That
14,000 dollars was sent to the passphrase of an empty string.
There is certain brainwallet tool site where that is default
pass phrase and someone just used it. [Laughter] So here is
how brainwallets works you start with a pass phrase I'm sure you
heard of correct battery horse staple. First thing we do is run
it through Shot 256. The address is treated as 256 bit integer
and thats your private key. The next thing we do is compute
the public key. So an interesting thing is well
actually for one this step is the most CMU step intensive of
the process. Its and two, theres actually two different
ways to represent a public key compressed and uncompressed for
a long time uncompressed was default most brainwallets still
default to this. Theres also a compressed format which is
basically a truncated version where you spend a little bit
more CPU time to restore the part that is left out. And you
can usually pick which one you want the use. So then you have a
public key. We put this through trial 56 as well but it is still
kind of long so we put it through right MD-1 160 which is
obscure hash algorithm. Most transaction use this as the on
network and on disc format. And well 160 bits in hex is kind of
unwieldily for a person and if you make any typos the money
would be gone for every so there is 58 check. You get the first
character identifies which cryptocurrency it goes to. The
rest of it is basic encoding of the check stem. So if you typo
it probably will catch your typo. So brainwallets make the
block chain into the public hash data base so what do we ask when
password hash database is made public. The first thing is are
the passwords in fact hashed. Well, yes they are. Are they
salted? No. Is the hash slow to crack? Well, kind of. Not slow
enough it turns out. Cracking yields money. So this is the
fantastic motivation for password crackers it turns out.
So back in 2013, I came across this blog post talking about
brainwallets and someone made test to see how many could be
crack them. I thought this was interesting, and you know I had
a half hour commute each way in the train. So I wrote a crack
over the course of a week. To see this in SSL. So it would
have taken a long list of hash 160s from a file and then and
standard in I could pass it passwords and pass phrases. No
real reason to build in my own passwords generation because
there are lots of other tools that will do that and spits
results out to you standard out. So I have a core I7 that is
about four or five years-old at this point and was able to do
10,000 guesses per second. Like a lot of people here, I find it
somewhat interesting to go through password leaks and crack
the hashes so I had word list sitting around so I just had to
feed it some of them and I was not prepared for the results. So
I got this going and went to a picnic and then I got home and I
saw how much wood could a wood chuck wood if a wood chuck could
chuck wood. This is funny and then I ran the balance check
script. Turns out the woodchucks can chuck about 250 bitcoins
worth of wood. [Laughter] At the time this was $20,000. So being
a good guy is hard. [Laughter] Running a dictionary is easy but
the hard part the being good so I put myself in a wonderful
little moral dilemma here because if I did absolutely
nothing I am not that smart somebody else will figure out
how to do the same thing I did and crack it and hey might not
be as nice as me. So I had to come up with something to do so
I thought the only thing I could think of to do was call my
friend Dan Kaminsky, a admitted white hat. So an hour, hour and
a half later I am Dan Kaminskys place all I have is
Mr. Woodchucks bitcoin address and no direct way to contact
him. So what do I do? We talked a while and we had this idea of
sending chunk a few cents and taking it back for extra money
there is tool called Vanity Gem. If youre not familiar with it
it generates a shit ton of private keys until you get one
that starts with a prefix you choose. But it has to be short
otherwise it takes forever so a crude way to send a message.
Cool. So my wife was there for moral support and listening to
this and she pipes up with yoinked. If you are not familiar
with that. [Laughter] It was perfect. So we send some money
to chuck and take the money back. At this point I should
clarify, bitcoin address does not hold a balance. It hold a
previous transaction output. So there a separate 250 bitcoin
transaction output that belongs the chuck and is . 00031337
bitcoin output that I just put there and hopefully Chuck will
notice that this address can take money back from him after
sending it and freak out about this and move his bitcoins so
this was the plan and I send the money to Chuck and try the take
it back because it is my money anyway but the bitcoin software
had other plans so I get the money back to yoink address and
the rest of it, the rest of Chucks 250 bitcoins go to
some other address I don't recognize. You can imagine my
reaction here. So Dan left for a while and told me to sort it
out. [laughter] So once I calmed down a little bit I remember how
bitcoin actually works. I thought it would just use the
right amount transaction output which seems reasonable but turns
out that it will choose outputs automatically based on the
product of size and age. Well 250 bitcoins that was put there
several weeks ago is higher priority than a few pennies that
I just put there. So I got that -- I got my fraction of penny of
bitcoin and sent back to address and my change went to other
address that the bitcoin wallet generated for me so I put the
money back and only borrowed Chuck's money for a few minutes.
It was fine. So I do this for a few days and he doesn't seem to
notice that the coin is all still there. So cryptocurrency
totally hard the trace. Well, I'm going to do it anyway. So I
follow the bitcoins and quickly I find out that he was a minor
from a bitcoin mining pool called deep bit which just so
happens I happened to use back in 2011 on the web when GPU
mining was a reasonable thing to do. So I got in touch with the
guy with deep bit and I spent an hour on RIC convincing him that
I was both crazy [Laughter] Im sorry, not crazy and a
good guy. He was actually really good he was like no I'm not
going to give you this guys e-mail address but I will pass
along contact information for you. I cant complain about
that. So he does this and the next morning I check my e-mail
and I have this thing asking what the hell who am I what the
hell is wrong with his bitcoins. The problem is I knew that the
person I had gotten in touch with was the person that funded
Brainwallet. Which is not necessarily the rightful owner
of the brainwallet and the best way to sort this out was talk to
guy on phone. So I did. He was really nice. I asked him if he
knew what the brainwallet was and he did and I asked him if I
he had money in there and he said he did and I said I knew
what his pass phrase and I said I'm a nice guy but there are
people that are not so nice and I hear his jaw hit the floor
over the phone. He was very, as I said, he was very nice. I
didn't tell him that I borrowed his bitcoins without asking. I
felt it was better that way. He sent me two bitcoins for my
trouble about I sent that to my friend as a wedding gift because
I didnt want to make money off of the whole thing. He used
his bitcoin and hes fine. Nothing bad happened to him
which is great. And he wasn't an idiot. I talked to him and he
realized that choosing a standard password would not
protect his bitcoins but how many people actually have a good
intuition of what is a password or pass phrase cracker can
actually do. Show of hands, how many of you have use obscure
quote or song lyrics or something like that as the
encryption key or GPG wallet as the disc encryption. Anyone? I
don't believe you. [Laughter] Well, lots of people do. I have
done it and there is post of reddit about year, year and a
half ago, somebody had put a couple bitcoins in brainwallet
and his pass phrase was an obscure poem in Africaans and it
got stolen. So which is small which is okay and the next thing
for me to do is see if I can make my brainwallet cracker fast
in order to just point out this is serious problem if you use
these things you're going to get robbed. So brain flare. There is
new [indiscernible] library that came out for bitcoin called Live
SCPP 256 K1 which is named after the bitcoin [indiscernible]
uses. Which is way faster. I got 130,000 pass phrases a second
out of my machine. And a benchmark thats in SCPP too. 560
million pass phrases checked per dollar per instance time on C3
large instances. You can pretty easily call Amazon and call your
instant limit bumped by is currently a couple thousand.
With a thousand instances and a 175 dollars you can check a
trillion pass phrases in nine hours with this thing. But uh
Wait. Yeah. So remember this? X case CD. So X case CD is not
always right. Brain flare can cover that search space with a
thousand instances in less than a week for about 28 hundred
dollars, and bad guys don't use ECC2 well maybe but it will be
somebody else's ECC2 instances. [Laughter] So they dont have
to pay for it. And these also have BOT nets and these days a
small bot net would be a 100 thousand nodes. IF we want to
get a nice lower bound we can assume that these nodes are 10
percent as fast as these ECC2 instances which are not fast.
And with that you can try 2 of the 48 passwords a day which is
275 trillion that is a lot of pass phrases. If is still not
fast enough for you there is plenty of room for optimization
and fancy math to make it go faster and this can definitely
get your CPU accelerated and it can definitely be FTA
accelerated. It can even be A6 accelerated but I don't expect
that to happen. Mining A6, mine bitcoins they can't do anything
else. They cant even hash arbitrary data. They only hash
blogs and if you want to get A6 made for something you will drop
a few million dollar to get a bad run done. I don't see that
happening. How Brain Flare works. So the first thing you
need to do is get a copy of block chain. The bitcoin block
chain is currently about 40 gigs takes a few hours to download
usually then you need to extract all the unique addresses from it
and then preprocess those because checking one by one
would be slow as hell and then we have out candidate pass
phrase generation. We feed those in and calculate the
corresponding addresses. We check them for matching address
in the block chain and if there is a match, win! Bitcoin
currently has had about 80 million addresses used ever. I
use a technique called a Bloom filter to check all of them,
effectively simultaneously. Bloom Filter is like second or
third year computer science stuff. If you don't know what it
is go look it up on Wikipedia. I will give you a very brief
explanation but the important thing is it tells you no match
or there is a probably a match. So it does mean it has false
positives but you can clean those up later and the
likelihood of false positive is dependent on how much, it
depends on the parameter of the filter and how many items have
been inserted. The wave grain, frankly its built a parameter
and you get about one false positive in every 380 million
pass phrases with a hundred million addresses inserted why a
hundred million and not 80 million you can crack multiple
block chains at once. Its just going to make your false
positives a little higher. All of the out coins use the same
format to load as many of them as you want to in there so you
can check bitcoin brainwallet, dashcoin, lightcoin, whatever,
all at the same time and it doesn't slow you down. So
brainwallet uses, or brain flare uses 512 megabyte to filter this
is two to three bits nice round number and each hash 160 is
mapped to 20 different bits in the bit mask when we insert a
hash 160 we insert the corresponding bits to check
whether or not the hash 160 is present. We look through those
bits one by one until we find one that is not set. If we find
one that is not set we stop looking and say no match if we
get through the end and they all there we say probable match.
Normally with the Bloom filter you take your input and run it
through a bunch of different hashes to generate the bits you
don't have to use a cryptographic hash for this it
just has to have a uniform distribution. Usually something
like XX hash is used. It is called hash 160 already hashed
so we cheat. We just bit slice the thing and cut it up into
chunks and combine in different ways and this turns out to work
very well and it takes huge CMU cycles per hash 160. Super fast.
Candidate passphrase generation is tricky. Wordless for password
cracking not so easy to find. Passphrase less though so I did
some scraping. Song lyrics, Wikipedia, WikiQuote, project
Gutenberg, reforms, like bitcoin, Reddit, the cypher
punks mailing list, whatever. And then you have all this raw
data so you have the clean it up. Every source is going to
require different clean up so I'm not going to go in how to do
that but use your favorite scripting language. It is not
hard. Once youve got a clean list of phrases. You can run
rules against them. So you can try it with normal
capitalization, all caps, all lower case initial caps with or
without punctuation or with or without spaces. Some results.
[Laughter] So the QTC1 I am sure somebody found and they just
burned the coins. It got sent to an invalid address. So those
coins are gone forever, it was about 2 bitcoins. I think that
is Texas Social Security number. And the memory is the name of
that melty clock painting made by Dahli. That had bitcoin when
I found it but I could not figure out how to contact that
guy. I used gambling sites. But those dont make you register
so I had no way to get in touch with him. I don't know if he
cleaned it out himself or got robbed. Unfortunately. Even for
of these ones are tiny amounts. So [Luaghter] There were a
lot of and ran quotes. A lot of them looks like they were put
there for people to find. They had like a tiny fraction of the
penny of bitcoin in them but good times. So I went through
all of ones that I was able to crack added up to 733 bitcoins.
I mean this is starting in 2011 and going through I think I
scraped the block chain last some time in June. I didn't
necessarily find any of these while they had balance but a lot
of them did have money in them at some point and it is very
very hard to tell which ones were stolen from and which ones
the owner just moved the money out. To be clear, I did not take
any of it with the exception of borrowing a little bit of
Chucks bitcoin for a few minutes, on accident. So dont
be Chuck. Any password or phrase phrase that you can come up with
on your own, can be found by a cleverer guesses algorithm and
if somebody else came up with it, it will end up in a word
list or phrase list at some point and there is better ways
to do this. There is a light weight bitcoin wallet called
Electrum. It does a nice little thing. It will randomly generate
a master key and export this for you as 12 words just memorize
those 12 words and you can restore your wallet. It
doesnt give you just one address, it gives you as many
addresses as you want. Pretty convenient. And then I mentioned
earlier, work wallet which does support a salt. They recommend
you use your e-mail address you can use your full name or ID
number or whatever. And it uses S crypt for hardening but I have
not benchmarked it but I would be impressed if you could make a
hundred guesses a second against it. Then theres my personal
favorite encrypted paper wallet. Which is where you print out an
encrypted version of your private key. The encryption is
hardened with s crypt so even if you find one of these things you
still have the crack it and if you know somebody found it and
you have another one somewhere else you keep one in the bank
vault and one under your bed you can get the other copy and
remove your funds before they crack it. Im a big fan of
this one. So a lot of people spend a lot of time trying to
figure out how to determine how strong a password corps phrase
is. Really easy when computer generated randomness. If
youre willing to assume the random number generator is good,
then all you have to do is count the bits. Each bits doubles the
strength, each 10 bits increases by a thousand fold. When is
person chooses it is more complicated. Randomness and
unpredictableness end up being more or less the same thing and
needs predictable and I know you have used pony sites that will
give you a password strength meter and you noticed that
password strength meters do not agree with each other and the
best ones I have seen a team by drop box, its called ZXCVBNM.
If you are confused by that name, look at the bottom of the
pretty keyboard. And It works pretty well but does have
limitations and failure cases. Most of which are caused by the
inherently limited dictionary size that is such a tool can
have. I ran a few things through it. Quick Evo Hash read it has
42 bits of entropy but that word that Bart played on the Simpson
and that is on the word list. 1234567 which is the kind of
[indiscernible] an idiot would use on his brainwallet. Rated as
92.90 bits of entropy, which would take centuries to crack.
So clearly, these estimates are not credible. Microsoft did a
study where that determined that the average users password
was about 40 bits in strength. Rat. You can make things better
with key stretching which is a must have in any modern
encryption or password hashing application. The idea is you
just make the hash take a lotted of CPU time. If it take a
hundred mill seconds for legitimate users the password to
be checked not a big deal be youre going to make a cracker
really sad if they have to spend a hundred milliseconds each
time. Even if they super optimize it, they are checking
dozens of hundreds of passwords a second. Which sucks for them.
And brain flare does 130,000 a second on one computer and
stretching could make that one per second. Easily. Common
algorithms S crypt, d crypt, shop [indiscernible] which is
not the same as shop I 12. [Indiscernible] to some sort of
stuff. There is a password hashing competition which was
just recently completed. They announced the winner as argon 2.
I need to read up about that, it sounds really interesting. You
end up being able to increase strength by about a million fold
using key stretching. And it is not that expensive of a trade
off. But you can do more. There is extreme key stretching. I
came up with this but I have seen other people talk about it
as well, so its not that clever of an idea. So what you
want to so a have a short value say five digits, six digits
something like that that is written down or stored on a
disc, this is shortcut and run through its own key function.
And if you have the shortcut and the pass phrase it takes hundred
mill seconds a second to recompute the key or verify it.
If youre missing the shortcut you have to brute force it. The
legitimate user having the pass phrase as a password can
recovery their shortcut in a few hours or a day or so but the
attacker has to spend that long on every pass phrase or password
they check. But then, who has time for that? Pretty easy to
generate a secure password or pass phrase. Generate it
randomly. [Indiscernible] is great. You might not be able --
if you have a lot of these you may not be able to remember them
all but you need a back up the password managers can do that.
But you need a master password for your password manager and
you need to back up the password manager. And then the back ups
can be cracked and turtles all the way down. You still have to
memorize at least one strong pass phrase or password. I want
to go over about what I have seen actual brainwallet thieves
actually doing in the wild. There seems to be about half a
dozen of them currently. Theyre pretty sophisticated.
I have seen them do crazy things like looking for brainwallets as
part of multi stig addresses. If you don't know what that means
don't worry about it. And they compete with each other and they
have to be fast and they are not going to be fast enough manually
so they have BOTs. Cracking with brain flare or something like
it, isnt real time. It would be too slow. Rainbow tables are
lot faster than actually fully graphing but they are also kind
of slow so look up tables are the only option. And some of
these guys seem to have a big look up tables. If I were going
to build these things I have not but if I were, I would go with a
disc key that the value store using you know whatever sequel
data base is popular that day. Use a truncated hash 256 as the
key. The pass phrase or private key has a value whichever one is
shorter. Then you just have to monitor the transaction. You
can't monitor the block chain. You have to actively monitor the
network. Because by the time it is in a block, somebody else
has, whos monitoring transactions. has already gotten
it. So you have to talk to network and then when you see a
private key, or an address that you a private key for you sweep
it off to your own address and do this faster than the other
guys that are doing this. So a $120. 04 tera byte hard drive
should be big enough for that 64 billion pass codes or pass
phrases or words. In the wild, I am pretty sure I can confidently
say that somebody has one with at least a hundred billion
entries. Because they are able to instantly crack any 5
character password I put out. Like including any numbers,
letters and special characters, symbols. Instantly. Anything on
common word lists also is done instantly. Many songs, lyrics,
lyrics that sort of thing that vanishes instantly. Six random
characters I tried a few of and the ones that I have made have
not been stolen yet. So this is clearly a little bit too big.
But brain flare can go through that space on EC2 for 1300
dollars. If you actually want to memorize something secure,crypto
neumonics are the way to go. A device that has been around
forever, the idea is that you take a big list of words and you
roll some casino dice. So you pick words from that list and
your pass phrase is made up of those words. Electro images as I
said earlier, also exist. It is also pronounce able password
generators I don't think they work that well but some people
like them. Then there is structured generators. Um this
is trying to not only come up with words but to put those
words together in meaningful combinations. You can do
adjective noun verb topples, use a mark up chain to generate what
looks like sentences. That sort of thing. It seems like it's go
to be easy to remember but a lot of research going on this and I
expect this to improve in the wild soon. So your meet is
predictable. Don't use it to generate passcode or pass
phrases. Dont be robbed. So I figured I would make this fun
for everyone. So DefCoin exists. Its a crypto currency for
Defcon. Coin based contests, they use it. The Crack Me if You
Can folks were helpful enough, or kind enough to make me a
bunch of passwords and pass phrases to use as brain wallets.
So brain flare will be online shortly. And I'm going to over
the next hour of so make a bunch of DefCoin brain wallets. So if
you want some DefCoin, you can download brain flare and
hopefully you can be faster than everybody else here. And I will
announce this on twitter when it is done which should be within
an hour or two. Any questions? Got it? Are we doing a line or
just shouting at people? [Inaudible question from
audience] Yup, in fact somebody, theres a.. Alright, he asked
it seems the big problem here is that brainwallets dont just
use shot 56. He is exactly right. A popular site for making
these things is brainwallet.org and theyre on Github and
somebody actually submitted a patch to upgrade to, upgrade it
to a hardened hash and the guy rejected the patch with some
explanation of well elliptic or public key derivation is slow so
this is unnecessary. This guy has been accused of cracking
brainwallets himself. And yeah his site will default to empty
string as a pass phrase and no complexity requirements enforced
so okay. Who is next? You. [Inaudible question from
audience] He asked if inserting spaces in a password or pass
phrase would strengthen it sufficiently? No adding spaces
does not significantly increase the strength of the password
length. It really doesnt matter, its complexity that
matters. I think you were first. [Inaudible question from
audience] He asked if deterministic wallets can have
the same problem. BitCoin has hierarchical deterministic
wallets. If you seeded them with a pass phrase that you chose
yourself then yes, it would have the same problem depending upon
whether or not if hardening or salting was used. Electrum is
the most popular took that does this and it will choose a pass
phrase for you so you dont have that problem. [Inaudible
question from audience] Does adding spaces or capitalization
to a password actually weaken it under any circumstances? Oh if
like someone hears you type it. If someone is hearing you type
passwords and is using this against you have other problems.
[Laughter] But I mean the weakest version of any pass
phrase is going to be one that appears verbatim somewhere. So
if you strip all the spaces it would be very, very, very
slightly stronger but if youre relying on this to save
you will be disappointed. Anyone else? [Inaudible question from
audience] There was that one in Afrikaans. I found some in
Chinese and Russian. You said any multi language,like two
languages in them. I didn't find one but I don't think the list I
was using had anything like that in them. So there might be I
just didn't find them. [Inaudible question from
audience] I can't hear you. [Inaudible question from
audience] I had slides with examples on there. There was
definitely Use the Force, Luke in there. Anybody else?
[Inaudible question from audience] Oh yeah, Im sorry I
did skip over that. He is asking how I figured out what people
are actually doing. The answer is I made bait wallets. So you
know I made this mental model of how I would steal brain wallets
if I were going to do it. I realized they are going to have
BOTS and so if I send a small amount of bitcoin to a weak
brainwallet any BOTS capable of stealing it will steal it. So I
was able to use their theft BOTS as an oracle against their look
up tables; and then by doing some [indiscernible] forensics,
I was able to get some idea, a rough idea of how many of them
there are. Anyone else? Way in the back. [Inaudible question
from audience] Are you saying it is too small or too big by a
factor of 10. [Inaudible comment from audience] He is saying that
my math was wrong. One second. My assumption is that storing a
single pass phrase takes a hundred bites. [Inaudible]
Right. If you know what the dictionaries are you still have
to store the dictionaries somewhere. So your dictionary is
taking up space either way. So you can't optimize it that much.
[Inaudible] Im sorry I am having a little bit of trouble
hearing you. [Inaudible comment from audience] Right but the
look up table has the dictionary words or the private keys
themselves. Find me later and we can talk about this. (Applause)
Nobody has anything to say about this?