nullcon HackIM – 2017 – Crypto 1

Here is how to resolve the challenge “Breaking Brain” provided, during a CTF, by nullcon HackIM in February 2017. I took me more time than the Crypto 2… but I got it!

nullcon HackIM – 2017 – cryptopuzzle1
nullcon HackIM – 2017 – cryptopuzzle1

Very interesting challenge! I learned a lot about Bitcoin and the way they generate an address from a passphrase.

First, I got the bitcoin address from the QR code “17iUnGoZbFrGS7uU9z2d2yRT9BKgVqnKnn“.

After that, I made some researches regarding the bitcoin passphrase, private key,  public key, and the bitcoin address. I found this interesting link:

https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses

https://en.bitcoin.it/wiki/Wallet_import_format

I found also an interesting C++ program to get a public key (Bitcoin) from a private key (Bitcoin):


#include <stdlib.h>;
#include <stdio.h>;
#include <openssl/ec.h>;
#include <openssl/obj_mac.h>; // for NID_secp256k1

// for executable: gcc -lcrypto -std=c99 priv2pub.c -o priv2pub
// for dynamic lib: gcc -lcrypto -std=c99 -fPIC -shared -Wl,-soname,libpriv2pub.so.1 priv2pub.c -o libpriv2pub.so.1.0

// calculates and returns the public key associated with the given private key
// - input private key and output public key are in hexadecimal
// - output is null-terminated string
// form = POINT_CONVERSION_[UNCOMPRESSED|COMPRESSED|HYBRID]
unsigned char *priv2pub( const unsigned char *priv_hex,
point_conversion_form_t form )
{
 // create group
 EC_GROUP *ecgrp = EC_GROUP_new_by_curve_name( NID_secp256k1 );

 // convert priv key from hexadecimal to BIGNUM
 BIGNUM *priv_bn = BN_new();
 BN_hex2bn( &priv_bn, priv_hex );

 // compute pub key from priv key and group
 EC_POINT *pub = EC_POINT_new( ecgrp );
 EC_POINT_mul( ecgrp, pub, priv_bn, NULL, NULL, NULL );

 // convert pub_key from elliptic curve coordinate to hexadecimal
 unsigned char *ret = EC_POINT_point2hex( ecgrp, pub, form, NULL );

 EC_GROUP_free( ecgrp ); BN_free( priv_bn ); EC_POINT_free( pub );
 return ret;
}

// calculates and returns the public key associated with the given private key
// - input private key is in hexadecimal
// - output public key is in raw bytes
// form = POINT_CONVERSION_[UNCOMPRESSED|COMPRESSED|HYBRID]
unsigned char *priv2pub_bytes( const unsigned char *priv_hex,
point_conversion_form_t form,
unsigned char *ret )
{
 // create group
 EC_GROUP *ecgrp = EC_GROUP_new_by_curve_name( NID_secp256k1 );

 // convert priv key from hexadecimal to BIGNUM
 BIGNUM *priv_bn = BN_new();
 BN_hex2bn( &priv_bn, priv_hex );

 // compute pub key from priv key and group
 EC_POINT *pub = EC_POINT_new( ecgrp );
 EC_POINT_mul( ecgrp, pub, priv_bn, NULL, NULL, NULL );

 // convert pub_key from elliptic curve coordinate to bytes
 //  (first call gets the appropriate length to use)
 size_t len = EC_POINT_point2oct( ecgrp, pub, form, NULL, 0, NULL );
 EC_POINT_point2oct( ecgrp, pub, form, ret, len, NULL );

 EC_GROUP_free( ecgrp ); BN_free( priv_bn ); EC_POINT_free( pub );

 return ret;
}

int main( int argc, const unsigned char *argv[] )
{
 // get priv key from cmd line and compute put key
 unsigned char *pub_hex = priv2pub( argv[1], POINT_CONVERSION_UNCOMPRESSED );

 printf( "%s\n", pub_hex );

 free( pub_hex );

 return 0;
}

// testcase :
// $./priv2pub 18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725
// 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6

I used this C++ program combined with three Python scripts and a bash script (I know it is a mess!).

The process was like this:

  1. Python script “generate passphrases” to:
      • generate a bunch of passphrases;
      • generate the private key from theses passphrases;
      • write all generated private keys and passphrase to dedicate files;
    from hashlib import sha256
    import itertools
    
    f_hp = open('hashpassphrase', 'w')
    f_p = open('passphrase', 'w')
    
    passphrase = "ucoitsgr"
    
    list_passphrase = list()
    
    for subset in itertools.permutations(passphrase,8):
    	new_passphrase = "8ln"+''.join(subset)+"nl8"
    	sha = sha256(new_passphrase).hexdigest()
    	f_hp.write(sha+'\n')
    	f_p.write(new_passphrase+'\n')
    
    f_p.close()
    f_hp.close()
    
  2. Bash script “generate public keys“:
      • get the file generated before (private keys);
      • generate for each private key the corresponding public key via the C++ program;
      • write all public keys to a file;
    #!/bin/bash
    
    while IFS='' read -r line || [[ -n "$line" ]]; do
        ./bitcoin $line >> publickey
    done < "$1"
    
  3. Python script “generate addresses“:
      • get the file generated before (public keys);
      • generate for each public key the corresponding address;
      • check if is “17iUnGoZbFrGS7uU9z2d2yRT9BKgVqnKnn” in the list;
    import hashlib
    import base58
    
    f = ""
    with open('publickey') as f:
        content = f.readlines()
    
    f.close()
    
    # remove whitespace characters like `\n` at the end of each line
    content = [x.strip() for x in content]
    
    for publickey in content:
    	ripe = hashlib.new('ripemd160')
    	sha = hashlib.sha256(publickey.decode('hex')).hexdigest().decode('hex')
    	ripe.update(sha)
    	extended_ripe = "00"+ripe.hexdigest()
    	first_sha256 = hashlib.sha256(extended_ripe.decode('hex')).hexdigest()
    	second_sha256 = hashlib.sha256(first_sha256.decode('hex')).hexdigest()
    	last_ripe=extended_ripe+second_sha256[:8]
    	unencoded_string = str(bytearray.fromhex(last_ripe))
    	encoded_string = base58.b58encode(unencoded_string)
    	if encoded_string == "17iUnGoZbFrGS7uU9z2d2yRT9BKgVqnKnn":
    		# 5KjzfnM4afWU8fJeUgGnxKbtG5FHtr6Suc41juGMUmQKC7WYzEG
    		print "Address = "+encoded_string
    		print "Public key = "+publickey
    		break
    
    Address = 17iUnGoZbFrGS7uU9z2d2yRT9BKgVqnKnn
    Public key = 047663D087DD1DA8315644E0800B7651E0763B5FBF9A2388834DB0BBB282D5A1761FD8C993DD3EA7FA5CDB616B591FA391DC00BAFCE7E70FEB1A7002A10E9CA152
    

To know the private key linked to the public key found, you can enter this command:


cat -n publickey | grep "047663D087DD1DA8315644E0800B7651E0763B5FBF9A2388834DB0BBB282D5A1761FD8C993DD3EA7FA5CDB616B591FA391DC00BAFCE7E70FEB1A7002A10E9CA152"
  3284    047663D087DD1DA8315644E0800B7651E0763B5FBF9A2388834DB0BBB282D5A1761FD8C993DD3EA7FA5CDB616B591FA391DC00BAFCE7E70FEB1A7002A10E9CA152

You have the line on which line the public key is located in the file and after that, you can enter this command to find the private key in the other file:


head -3284 hashpassphrase | tail -1

fda5ca43c8573c06bc0f829f8cc5e4c3667c11388a87fa532d2669135866b2c4

Do the same with the passphrase file:


head -3284 passphrase | tail -1

8lnustorcginl8

Last step is to find the WIF address from the private key with a Python script “generate WIF address“:


import hashlib
import base58

privatekey = "fda5ca43c8573c06bc0f829f8cc5e4c3667c11388a87fa532d2669135866b2c4"

new_privatekey = "80"+privatekey

first_sha256 = hashlib.sha256(new_privatekey.decode('hex')).hexdigest()
second_sha256 = hashlib.sha256(first_sha256.decode('hex')).hexdigest()

fourfirstbytes = second_sha256[:8]
last_ripe = new_privatekey+fourfirstbytes
unencoded_string = str(bytearray.fromhex(last_ripe))
encoded_string = base58.b58encode(unencoded_string)
print "WIF = "+encoded_string

WIF = 5KjzfnM4afWU8fJeUgGnxKbtG5FHtr6Suc41juGMUmQKC7WYzEG

Here is the flag:

flag{5KjzfnM4afWU8fJeUgGnxKbtG5FHtr6Suc41juGMUmQKC7WYzEG}

I know it is a mess, but I needed to go right to the point and solve this challenge!

After this… I really do not want to have an account with such algorithm at Brainwallet 🙂

Do not hesitate to leave me comments! 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s