Exploiting Low Order Generators in One-Time Ring Signatures

Last week the Monero team disclosed a major bug in CryptoNote based cryptocurrencies (reddit thread) which could be used to create “create an infinite amount of coins”. Monero itself was quietly fixed in February (release, pull request) and the since then every user syncing the blockchain from scratch validates that it was never exploited in Monero. However, it was used in CryptoNote based shitcoin ByteCoin to create about 700 million coins out of thin air.

There are already a few good explanations of the bug, for example at the Monero StackExchange and the modern crypto mailing list. This article gives additional background about the signature scheme and the properties of the curve that allowed this bug to slip in.

Apart from the value at stake, this bug is interesting because it shows the risks of breaking a specialized cryptosystems such as Ed25519 apart and apply the parts in other contexts. Ed25519 is designed for plain cryptographic signatures and the curve it is based on is used in CryptoNote to implement one-time ring signatures. In contrast to a regular signature scheme, one-time ring signatures using the curve require that part of the signature does not generate a small subgroup. Ensuring this is necessary when using curves with a cofactor. CryptoNote did not do that.

Hash-based ring signatures

A ring signature proves that the signer is among a set of public keys (aka “the ring”), without revealing which public key belongs to the signer. The construction used in CryptoNote/Monero and also for example in Confidential Transactions is based on hash rings.

For simplicity assume that for now the ring only consists of 1 key, which essentially reduces the scheme to a Schnorr signature. As usual, G is a generator of cyclic group in which the discrete logarithm is hard and we’re using additive notation for group operations. Then the signature scheme consists of the of the following three algorithms (keygen, sign, verify):

keygen:
draw scalar x uniformly at random
P <- x*G
publish public key P

sign message m (ring size 1):
draw scalar k uniformly at random
e <- hash(m, k*G)
s <- k - e*x
publish signature (e, s)

verify signature (e, s) over message m for public key P (ring size 1):
e == hash(m, s*G + e*P)

Let’s get a basic informal understanding for why such Schnorr based schemes work by taking the perspective of Eve, who does not know the discrete logarithm x of P. Obviously, Eve would invalidate the signature when attempting to just change the message m. Further, when trying to fake a signature without knowing x Eve can not to just set s as in the regular signing algorithm. But to make a signature that passes verification for some public key P Eve must find s, s.t. k*G = s*G + e*P. We can rearrange that in the following way:

k*G - s*G = e*P
(k - s)*G = e*P
((k - s)/e)*G = P

That means that if she would find such an s she could compute the discrete logarithm of P. This is a contradiction.

Note that during verification the output of the hash function e is also part of the input to the hash function. How about during signing Eve chooses s at random and then simply hashes s*G + e*P? The problem is that the properties of a cryptographic hash function prevent Eve from knowing e before before evaluating the hash function. So e can not be fed into the hash function and as a consequence s must be chosen to account for e only after hashing.

Rings of size one naturally don’t make a lot of sense but are sufficient for this post’s purpose. The curious can for example have a look at the explanation in the Borromean signature paper(section 2.2).

One-time ring signatures

One-time ring signatures are used in CryptoNote to allow combining the privacy properties of ring signatures with a mechanism to detect double spending. This is done by introducing the concept of a “key image”. The key image is a group element that is deterministically derived from a key but in itself doesn’t reveal anything about the key. Define hashp to be a hash function that hashes to an element in the group. Then the key image I for the key pair (x, P=x*G) is I = x*hashp(P) so P and I have the same discrete logarithm. A one-time ring signature includes the key image belonging to the signer.

The CryptoNote protocol allows using ring signatures when spending coins by enforcing that each key image can occur only once in the blockchain. Let’s for example assume there are two unspent coins – in our case just represented by public keys P1 and P2. Alice knows the private key to P1, so she can spend the coin by providing a one-time ring signature with P1, P2 and the key image I corresponding to P1. An observer can not tell whether P1 or P2 was spend. But if Alice would attempt to spend P1 again (even with a different ring) she would require the same key image which is rejected by the network. However, P2 can still be spent because the signature uses a different key image.

Now the concrete one-time ring signature scheme – again shown only for rings of size 1:

keygen:
draw scalar x uniformly at random
P <- x*G
publish public key P

sign message m (ring size 1):
I <- x*hashp(P)
draw scalar k uniformly at random
e <- hash(m, k*G, k*hashp(P))
s <- k - e*x
publish signature (I, e, s)

verify signature (I, e, s) on message m for public key P (ring size 1):
e == hash(m, s*G + e*P, s*hashp(P) + e*I)

Intuitively, it’s very hard to create a signature where I != x*hashp(P) because the same s that is used to prove knowledge of the discrete logarithm x of P is also used for I.

The one-time ring signature scheme for rings larger than 1 is described in the CryptoNote whitepaper(section 4.4) although in a less space efficient way. The construction is also related to the proof of discrete log equality used in perfectly binding Confidential Transactions. Note that actually by now a more general scheme that is based on one-time ring signatures called Ring Confidential Transactions has replaced regular one-time ring signatures in Monero.

Low order keys in Ed25519

As mentioned in the beginning, CryptoNote uses Ed25519’s curve (also referred to simply as “Ed25519”) to represent its group elements. One of Ed25519’s properties is that the number of points on the curve (curve order) is larger than the number of points in the group generated by the base point G (group order). The group order is the prime l = 2^252 + 27742317777372353535851937790883648493 and the curve order is 8*l The ratio of the curve order and the group order is known as the cofactor which is 8 in the case of Ed25519. This is, for example, different to the curve secp256k1 used in Bitcoin which has cofactor 1.

The cofactor indicates that there are groups of low order on the curve. For example, let P be the point represented by 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 then P generates the (unique) group of order 8 which implies 8*P = 0. There are only few points on the curve with low order. One way to find them is to generate a random point on the curve with order a*l and then multiply by l to get a point of order 1 <= a <= 8. On the other hand, hashp ensures that the resulting point is in the prime order group by multiplying it by 8 before outputting it.

In the case of the regular Ed25519 signature algorithm it doesn’t matter if a public key is of low order. But Ed25519 implementations make sure that a private key is a multiple of 8 (“clamping”), so when multiplying it with a low order point then the result is always 0 (instead of leaking bits from the private key). Therefore, after running the Diffie-Hellman protocol on such a curve the key shared between the two parties can be 0 if one party doesn’t behave “contributory”.

Attack & Fix

Assume the attacker owns a coin and therefore can create a regular one-time ring signature to spend it with key image I = x*hashp(P). The attacker can spend the coin again with key I' = I + L where L is a low order point with order o. Remember the verification equation includes s*hashp(P) + e*I. If o divides e, (e = e'*o) then e*I' = e*I + e'*o*L = e*I so a valid signature with I' can created in the same way as with I (except that the message m now has to commit to I'). Since o is at most 8 it is easy to to retry signing until there is a suitable hash e.

Interestingly, in ByteCoin this was exploited in a much less effective way. The attacker used a low order public key P requiring a low order key image I. Because there are only 8 low order points on the curve (multiple representations of the same point are disallowed in CryptoNote) this attack can be only performed 8 times in one blockchain.

The fix implemented in Monero is to verify that each key image I generates a group of the prime order l by checking that l*I = 0. If I actually had order l' != l then for l*I = 0 to hold, l must be divisible by l' which is a contradiction because l is prime. So the additional cost introduced by the fix is one scalar multiplication per transaction input.

Conclusion

This article gave yet another example for how cryptographic parts can not be easily repurposed. In particular, when implementing more complex protocols based on curves with a cofactor (like for example Ed25519 or Curve25519) the group order of user supplied generator points should always be verified. Deciding case-by-case whether that’s necessary is quite dangerous in practice. There is, however, potential to get rid of this bug class for some cryptosystems by eliminating cofactors through point compression (see Decaf). Alternatively, when designing a new cryptosystem it should be considered to use a prime order curve such as secp256k1.