4

I am a student researcher at IIT Bombay (India). I have been recently understanding the cryptography behind Monero as well as its implementation.

The elliptic curve used in the CryptoNote protocol is Ed25519 (of order 8q, where q is a prime). This post described the possibility of a small subgroup (order q) confinement attack on CryptoNote based cryptocurrencies. To this end, the field elements in the implementation of Monero seem to be multiplied by 8 to ensure they lie in the smaller subgroup. At this point, I am a bit confused about the exact curve underlying Monero, is it the whole of Ed25519 or the subgroup of Ed25519?

On the other hand, the Ristretto255 [1, 2] curve (built on Curve25519) has the same order as that of the curve used in the CryptoNote white paper [3]. My question is the following: Can we have a mapping from Ed25519 used in Monero to the Ristretto255 group? Will the relationship between public and/or private keys be preserved? Basically, if Monero has to be implemented using Ristretto255 in future for better performance, what would be the way to convert a Ed25519 curve point to a Ristretto curve point?

Apologies if I am missing anything trivial since I am beginner.

References:

  1. https://ristretto.group/details/index.html

  2. https://tools.ietf.org/pdf/draft-hdevalence-cfrg-ristretto-01.pdf

  3. https://cryptonote.org/whitepaper.pdf

  • Monero's sc_reduce32() function can directly be implemented by the libsodium crypto_core_ed25519_scalar_reduce() function. Monero's secret_key_to_public_key() function can directly be implemented by the libsodium's crypto_scalarmult_ed25519_base_noclamp() function. Private keys normalized by cascaded sc_reduce32() and secret_key_to_public_key() operations appear to be called red25519. – skaht May 18 at 3:57
  • Exemplified IETF functionality can be demonstrated with % echo -n "no" | bx base16-encode | bx sha256 | ./25519 742eefe877d713693985a6e0e1376033cf115f3c8d02f7c40a1ee68d75824d39 or results replicated using a few Monero constructs % echo -n "no" | bx base16-encode | bx sha256 | bx sha512 | cut -c 1-64 | ./clamp | ./sc_reduce32 | ./secret_key_to_public_key 742eefe877d713693985a6e0e1376033cf115f3c8d02f7c40a1ee68d75824d39. Finally, libsodium's Ristretto functionality is documented at doc.libsodium.org/advanced/point-arithmetic/ristretto – skaht May 18 at 4:03
5

Building on Knaccc's answer.

Curve25519

The first step to build an Elliptic curve library is to define a field of prime characteristic. In this case, the field is 2^255 - 19, I denote this with K. In most eprints it is denoted as F_p.

We then define a curve over this field of prime characteristics. The curve that we define in this case is a Montgomery curve called Curve25519. Where the points on the curve are in K. Not every point is on the Montgomery curve, just like regular curves. It is only the set of points whose x and y value satisfy the curve equation. The set of points which are on the curve is defined as M(K). These points form a Group.

Comparing Curve25519 and Ed25519

First, they are both defined over the same prime field K. But Ed25519 has a different curve equation. We know that there is a Group of points which are on the Montgomery curve denoted M(K). So the question is whether, the Group of points on Ed25519 are the same points?

Lets denote the group of points on Ed25519 as E(K). There is a relationship between Curve25519 and Ed25519, it's called a birational equivalence: https://crypto.stackexchange.com/questions/43013/what-does-birational-equivalence-mean-in-a-cryptographic-context

The link above explains it very well, in short, there is a way to transform Curve25519 to look like Ed25519 except for a few points. These are called the exceptional points.

This means that M(K) and E(K) have roughly the same amount of points. The exceptional point, only comes up in the affine mapping, so can be avoided if we use projective.

In short, we can think of there being a mapping from M(K) to E(K). We are actually interested in E(K), but I mentioned Curve25519 first because Ed25519 came from it, in the relationship mentioned above.

Order of E(K)

The next question is "How many points are in the Group E(K)?"

There is paper by Craig Costello which says that the order must be even for both Edwards and Montgomery Curves.* In our case, the order is 8q. Where q is prime.

By lagranges theorem, E(K) can be decomposed into smaller groups which are multiples of its order. One group has has q points E_1(K) and the other group has 8 points E_2(K). This has been slightly simplified, see the link that knaccc posted above.

We are now looking at three groups E(K), E_1(K) and E_2(K).

Notice that the points in E_1(K) and E_2(K) are in E(K) since E_1(K) and E_2(K) are just decompositions of EK(). This means that E_1(K) and E_2(K) are subsets of E(K). We can go further and show that they are both subgroups.

Small subgroup

The points in E_2(K) have order 8. This means that if I take any point in E_2(K) and add it to itself 8 times, then I will arrive at a special point called the identity point. You can think of it as the zero point.

For example; if P \in E_2(K) then P + P + P + P + P + P + P + P = 0 . Instead of manually writing out the additions I could have equivalently written 8P = 0. This is known as scalar multiplication. In the case of 8P , 8 is the scalar.

The points in E_1(K) have order q. This means that in order to arrive at 0. You need to add the point to itself q times. ie if P \in E_1(K) then qP = 0.

The number 8 is small and all points in E_2(K) have an order of 8. We call this subgroup the small-order subgroup.

Contrasting, q is a prime and is large and all points in E_1(K) have an order of q. We call the subgroup E_1(K) the prime order subgroup.

E_1(K) and E_2(K)

So what's the problem? The problem is a mixture of two things:

  1. We cannot force the user to use either E_1(K) or E_2(K). We have to assume that they have taken points from E(K).
  2. You can mix points in E_1(K) and E_2(K) together.

Constructing the attack

Context: You are only allowed to use a point once. Using the point twice is analogous to double spending.

Goal: The attacker will attempt to use a point twice.

  1. Pick a point in E_1(K). Lets call it P.
  2. Pick 2 points in E_2(K). lets call them R_1 and R_2.
  3. Compute T_1 = P + R_1 and compute T_2 = P + R_2.

The attacker tells Alice "T_1 is his point, you can use it to check on the blockchain when I make a payment."

The attacker tells Bob "T_2 is my point, you can use it to check on the blockchain when I make a payment".

These two points look different. But when we multiply it by a number that is a multiple of 8. We see that R_1 and R_2 disappear and the points become equivalent.

8 * T_1 = 8 (P + R_1) = 8 * P + 8 * R_1 = 8P + 0 = 8P.

As knaccc said above, whenever the scalar is a multiple of 8, the part that comes from E_2(K) disappears. So it looks like we have different points, but when multiplied by a multiple of 8, we can make the point be equivalent. This means that the attacker does not need to know the private key to T_1 or T_2. He just needs to sign with the private key for P.

This has lead to attacks as seen in this link : How does the recent patched key image exploit work in practice?

If I have not explained it well so far, essentially E_2(K) is bad and E_1(K) good!

Getting rid of E_2(K)

The way that Monero uses is called a subgroup check, and we essentially check if T_1 is in the prime subgroup, in our case this is E_1(K). To check if a point is in a specific subgroup, you multiply that point by the subgroup order and check if you get the identity (zero) point.

Let's take T_1 again and multiply it by the order of the prime subgroup.

q * T_1 = q (P + R_1) = q * P + q * R_1 = 0 + q*R_1 = qR_1.

If our point T_1 was in E_1(K), then it would have produced the identity. Since we did not arrive at the identity point, we know that this point has components in E_2(K).

This check is great and does what we want but it is also expensive to multiply by that large prime q. We must do this to every point we receive before running any verification procedure.

This check guarantees that a point is always in E_1(K). You can think of it as mapping E(K) -> E_1(K), where the order of E_1(K) is q.

What if we could build a group of order q from E(K)? This would also solve our problem. This is essentially what Ristretto does. You can think of it as E(K) -> 2E(K)/E[4] . Notice that it does not map to E_1(K). E_1(K) and 2E(K)/E[4] are groups of prime order, but they do not contain the same points. E_1(K) contains points which are in the prime order subgroup of E(K) while 2E(K)/E[4] contains points which form a prime order subgroup from E(K).

Ristretto

Ristretto is an extension on Decaf: https://www.shiftleft.org/papers/decaf/decaf.pdf

Above we alluded to the relationship between Curve25519 and Ed25519. There is another type of relationship that curves can have which we call an isogeny. In the Decaf paper, it cites a paper which shows that there is a family of curves whom are all isogenous to each other.

Furthermore, when we transform one curve to another curve, it can pick up a factor. For example, given two curves E' and E'' which are 2-isogenous, we have functions which maps points between E' and E'' and each map will double the corresponding point on the other curve. Here is a link to a test case for a 2-isogeny: https://github.com/cloudflare/circl/blob/master/ecc/goldilocks/isogeny_test.go#L21

The test in the link maps a point from E' to E'', then immediately maps the point back to E' . This means that the resulting point on E' will be 4 times the original point.

Decaf does not work outright for Ed25519, but it does for Curve25519, however since Curve25519 and Ed25519 are birationally equivalent. The formulas can be modified to map to Ed25519 through Curve25519. This is what Ristretto does along with few other modifications: https://ristretto.group/details/isogenies.html#from-montgomery-to-edwards-via-isomorphism

So far, we have a family of curves, one of which is a Montgomery curve in our case Curve25519 and we have Ed25519 which can be mapped to, by any one of the family of curves through Curve25519. The only important curve in the family of curves worth mentioning is the Jacobi quartic curve. The Jacob curve is 2-isogenous to the Curve25519.

Encoding the point

Let's say I have a point P in E(K). Recap that E(K) is the group of points on the Ed25519 curve. First we use our birational map the point to Curve25519. So the point is now a point in M(K).

From the decaf paper, we know that there is a 2-isogeny from the Montgomery Curve to the Jacobi quartic. We apply this isogeny and our point is mapped to a point on the Jacobi quartic, but since it is a 2-isogeny it also picks up a factor of 2. If P was in the small-order subgroup E_2(K) then when we map it to the Jacobi quartic we would only need to double the corresponding Jacobi point twice in order to get the identity element.

What is the importance?

Instead of checking if our point is in the correct subgroup, our strategy will be to now group all points which differ by a point of order 4 and force an algorithm to output a specific point. All of the points which differ by a point of order 4 are exactly all of the points which were equivalent when we multiplied by a scalar which was a multiple of 8 in E_1(K).

To see this, let P \in E_1(K) and let R_1, R_2 \in E_2(K)

Compute T_1 = P + R_1 . When T is mapped to the Jacobi quartic, it picks up a factor of 2.

2 * T_1 = 2 * P + 2* R_1 2 * T_2 = 2 * P + 2* R_2

Notice that because R_1 was doubled, it is now an order of 4 away from the identity point. So T_1 and T_2 differ by a point of order 4, when we apply the isogeny to map it to the Jacobi quartic. Notice also that P + 0 also differs by a point of order 4 and is also in this group of point which differ by a point of order 4.

Why is this important?

The Jacobi quartic has a really succinct representation for all of it's points which differ by a point of order 2. But for this explanation, lets pretend it is by an order of 4, the logic still follows through. :https://ristretto.group/details/isogeny_encoding.html#encoding-mathcal-j--mathcal-j2

As the link mentions, it is possible to consistently pick one of the points in the set of points which differ by an order of 2(again lets pretend it says 4), by enforcing two sign checks. These two can be easily programmed into an algorithm.

Another example of a sign check, is when you are sending a point to another user. You take the Y co-ordinate and use a bit to denote the sign of the X co-ordinate. In this case, you are distinguishing between the negative and positive-ness if the X co-ordinate. This check is usually done on the Edwards curve Ed25519.

Contrasting, this check is computed on the Jacobi quartic curve, which is not the curve that we are doing arithmetic on. It is Ed25519. Fortunately, the encoding can be transported to Ed25519 https://ristretto.group/details/isogeny_encoding.html#transporting-an-encoding-along-an-isogeny

So we make our sign choices in the Jacobi quartic, then we transport these sign choices to the correct curve.

Summary

When you compress a point, you use a 2-isogeny to transport the point to the Jacobi quartic, picking up a factor of 2, you then make two sign choices which picks a specific point. When you decompress a point you check that these two checks are satisfied on the Jacobi quartic curve, which means that this point is the specific point out of all of the points which differ by a point of order 4. Then you transport the point to the Ed25519 curve.

Important Details

In the above sentence, I said specific point , I did not say a point that is in E_1(K). The point that we pick as a representative can be in E_2(K) , we just need to consistently pick the same point, which our sign check allows.

_Question: So If we can pick a point in E_2(K) , how does Ristretto solve the prime group problem?_

Ristretto does not force a point to be in E_1(K). It builds a prime order group from E(K). And it does this by always picking the same point out of the possible 8 equivalent points. This new Ristretto group will have prime order, because it is always picking 1 out of the 8 possible points.

Does this really solve the problem?

We can formulate the problem another way. Each Point in E(K) had 8 different equivalent points. No matter which one of these 8 equivalent points you give the Ristretto algorithm, it will give you exactly the same one. The other 7 points are no longer representable. Caveat

There is are two security caveats. We are assuming that all points are passed through the Ristretto ENCODING algorithm.

If the points are modified at a later point, after going through the encoding algorithm. Then it is possible to simply change the representative point that was chosen.

This is why you must only add Ristretto points with Ristretto points. Ie only the representatives of the set of points should be used. You should never mix a RistrettoPoint with an EdwardsPoint, because the EdwardsPoint you are mixing with, may not be the representative for the set of possible points. This is mentioned in the IETF you linked, at the end I think.

Thing I have omitted or lied about

The Jacobi quartic actually has a succinct representation for points which differ by an order of 2, and Ristretto applies an extra step to transform the points which differ by an order of 4 to points which differ by an order of 2. This is explained in the torquing section, but is not important to understand most of Ristretto.

Hope that helps. If any mistakes are found, please feel free to correct them.

| improve this answer | |
  • A lot of things were omitted or removed to shorten the explanation. I think that your comments are off topic in so far as allowing one to understand how Ristretto works. The cofactor part was more of a motivation for Ristretto. I should have made that clearer. – user679128 May 10 at 7:26
  • Thanks a lot for the detailed explanation of the small-subgroup attack as well as the idea of Ristretto. Your answer was a great start point for me to read literature on Ristretto and Edwards curve! I tried the following experiment: 1. Take a random scalar x in F_q, 2. Compute P = xG, G is basepoint of Ed25519 (P essentially becomes a Monero address), 3. Compute Encoding s of P as described here 4. Check if s is a valid encoding in Ristretto. For 100 runs of this expt, (...continued in next comment) – Suyash Bagad May 17 at 10:59
  • For 100 runs of this expt, typically only 6-10 Monero add. seem to be have valid encoding in Ristretto. Now this confuses me how can we convert Monero add. to Ristretto points. Note that the byte-encoding of s is nothing but CompressedRistretto representation. So, for each example point P, let the byte encoding of P be s(P). Then I decompress this CompressedRistretto to get a Ristretto point using the function in Ristretto implementation. What am I missing here? – Suyash Bagad May 17 at 11:23
  • Hi, I think it’s probably better to post this as a new question. Maybe on crypto.stackexchange if you make it general. One thing which does not look right to me, is that x is taken from F_q which I assume is the prime field 2^225-19 and not the scalar field. – user679128 May 17 at 11:29
4

To this end, the field elements in the implementation of Monero seem to be multiplied by 8 to ensure they lie in the smaller subgroup

The group elements are multiplied by 8 to ensure they lie in the correct subgroup. I'm phrasing it in this way to avoid ambiguity, so that "smaller subgroup" is not misinterpreted as one of the really small subgroups which only have 1, 2, 4 or 8 points. This is only done in particular situations where there is risk that a group element (a.k.a. Elliptic Curve point) may not be in the correct subgroup (e.g. when a point you're provided with is from an untrusted source).

There are possible attacks when a point is in one of the larger subgroups which is not the correct subgroup. If there was no correct-subgroup check, this could have been used to provide a key image which looked unique, but that actually ended up being equivalent to a different point when multiplied with a scalar that was a multiple of 8.

Small subgroup attacks are related to the idea that there are certain points on the Ed25519 curve, where no matter what scalar they are multiplied by, the result can only end up being one of [1,2,4 or 8] Ed25519 points. See What are the hex representations of the small subgroup curve points on Ed25519? for a list.

is it the whole of Ed25519 or the subgroup of Ed25519?

There is only one curve, which is the standard Ed25519 curve. A subgroup of possible points on that curve are used in Monero, meaning that only 1/8th of the points on the Ed25519 curve are in the correct subgroup.

I'm not familiar enough with the implementation specifics of how Ristretto works to answer your question on interoperability.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.