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

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

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.

• Can someone add a link to the place in the code where the new subgroup check is done? – relG Sep 23 '18 at 12:17
• Perhaps "whose group order divides 8"? Group orders that are divisible by 8 would be 8, 16, 24, etc... – Nicholas Pipitone Nov 11 '18 at 18:47

Looks like it was being exploited on Bytecoin For example, these 2 transactions spend the output 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 twice!

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

• Interesting these transactions should have been hidden, given that chainradar and bytecoin are said to be affiliated. – user36303 May 20 '17 at 12:00
• seems like chainradar is having some difficulties in general, looking up any BCN block/TX doesn't seem to work at times – JollyMort May 20 '17 at 12:11

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):

Step 2 (triple spending):

Step 3 (quadruple spending):