CTF Defcon 2019 - CaptureTheCoin Write-up - Linkable payment 300

Defcon 2019 CTF Write-up - CaptureTheCoin

Website: https://capturethecoin.org/

Linkable Payments Score: 300

The Question:

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 log 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 kP'. The secret can have only small possible values. If we are able to learn the result kP'(from err_log.json), we then also learn k1 = k 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

The Code:

Logoctf/linkable_payment.py at master · vietjovi/ctfGitHub

Read more write-up at http://kubertu.com

Ref: https://www.nds.ruhr-uni-bochum.de/media/nds/veroeffentlichungen/2015/09/14/main-full.pdf https://web-in-security.blogspot.com/2015/09/practical-invalid-curve-attacks.html

NextInstall Zabbix Agent with only one command via Terminal

Last updated

Was this helpful?