Overcoming The Subgroup Attack in Ed25519: Meet Ristretto255

First, let me outline a a core principle of elliptic curve cryptography. With this, we have a prime number (p) and an equation such as:

y²=x³+7 (mod p)

and where p is a prime number. To keep it simple, let’s select p=37, then the following points are possible [here]:

(0, 9) (0, 28) (3, 16) (3, 21) (4, 16) (4, 21) (5, 13) (5, 24) (6, 1) (6, 36) (8, 1) (8, 36) (9, 12) (9, 25) (12, 12) (12, 25) (13, 13) (13, 24) (16, 12) (16, 25) (17, 6) (17, 31) (18, 17) (18, 20) (19, 13) (19, 24) (22, 6) (22, 31) (23, 1) (23, 36) (24, 17) (24, 20) (30, 16) (30, 21) (32, 17) (32, 20) (35, 6) (35, 31)

Notice that we do not get a valid point at x=1 and x=2, and that we get double points for each x (because of the square root operation). The order of the curve is then the number of value points we can have.

The problem with Ed25519

Ed25519 is now used in many areas and provides a simpler and more scalable signature than ECDSA. The signature is typically known as EdDSA. But there’s a possible attack on it. Overall, Ed25519 uses Curve 25519 and which has an order of 8q and where q is a prime number — and where the order of the curve is the number of valid elliptic curve points that can be produced. The attack involves the possibility of creating a small subgroup of order q and creating a confinement attack.

Overall, Curve 25519 have a Montgomery curve that is defined with:

The prime number is:

and where we have a base point at x = 9.

The order is then a prime number of:

and which has a co-factor of 8 which means there are 1/8th of the elements of elliptic curve group. This prime order subgroup defends against the Pohlig-Hellman attack. Within X25519, the subgroup problem is removed by clearing the lower three bits of the private key, and which makes sure it is divisible by 8.

https://medium.com/asecuritysite-when-bob-met-alice/clamping-47f4163765ca

Here is the clamp applied in X25519 [here]:

This feature is not part of Ed25519. The conversion of Curve 25519 into a safe prime ordered curve was initially defined by Mike Hamburg with the Decaf method:

This can then be applied to Curve 25519 with Ristretto255.

Ristretto255

Ristretto255 encodes group elements using 255 bits and provides a prime-order group of size 2252, and implemented with Curve25519. We use a prime of 2255−19. In this case, we will hash a string with SHA-512, and then map this to a point on the curve. This will be computed for Ristretto255 and an Edwards curve. In this case we will use Rust to hash a string with SHA-512, and then map this hash to Ristretto255 and also to Ed25519.

First we create the with:

cargo new ris

We then go into the ris folder, and add the following to the cargo.toml file [here]:

[package]
name = "ris"
version = "0.1.0"
edition = "2024"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
curve25519-dalek = "4.1.1"
ed25519-dalek ="2.1.1"
rand_core = { version = "0.6.4", features = ["std"] }
hex="0.4.3"
sha2="0.10.8"

Next we go into the src folder, and edit the main.rs file with [here]:

use std::io::{stdout, Write};
use sha2::{Sha512};
use hex;
use curve25519_dalek::{RistrettoPoint,EdwardsPoint};
use std::env;

fn main() {
    
    let mut msg = "Ristretto is traditionally a short shot of espresso coffee";
    let args: Vec <String>= env::args().collect();
  
    if args.len() >1 { msg = args[1].as_str();}
  let P = RistrettoPoint::hash_from_bytes::(msg.as_bytes());
  println!("Message: {:?}",msg);
  println!("\nRistretto Point: {}",hex::encode(P.compress().as_bytes()));
  let E = EdwardsPoint::nonspec_map_to_curve::(msg.as_bytes());
  println!("\nEdwards Point: {}",hex::encode(E.compress().as_bytes()));
}

Finally we simply build with [here]:

cargo build

Some text vectors are given here [link]:

let labels = [
    "Ristretto is traditionally a short shot of espresso coffee",
    "made with the normal amount of ground coffee but extracted with",
    "about half the amount of water in the same amount of time",
    "by using a finer grind.", 
    "This produces a concentrated shot of coffee per volume.",
    "Just pulling a normal shot short will produce a weaker shot",
    "and is not a Ristretto as some believe.",
];

let encoded_hash_to_points = [
    "3066f82a1a747d45120d1740f14358531a8f04bbffe6a819f86dfe50f44a0a46",
    "f26e5b6f7d362d2d2a94c5d0e7602cb4773c95a2e5c31a64f133189fa76ed61b",
    "006ccd2a9e6867e6a2c5cea83d3302cc9de128dd2a9a57dd8ee7b9d7ffe02826",
    "f8f0c87cf237953c5890aec3998169005dae3eca1fbb04548c635953c817f92a",
    "ae81e7dedf20a497e10c304a765c1767a42d6e06029758d2d7e8ef7cc4c41179",
    "e2705652ff9f5e44d3e841bf1c251cf7dddb77d140870d1ab2ed64f1a9ce8628",
    "80bd07262511cdde4863f8a7434cef696750681cb9510eea557088f76d9e5065",
];

So, let’s try our program [here]:

And, so, we can see that this works for the string of “Ristretto is traditionally a short shot of espresso coffee”, and which gives a point of “3066f82a1a747d45120d1740f14358531a8f04bbffe6a819f86dfe50f44a0a46”. Note in Curve 25519, we only define the x-axis point.

Conclusions

While X25519 is fixed, Ed25519 is not, so please consider converting to Ristretto255 in some applications. Learn more about Curve 25519 here:

Curve 25519