Solving CaptureTheEther - Part 4 of 5 - Accounts
Overview
These challenges are meant to teach about the fine details of EVM-compatible networks accounts, contract deployment and cryptographic key pairs.
There's a good (albeit a bit outdated) book that explains the working of the Ethereum ecosystem in a good and easy-to-understand fashion: Antonopoulos' and Wood's Mastering Ethereum. Most solutions for this category come from chapters 4, 5 and 7. Still, I encourage you to find more and updated bibliography, as Ethereum is constantly evolving.
Info
All my solutions to CaptureTheEther were coded some time ago, while I was still new at Solidity and EVM. All of them work, however they certainly don't meet any good coding recommendation whatsoever.
It was part of my learning path, and I don't intend to update them as it serves me (and hopefully you too!) as a remainder that learning is a never-ending process that rewards you when you look back and see your real progress.
The complete code for these solutions is at my CTE-Solutions github repo.
Fuzzy identity
This is a contract that requires some specific conditions to be called, in particular, the transactions must come from an account whose address includes the badc0de hexadecimal string somewhere, and that account must implement the name() function that returns the string smarx
Contract analysis
The contract requires the player to call authenticate(), so that bool isComplete is set to true. To successfully call that function, there are two checks that must be passed. The first one requires that the msg.sender implements the IName interface, and that name() returns smarx. The second check requires that the originating account has badc0de somewhere in its address.
1pragma solidity ^0.4.21;
2
3interface IName {
4 function name() external view returns (bytes32);
5}
6
7contract FuzzyIdentityChallenge {
8 bool public isComplete;
9
10 function authenticate() public {
11 require(isSmarx(msg.sender));
12 require(isBadCode(msg.sender));
13
14 isComplete = true;
15 }
16
17 function isSmarx(address addr) internal view returns (bool) {
18 return IName(addr).name() == bytes32("smarx");
19 }
20
21 function isBadCode(address _addr) internal pure returns (bool) {
22 bytes20 addr = bytes20(_addr);
23 bytes20 id = hex"000000000000000000000000000000000badc0de";
24 bytes20 mask = hex"000000000000000000000000000000000fffffff";
25
26 for (uint256 i = 0; i < 34; i++) {
27 if (addr & mask == id) {
28 return true;
29 }
30 mask <<= 4;
31 id <<= 4;
32 }
33
34 return false;
35 }
36}
Vulnerability / Attack vector
There's no real vulnerability here. This challenge is meant to understand the inner workings of EVM CREATE and/or CREATE2 opcodes.
Solution
The solution to this level is divided in two parts: first, we have to implement a contract that meets the isSmarx(address) requisites, and then that contract should be deployed in an address that passes the isBadCode(address) checks. That contract should have a public function that acts as a proxy to call authenticate().
The code for the contract I used:
1contract Solution is IName {
2 function name() external view returns (bytes32) {
3 return bytes32("smarx");
4 }
5
6 function solve(address target) public {
7 FuzzyIdentityChallenge(target).authenticate();
8 }
9}
Now, to deploy this contract to an address with badc0de hex string somewhere in its address, there are two approaches:
- Using
CREATEopcode, manipulating the deployer address' nonce. - Using
CREATE2opcode, manipulating the seed value.
I went for the second option, because incrementing my player address' nonce would imply a lot of transactions and a waste of time and gas (even in a testnet, it's a quite scarce resource!).
This python script calculates the CREATE2 deployment address for a contract, given its bytecode, the deployer's address, and salt value:
1from web3 import Web3
2
3deployingAddr = DEPLOYING_ADDRESS
4addrbytes = bytes.fromhex(deployingAddr)
5bytecode = CONTRACT_BYTECODE
6hashbytecode = Web3.keccak(hexstr=bytecode)
7salt = 1
8
9header = bytes.fromhex("ff") + addrbytes
10
11while 1:
12 salthex = Web3.toHex(salt)[2:]
13 saltbytes = '0' * (64 - len(salthex)) + salthex
14
15 predicted = Web3.toHex(Web3.keccak( header + bytes.fromhex(saltbytes) + hashbytecode))[-40:]
16
17 if "badc0de" in predicted:
18 print("0x" + predicted)
19 print(saltbytes)
20 exit()
21 else:
22 salt = salt+1
The deploying address is another contract, shown below:
1contract Deployer {
2
3 function getBytecode() public view returns(bytes memory) {
4 return abi.encodePacked(type(Solution).creationCode);
5 }
6
7 function predictAddress(bytes32 salt) public view returns(address) {
8 bytes memory code = abi.encodePacked(type(Solution).creationCode);
9 address predictedAddress = address(uint160(uint(keccak256(abi.encodePacked(bytes1(0xff), address(this), salt, keccak256(code))))));
10 return predictedAddress;
11 }
12
13 function deployContract(bytes32 salt) public returns(address) {
14 bytes memory code = abi.encodePacked(type(Solution).creationCode);
15 address addr;
16 assembly {
17 addr := create2(0, add(code, 0x20), mload(code), salt)
18 }
19 return(addr);
20 }
21
22}
The while loop in the Python script bruteforces the salt value until it finds a suitable one, that is, a value that generates an address with badc0de in it. Once that value is found, it is passed as argument to the deployContract(bytes32) function of the Deployer contract.
If everything works as expected, an instance of the Solution contract will be deployed to an address that meets the requirements, and the challenge is solved by calling solve(address) in that contract, with the argument being the address of the original challenge contract.
Conclusions
The CREATE and CREATE2 opcodes are a great tool to precalculate the deployment address of a contract before deploying it. This has some useful consequences, such as being able to pre-fund a contract before it gets deployed, or (pretty much like this example) the generation of vanity addresses.
Public key
This challenge requires the player to find the public key of an account, given in the contract. There's a hint, reminding us that the address is the last 20 bytes of the hash of the public key.
Contract analysis
The contract is very simple and short:
1pragma solidity ^0.4.21;
2
3contract PublicKeyChallenge {
4 address owner = 0x92b28647ae1f3264661f72fb2eb9625a89d88a31;
5 bool public isComplete;
6
7 function authenticate(bytes publicKey) public {
8 require(address(keccak256(publicKey)) == owner);
9
10 isComplete = true;
11 }
12}
The owner address is a constant in the code, and the authenticate(bytes) function checks that the keccak256() hash of the public key, casted to address type, equals the owner's address.
Vulnerability / Attack vector
The goal is to recover the public key of the given address. Since reversing keccak256() is not possible, there should be another way to get the key back.
Reading Ethereum's yellow paper and Mastering Ethereum book to understand the key generation mechanics, it's easy to calculate the public key back from a signed transaction.
Solution
If there are transactions signed with the private key for that address, using the v, r and s values of the signature, and the message values previous to signing, it is possible to easily get back the public key.
To find some signed transaction, it's useful to visit the Etherscan page for the address. Once a transaction is found, this script regenerates the message previous to signature, and gets back the public key.
1rom eth_account._utils.signing import extract_chain_id, to_standard_v
2from eth_account._utils.transactions import serializable_unsigned_transaction_from_dict
3
4from web3.auto.infura.ropsten import w3
5from web3 import Web3
6
7tx = w3.eth.getTransaction('0xabc467bedd1d17462fcc7942d0af7874d6f8bdefee2b299c9168a216d3ff0edb')
8print(Web3.toHex(tx.hash))
9
10# From the tx, we need the v, r and s values to generate the signature for that key
11v = to_standard_v(extract_chain_id(tx.v)[1])
12r = Web3.toInt(tx.r)
13s = Web3.toInt(tx.s)
14signature = w3.eth.account._keys.Signature(vrs=(v, r, s))
15
16# The signature.recover_public_key_from_msg_hash() needs the msg hash before signature, so
17# now we need to regenerate the message hash from the transaction values
18# This hash involves the gas price, nonce, chainId, message data, value, gas and destination address
19tx_msg = {}
20tx_msg['gasPrice'] = tx['gasPrice']
21tx_msg['nonce'] = tx['nonce']
22tx_msg['chainId'] = extract_chain_id(tx.v)[0]
23tx_msg['data'] = tx['input']
24tx_msg['value'] = tx['value']
25tx_msg['gas'] = tx['gas']
26tx_msg['to'] = tx['to']
27
28# Using eth_account._utils.transactions functions we can serialize the RLP encoding of the message to recover the pk
29# https://github.com/ethereum/eth-account/blob/5558be9ce3fef8fe396c45bb744e377c7af5333d/eth_account/_utils/legacy_transactions.py
30pre_sign = serializable_unsigned_transaction_from_dict(tx_msg)
31print(signature.recover_public_key_from_msg_hash(pre_sign.hash()))
Note that you will need a valid Infura key as environment variable before using the code.
Conclusions
The public key infrastructure is what keeps Ethereum (and other cryptocurrency networks) secure. Even if you don't need to know the deep details of its workings to use the networks, it is indeed a good sport to understand the underlying security aspects of the system.
Account takeover
This is a step further from the previous contract. To solve this level, the authenticate() function must be called from the owner account. That is, we need to impersonate another account, without knowing its private key.
Contract analysis
Similar to the previous one, this contract has a single public function authenticate(), that is meant to be called from the address of the owner, hardcoded into the contract.
1pragma solidity ^0.4.21;
2
3contract AccountTakeoverChallenge {
4 address owner = 0x6B477781b0e68031109f21887e6B5afEAaEB002b;
5 bool public isComplete;
6
7 function authenticate() public {
8 require(msg.sender == owner);
9
10 isComplete = true;
11 }
12}
Vulnerability / Attack vector
Recovering some account's private key is by all means impossible. If it wasn't, Ethereum (and all the other EVM-compatible networks) would not be secure, allowing anyone to spend other people's ether.
However, this is a game, so there must be a solution. The signature algorithm used in Ethereum is called Elliptic Curve Digital Signature Algorithm (or ECDSA for brevity). The concept is that, given a secret (or private) key generated securely, a public key can be derived. Using the private key the owner is able to sign messages, and using the public key anyone is able to verify that the message was signed by that secret key.
This signing process generates for each signature, two values named r and s, used for the signing and verification process. The flaw lies in the fact that if two signatures share the same r value, the secret key can be regenerated using maths. For more information about this statement, Mastering Ethereum chapter 06 is a good starting point.
Solution
In a similar approach to the previous level, the first step is to check the owner address' Etherscan page in order to see the transactions signed with the account's private key, that is, the outgoing transactions from the account.
As explained in the previous section, the two first transactions originated from this account share the same r. This can be checked with the following script, line 52.
1import ecdsa
2import libnum
3import eth_account
4
5from eth_account._utils.signing import extract_chain_id, to_standard_v
6from eth_account._utils.transactions import serializable_unsigned_transaction_from_dict
7
8from web3.auto.infura.ropsten import w3
9from web3 import Web3
10
11contract_address = DEPLOYED_CONTRACT_ADDRESS
12contract_abi = DEPLOYED_CONTRACT_ABI
13contract_instance = w3.eth.contract(address=contract_address, abi=contract_abi)
14
15# Auxilliary function to create a pre-signature RLP encoded transaction
16def createUnsignedTransaction(transaction):
17 tx_msg = {}
18 tx_msg['gasPrice'] = transaction['gasPrice']
19 tx_msg['nonce'] = transaction['nonce']
20 tx_msg['chainId'] = extract_chain_id(transaction.v)[0]
21 tx_msg['data'] = transaction['input']
22 tx_msg['value'] = transaction['value']
23 tx_msg['gas'] = transaction['gas']
24 tx_msg['to'] = transaction['to']
25
26 return serializable_unsigned_transaction_from_dict(tx_msg)
27
28def solveChallenge(secret_key):
29 account = '0x6B477781b0e68031109f21887e6B5afEAaEB002b'
30
31 # Get nonce and create a new transaction
32 nonce = w3.eth.getTransactionCount(account)
33 txn = contract_instance.functions.authenticate().buildTransaction({
34 'gas': 2000000,
35 'gasPrice': w3.toWei('2', 'gwei'),
36 'nonce': nonce
37 })
38
39 # Sign the transaction and send it to miners
40 txn_signed = w3.eth.account.sign_transaction(txn, private_key=secret_key)
41 txn_hash = w3.eth.send_raw_transaction(txn_signed.rawTransaction)
42
43 print('Transaction sent: ' + Web3.toHex(txn_hash))
44
45G = ecdsa.SECP256k1.generator
46order = int(G.order())
47
48tx1 = w3.eth.getTransaction('0xd79fc80e7b787802602f3317b7fe67765c14a7d40c3e0dcb266e63657f881396')
49tx2 = w3.eth.getTransaction('0x061bf0b4b5fdb64ac475795e9bc5a3978f985919ce6747ce2cfbbcaccaf51009')
50
51# Check that they have effectively the same r
52if Web3.toInt(tx1.r) == Web3.toInt(tx2.r):
53 print('Both share r: ' + str(Web3.toHex(tx1.r)) + '\n')
54else:
55 exit()
56
57# First tx hash reconstruction
58presign1 = createUnsignedTransaction(tx1)
59presign2 = createUnsignedTransaction(tx2)
60
61# Values used later
62z1 = Web3.toInt(presign1.hash())
63z2 = Web3.toInt(presign2.hash())
64
65r1 = Web3.toInt(tx1.r)
66r2 = Web3.toInt(tx2.r)
67
68s1 = Web3.toInt(tx1.s)
69s2 = Web3.toInt(tx2.s)
70
71# Now we need both hashes and both S values, to calculate k
72# k = (hash1 - hash2) / (s1 - s2) --- the s1 and s2 signs can be + or -, so all combinations should be tested
73dif_hashes = z1 - z2
74sign_variations = [s1 - s2, s1 + s2, -s1 - s2, -s1 - s2]
75
76for variation in sign_variations:
77 k = (dif_hashes * libnum.invmod(variation, order)) % order
78 d = (((s1 * k - z1) % order) * libnum.invmod(r1, order)) % order
79
80 a = eth_account.Account.from_key(d)
81 if a.address == tx1['from']:
82 print('Secret key : ' + str(Web3.toHex(d)))
83 solveChallenge(d)
84 exit()
The full solution gets both transactions from the blockchain, and recreates the messages previous to signature. Next, it tests the possible variations for the sign of the denominator of the equation: given 2 values for s1 and s2, every possible variation of positive and negative signs in those values could generate a valid key.
The maths are explained here and here. The code above is my implementation of the ECDSA calculations shown in those links.
Again, you will need an Infura key as environment variable, and replace the values in lines 11 and 12 with the correct address and ABI for the contract. The script function solveChallenge(secret_key) will execute the transaction from the owner account, and solve the challenge.
Conclusions
Knowing the possible flaws, or rather, weaknesses in the algorithms makes us better at enforcing security in our implementations. However, as the usual security procedure says, never try to implement your own version of an algorithm. Instead, use well-tested and secure libraries.