Vanitygen: Vanity bitcoin address generator/miner [v0.22]

[samr7]

By the way, did you find anything about the single-proc behaviour? I'm not sure my laptop would handle the heat of having both CPUs working anyway, but other people with several CPUs might be interested in taking advantage of all of them.

this is cool.   I noticed it seems to only fill up 1 cpu core.  Should I kick off multiple instances so as to max out all my CPU power?   Or will it be redundant re-searching keyspace it already searched for my vanity phrase?

That's correct.  For the time being, you need to kick off one instance for each CPU core you want to use.  The key space searches won't be coordinated, but it's quite unlikely that any two instances of this program that are ever started by anybody will ever check the same keys.

Proper entropy is hard.

Process ID is 16 bits. Unix time is about 26 bits of entropy (assuming 2 year span, second resolution). Total Entropy: 42 bits. (unless I am missing a source of entropy)

Digging through OpenSSL 1.0.0d, the main source of entropy for the default RNG on Linux would appear to be /dev/urandom, or failing that, /dev/random or /dev/srandom.  In fact, if you want to, you can load it up in strace and watch it open /dev/urandom and read random bytes.

[SgtSpike]

Any chance a trusted member can provide a windows binary for this? I can not compile things on windows for the life of me!

Not sure if I qualify as "trusted" but here is a quick Cygwin build: http://www.sendspace.com/file/yzsf0z

Thanks.  I get this error though:

assertion "check_upper || ((bnlow2 == NULL) && (bnhigh2 == NULL))" failed: file
"vanitygen.c", line 482, function: get_prefix_ranges
    113 [sig] vanitygen 956 open_stackdumpfile: Dumping stack trace to vanitygen
.exe.stackdump

You probably should paste that file somewhere.

Doesn't mean anything to me...

Stack trace:
Frame     Function  Args
0028C6B4  763E1184  (00000128, 0000EA60, 00000000, 0028C7D8)
0028C6C8  763E1138  (00000128, 0000EA60, 000000A4, 0028C7BC)
0028C7D8  610C92FA  (00000000, 00000128, 0028C7F8, 00000000)
0028C8B8  610C6057  (00000000, 00000000, 00000000, 00000000)
0028C908  610C643C  (000003BC, 0028C930, 00000002, 00000004)
0028C9C8  610C6551  (000003BC, 00000006, 0028C9F8, 610C65F5)
0028C9D8  610C658C  (00000006, 0028CE80, 763F8B12, 61FB0000)
0028C9F8  610C65F5  (61180054, 00406480, 004063AF, 000001E2)
0028CA28  6100109B  (004063AF, 000001E2, 00406910, 00406480)
0028CAE8  0040212C  (00000000, 00D3331D, 0028CC78, 00D316B8)
0028CCA8  00403F02  (00000000, 00000080, 00D53730, 00001F5C)
0028CCF8  00404A58  (0028CD36, 00000000, 0028CD68, 61007038)
0028CD68  61007038  (00000000, 0028CDA4, 61006980, 7EFDE000)
End of stack trace

[samr7]

Thanks.  I get this error though:

assertion "check_upper || ((bnlow2 == NULL) && (bnhigh2 == NULL))" failed: file
"vanitygen.c", line 482, function: get_prefix_ranges
    113 [sig] vanitygen 956 open_stackdumpfile: Dumping stack trace to vanitygen
.exe.stackdump

Wow SgtSpike, you must have been trying patterns prefixed with varying numbers of 1s in order to trigger this bug.  Well beyond my humble test suite.  Anyway, it's mostly clear what went wrong and I'll post a new version in a bit.

[samr7]

New version 0.4 pasted.  Soon it'll go on github, but not yet.

• Fix assertion failure when using exact prefixes starting with more than one 1, reported by SgtSpike
• Include a Win32 binary

[samr7]

Proper seeding of crypto-hard primitives is a hard problem,
which has been worked on and solved (/dev/urandom).

Unless I'm missing something, the above method is rather lame
as opposed to what a standard linux kernel implementation does.

I can't agree more.  However, EC_KEY_generate_key() gets random numbers from the well-scrutinized OpenSSL RNG, also used by the official bitcoin client and probably half the HTTPS servers on the internet.  And indeed, on Linux, OpenSSL will use /dev/urandom.  I wouldn't be too worried about it, if there's a serious problem, we'll probably find out on the news.

[sirky]

Any chance a trusted member can provide a windows binary for this? I can not compile things on windows for the life of me!

Not sure if I qualify as "trusted" but here is a quick Cygwin build: http://www.sendspace.com/file/yzsf0z

Thanks a lot for this!

[riush]

Meh. Now I generated a hand full of nice addresses and the import doesn't work... Gotta try recompiling the most current patch to bitcoin later...
Can anybody verify the import works?

btw. to run on multiple cores I just use this.. it's not nice, but it works (for me ):

Code:

threads = []

(ARGV[1].to_i rescue 1).times do
  threads << Thread.start do
    puts `./vanitygen #{ARGV[0]}`
    Process.kill("INT", Process.pid)
  end
end

Signal.trap("INT") do
  puts "exiting"
  threads.each {|t| t.kill}
end

threads.each {|t| t.join}

run it like `ruby vanitygen.rb 1bit 4`

[pB11]

Digging through OpenSSL 1.0.0d, the main source of entropy for the default RNG on Linux would appear to be /dev/urandom, or failing that, /dev/random or /dev/srandom.  In fact, if you want to, you can load it up in strace and watch it open /dev/urandom and read random bytes.

Indeed, my mistake. time() is not the only source of entropy by default.
I didnt look deep enough.

Code:

openssl-1.0.0d/crypto/rand/md_rand.c: ssleay_rand_bytes():
	if (!initialized)
		{
		RAND_poll();
		initialized = 1;
		}

Btw using just time() was quite secure anyway. Assuming Vanitygen runs at least several minutes, the amount of keys to brute-force is >2^64:
 - 15 bit PID
 - 21 bit timeframe (1 month)
 - 7-8 bit CPU speed, + a few bits of time uncertainty each EC_KEY_generate_key()
 - 2^20+ keys to generate  

[dserrano5]

btw. to run on multiple cores I just use this.. it's not nice, but it works (for me ):

I do:

Code:

$ for I in {1..4}; do (./vanitygen -r foo; killall vanitygen) & done

The first to finish kills the others .

[drrussellshane]

Sorry for my noobness... how does one import keys?

[SgtSpike]

Thanks.  I get this error though:

assertion "check_upper || ((bnlow2 == NULL) && (bnhigh2 == NULL))" failed: file
"vanitygen.c", line 482, function: get_prefix_ranges
    113 [sig] vanitygen 956 open_stackdumpfile: Dumping stack trace to vanitygen
.exe.stackdump

Wow SgtSpike, you must have been trying patterns prefixed with varying numbers of 1s in order to trigger this bug.  Well beyond my humble test suite.  Anyway, it's mostly clear what went wrong and I'll post a new version in a bit.

I excel at breaking stuff. 

And thank you VERY much for posting a binary as well.  Much appreciated - I hate trying to compile on a Windows box, and I'm a chicken with my head cut off in Linux.

[SgtSpike]

Is there a way to make the search caps-insensitive?

[gentakin]

Use regular expressions. Like this:

[g|G][e|E|3][n|N][t|T|7]    and so on. This matches Gent, gent, g3N7, ..

Adding * allows repeating the character.
G[e|E]*n  matches GeeeeEEEeeeen, Gen and Gn. If you want to have at least 1 occurence of the character, use + instead of *.

That's how I know regexps. Not sure if it is actually the pcre-style regexp syntax used in vanitygen.

[dserrano5]

Sorry for my noobness... how does one import keys?

You need to use a modified bitcoin client (read the OP) and run:

Code:

bitcoind importprivkey 5KhUstDBWc...

The string to use is the "Privkey" as returned from vanitygen.

Adding * allows repeating the character.
G[e|E]*n  matches GeeeeEEEeeeen, Gen and Gn. If you want to have at least 1 occurence of the character, use + instead of *.

That's how I know regexps. Not sure if it is actually the pcre-style regexp syntax used in vanitygen.

What you describe, particularly the '+' bit, applies to both GNU extended and Perl compatible regexen.

[SgtSpike]

Use regular expressions. Like this:

[g|G][e|E|3][n|N][t|T|7]    and so on. This matches Gent, gent, g3N7, ..

Adding * allows repeating the character.
G[e|E]*n  matches GeeeeEEEeeeen, Gen and Gn. If you want to have at least 1 occurence of the character, use + instead of *.

That's how I know regexps. Not sure if it is actually the pcre-style regexp syntax used in vanitygen.

Thank you much!

EDIT:  Hmmm, didn't work.  "Invalid character '[' in prefix 1[p|P]etc..."

[dserrano5]

EDIT:  Hmmm, didn't work.  "Invalid character '[' in prefix 1[p|P]etc..."

You don't need the pipe: 1[Aa][Bb][Cc]. In some shells you may have to escape/quote the square brackets. Safest is to enclose the whole regex in single quotes (double quotes in windows' cmd).

[SgtSpike]

EDIT:  Hmmm, didn't work.  "Invalid character '[' in prefix 1[p|P]etc..."

You don't need the pipe: 1[Aa][Bb][Cc]. In some shells you may have to escape/quote the square brackets. Safest is to enclose the whole regex in single quotes (double quotes in windows' cmd).

I have the targets stored in a text file.  I tried encapsulating each regex in single and double quotes, both errored out.  It seemed that the command window changed the double quotes to an o with two dots over it, and the single quotes to one of those AE letter combos.  Not sure what's up with that.

Regardless, still getting the invalid character '[' error without pipes in the text file.  Any other suggestions?

[Shevek]

Btw using just time() was quite secure anyway. Assuming Vanitygen runs at least several minutes, the amount of keys to brute-force is >2^64:
 - 15 bit PID

To be used once (for one key). If used twice or more times, the full chain of keys can be compromised.

- 21 bit timeframe (1 month)

Again, to be used once. Consecutive keys will have a time variation about perhaps 8~10 bits.

- 7-8 bit CPU speed, + a few bits of time uncertainty each EC_KEY_generate_key()

To be used for one key. The entropy between keys drastically falls.

- 2^20+ keys to generate  

I don't understand your claim: each key needs 256 bits to be builded. And these 256 bits should have high entropy quality (ideally, 256 bits of entropy). So, picking up 256 bits really random is a hard task.

Guys: velocity and good entropy cannot be pushed together. Use these vanity addresses only if you like strong emotions.

[Pieter Wuille]

That's not entirely true: as addresses are only 160 bits, it suffices to try 2^160 private keys to have a reasonable chance of finding one that matches a given address. Thus, a private key only needs 160 of randomness.

Furthermore, if you limit eg. four base58 characters of the address to particular string (as this patch allows you to), you already lock log(58^4)/log(2)=23.4 bits of those 160 bits through other means.

I say you need 136.6 bits of entropy per vanity key found (assuming the above restriction), not per attempt, as the attacker cannot observe your failed attempts.

[Shevek]

That's not entirely true: as addresses are only 160 bits, it suffices to try 2^160 private keys to have a reasonable chance of finding one that matches a given address. Thus, a private key only needs 160 of randomness.

Th 160-bit reduction of addresses of public keys is a way to keep shorter chains with still good collision resistance. But inside this, there is a true 256-bit public key

Thus, the task-force needed to blow up a private key (that is: the number of tries in EC-product in order to find one private key that matches the targeted public key) is ~2^256 because the EC-multiplier is just a 256 bit number (a 78-decimal-digit integer, if you want).

If you resign 96 bits of good entroy, you are giving a chance to an attacker to resolve your priv. key after 2^160 tries. It is still huge but... why resign the full strength of the elliptic curve?