Capture the Coin — Blockchain Category Solutions
Capture the Coin — Blockchain Category Solutions
By Peter Kacherginsky, Mark Nesbitt, Joel Kenny, Don Yu
In this post we continue our coverage of solutions for the Capture the Coin competition that we ran during Defcon 2019. We will focus on the five challenges in the Blockchain category covering a variety of topics such as Bitcoin Scripting, cryptocurrency malware, Ethereum smart contracts, and wallet forensics.
Satoshi’s Secret
By Mark Nesbitt
When someone says that they “own” a certain number of bitcoins, what that means is that they are capable of signing a valid transaction that sends that number of bitcoins to someone else. Let’s take a closer look at how that actually works.
A bitcoin transaction has inputs and outputs. A new transaction identifies the outputs of previous transactions, which serve as the new transaction’s inputs.
Outputs are “locked” with a script made up of data and opcodes. In order to spend an output, the spending transaction supplies an “unlocking” script that is concatenated to the output script and evaluated according to stack-based rules. If the stack is left in a valid state, the transaction can spend the coins.
An example of a simple locking script could be:
<PUB_KEY> OP_CHECKSIG
In order to spend an output that has this locking script, the spending transaction must have an input with an unlocking script that provides a valid signature, resulting in the following script:
<SIG> <PUB_KEY> OP_CHECKSIG
All 3 items are pushed onto the stack. When evaluated, OP_CHECKSIG confirmed that <SIG> is valid for <PUB_KEY>. If the signature validates, OP_CHECKSIG returns “true” to the stack, resulting in a valid stack state. Thus, anyone with the ability to provide a valid signature for the <PUB_KEY> specified in the output locking script can spend the coins.
There are many different ways to write a locking script. Consider a slightly more complicated script:
OP_DUP OP_HASH160 <160 bit hash> OP_EQUALVERIFY OP_CHECKSIG
What would it take to spend this output? (Hint: Learn more about this here.)
Both of the examples above ultimately require the unlocking script to include a valid signature for a public key that is bound to the locking script. But that’s not a requirement of the bitcoin network — it’s just the best way to make sure that the ownership of coins is securely implemented. Consider the script below:
OP_HASH256 <256 bit hash> OP_EQUALVERIFY
Anyone that can provide data that, when hashed, equals the <256 bit hash> value, will be able to spend the coins. No private keys required!
Consider the following Bitcoin testnet transaction:
The script for this transaction is:
OP_HASH256 OP_PUSHBYTES_32 <64c9e17ec60cd8e074aa24fdb533b3147b651cc18d7c9bcd6b00ef483affc22f> OP_EQUAL
Anyone that can find a value that hashes to 64c9e1… can spend these coins.
So this challenge basically boils down to breaking SHA-256. You got this!
A strategy for trying to break a strong cryptographic hash function is to start randomly guessing. I’ll start with guessing “coinbase”.
In hex, “coinbase” is “636f696e62617365”.
Hide and Seek
In this puzzle you are presented with a seed phrase protecting a cryptocurrency wallet and a challenge to locate a hidden transaction associated with the wallet:
play fever bullet unlock error palm insect pottery tower torch memory liquid
Modern cryptocurrency wallets follow a set of standards to create backups and to generate keys: BIP-39, BIP-32, BIP-44, and SLIP-44.
The first standard is BIP-39: Mnemonic code for generating deterministic keys. It defines a way to encode a randomly generated entropy using common English language words. BIP-39 works by breaking up a 128–256 bit binary blobs into 11-bit chunks with each corresponding to an index in a wordlist. By looking up an index for each of the words in the mnemonic phrase above, it is possible to reconstruct the original random entropy and generate BIP-39 seed:
eb872c547351612701035f9a62a8c39d87c9f3af8fea5adc77bd3861384095407902f3c9e5b5d09ac422ed4e6b8c0ae7358c28b6ed40cf6e8b077775edb49fee
The next two standards are used to generate the actual private keys from the BIP-39 seed above. BIP-32: “Hierarchical Deterministic Wallets” defines a secure algorithm to generate an arbitrarily sized tree of private keys from a single master private key derived from a BIP-39 seed. The standard uses a special notation to define a key at any level in the tree. For example, m/0/1 defines the second grandchild derived from the first child derived from the master key. The table below illustrates some of the private keys derived from the first child:
m/0/0 — KxDTisYSXy8fwZBtxiXKNRCkipFviJLosSceTf7BXmC79xAqzDBW
m/0/1 — KzbaM51UVBognvXyuMMPTgrWnEZxdwTgZDqvmbf8SyqNyetVWGqm
m/0/2 — L5QG1cxQgawk7Xf8NSbwJFPbzz13uFuvMT9uGsxKgZuwHYsGC2iP
m/0/3 — KxiAyNsQKSZpTZUiQA81v59bEav7vj7odnvRVicdW8FvtGRTxZNn
BIP-44: Multi-Account Hierarchy for Deterministic Wallets and SLIP-0044 : Registered coin types for BIP-0044 standards builds on top of BIP-32 to define specific paths corresponding to different cryptocurrency types. The table below illustrates some of the common paths:
m/44'/0'/0'/0/0 — first Bitcoin address in the chain
m/44'/0'/0'/0/1 — second Bitcoin address in the chain
m/44'/1'/0'/0/0 — first Bitcoin Testnet address in the chain
m/44'/1'/0'/0/1 — second Bitcoin Testnet address in the chain
m/44'/2'/0'/0/0 — first Litecoin address in the chain
m/44'/3'/0'/0/0 — first Dogecoin address in the chain
Notice that all of the hierarchical wallets are in the 44’ tree. The extra ‘ (single quote) next to the number indicates that the particular tree branch is hardened.
As you can tell, a single mnemonic phrase provided in the challenge can produce an infinite number of addresses to review and look for hidden transactions. The challenge gives us a hint that the one transaction we are looking for is in the Bitcoin Testnet branch which can be defined as follows:
m/44'/1'/0'/0/[2³¹ addresses]
Below is a sample script which will bruteforce the address space and query a sample blockchain API to determine if any of the addresses have any transactions:
from bitcoinlib.wallets import HDWallet
from bitcoinlib.services.services import Service
SEED = “play fever bullet unlock error palm insect pottery tower torch memory liquid”
w = HDWallet.create(name=”Wallet”, keys=SEED, network=’testnet’)
for i in range(0,1000):
address = w.key_for_path(path=”m/44'/1'/0'/0/%d” % i).address
transactions = Service(network=’testnet’).gettransactions(address)
for t in transactions:
print(t.info())
Running the above on the command-line produces the following output (after some time):
$ python3 hideandseek.py 2>/dev/null
[..redacted..]
Inputs
- 2Mv1XoyfFa6cygsdVJ32iEA8HsWHeVWWtcY 1595764 731f64c418415ca4be54416361bcfcc9b606a5349b425342655bb8f2d3406b18 0
p2sh-segwit p2sh_p2wpkh; sigs: 0 (1-of-0) not validated
Outputs
- 2Mxm8UG8Cuf3NRnCS3bakhtTRLxYEBDfU2J 1416234 p2sh
- mygH814iJuKrg7tCY2fspCCpxtU3jrzDsd 179362 p2pkh
[..redacted..]
A single transaction was detected which paid mygH814iJuKrg7tCY2fspCCpxtU3jrzDsd 179362 Satoshis. Checking the exact amount on the website gives use the flag!
Evil Droid
By Joel Kenny
In this puzzle you’re given an Android malware sample and have to reverse engineer it to find the address it is sending crypto to. The malware is based on a technique used in Gustuff, a malware app that was discovered in the wild earlier this year.
To start, decompile the .apk. You can use JADX, and there is even an online version.
Looking at the app’s AndroidManifest.xml, you can see that it has an accessibility service.
<service android:label=”@string/accessibility_service_label” android:name=”com.capturethecoin.thestealer.SneakyService” android:permission=”android.permission.BIND_ACCESSIBILITY_SERVICE”>
<intent-filter>
<action android:name=”android.accessibilityservice.AccessibilityService”/>
</intent-filter>
<meta-data android:name=”android.accessibilityservice” android:resource=”@xml/accessibility_service_config”/>
</service>
An accessibility service on Android can enumerate views on the screen and can interact with them on the user’s behalf. The code for this service is in SneakyService.java. This code in onAccessibilityEvent()is going to replace a bitcoin address when the user enters it into a specific target app:
…
if (companion.isCryptoAddress(text)) {
String decryptMsg = Encryption.decryptMsg(f4b);
AccessibilityNodeInfo source2 = accessibilityEvent.getSource();
Intrinsics.checkExpressionValueIsNotNull(source2, str);
if (!TextUtils.equals(source2.getText(), decryptMsg)) {
accessibilityEvent = accessibilityEvent.getSource();
Intrinsics.checkExpressionValueIsNotNull(accessibilityEvent, str);
Intrinsics.checkExpressionValueIsNotNull(decryptMsg, “payload”);
performSetTextAction(accessibilityEvent, decryptMsg);
}
}
…
Now to find the flag you just have to evaluate the expression
Encryption.decryptMsg(f4b);
The quick and web based way is to use a Java Playground.
public class Encryption {
/* renamed from: a */
private static final byte[] f3a = new byte[]{(byte) 122, (byte) 61, (byte) 66, (byte) 31, (byte) 11, (byte) 0, (byte) 33, (byte) 84, (byte) 16, (byte) 68, (byte) 56, (byte) 77, (byte) 61, (byte) 66, (byte) 31, (byte)127, (byte) 66, (byte) 31, (byte)127, (byte) 42, (byte) 27, (byte) 3, (byte) 9, (byte) 17, (byte) 0, (byte) 33, (byte) 84, (byte) 31, (byte) 11, (byte) 31, (byte) 11, (byte) 31};
public static byte[] encryptMsg(String str) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, IllegalBlockSizeException, BadPaddingException {
Key secretKeySpec = new SecretKeySpec(f3a, “AES”);
Cipher instance = Cipher.getInstance(“AES/ECB/PKCS5Padding”);
instance.init(1, secretKeySpec);
return instance.doFinal(str.getBytes(StandardCharsets.UTF_8));
}
public static String decryptMsg(byte[] bArr) throws NoSuchPaddingException, NoSuchAlgorithmException, InvalidKeyException, BadPaddingException, IllegalBlockSizeException, UnsupportedEncodingException {
Key secretKeySpec = new SecretKeySpec(f3a, “AES”);
Cipher instance = Cipher.getInstance(“AES/ECB/PKCS5Padding”);
instance.init(2, secretKeySpec);
return new String(instance.doFinal(bArr), StandardCharsets.UTF_8);
}
}
class Playground {
public static final byte[] f4b = new byte[]{(byte) -92, (byte) 12, (byte) 23, (byte) 115, (byte) 84, (byte) 48, (byte) -125, (byte) -66, (byte) 40, (byte) 59, (byte) 105, (byte) 63, (byte) 19, (byte) 29, (byte) -93, (byte) -67, (byte) 92, (byte) 119, (byte) 69, (byte) -62, (byte)127, (byte) 35, (byte) 114, (byte) 85, (byte) 117, (byte) -5, (byte) -34, (byte) -94, (byte) -73, (byte) -97, (byte) 41, (byte) -78, (byte) 59, (byte) 13, (byte) -116, (byte) -103, (byte) -51, (byte) 53, (byte) -112, (byte) 25, (byte) -30, (byte) -76, (byte) 109, (byte) -52, (byte) -114, (byte) 118, (byte) -80, (byte) 0};
public static void main(String[ ] args) throws Exception {
String output = Encryption.decryptMsg(f4b);
System.out.println(output);
}
}
Running the code above yields the flag, a Bitcoin address: 1Ant1MoneyMoneyC1ub823ckj48m429vs3
Daily Double…spend
By Don Yu
Double spending is the canonical exploit in the blockchain space. There are multiple avenues to double spend a blockchain, but the overarching concept is the same: An attacker sends a transaction to some victim. The victim upon receiving the transaction assumes the transaction is in some finalized state. Under this assumption, the victim will payout the attacker in some form. (eg. Exchanging cryptocurrency for cash, or buying an item using cryptocurrency) The attacker then creates a new transaction that essentially “overwrites” the previous transaction by sending the same funds to a different location. At this point, the victim will have paid out because they believed they had received some amount of cryptocurrency, however the double spending transaction reroutes the cryptocurrency the victim originally received to some other target.
In order to double spend transactions in a UTXO blockchain, an attacker must first submit a transaction that sends some set of transaction outputs to the victim. Once the transaction is placed within some mined block, it can be double spent. The attacker constructs a double-spending transaction that consumes the same transaction outputs as the original transaction. The attacker must then induce some reorganization of the blockchain that removes the block with the original transaction and adds a block with the double-spending transaction to the blockchain. (For proof-of-work chains, the most common method is to 51% attack the blockchain) Afterwards, the original transaction is essentially “erased” from the blockchain history with the double-spending transaction taking its place.
In this challenge you are presented with a list of transactions including a reorg and a double spend hidden inside. If you understand the concept of a double spend, finding the solution is relatively straightforward. What would a double spend look like in the wild? It would most likely occur in a reorg event. Unfortunately, reorgs also happen naturally due to how blocks propagate through a mining network. This means that after finding a reorg, we must then search the reorg for a pair of transactions that consume the same UTXO.
Here’s a solution that I hacked together:
require “json”
require ‘pp’
file = File.open “./doublespend.json”
json_data = JSON.load file
def check_for_reorg(json_data)
(1..json_data.length — 1).each do |ind|
prev = json_data[ind — 1]
curr = json_data[ind]
if has_reorg?(prev, curr)
puts “Found reorg”
doublespend_check = check_for_doublespend(prev, curr)
exit(0)
end
end
puts “No reorg found”
end
def has_reorg?(prev, curr)
hashes_prev = prev.map {|block| block[‘hash’]}
hashes_curr = curr.map {|block| block[‘hash’]}
# Assume prev.length == curr.length
(1..prev.length — 1).each do |ind|
if prev[ind][‘hash’] != curr[ind — 1][‘hash’]
prev_txs = prev[ind][‘transactions’].map {|tx| tx[‘txid’]}
curr_txs = curr[ind — 1][‘transactions’].map {|tx| tx[‘txid’]}
return true
end
end
return false
end
def check_for_doublespend(prev, curr)
prev_txs = prev.reduce([]) {|base, block| base + block[‘transactions’]}
curr_txs = curr.reduce([]) {|base, block| base + block[‘transactions’]}
prev_txs.each do |target_tx|
lookup_res = lookup_tx(target_tx, curr_txs)
if lookup_res != []
PP.pp lookup_res
exit(0)
end
end
end
def lookup_tx(target_tx, transactions)
transactions.each do |candidate_tx|
if target_tx[‘in_txos’] == candidate_tx[‘in_txos’] && target_tx[‘receiver’] != candidate_tx[‘receiver’]
return [target_tx[‘txid’], candidate_tx[‘txid’]]
end
end
return []
end
check_for_reorg(json_data)
Tricky Ether
The Ethereum smart contract challenge is designed to educate players about common pitfalls in Solidity code. As part of the challenge, players are instructed to cause the smart contract to self-destruct. There is only one function that can be called that would cause that:
function destroyme() public {
require(msg.sender == owner);
selfdestruct(msg.sender);
}
Notice the require function which makes sure that only the contract owner can call it. The owner of the contract is set in the constructor and is set to the original contract creator:
constructor() public payable {
owner = msg.sender;
}
Normally, we would be stuck at this point if not for a suspiciously named function hackme which makes a delegatecall() to a user specified address and a hard-coded function identifier:
function hackme(address _address) public { _address.delegatecall(“0x12345678”);
}
Delegatecall is a unique function designed to call libraries while preserving calling contract’s context. Here is how it’s defined in Solidity docs:
Libraries are similar to contracts, but their purpose is that they are deployed only once at a specific address and their code is reused using the DELEGATECALL (CALLCODE until Homestead) feature of the EVM. This means that if library functions are called, their code is executed in the context of the calling contract, i.e. this points to the calling contract, and especially the storage from the calling contract can be accessed.
With this in mind, if we called the hackme() function with a library contract address and a function that modifies the local storage owner, then it would in fact modify the owner for the challenge contract.
There is one last piece of the puzzle and that is the hard-coded 0x12345678 parameter in the delegatecall function. The value is a low-level identifier used to select a specific function in the contract. Here is how it’s defined in Solidity docs:
The first four bytes of the call data for a function call specifies the function to be called. It is the first (left, high-order in big-endian) four bytes of the Keccak (SHA-3) hash of the signature of the function. The signature is defined as the canonical expression of the basic prototype, i.e. the function name with the parenthesised list of parameter types. Parameter types are split by a single comma — no spaces are used
With this in mind there may exist a function which hashed prototype produces the four bytes 0x12345678. We could try to brute-force the function prototype or manually patch it in our smart contract; however, we could also take a shortcut by using a Fallback function:
A contract can have exactly one unnamed function. This function cannot have arguments and cannot return anything. It is executed on a call to the contract if none of the other functions match the given function identifier (or if no data was supplied at all).
Using a fallback function and a custom contract, we can effectively override the challenge contract owner variable and execute the self-destruct function. Below is a sample Solidity contract for this purpose:
pragma solidity ^0.5.0;
contract Hackme {
address public owner;
function() external payable {
owner = msg.sender;
}
}
Conclusion
We hope you enjoyed solving challenges in this category and see you in the final part of the Capture the Coin solution series.
If the challenges in this blog look something you would like to do full time, join us at Coinbase to help build the most trusted brand in the Crypto here!
This website contains links to third-party websites or other content for information purposes only (“Third-Party Sites”). The Third-Party Sites are not under the control of Coinbase, Inc., and its affiliates (“Coinbase”), and Coinbase is not responsible for the content of any Third-Party Site, including without limitation any link contained in a Third-Party Site, or any changes or updates to a Third-Party Site. Coinbase is not responsible for webcasting or any other form of transmission received from any Third-Party Site. Coinbase is providing these links to you only as a convenience, and the inclusion of any link does not imply endorsement, approval or recommendation by Coinbase of the site or any association with its operators.
All images provided herein are by Coinbase.
Capture the Coin — Blockchain Category Solutions was originally published in The Coinbase Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.
OhNoCoinbase via https://ift.tt/2PblI7a @Coinbase, @Khareem Sudlow