Pages:
Author

Topic: (Successful) Dictionary Attack Against Private Keys (Read 9452 times)

staff
Activity: 4284
Merit: 8808
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
legendary
Activity: 1974
Merit: 1030
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.
legendary
Activity: 1764
Merit: 1002
gmaxwell,

thx for contributing so much to our overall understanding of this problem.
staff
Activity: 4284
Merit: 8808
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. Tongue

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.
legendary
Activity: 1204
Merit: 1002
RUM AND CARROTS: A PIRATE LIFE FOR ME
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.

Quote
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.
legendary
Activity: 1204
Merit: 1002
RUM AND CARROTS: A PIRATE LIFE FOR ME
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.
staff
Activity: 4284
Merit: 8808
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.

Quote
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.
full member
Activity: 238
Merit: 100
please rename the topic to dictionary attack againt brainwallets. sounds less stupid that way, OP.
legendary
Activity: 1400
Merit: 1000
I owe my soul to the Bitcoin code...
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.
staff
Activity: 4284
Merit: 8808
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".
legendary
Activity: 1400
Merit: 1000
I owe my soul to the Bitcoin code...
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
staff
Activity: 4284
Merit: 8808
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 1 | grep '"n" : ,' -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

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.
member
Activity: 62
Merit: 10
hero member
Activity: 504
Merit: 500
member
Activity: 62
Merit: 10
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
full member
Activity: 180
Merit: 100
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.
hero member
Activity: 490
Merit: 500
It's not a glitch lol
full member
Activity: 238
Merit: 100
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://bitcointalksearch.org/topic/m.3087310

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.
full member
Activity: 238
Merit: 100
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://bitcointalksearch.org/topic/m.3087310
Pages:
Jump to:
© 2020, Bitcointalksearch.org