SHA2017 - Stolen Bitcoins (300pt)

Reverse engineer bitcoin script

August 6, 2017
reverse

Stolen Bitcoins (300pt)

Reverse

Description: Someone stole our Bitcoins, luckily we captured the transaction. Can you find the flag that will allow us to get them back?

Files:

stolenbitcoins.tgz
Decoded script for convenience: script.txt

Solution

Opening the archive reveals a transmission file with some encoded data:

01000000000100e40b5402000000f...

Since the description says this is a Bitcoin transaction, I tried decoding it with Chain Query which revealed the following information:

{
	"result": {
		"txid": "3997ec296bdc4d7c521369c64d84ebb170cf9263ebc40d2b568e22059b02f0f5",
		"hash": "3997ec296bdc4d7c521369c64d84ebb170cf9263ebc40d2b568e22059b02f0f5",
		"size": 672,
		"vsize": 672,
		"version": 1,
		"locktime": 0,
		"vin": [

		],
		"vout": [
			{
				"value": 100.00000000,
				"n": 0,
				"scriptPubKey": {
					"asm": "0 10 OP_PICK 23 OP_PICK OP_ADD 99 OP_EQUAL OP_ADD 33 OP_PICK 21 OP_PICK OP_ADD 198 OP_EQUAL OP_ADD 37 OP_PICK 98 OP_ADD 206 OP_EQUAL OP_ADD 29 OP_PICK 25 OP_PICK OP_ADD 104 OP_EQUAL OP_ADD 26 OP_PICK 29 OP_PICK OP_ADD 148 OP_EQUAL OP_ADD 6 OP_PICK 3 OP_PICK OP_ADD 157 OP_EQUAL OP_ADD 30 OP_PICK OP_RIPEMD160 412fc6097e62d5c494b8df37e3805805467d1a2c OP_EQUAL OP_ADD 13 OP_PICK 11 OP_PICK OP_ADD 105 OP_EQUAL OP_ADD 32 OP_PICK 34 OP_PICK OP_ADD 155 OP_EQUAL OP_ADD 1 OP_PICK 113 OP_ADD 238 OP_EQUAL OP_ADD 18 OP_PICK 32 OP_PICK OP_ADD 149 OP_EQUAL OP_ADD 5 OP_PICK 3 OP_PICK OP_ADD 157 OP_EQUAL OP_ADD 2 OP_PICK 4 OP_PICK OP_ADD 112 OP_EQUAL OP_ADD 9 OP_PICK 34 OP_PICK OP_ADD 158 OP_EQUAL OP_ADD 25 OP_PICK 30 OP_PICK OP_ADD 149 OP_EQUAL OP_ADD 4 OP_PICK 11 OP_PICK OP_ADD 148 OP_EQUAL OP_ADD 21 OP_PICK 17 OP_PICK OP_ADD 111 OP_EQUAL OP_ADD 36 OP_PICK 22 OP_ADD 119 OP_EQUAL OP_ADD 27 OP_PICK 17 OP_PICK OP_ADD 106 OP_EQUAL OP_ADD 22 OP_PICK 17 OP_PICK OP_ADD 105 OP_EQUAL OP_ADD 35 OP_PICK 12 OP_ADD 115 OP_EQUAL OP_ADD 38 OP_PICK 111 OP_ADD 213 OP_EQUAL OP_ADD 8 OP_PICK 23 OP_PICK OP_ADD 106 OP_EQUAL OP_ADD 31 OP_PICK 7 OP_PICK OP_ADD 151 OP_EQUAL OP_ADD 12 OP_PICK 28 OP_PICK OP_ADD 148 OP_EQUAL OP_ADD 34 OP_PICK 53 OP_ADD 176 OP_EQUAL OP_ADD 28 OP_PICK 22 OP_PICK OP_ADD 106 OP_EQUAL OP_ADD 19 OP_PICK 4 OP_PICK OP_ADD 108 OP_EQUAL OP_ADD 23 OP_PICK OP_RIPEMD160 c47907abd2a80492ca9388b05c0e382518ff3960 OP_EQUAL OP_ADD 15 OP_PICK 18 OP_PICK OP_ADD 155 OP_EQUAL OP_ADD 11 OP_PICK OP_RIPEMD160 8e95e8ccac6c8eb91b8a7a8f02bca2fa2268d4b2 OP_EQUAL OP_ADD 16 OP_PICK 21 OP_PICK OP_ADD 152 OP_EQUAL OP_ADD 3 OP_PICK 34 OP_PICK OP_ADD 156 OP_EQUAL OP_ADD 17 OP_PICK 3 OP_PICK OP_ADD 157 OP_EQUAL OP_ADD 24 OP_PICK 20 OP_PICK OP_ADD 106 OP_EQUAL OP_ADD 7 OP_PICK OP_RIPEMD160 38f77e12c50a398d5eae85c9408667f971d09d09 OP_EQUAL OP_ADD 14 OP_PICK 29 OP_PICK OP_ADD 107 OP_EQUAL OP_ADD 20 OP_PICK 23 OP_PICK OP_ADD 147 OP_EQUAL OP_ADD OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP OP_NIP 38 OP_EQUAL",
					"hex": "4c01004c010a794c011779934c016387934c0121794c011579934c02c60087934c0125794c0162934c02ce0087934c011d794c011979934c016887934c011a794c011d79934c02940087934c0106794c010379934c029d0087934c011e79a64c14412fc6097e62d5c494b8df37e3805805467d1a2c87934c010d794c010b79934c016987934c0120794c012279934c029b0087934c0101794c0171934c02ee0087934c0112794c012079934c02950087934c0105794c010379934c029d0087934c0102794c010479934c017087934c0109794c012279934c029e0087934c0119794c011e79934c02950087934c0104794c010b79934c02940087934c0115794c011179934c016f87934c0124794c0116934c017787934c011b794c011179934c016a87934c0116794c011179934c016987934c0123794c010c934c017387934c0126794c016f934c02d50087934c0108794c011779934c016a87934c011f794c010779934c02970087934c010c794c011c79934c02940087934c0122794c0135934c02b00087934c011c794c011679934c016a87934c0113794c010479934c016c87934c011779a64c14c47907abd2a80492ca9388b05c0e382518ff396087934c010f794c011279934c029b0087934c010b79a64c148e95e8ccac6c8eb91b8a7a8f02bca2fa2268d4b287934c0110794c011579934c02980087934c0103794c012279934c029c0087934c0111794c010379934c029d0087934c0118794c011479934c016a87934c010779a64c1438f77e12c50a398d5eae85c9408667f971d09d0987934c010e794c011d79934c016b87934c0114794c011779934c029300879377777777777777777777777777777777777777777777777777777777777777777777777777774c012687",
					"type": "nonstandard"
				}
			}
		]
	},
	"error": null,
	"id": null
}

Here we can see that it is a transaction to pay a lot of bitcoins to a single utxo with a suspiciously long script.

For those who are unfamiliar: when you send bitcoins to someone, you don’t actually send it to their account or address. Instead, you provide a script (also known as a “locking script” or “scriptPubKey”) written in Bitcoin’s appropriatly named scripting language: Script.

In order for someone to later spend this utxo, they must be able to validate the script. Essentially, this means they will provide another script (the “unlocking script” or “scriptSig”) that is concatenated before the locking script. If the entire program runs without failure and terminates with a non-zero value at the top of the stack, the transaction is valid.

Normally, people will use one of a few common scripts such as Pay-to-Public-Key-Hash (P2PKH) or Pay-to-Multisig (P2MS) which have the same effect as actually sending bitcoins to an address. However, this is not a requirement.

The Script

While the script looks very intimidating at first glance, it can be broken down and understood.

We start with a single zero that just pushes the value zero onto the stack:

Then the following type of pattern repeats:

10 OP_PICK 
23 OP_PICK 
OP_ADD 
99 
OP_EQUAL 
OP_ADD

Let’s break it down and see what it does. I’ll go opcode by opcode and keep track of the stack. First, we have a stack containing some previous values (that we have to figure out) followed by that zero:

(I’m drawing a stack that grows upwards)

--- << base
0
val_1
val_2
val_3
...
val_n

The OP_PICK code pops n off the top of the stack and then copies the value n bytes back to the top of the stack. So after performing:

10 OP_PICK

the stack looks like:

val_10
--- << base
0
val_1
val_2
val_3
...
val_n

Then we perform another OP_PICK, however since the stack has grown by one, we are actually selecting the n-1th value. (This tripped me up for a while). So our stack now looks like this:

val_22
val_10
--- << base
0
val_1
val_2
val_3
...
val_n

Next, we perform a OP_ADD which simply pops two values off the stack, adds them, then pushes the sum back on:

val_10 + val_22
--- << base
0
val_1
val_2
val_3
...
val_n

Then we push a constant onto the stack: 99.

99
val_10 + val_22
--- << base
0
val_1
val_2
val_3
...
val_n

Next, we perform an OP_EQUAL which pops two values off the stack and checks if they are equal. If they are, a 1 is pushed onto the stack. Otherwise, a 0 is pushed on.

(val_10 + val_22 == 99 ? 1 : 0)
--- << base
0
val_1
val_2
val_3
...
val_n

Finally, an OP_ADD takes this 1 or 0 value and adds it to the zero from earlier.

In this way, the stack pointer has been reset to the original position for the next block:

33 OP_PICK 
21 OP_PICK 
OP_ADD 
198 
OP_EQUAL 
OP_ADD

Now, what conditions have to be met in order to validate the transaction? Well, after a whole bunch of these code sections, we see the following:

OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP OP_NIP OP_NIP 
OP_NIP OP_NIP 

38 
OP_EQUAL

The OP_NIP operation removes the second value from the top of the stack. So as we go operation by operation, the values from before are removed and we are left with just the sum value:

--- << base
sum

Then we push 38 and check for equality. Now in order for the transaction to be valid, the script must end with a non-zero value at the top of the stack. So our sum must be equal to 38. Since there are exactly 38 code sections, all of the equality checks must be true.

Essentially this leaves us with a bunch of equations we have to satisfy to determine the flag.

Other section types:

There are two other types of sections that maintain the stack frame:

Adding with a constant

1 OP_PICK 
113 
OP_ADD 
238 
OP_EQUAL 
OP_ADD

In this case, we check if val_1 + 113 == 238. Since this must be true, we can determine that val_1 is equal to 125 or '}'. Since flags are of the format flag{md5} we can deduce that the flag is stored backwards from the top of the stack like so:

}
val_2
val_3
...
val_33
{
g
a
l
f

Hash Check

The third block type is a hash comparison such as:

30 OP_PICK 
OP_RIPEMD160 
412fc6097e62d5c494b8df37e3805805467d1a2c 
OP_EQUAL 
OP_ADD

This is checking whether ripemd160(val_30) == '412fc6097e62d5c494b8df37e3805805467d1a2c'. Since we know that val_30 is a single ascii character, we only have to brute force a space of 2^7 which can be done like so:

import hashlib

def find(hash_string):
    for i in range(32,128):
        c = chr(i)
        h = hashlib.new('ripemd160')
        h.update(c)

        if h.hexdigest() == hash_string:
            return c

    return ''

>>> find('412fc6097e62d5c494b8df37e3805805467d1a2c')
'2'

The Boring Part

Now, we have a series of equations and all that’s left to do is find a flag such that all the equations are true. Unfortunately, after you go through and fill in all the constant ones, none of the other characters are forced to any value.

Example equations below (left side is character index, right side is raw value)

10 + 22 = 99
13 + 10 = 105
4 + 10 = 148
33 + 20 = 198
29 + 24 = 104
26 + 28 = 148
6 + 2 = 157
5 + 2 = 157
...

It felt kind of like a less exciting sudoku puzzle.

In fact, I found two distinct sets of characters that had no equations comparing them to the other set.

After I had gone through all the equations, I actually had three flags that appeared to pass all the checks:

flag{e612123bd7128a3df7598a6198fffc97}
flag{e622223bc6128a4ce7698a6198feec88}
flag{e632323bb5128a5bd7798a6198fddc79}

Note: I’m not sure if I made a mistake here or if there was a slight logic error in the problem creation

As the saying goes, “the third flag’s the charm,” or something like that.