[BOUNTY] 0.2 BTC bounty for figuring out entropy in this python app

[SgtSpike]

A long while ago, when I was in to generating vanity addresses, I used this set of python scripts:  https://mega.co.nz/#!DwQlmL4L!ISzPiTuA5Y0PUIQNv79cy0PhJ4VlFEbLXx7c4ouN7jI

I didn't write the script, but I would like to know how safe Bitcoin addresses that were generated with this script are.  So, a 0.2 BTC bounty to anyone who can find the source(s) of entropy in this code, and describe how easily those addresses could be regenerated.  I've never learned python, so it's a bit difficult for me to follow what is happening in the code.

EDIT:  I suspect the randomness would be in the generate.py file, so I'll paste that code here for ease of looking at:

Code:

from __future__ import print_function
import hashlib
import time
import binascii
import base64
import sys
import ahocorasick


ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

def base58encode(inp):
	BASE = 58;
	bi = int(binascii.hexlify(inp), 16)
	s = ""
	while bi > 0:
		s = ALPHABET[bi%BASE] + s
		bi = bi/BASE                                                                                                                   
	nPad = 0
	for c in inp:
		if c == '\0': nPad += 1
		else: break
	
	return (ALPHABET[0]*nPad) + s

def public2address(publickey):

	ripemd = hashlib.new('ripemd160')

	version = '\x00'

	ripemd.update(hashlib.sha256(publickey).digest())

	keyhash = version+binascii.unhexlify(ripemd.hexdigest())

	checksum = hashlib.sha256(hashlib.sha256(keyhash).digest()).digest()[0:4]

	bitcoinaddress = base58encode(keyhash+checksum)

	return bitcoinaddress

def main():
	outfile = sys.argv[1]
	target = sys.argv[2]
	
	from M2Crypto import EC
	curve   = 'secp256k1'
	ec_curve = eval('EC.NID_%s' % curve)
	
	tree = ahocorasick.KeywordTree()
	file = open(target)
	
	print("Reading file...")
	
	for line in file:
		l = line.rstrip()
		tree.add(l)
	
	print("Generating tree...")
	
	tree.make()
	
	ec = EC.gen_params(ec_curve)
	CONST1 = binascii.unhexlify("308201130201010420")
	CONST2 = binascii.unhexlify("a081a53081a2020101302c06072a8648ce3d0101022100fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f300604010004010704410479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8022100fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141020101a144034200")
	
	test = False
	
	count = 0
	t = time.time()
	interval = 500
	
	with open(outfile, 'a') as finds:
		while True:
			ec.gen_key()
		
			#M2Crypto adds some stuff to the public key		
			pubkey = ec.pub().get_der()[23:]
		
			address = public2address(pubkey)
			where = tree.search(address.lower()[:10])
			if test or where:
				print("Address: "+address)
				print("Public key: "+binascii.hexlify(pubkey))
				#For some reason it can only save the private key to a file -.-
				ec.save_key("key"+outfile, None)
				with open("key"+outfile) as keyfile:
					keyfile.readline()
					priv = keyfile.readline().rstrip()
					#M2Crypto adds some stuff to the private key.
					#Removing it, and re-encoding to base58
					shortpriv = base64.b64decode(priv)[7:-9]
					print("Private key base58: "+base58encode('\x80'+shortpriv+hashlib.sha256(hashlib.sha256('\x80'+shortpriv).digest()).digest()[0:4]))
					priv = CONST1 + shortpriv + CONST2 + pubkey
					print("Private key full hex: "+binascii.hexlify(priv))
				if not test:
					word = address[where[0]:where[1]]
					print(word)
					finds.write(word+" "+address+" "+binascii.hexlify(pubkey)+" "+binascii.hexlify(priv)+"\n")
				print("")
			count += 1
			if count%interval == 0:
				dt = time.time() - t
				print(str(int(interval/dt)) + " keys/sec    ",end='\r')
				t = time.time()

main()

[runeks]

Looks like it uses OpenSSL to generate keys. So I'd say it's as safe as OpenSSL's default key generation is.

M2Crypto is a Python wrapper around the OpenSSL library: https://pypi.python.org/pypi/M2Crypto

Code:

	from M2Crypto import EC

[...]
	
	ec = EC.gen_params(ec_curve)


[...]
	
	with open(outfile, 'a') as finds:
		while True:
			ec.gen_key()

[...]

EDIT: Yup. Looks like it's a wrapper around OpenSSL's EC_KEY_generate_key()

From M2Crypto source EC.py:

Code:

    def gen_key(self):
        """
        Generates the key pair from its parameters. Use::
            keypair = EC.gen_params(curve)
            keypair.gen_key()
        to create an EC key pair.
        """
        assert m2.ec_key_type_check(self.ec), "'ec' type error"
        m2.ec_key_gen_key(self.ec)  

And from ./SWIG/_ec.i:

Code:

%rename(ec_key_gen_key) EC_KEY_generate_key;

So, a 0.2 BTC bounty to anyone who can find the source(s) of entropy in this code, and describe how easily those addresses could be regenerated.

So, in short, it should be exactly as hard as any other key generated by OpenSSL.

[jackjack]

Yep, safe as OpenSSL
Should be enough

[SgtSpike]

Runeks - can you confirm I should send the 0.2 BTC bounty to 1runeksijzfVxyrpiyCY2LCBvYsSiFsCm?

Jackjack - thanks for the additional input.

It does indeed sound like OpenSSL has decent entropy sources:

OpenSSL

OpenSSL implements such a hash-based entropy juicer. It provides a function RAND_add(buf, n, e) that adds a buffer of length n and entropy e to the entropy pool. Internally, the entry pool is just an MD5 or SHA1 hash state: RAND_add calls MD_update to add the bytes to a running hash computation. The parameter e is an assertion made by the caller about the entropy contained in buf. OpenSSL uses it to keep a running estimate of the total amount of entropy in the buffer. OpenSSL also provides a RAND_bytes(buf, n) that returns a high-entropy random byte sequence. If the running estimate indicates that there isn't enough entropy in the pool, RAND_bytes returns an error. This is entirely reasonable.

The Unix-specific code in OpenSSL seeds the entropy juicer with some dodgy code. The essence of RAND_poll in rand_unix.c is (my words):

    char buf[100];
    fd = open("/dev/random", O_RDONLY);
    n = read(fd, buf, sizeof buf);
    close(fd);
    RAND_add(buf, sizeof buf, n);

Notice that the parameters to RAND_add say to use the entire buffer but only expect n bytes of entropy. RAND_load_file does a similar thing when reading from a file, and there the uninitialized reference is explicitly marked as intentional (actual code):

    i=fread(buf,1,n,in);
    if (i <= 0) break;
    /* even if n != i, use the full array */
    RAND_add(buf,n,i);

The rationale here is that including the uninitialized fragment at the end of the buffer might actually increase the actual amount of entropy, and in any event being honest about the amount of entropy being claimed won't break the entropy pool estimates.

Similarly, the function RAND_bytes(buf, n), whose main purpose is to fetch n high-entropy bytes from the juicer, adds the contents of buf to the entropy pool (it behaves like RAND_add(buf, n, 0)) before it fills in buf.

In at least three different places, then, the OpenSSL developers explicitly chose to use uninitialized buffers as possible entropy sources. While this is theoretically defensible (it can't hurt), it's mostly a combination of voodoo and wishful thinking, and it makes the code difficult to understand and analyze.

In particular, the RAND_bytes convention causes problems at every call site that looks like:

    char buf[100];
    n = RAND_bytes(buf, sizeof buf);

This idiom causes so many warnings with Valgrind (and its commercial cousin, Purify) that there is an #ifdef to turn the behavior off:

    #ifndef PURIFY
                MD_Update(&m,buf,j); /* purify complains */
    #endif
 

The other two cases occur much more rarely: in RAND_poll, one would have to be reading from /dev/random when the kernel had very little randomness to spare, or calling RAND_load_file on a file that reported one size in stat but returned fewer bytes in read. When they do occur, a different instance of MD_update, the one in RAND_add, is on the stack trace reported by Valgrind.

http://research.swtch.com/openssl

[runeks]

Runeks - can you confirm I should send the 0.2 BTC bounty to 1runeksijzfVxyrpiyCY2LCBvYsSiFsCm?

Yes, thank you.

[SgtSpike]

Runeks - can you confirm I should send the 0.2 BTC bounty to 1runeksijzfVxyrpiyCY2LCBvYsSiFsCm?

Yes, thank you.

Done!

[runeks]

Runeks - can you confirm I should send the 0.2 BTC bounty to 1runeksijzfVxyrpiyCY2LCBvYsSiFsCm?

Yes, thank you.

Done!

Received! Thank you very much sir.

[changjixiong]

hoho, I am searching for a key genarate program use python, here it is