(Successful) Dictionary Attack Against Private Keys

[Sothh]

Hey all,

Just wanted to post some interesting findings I am getting while running a sort of brute force against the blockchain.

Here is what I am doing:

Take a fairly long dictonary, get the sha256 of an entry, then calculate the bitcoin address using that hash as the private key.

So far I have found addresses for the following hashes:

love
test
fuckyou
password
1234
12345
123456

(I have not tried many.)

For example, the sha256 of "12345" is the address 18YXnSUCPDVNEpPGDFRVrdVye63RpH2MA4, which received a total of 0.11014424 BTC over its lifetime.

These addresses don't have any money in them currently, but have at some point.  In other words, if I had done the same thing when the address was in use I could have stole the bitcoins from the address.

I am unsure why these addresses exist, and why anyone would use them.  Some have been used fairly recently.

[1715281312]

1715281312

[1715281312]

1715281312

[gmaxwell]

They exist because of brainwallet.org. Amusingly, the site's creator started down his path much as you have, but then decided that "password derived" keys were useful so he setup a website.

Humans are unconditionally a terrible source of entropy. Many people using keys they sincerely believed were secure have been robbed. Often complicated "schemes", and even common password advice produce worse passwords instead of better ones.  This baddness is multiplied by the face that using JS tools make the performance of reasonable KDFs unacceptable and because the application prevents the use of effective salting, so the attacker gets an enormous simultaneous attack multiplier.

But there is really nothing that can be done except to keep telling people: Do Not Use Human Derived "entropy" for private keys.

It may be worth pointing out to you that a prudent person doesn't try doing this:  What happens if you find a key with 1000 BTC and can't determine the owner?  Your choice will be to rob them yourself or to leave it be and hope they move the coin before someone else robs them. If you don't want to potentially be in that situation you shouldn't be attempting to crack other people's ignorantly produced keys.

[mindtomatter]

It may be worth pointing out to you that a prudent person doesn't try doing this:  What happens if you find a key with 1000 BTC and can't determine the owner?  Your choice will be to rob them yourself or to leave it be and hope they move the coin before someone else robs them. If you don't want to potentially be in that situation you shouldn't be attempting to crack other people's ignorantly produced keys.

Isn't it better to have a few large public failures based on this obvious weakness to inform and teach the community why this is a bad thing to do?   Pretending it's not a problem means more users will make the same dumb mistake because they haven't seen any negative repercussions derive from it.   I'd rather have good guys trying to break our money for the betterment of that money than rely on malicious actors who have all the incentives to maximize the value they extract and do it as covertly as possible to prevent exactly those lessons from being learned.   If security is an arms race, it always makes sense to have a red team of good guys.

[01BTC10]

It's been already done. Some peoples have huge amount of private keys already imported and a script that check if there is a balance. If there is a deposit then it's automatically transferred to another address. Try a small deposit of 0.01BTC to one of those address and see what happen There is a thread about this somewhere.

[gmaxwell]

Isn't it better to have a few large public failures based on this obvious weakness to inform and teach the community why this is a bad thing to do?   Pretending it's not a problem means more users will make the same dumb mistake because they haven't seen any negative repercussions derive from it.   I'd rather have good guys trying to break our money for the betterment of that money than rely on malicious actors who have all the incentives to maximize the value they extract and do it as covertly as possible to prevent exactly those lessons from being learned.   If security is an arms race, it always makes sense to have a red team of good guys.

People have been very loudly told not to do this and many people don't— sadly, many other people smugly think they are smart enough to do it safely (I would even bet that most posters in this thread are among them). People have been stolen from, those who needed that to learn already learned— many others just blame the victims "Oh, I wouldn't use a key that stupid", ... yes, yes you would.

In any case, you misunderstand my advice there.  I wasn't making that suggestion for the benefit of the victims— they're already doomed through their ignorance and actions.  I was making that suggestion for the benefit of Sothh. There is no good team here.  Once you embark down this path you potentially find keys and have to choose between becoming a thief yourself or sitting passively while some other thief takes the coin. If you don't want to find yourself in that situation, for sake of your own personal ethics, then you shouldn't be trying— you should instead work on educating people to behave more safely... and compromising bad coins appears to be ineffective, due to the aforementioned victim blaming.

[Sothh]

I was just doing this out of curiosity.  If I do come across 1000 BTC I will try to find who it belongs to, and if I can't, I will take a small amount (like .5BTC or so) send it to an address I have posted on this forum, and then let it be.  The user will see money has been taken so his key is bad, and then he will google where it went to, and see it went to me.  I will give it back if he contacts me, or keep it if he does not, as a small tip for keeping his money safe.  

EDIT:

Found these two with positive balances:

Prehash: chocolate
Balance: 5.46E-5 BTC
Address: 1DTqPEUuuTeCJAYDadDnoPDKGvqDVFLRJN
Total Received: 5460

Prehash: basketball
Balance: 5.46E-5 BTC
Address: 1PYckPfNVrMWepDBN6Mzb1QqaEWWB4t1bx
Total Received: 5460

[Nigeria Prince]

Ok. I sent chocolate and Basketball. Give some more.

[gmaxwell]

Ok. I sent chocolate and Basketball. Give some more.

Please don't crap up the utxo set keeping around more of these junk outputs.

When you redeem these things, send them to an OP_RETURN txout with a value of 0.  This will convert the output into fees and prevent a new output from being created in the txout set.

[marcus_of_augustus]

It may be worth pointing out to you that a prudent person doesn't try doing this:  What happens if you find a key with 1000 BTC and can't determine the owner?  Your choice will be to rob them yourself or to leave it be and hope they move the coin before someone else robs them. If you don't want to potentially be in that situation you shouldn't be attempting to crack other people's ignorantly produced keys.

You probably have a duty to move the bitcoins somewhere safer for them before someone nefarious does and to serve as a warning to others 

It is kind of like finding a stash of cash poorly hidden under a rock in a public park ... and then you could maybe donate them to a charity of your choice? Or if you can't find the owner you could use a finders keepers ethical reasoning to disburse them as you see fit ....

[gmaxwell]

You probably have a duty to move the bitcoins somewhere safer for them before someone nefarious does and to serve as a warning to others 

It is kind of like finding a stash of cash poorly hidden under a rock in a public park ... and then you could maybe donate them to a charity of your choice? Or if you can't find the owner you could use a finders keepers ethical reasoning to disburse them as you see fit ....

Maybe. I mean, if the key was "password" then okay sure.  But if you threw three cpu months at it and the key was found as the product of some increasingly powerful analysis that you performed, some product of you and the victim being on a similar mental wavelength... it may reasonably be the case the the only people in the world who know the key are you and the victim.  But you don't know that.

Rather than stressing about it then, I suggest anyone considering doing this think ahead.

Besides, do you go around jiggling the neighbors doors and trying their windows? Why not? How is this different— beyond the possibility of getting caught being substantially reduced?

[TippingPoint]

Besides, do you go around jiggling the neighbors doors and trying their windows? Why not? How is this different— beyond the possibility of getting caught being substantially reduced?

Good point ^

[Sothh]

I am no longer running the attack.  It was only to prove a point, for security awareness.  I have not taken a single uBtc from any account I found.

[saddambitcoin]

i just found more goodies at "chocolates"

why would someone send such a small amount of BTC there?  i don't get it...

[gmaxwell]

Ok. I sent chocolate and Basketball. Give some more.

No you didn't.

[J35st3r]

There are also some transactions sent to addresses derived from raw hexadecimal private keys (this was the subject of my very first post, and yes I do now understand why it wraps), for instance ...

DEADBEEFDEADBEEFDEADBEEFDEADBEEFDEADBEEFDEADBEEFDEADBEEFDEADBEEF

5KWMcKxLvqmxBP5u6GcycvpJUdcA8sxZjK8Nm5uKUZsHch6i5K3

https://blockchain.info/address/12XwKrWbrSppJXQuqLyyZ8vVCk2FgaH7DW

And no, I didn't create this myself 

[jackjack]

Look at private key 0000000000000000000000000000000000000000000000000000000000000001

[fpgaminer]

On a related note, I thought about a partial solution to this problem of weak password based private keys.  My specific use case was deriving the seed for a deterministic wallet from a password on a hardware wallet.  Though, it could certainly be applied elsewhere.  (NOTE: I don't plan to implement this without further thought and experimentation.)

Ask the user for their full name, DOB, and/or any other personal information.  Concat with their password.  Chuck into an unusually expensive KDF, one that could take minutes or more to run.  Save the seed in protected flash on the hardware wallet (inaccessible to the outside world).  Feel free to encrypt that seed with a wallet pin/password (use the usual second long KDF here), if the user desires (for extra protection, and to prevent physical theft of the wallet).

Benefits:  This adds extra entropy that the user already has and can easily remember.  Some information may be difficult for an attacker to acquire (Social Security number, driver's license number, etc).  It mimics existing security restrictions present in the banking system and elsewhere.  By storing the derived seed (securely), the user only needs to enter this information once.  Since this process occurs infrequently we can use a very expensive KDF to make brute forcing painful.  The personal information also helps to make the derived seed unique to each user, even if two users choose the same (stupid) password.

It should be great at mitigating the kind of drive-by thefts demonstrated in this thread.  But, if an attacker has access to some or all of the personal information, then we're back to depending on the user's password choice and the strength of the KDF.  In extreme cases, one could set-up the KDF to take a day.  Again, this happens infrequently for the user (certainly 24 hours is significantly better than the turn-around on a stolen credit card, for example).  But, it would make attackers squirm.  The top 10,000 passwords would take 10,000 CPU-days of effort (now imagine the attacker doesn't know the name of your first dog...).

[Nigeria Prince]

I have wallet.dat generated with 123000 most common keywords from wordlists.
USE FOR SCIENTIFIC RESEARCH ONLY!!

Buy here: http://satoshibox.com/5228477e4c347bc5590041a7

[jackjack]

I have wallet.dat generated with 123000 most common keywords from wordlists.
USE FOR SCIENTIFIC RESEARCH ONLY!!

Buy here: http://satoshibox.com/5228477e4c347bc5590041a7

Go to service subforum ffs

[Carlton Banks]

Besides, do you go around jiggling the neighbors doors and trying their windows? Why not? How is this different— beyond the possibility of getting caught being substantially reduced?

Good point ^

I disagree, it is not a very representative analogy.

Here's why: there is a very high probability that locked houses have valuables inside, and it is possible to make a well judged assessment as to how valuable the contents are to improve your luck even further. There is no way of knowing whether a brain wallet seed leads to funded addresses or how much is in those addresses, you are relying on the partially predictable behaviour of human actors.

[johnyj]

What happens if you find a key with 1000 BTC and can't determine the owner? 

Remove 1 bitcoin from that address to infom the owner that the key is compromised 

[gmaxwell]

Ask the user for their full name, DOB, and/or any other personal information. 

So I did a little informal study of this on IRC with a little test page, and it was basically impossible convince people that their personal information wasn't being "connected" to their account in some way.  (and to some extent it is: someone who had their credentials recovered would have a harder time denying them).   This is least recovers from the saltlessness problem, though it leaves the door open for targeted attacks against passwords which are almost never strong enough... but I can't figure out how to get the user past the "personal information" problem.

[cryptocoinsnews]

http://www.cryptocoinsnews.com/2013/09/05/dictionary-attack-against-private-bitcoin-keys/

[Sothh]

correct horse battery staple

has thousands of transactions and has all this dust in it.  People are making transfers in and out.  Are they collecting the dust?  If I import the key into Armory wallet it crashes it when it tries to look at the transactions.

Ninja post.  https://bitcointalk.org/index.php?topic=288295.msg3087310#new

[Sothh]

correct horse battery staple

has thousands of transactions and has all this dust in it.  People are making transfers in and out.  Are they collecting the dust?  If I import the key into Armory wallet it crashes it when it tries to look at the transactions.

Ninja post.  https://bitcointalk.org/index.php?topic=288295.msg3087310#new

Ha, less than 2 minutes difference.  It is because someone mentioned it on reddit.

I actually found it myself last night, but did not have time to post about it.

[champbronc2]

It's not a glitch lol

[LAMarcellus]

Ok. I sent chocolate and Basketball. Give some more.

Please don't crap up the utxo set keeping around more of these junk outputs.

When you redeem these things, send them to an OP_RETURN txout with a value of 0.  This will convert the output into fees and prevent a new output from being created in the txout set.

Is there a tut or guide where I can learn more about command like OP_RETURN txout?


Also for what its worth,
These topics need to be brought up and refreshed opn occassion for the benefit of new users and continuing ed for old users alike.

[fat%]

Alright, so it looks like I managed to find the private keys of at least 13 addresses with positive balances (always 0.0000546) over the last 20 minutes or so. What I did was I visited http://en.wikipedia.org/wiki/List_of_Latin_words_with_English_derivatives and manually picked some random words from that list, entered them as a passphrase at brainwallet.com and manually looked up if the addresses were used before. Until now I found the following private keys with corresponding addresses:

TERM	PRIVATE KEY	ADDRESS	LINK
important	5JDUmWkA82w4Pas8j4eARzQeZtdReUoishzoBEgRGSFMcj2YBos	1GzbteqnMuDRU4iYeqka5YkgbhcA3qxTJd	Here
different	5K1d51cwAVq83qkBVzhHZ8u5xtSauctmCtJPf6g7BdDWaykHRFF	13zJp8PV7cY2cgLubFQzDFihHArgBgtM3C	Here
government	5K7kzFpqBTiegqevfc61pyCkzb6ds6hfvHP1rEWXqR7SXC3MMkj	1PXegNYkYCvkYsrDb3kxoQRQNh9VWToJBm	Here
insurance	5Jaj9sMkoLYzwtcv7UUjF69VUwyov5iTtXHQE6f2Mc8Ca5MkBrE	19RFdcSUJtFRusvc2uKTUnmx9PcR1tXgca	Here
medicines	5KZPBNWe2Fp7MZevX7JdghoZnXuXG7R27TThCKxj9kve2Nf4V7z	1Am8qpytgq1ySjesufAcdZw1buDnfKg3B8	Here
materials	5K9gHpgLZmVjejRDveJPEhCk8n33NdxPfr5tQzYDNdrkpPKB8bm	16zBDyZfRz2DbHSw5YXFUCaFJK48UkphpD	Here
perceived	5KjV1dJE58aFPB5HvTs8nbuQe8r8fUvHFEh3Pu8hQ8A7qSChEsi	1Ajzkqundi3i8SAZEUifXJcy79egAGCh7P	Here
patriotic	5JoQrSF3Bmi2NwZtspvqrXB1Am5SjnPUTYABT5r5gTi66ZHUiuV	16Urcu2LRTbZvGU5hujENx4MfjEMTfrosi	Here
amplitude	5JRUt4fu5n9c9mLTBGPv93jan16pxZhvwA23dUCwE5wtYr6jQbP	14Smg3UD6DaQhveJp17WuX4N2pffR4QiGC	Here
anniversary	5JJoefcjSo9SKn2eZE6VndoeaPC1PY9wMp6NHPzLCDjp2hqyqPM	14wMQhfw4bFFxzcyUVzgmVamjCjzXeozuJ	Here
amplification	5KNUAQKqdeHASbXrJSXs894RMk8K9QPE7DBPtyL42yVGLpTR5Wy	15f9gbgshS1LM7tYaEJYHZ3EQJU9dL2NRU	Here
triangular	5KR8CRg662edTqU4AmPKEAVbg8Qj9RA1WbY6MNzb64T4kAyzDLV	1P8JccH4BnQ5snwE6Mj6C9pu4hAUbfbhhi	Here
abbreviation	5JR7aQHZuYisNYHUTXnVML66Vy731EYW5B3W6ztJTthJun35iUa	1H9pZi9gypLwz2kRqn9kMnKfFopFY14EyN	Here

Note: The address sending the BTC to the minor ones is always this one: 1HoVUP4cSjsUQXR2dSMN8wXTLct2EbiSAB with the same transaction ID 632856fb634e50f0bba8ebe0b20798256c70a6626bcbf3d1cb4e16590a79da9f. There was only one major transaction of 0.0463834 BTC from the same address to this one 1J8GRz2nMmGYP6XQSfUnBgGzw9s6HSZEZU. The 500 minor ones add up to a total of 0.0358 BTC. Due to the fact that manually guessing the private keys of all 500 addresses is very time consuming and does not yield a high amount of BTC I don't think I'll continue doing so. Importing the 13 addresses into my wallet took me roughly 7-8 minutes per address, adding up to a total of about somewhat less than 2 hours after having found the private keys.

Conclusion: Whoever did this: You've been busted. Better not use the "List of Latin words with English derivatives" as the basis of your brainwallet based addresses. There are also some other lists I have not tried out yet, but you are free to do so.

Jeez, tossing is hard, but fun.

[virtualmaster]

Alright, so it looks like I managed to find the private keys of at least 13 addresses with positive balances (always 0.0000546) over the last 20 minutes or so. What I did was I visited http://en.wikipedia.org/wiki/List_of_Latin_words_with_English_derivatives and manually picked some random words from that list, entered them as a passphrase at brainwallet.com and manually looked up if the addresses were used before. Until now I found the following private keys with corresponding addresses:

TERM	PRIVATE KEY	ADDRESS	LINK
important	5JDUmWkA82w4Pas8j4eARzQeZtdReUoishzoBEgRGSFMcj2YBos	1GzbteqnMuDRU4iYeqka5YkgbhcA3qxTJd	Here
different	5K1d51cwAVq83qkBVzhHZ8u5xtSauctmCtJPf6g7BdDWaykHRFF	13zJp8PV7cY2cgLubFQzDFihHArgBgtM3C	Here
government	5K7kzFpqBTiegqevfc61pyCkzb6ds6hfvHP1rEWXqR7SXC3MMkj	1PXegNYkYCvkYsrDb3kxoQRQNh9VWToJBm	Here
insurance	5Jaj9sMkoLYzwtcv7UUjF69VUwyov5iTtXHQE6f2Mc8Ca5MkBrE	19RFdcSUJtFRusvc2uKTUnmx9PcR1tXgca	Here
medicines	5KZPBNWe2Fp7MZevX7JdghoZnXuXG7R27TThCKxj9kve2Nf4V7z	1Am8qpytgq1ySjesufAcdZw1buDnfKg3B8	Here
materials	5K9gHpgLZmVjejRDveJPEhCk8n33NdxPfr5tQzYDNdrkpPKB8bm	16zBDyZfRz2DbHSw5YXFUCaFJK48UkphpD	Here
perceived	5KjV1dJE58aFPB5HvTs8nbuQe8r8fUvHFEh3Pu8hQ8A7qSChEsi	1Ajzkqundi3i8SAZEUifXJcy79egAGCh7P	Here
patriotic	5JoQrSF3Bmi2NwZtspvqrXB1Am5SjnPUTYABT5r5gTi66ZHUiuV	16Urcu2LRTbZvGU5hujENx4MfjEMTfrosi	Here
amplitude	5JRUt4fu5n9c9mLTBGPv93jan16pxZhvwA23dUCwE5wtYr6jQbP	14Smg3UD6DaQhveJp17WuX4N2pffR4QiGC	Here
anniversary	5JJoefcjSo9SKn2eZE6VndoeaPC1PY9wMp6NHPzLCDjp2hqyqPM	14wMQhfw4bFFxzcyUVzgmVamjCjzXeozuJ	Here
amplification	5KNUAQKqdeHASbXrJSXs894RMk8K9QPE7DBPtyL42yVGLpTR5Wy	15f9gbgshS1LM7tYaEJYHZ3EQJU9dL2NRU	Here
triangular	5KR8CRg662edTqU4AmPKEAVbg8Qj9RA1WbY6MNzb64T4kAyzDLV	1P8JccH4BnQ5snwE6Mj6C9pu4hAUbfbhhi	Here
abbreviation	5JR7aQHZuYisNYHUTXnVML66Vy731EYW5B3W6ztJTthJun35iUa	1H9pZi9gypLwz2kRqn9kMnKfFopFY14EyN	Here

Note: The address sending the BTC to the minor ones is always this one: 1HoVUP4cSjsUQXR2dSMN8wXTLct2EbiSAB with the same transaction ID 632856fb634e50f0bba8ebe0b20798256c70a6626bcbf3d1cb4e16590a79da9f. There was only one major transaction of 0.0463834 BTC from the same address to this one 1J8GRz2nMmGYP6XQSfUnBgGzw9s6HSZEZU. The 500 minor ones add up to a total of 0.0358 BTC. Due to the fact that manually guessing the private keys of all 500 addresses is very time consuming and does not yield a high amount of BTC I don't think I'll continue doing so. Importing the 13 addresses into my wallet took me roughly 7-8 minutes per address, adding up to a total of about somewhat less that 2 hours after having found the private keys.

Conclusion: Whoever did this: You've been busted. Better not use the "List of Latin words with English derivatives" as the basis of your brainwallet based addresses. There are also some other lists I have not tried out yet, but you are free to do so.

Jeez, tossing is hard, but fun.

It is highly improbably to be a successful dictionary attack by amounts less of 1 mBTC. It is more probable that it was a test or a communication.

[fat%]

Alright, so it looks like I managed to find the private keys of at least 13 addresses with positive balances (always 0.0000546) over the last 20 minutes or so. What I did was I visited http://en.wikipedia.org/wiki/List_of_Latin_words_with_English_derivatives and manually picked some random words from that list, entered them as a passphrase at brainwallet.com and manually looked up if the addresses were used before. Until now I found the following private keys with corresponding addresses:

TERM	PRIVATE KEY	ADDRESS	LINK
important	5JDUmWkA82w4Pas8j4eARzQeZtdReUoishzoBEgRGSFMcj2YBos	1GzbteqnMuDRU4iYeqka5YkgbhcA3qxTJd	Here
different	5K1d51cwAVq83qkBVzhHZ8u5xtSauctmCtJPf6g7BdDWaykHRFF	13zJp8PV7cY2cgLubFQzDFihHArgBgtM3C	Here
government	5K7kzFpqBTiegqevfc61pyCkzb6ds6hfvHP1rEWXqR7SXC3MMkj	1PXegNYkYCvkYsrDb3kxoQRQNh9VWToJBm	Here
insurance	5Jaj9sMkoLYzwtcv7UUjF69VUwyov5iTtXHQE6f2Mc8Ca5MkBrE	19RFdcSUJtFRusvc2uKTUnmx9PcR1tXgca	Here
medicines	5KZPBNWe2Fp7MZevX7JdghoZnXuXG7R27TThCKxj9kve2Nf4V7z	1Am8qpytgq1ySjesufAcdZw1buDnfKg3B8	Here
materials	5K9gHpgLZmVjejRDveJPEhCk8n33NdxPfr5tQzYDNdrkpPKB8bm	16zBDyZfRz2DbHSw5YXFUCaFJK48UkphpD	Here
perceived	5KjV1dJE58aFPB5HvTs8nbuQe8r8fUvHFEh3Pu8hQ8A7qSChEsi	1Ajzkqundi3i8SAZEUifXJcy79egAGCh7P	Here
patriotic	5JoQrSF3Bmi2NwZtspvqrXB1Am5SjnPUTYABT5r5gTi66ZHUiuV	16Urcu2LRTbZvGU5hujENx4MfjEMTfrosi	Here
amplitude	5JRUt4fu5n9c9mLTBGPv93jan16pxZhvwA23dUCwE5wtYr6jQbP	14Smg3UD6DaQhveJp17WuX4N2pffR4QiGC	Here
anniversary	5JJoefcjSo9SKn2eZE6VndoeaPC1PY9wMp6NHPzLCDjp2hqyqPM	14wMQhfw4bFFxzcyUVzgmVamjCjzXeozuJ	Here
amplification	5KNUAQKqdeHASbXrJSXs894RMk8K9QPE7DBPtyL42yVGLpTR5Wy	15f9gbgshS1LM7tYaEJYHZ3EQJU9dL2NRU	Here
triangular	5KR8CRg662edTqU4AmPKEAVbg8Qj9RA1WbY6MNzb64T4kAyzDLV	1P8JccH4BnQ5snwE6Mj6C9pu4hAUbfbhhi	Here
abbreviation	5JR7aQHZuYisNYHUTXnVML66Vy731EYW5B3W6ztJTthJun35iUa	1H9pZi9gypLwz2kRqn9kMnKfFopFY14EyN	Here

Note: The address sending the BTC to the minor ones is always this one: 1HoVUP4cSjsUQXR2dSMN8wXTLct2EbiSAB with the same transaction ID 632856fb634e50f0bba8ebe0b20798256c70a6626bcbf3d1cb4e16590a79da9f. There was only one major transaction of 0.0463834 BTC from the same address to this one 1J8GRz2nMmGYP6XQSfUnBgGzw9s6HSZEZU. The 500 minor ones add up to a total of 0.0358 BTC. Due to the fact that manually guessing the private keys of all 500 addresses is very time consuming and does not yield a high amount of BTC I don't think I'll continue doing so. Importing the 13 addresses into my wallet took me roughly 7-8 minutes per address, adding up to a total of about somewhat less that 2 hours after having found the private keys.

Conclusion: Whoever did this: You've been busted. Better not use the "List of Latin words with English derivatives" as the basis of your brainwallet based addresses. There are also some other lists I have not tried out yet, but you are free to do so.

Jeez, tossing is hard, but fun.

It is highly improbably to be a successful dictionary attack by amounts less of 1 mBTC. It is more probable that it was a test or a communication.

Well, might be true. But it worked out. Tried "investigation" and "ambulance", same result. All latin based derivatives.

[gmaxwell]

To get rid of these junk "password testing outputs" don't create yet more outputs, here is how you make a transaction to defragment the utxo set:

For this game we'll need a copy of bitcoind or the bitcoinqt debug console. You don't need a synced up blockchain, unless you're going to use it to look up the scriptPubKeys, and if you are you'll need the node to be running with txindex=1 in the configuration.  You'll also want this patch so that you can relay OP_RETURN transactions, and a configuration which addnode=173.242.112.53  and addnode=relay.eligius.st  to make sure the OP_RETURN transactions get relayed to someone who will mine them.

First figure out the txid:vouts  you'll be spending.

Then run

$ bitcoind createrawtransaction '[{"txid":"50bb362e201ed2246a415dad53f63cbb41b88c145ea7a41ee111b9e4353f80f5","vout":224},{"txid":"dda2e022a81ac6dcc219bd1a8bc7038bf55f5039b8a74a78ac473b6b32a5d146","vout":414}]' '{"1GMaxweLLbo8mdXvnnC19Wt2wigiYUKgEB":1e-8}'


The destination doesn't matter as you'll see in a moment.

This will return:
0100000002f5803f35e4b911e11ea4a75e148cb841bb3cf653ad5d416a24d21e202e36bb50e0000 00000ffffffff46d1a5326b3b47ac784aa7b839505ff58b03c78b1abd19c2dcc61aa822e0a2dd9e 01000000ffffffff0101000000000000001976a914a86e8ee2a05a44613904e18132e49b2448adc4e688ac00000000

Which is an unsigned transaction in hex. I've bolded the two parts you need to modify by hand:

(0) The "1" which is the value of the output in satoshis, the number is little endian which is why most of the 0s come after it.  Change that 1 to a zero.

(1) The long part beginning with 1976a914...88ac. This is the scriptPubkey that the transaction pays to.  We replace that with 016a which is a 1 byte script (thus the 01) containing OP_RETURN which is the 0x6a opcode. This tells bitcoin to not save an output to the database.

With these two modifications all the coin value gets consolidated into the miner's fees and the global bitcoin database is cleaned up:

The result is:
0100000002f5803f35e4b911e11ea4a75e148cb841bb3cf653ad5d416a24d21e202e36bb50e0000 00000ffffffff46d1a5326b3b47ac784aa7b839505ff58b03c78b1abd19c2dcc61aa822e0a2dd9e 01000000ffffffff010000000000000000016a00000000

Which we can decode:

$ bitcoind decoderawtransaction 0100000002f5803f35e4b911e11ea4a75e148cb841bb3cf653ad5d416a24d21e202e36bb50e0000 00000ffffffff46d1a5326b3b47ac784aa7b839505ff58b03c78b1abd19c2dcc61aa822e0a2dd9e 01000000ffffffff010000000000000000016a00000000
{
    "txid" : "b147506ef23be7c7e8e0169b0aadf0bd1942d8acb9e31b48b0a1b904bf15425e",
    "version" : 1,
    "locktime" : 0,
    "vin" : [
        {
            "txid" : "50bb362e201ed2246a415dad53f63cbb41b88c145ea7a41ee111b9e4353f80f5",
            "vout" : 224,
            "scriptSig" : {
                "asm" : "",
                "hex" : ""
            },
            "sequence" : 4294967295
        },
        {
            "txid" : "dda2e022a81ac6dcc219bd1a8bc7038bf55f5039b8a74a78ac473b6b32a5d146",
            "vout" : 414,
            "scriptSig" : {
                "asm" : "",
                "hex" : ""
            },
            "sequence" : 4294967295
        }
    ],
    "vout" : [
        {
            "value" : 0.00000000,
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "OP_RETURN",
                "hex" : "6a",
                "type" : "nonstandard"
            }
        }
    ]
}


Now this just needs to be signed.

To sign it we need the scriptPubKeys and the private keys.

To get the scriptPubKeys you can run:


$ bitcoind getrawtransaction <txid> 1 | grep '"n" : <vout>,' -A 3 | grep hex


Substituting the txid and vout.

All said and done, we sign our transaction hex using the scriptPubKeys and private keys in an


$ bitcoind signrawtransaction 0100000002f5803f35e4b911e11ea4a75e148cb841bb3cf653ad5d416a24d21e202e36bb50e0000 00000ffffffff46d1a5326b3b47ac784aa7b839505ff58b03c78b1abd19c2dcc61aa822e0a2dd9e 01000000ffffffff010000000000000000016a00000000 '[{"txid":"50bb362e201ed2246a415dad53f63cbb41b88c145ea7a41ee111b9e4353f80f5","vout":224,"scriptPubKey":"76a914f2b461e18eaeeb834e8964a0f6f46abfa5a493cf88ac"},{"txid":"dda2e022a81ac6dcc219bd1a8bc7038bf55f5039b8a74a78ac473b6b32a5d146","vout":414,"scriptPubKey":"76a9146adad08db0e0169c5db5b232e0cbe46af4e27fe288ac"}]' '["5KR8CRg662edTqU4AmPKEAVbg8Qj9RA1WbY6MNzb64T4kAyzDLV","5KjV1dJE58aFPB5HvTs8nbuQe8r8fUvHFEh3Pu8hQ8A7qSChEsi"]'  "NONE|ANYONECANPAY"


The final "NONE|ANYONECANPAY" uses the none and anyonecanpay sighash flags so that in theory the miner could merge this transaction with other cleanup transactions, it basically creates a signature that gives away these coins to anyone. You DONT want to use that option on normal spends of your own coins.

Which will return:


{
    "hex" : "0100000002f5803f35e4b911e11ea4a75e148cb841bb3cf653ad5d416a24d21e202e36bb50e0000 0008c493046022100fd91365fb7b652676a9baf0ff38970fc4adef66dc0d481985ad8ccd85a6762 6b022100b9c801ea7ed0efc93fa6f95d60cff4dbf476f276d80fdfa11e57356ddf46be928241046 a69146ba92ba33073caa21e74ebdc630813c9062281807ca6071bf6a83818ba8daa3836857154cb 6d7e036c9e36d1f67e75a5327b80b34761fd434ee067c61bffffffff46d1a5326b3b47ac784aa7b 839505ff58b03c78b1abd19c2dcc61aa822e0a2dd9e0100008c493046022100d4661ae28ddf7604 986b86de06b945600ae059a123c5c791202bdc63da4b7e6a022100a1ea94cacd5fa97f2435137da 8665fbd952507ad22e727567b3fb7fcdaeeb4348241040ace5fddc113ff9689496ea9abc30620d5 b032286df28e1a20cfeca112cf1c27050dacbc9de5dced5803b2d221f1c5163e4f0556b1f48e631 9cb2351dc3b347bffffffff010000000000000000016a00000000",
    "complete" : true
}


And the complete says the transaction is ready to send.

You can send it with sendrawtransaction <hex signed output>

If you don't want to go through the manual hex editing to get the transaction made into an OP_RETURN,  then at least please groom up multiple of these outputs into a payment to yourself...  the dust does you and no one else any good.

Congrats, you've now defragmented the Bitcoin global database a little bit. Have fun.

[Cablez]

I am sorry to drag this a bit off topic but seeing as I am not technically versed in these matters I was wondering.  I understand that these 'attacks' are on address/keypairs that are generated from in this case simple words mostly related to brainwallets.  What mechanisms are contained in the QT client that prevent simple brute forcing of address/keypairs or to put it another way how are secure addresses/keys generated in the QT client? Thanks

[gmaxwell]

I am sorry to drag this a bit off topic but seeing as I am not technically versed in these matters I was wondering.  I understand that these 'attacks' are on address/keypairs that are generated from in this case simple words mostly related to brainwallets.  What mechanisms are contained in the QT client that prevent simple brute forcing of address/keypairs or to put it another way how are secure addresses/keys generated in the QT client? Thanks

The QT client does not support "brainwallets" and its developers (as is the case for all the other compentently created wallet software) aggressively reject them.  Private keys in Bitcoin-QT are are 256 bits of cryptographically strong random data. Brute force searching to obtain one on a non-reversable classical computer is computation in the realm of "Step 1. first convert the local solar system to energy".

[Cablez]

Thanks very much gmaxwell.  That is what I had assumed was the case. So this is really about shortcuts taken to create addresses that could be recreated fairly easily.  Maybe the thread title is a tad misleading.

[bitcoindigi]

please rename the topic to dictionary attack againt brainwallets. sounds less stupid that way, OP.

[gmaxwell]

Maybe I am wrong but I don't think any wallet currently being used uses actual random data (such as input from a true random number generator).

No, Bitcoin-QT uses input from truly random sources (the operating system's true rng inputs and its own timing noise measurements, passed through cryptographic hardening just in case). AFAIK all other local client wallets do the same.

People have been trying to analyze patters in the way old blocks are mined so flaws in the private key generation algorithms could possibly be analyzed in a similar manner.

None of the things being analyzed in those discussions are actually (pseudo-)random things at all. E.g. the nonce used in mining is just a counter.

[crazy_rabbit]

please rename the topic to dictionary attack againt brainwallets. sounds less stupid that way, OP.

I'd like to rename it to: Stupidly short passwords strike again. It's not an attack if your brainwallet is the word "love". It's just stupid.

[crazy_rabbit]

Maybe I am wrong but I don't think any wallet currently being used uses actual random data (such as input from a true random number generator).

No, Bitcoin-QT uses input from truly random sources (the operating system's true rng inputs and its own timing noise measurements, passed through cryptographic hardening just in case). AFAIK all other local client wallets do the same.

People have been trying to analyze patters in the way old blocks are mined so flaws in the private key generation algorithms could possibly be analyzed in a similar manner.

None of the things being analyzed in those discussions are actually (pseudo-)random things at all. E.g. the nonce used in mining is just a counter.

It you can get true random numbers from these processes then why do companies make specialized random number generator cards?  Once company advertises that Satoshi dice uses their system.

http://en.wikipedia.org/wiki/Comparison_of_hardware_random_number_generators

Because sometimes, Like in the case of android- they are indeed: not random. Tricky tricky.

[gmaxwell]

It you can get true random numbers from these processes then why do companies make specialized random number generator cards?  Once company advertises that Satoshi dice uses their system.

Primarily because their throughput is relatively low. E.g. hundreds of bits per second.  There are applications where you want megabits of random data.

As far as Satoshi dice goes... thats pretty funny.  SDice's system is not random, their proof of faithful behavior requires that they be deterministic.

Because sometimes, Like in the case of android- they are indeed: not random. Tricky tricky.

Android's OS random numbers were plenty random... their libraries were mishandling them.

[cypherdoc]

gmaxwell,

thx for contributing so much to our overall understanding of this problem.

[dserrano5]

To get rid of these junk "password testing outputs" don't create yet more outputs, here is how you make a transaction to defragment the utxo set:

[Detailed technical explanation]

I think I'm missing something here. Isn't it easier to use a coin control patch/utility to pick e.g. 10 of these tiny outputs, combine with a large output of mine (so the resulting priority is high enough) and create a single output to myself? By repeating this procedure we could also reduce the UTXO set without having to fiddle with raw transactions and/or edit any hexdump.

[gmaxwell]

I think I'm missing something here. Isn't it easier to use a coin control patch/utility to pick e.g. 10 of these tiny outputs, combine with a large output of mine (so the resulting priority is high enough) and create a single output to myself? By repeating this procedure we could also reduce the UTXO set without having to fiddle with raw transactions and/or edit any hexdump.

Thats fine too, though it does result in moving more data than strictly required (the extra signature for the coins you're moving just as a source of priority) and priority also limits how much you can do thus for free.

What you don't want to do is just move one single worthless output by itself... that just further decreases the odds that it'll ever get cleaned up.

Eligius now has a pushtx interface which will directly accept OP_RETURN and other weird txn that eligius accepts: http://eligius.st/~wizkid057/newstats/pushtxn.php