How does the recent patched key image exploit work in practice?

Question

For more info https://getmonero.org/2017/05/17/disclosure-of-a-major-bug-in-cryptonote-based-currencies.html This has been patched months ago and was never exploited which can be proven by running a node because it checks every transaction's key image to see if this exploit was executed and nodes now reject blocks containing transactions with this exploit so it is safe but I am interested in how the key image could be manipulated to do this

Answer 1

Given a finite group of integers, any group element Z in a group of order n, Z^n will always equal the identity element (order == number of elements in group). ECC has an equivalent abstraction - multiplying any point in a finite group by the order of the group will result in the identity element. The identity element is analogous to zero in the set of integers; P + 0 = P will always be true. And the property is commutative, if a*L = 0 then a*(L+P) = a*L + a*P = a*P.

The original equation (ringct differs slightly, but that does not matter) for key image verification is R = r*H(P) + c*I. H(P) is a cryptographic hash of the public key, c cannot be chosen by the attacker (random oracle value from a cryptographic hash), I is the key image, and r is the value that signer uses to prove ownership AND uniqueness of the signature (there is a similar equation to prove ownership of the public key that I didn't list). If an attacker can find a second point on the curve, U, where c*I = c*U then funds can be spent twice. Given all of the information above, an attacker wants to find a U such that c*U = c*L + c*I = 0 + c*I = c*I.

There are points that satisfy the equation for the curve, but are not in the group specified by Ed25519 (they are in a "subgroup"). Some of these points are in a group whose order is divisible by 8. If one of these points is selected as the key image, when the "random oracle value" (c) is a multiple of the subgroup order it will cause the key image verification to map back to the "correct" point due to the identity cancellation.

So take a valid key image, and add a point whose group order is divisible by 8 (2, 4, 8). Then you have a 1/(2,4,8) probability of getting a c which will map to the same point as the "real" key image. The check added by Monero ensures that the key image point is in the correct group, so that these "equivalent" tags are rejected.

Answer 2

Looks like it was being exploited on Bytecoin

For example, these 2 transactions spend the output 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 twice!

http://chainradar.com/bcn/transaction/cef289d7fab6e35ac123db8a3f06f7675b48067e0dff185c72b140845b8b3b23

http://chainradar.com/bcn/transaction/7e418cc77935cc349f007cd5409d2b6908e4130321fa6f97ee0fee64b000ff85

Notice how the key image differs only in last 2 digits! That's because it's forged - ie 2 slighthly different key images for 1 output, allowing you to spend it twice by tricking the pre-patch node into thinking that both key images are valid for the given output. There can really be only 1 which can be checked only with a patched node, and one of those TX-es would become invalid.

Note that it's later patched in the code, but the patch applies only after Bytecoin block 1267000, so those double-spend transactions are still in the Bytecoin blockchain and have artificially inflated the supply.

Note that while I was writing this, there were some problems with chainradar block explorer and those transactions disappeared for a while! That doesn't mean that they're not in the blockchain (really, the only way to be sure is to run a Bytecoin node and check yourself if they're still there), but only that chainradar was not showing them (seem to be back now). Just in case, they can also be seen here:

https://minergate.com/blockchain/bcn/transaction/cef289d7fab6e35ac123db8a3f06f7675b48067e0dff185c72b140845b8b3b23

https://minergate.com/blockchain/bcn/transaction/7e418cc77935cc349f007cd5409d2b6908e4130321fa6f97ee0fee64b000ff85

Answer 3

The above answer by Lee Clagett is also helpful for understanding how the exploit on Bytecoin took place, which is different and less effective than the exploit discovered by MRL. The attacker first transferred funds from a valid Ed25519 point to a low-order point. Let us denote this low-order point as P. The signature for double-spend checking consists of a pair of scalars (c, r), and the verification procedure checks if the following equation holds:

c = Hs(Msg || c*P + r*G || c*I + r*Hp(P))

where I is the key image. In the usual case where P is a valid Ed25519 point, i.e. P = x*G with x being the secret key, I is supposed to be I = x*Hp(P), and there is an algorithm to generate (c, r) that satisfies the above equation using the secret key x.

On the other hand, in this exploited case, P is a low-order point and thus doesn't have a secret key. The attacker can also arbitrarily choose one of the low-order points as I and try to find r by brute force such that

c = Hs(Msg || r*G || r*Hp(P))

becomes multiple of the low order (8 in this case). Because both P and I are low-order points, the verification trivially checks:

Hs(Msg || c*P + r*G || c*I + r*Hp(P)) = Hs(Msg || r*G || r*Hp(P)) = c

Since there are only 8 low order points in the subgroup, the attacker tried to squeeze out the most profit from these 8 chances of double spend and quit.

Here's a detailed timeline:

Step 1 (testing):

• Transferring 9'999.99 BCN to a low-order destination 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 (in tx 4bf32408756a8c914f2dea12cb17b38400a8d4b9bf6edcced2c03fc23fb27a0d)
• Spending the above fund using a low-order key image c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa (in tx 56da63a36a60cc2151e322528f8685c927fdad9578a5678af8023f87dd27430c)
• (Note that this fund wasn't double-spent afterwards.)

Step 2 (triple spending):

• Transferring 62'999'999.99 BCN to a low-order destination 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 (in tx 2eb6eba0c298c9286accc0d9624173e8059bbeb09554aeb7ef1e2b7c373e3adb)
• Spending the above fund using a low-order key image c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a (in tx f5e6754d7859ff4abf7a9733d5852d5ba35a77cab3dff4bb929c626cf1737b5a)
• Spending the above fund using a low-order key image 0000000000000000000000000000000000000000000000000000000000000080 (in tx 17320545c428fe7d67ff2c8140eef5c970adfc5eecab978986ac8b4b12a1dd84)
• Spending the above fund using a low-order key image 0000000000000000000000000000000000000000000000000000000000000000 (in tx 85b477ca39976c1cf70c4bc5aa20c750859f9dbafcdba0a20aa79490cd9bdb1b)

Step 3 (quadruple spending):

• Transferring 188'999'999.99 BCN to a low-order destination 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 (in tx 07a09e3c26d8ffc2e890713a69974e943a23ef6ad65b3bcbfc2b0f0da1add8f4)
• Spending the above fund using a low-order key image 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 (in tx cef289d7fab6e35ac123db8a3f06f7675b48067e0dff185c72b140845b8b3b23)
• Spending the above fund using a low-order key image 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85 (in tx 7e418cc77935cc349f007cd5409d2b6908e4130321fa6f97ee0fee64b000ff85)
• Spending the above fund using the identity as the key image 0100000000000000000000000000000000000000000000000000000000000000 (in tx 5a3db49ef69e1f9dd9b740cabea7328cd3499c29fc4f3295bac3fa5e55384626)
• Spending the above fund using a low-order key image ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f (in tx 74298d301eb4b4da30c06989e0f7ff24a26c90bf4ffc4f2c18f34b7a22cf1136)