SlowMist: Understanding the Principles and Scalability Issues of Ed25519

Ed25519 is an elliptic curve-based digital signature algorithm that is efficient, secure, and widely adopted. This algorithm is utilized in a myriad of applications, including but not limited to, TLS 1.3, SSH, Tor, ZCash, WhatsApp, and Signal. This article aims to shed light on the following aspects:

1. Introduction to some elements of group theory to provide an intuitive understanding of Ed25519 and its scalability issues. For a deeper understanding, one should consider referring to additional resources;

2. Explanation of the implementation of Ed25519 with regards to the 1.0.1 version of the Rust library, ed25519-dalek;

3. Discussion of the scalability issues associated with this library.

Recapitulation of Mathematical Essentials

Definition and Properties of Groups

Group theory is part of the research content of abstract algebra. Still, some concepts of abstract algebra are very familiar to programmers. For instance, inheritance in object-oriented programming is a great example: we all know that once a subclass inherits from a superclass, it can use the methods defined in the superclass. Abstract algebra can be understood as defining certain properties for an abstract data structure, and the theorems derived from these properties hold true for all subclasses.

Continuing with the same analogy, let’s delve into how the data structure of a ‘group’ is defined.

A ‘group’ consists of an operation (denoted by *) and some elements, satisfying the following properties:

• CLOSURE: a*b = c. The closure property implies that the result of any operation within the group stays within the group.
• ASSOCIATIVITY: (a*b)*c = a*(b*c). The associativity rule implies that the order of operations does not impact the result.
• NEUTRAL ELEMENT (Identity): a*e = e*a = a. This property, also known as Identity, means that there exists an element that, when combined with any other element, always results in the other element.
• INVERSE: a*a^-1=e. The inverse property implies that there always exists an inverse for each element.

From these properties, we can derive several interesting theorems:

• The identity element, e, is unique. Let’s say there exist two identities e. e1*e2=e1 and e1*e2=e2, then e1=e2.
• a^-1 is also unique
• (a^-1)^-1 = a

Here are a few examples:

• The integers …, -2, -1, 0, 1, 2, … under the operation of addition form a group because they satisfy the four properties mentioned above.
• The integers under multiplication do not form a group because they do not meet the inverse property; for instance, 4*(1/4)=1, but 1/4 is not an integer.

Let’s quickly go through some terminologies used in group theory:

• Order: The ‘order’ refers to the number of elements in the group. In the examples given above, the groups are of infinite order.
• Abelian Group: An ‘Abelian group’ is a group that, in addition to the four properties mentioned earlier, also satisfies the commutative law (a*b = b*a).
• Cyclic Group: The examples provided above are groups with infinitely many elements. However, we often encounter groups with a finite number of elements, such as (Z+7): 0, 1, 2, 3, 4, 5, 6. This group consists of these seven numbers with addition as the operation, followed by modulus 7. So, 6 + 1 equals 0, not 7. This is known as a ‘cyclic group’, a name that is quite intuitive.
• Subgroup: A ‘subgroup’ is a portion of a group that itself is a group. For example, the set {0, 3, 6} from the group (Z+9): 0, 1, 2, 3, 4, 5, 6, 7, 8 can form a subgroup. The even numbers under addition form a subgroup of the integers, but the odd numbers do not because 1+3=4, and 4 is not odd.
• Generator: A ‘generator’ is a specific element g such that operating g on itself can eventually generate all elements of the group: g, g², g³, …, where g² = g*g.

Lagrange’s Theorem

Now, let’s introduce an interesting theorem, the derivation of which can be found in the video cited at the end of this article.

“The order of a group is divisible by the order of any of its subgroups.”

Why is this theorem interesting? Not just because the process of its proof ties together much of the knowledge we just introduced, but also due to the following conclusion:

“If the order of a group is a prime number p, then according to Lagrange’s theorem, the order of a subgroup must be either 1 or p. Aside from the identity element e, all elements in the group are generators.”

Implementation of Ed25519

Now let’s discuss Ed25519, which is one version of the EdDSA algorithm. EdDSA has 11 parameters (https://datatracker.ietf.org/doc/html/rfc8032#autoid-3). The specific choices of these parameters have a significant impact on the security and performance of the algorithm. For the specific choices of Ed25519, please refer to the link (https://datatracker.ietf.org/doc/html/rfc8032#autoid-9).

Furthermore, it is worth mentioning that this algorithm uses an elliptic curve called Curve25519 (https://datatracker.ietf.org/doc/html/rfc7748#autoid-5). Regarding elliptic curves, we only need to know that there are countless points on the curve, and the addition of these points can produce new points which still lie on the curve. These points, along with this addition operation, can form a group. Note that the addition operation on elliptic curves (https://www.wikiwand.com/en/Elliptic_curve_point_multiplication) has a special definition.

Let’s establish the following notations:

The addition of point A and point B is denoted as A+B.

The multiplication of scalar x and point A is denoted as [x]A.

For the Ed25519 curve, we have a total of 8l points, meaning that the order of the group is 8l, where l is a prime number, specifically l=2²⁵² + 27742317777372353535851937790883648493.

We have extracted a subgroup of prime order l from the group with order 8l (https://en.wikipedia.org/wiki/Abelian_group#Classification): G={0, B, [2]B, …, [l-1]B}. Here, 0 is a special point and the identity element in the group. For any point P, 0+P=P. B is another point, known as the base point. According to the definition, we have [l]B=0. The discussion that follows is all about this subgroup.

According to the paper (https://ed25519.cr.yp.to/ed25519-20110926.pdf), the Ed25519 algorithm works as follows, assuming that we are the Prover who knows a secret A=[a]B, where B is the base point, a is a scalar (also known as the private key), and A is a point (also known as the public key). Our goal is to prove to a Verifier who knows our public key that we know the corresponding private key, without directly revealing the private key:

1. Prover: Choose a random scalar r

2. Prover → Verifier: Send R:[r]B

3. Verifier → Prover: Choose and send a random scalar h

4. Prover → Verifier: Calculate and send s:=r+h*a

5. Verifier: Verify [s]B==R+[h]A

Although this is an interactive algorithm, there’s no need to worry. There’s a technique called the Fiat-Shamir heuristic (https://link.springer.com/chapter/10.1007%2F3-540-47721-7_12), which can transform any interactive algorithm into a non-interactive one. Eventually, we will use the non-interactive variant.

Digital signature algorithms provide us with the following APIs:

KeyGen() → sk, pk: sk is the private key, pk is the public key

Sign(m, pk) → sig: m is the message, sig is the signature

Verify(pk, sig, m) → 0/1

KeyGen

The KeyGen function outputs a private key and a public key:

1. Randomly generate a seed (https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/secret.rs#L167-L176). This seed is 32 bytes long. We use a cryptographically secure random number generator that is built into the system.

pub fn generate<T>(csprng: &mut T) -> SecretKey
where
    T: CryptoRng + RngCore,
{
    let mut sk: SecretKey = SecretKey([0u8; 32]);

    csprng.fill_bytes(&mut sk.0);

    sk
}

2. Expand the seed to 64 bytes (https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/secret.rs#L265-L282). This is the xseed in the figure. The lower 32 bytes of xseed is our private key (aka a). The upper 32 bytes, known as the nonce, will be used later in the Sign function. Its role is similar to a domain separator.

pub struct ExpandedSecretKey { // xseed
    pub(crate) key: Scalar,      // a
    pub(crate) nonce: [u8; 32],  // nonce
}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
    let mut h: Sha512 = Sha512::default();
    let mut hash:  [u8; 64] = [0u8; 64];
    let mut lower: [u8; 32] = [0u8; 32];
    let mut upper: [u8; 32] = [0u8; 32];

    h.update(secret_key.as_bytes());
    hash.copy_from_slice(h.finalize().as_slice());

    lower.copy_from_slice(&hash[00..32]);
    upper.copy_from_slice(&hash[32..64]);


         // 这一步是 clamp
    lower[0]  &= 248;
    lower[31] &=  63;
    lower[31] |=  64;

    ExpandedSecretKey{ key: Scalar::from_bits(lower), nonce: upper, }
}

3. Use the private key to generate a public key (https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/public.rs#L54-L68). The public key is a point on the elliptic curve. Specifically, we use the base point B of the elliptic curve to perform elliptic curve multiplication to obtain the public key. The scalar in the multiplication is obtained by hashing the private key a.

pub struct PublicKey(pub(crate) CompressedEdwardsY, pub(crate) EdwardsPoint);

impl<'a> From<&'a SecretKey> for PublicKey {
    /// Derive this public key from its corresponding `SecretKey`.
    fn from(secret_key: &SecretKey) -> PublicKey {
        let mut h: Sha512 = Sha512::new();
        let mut hash: [u8; 64] = [0u8; 64];
        let mut digest: [u8; 32] = [0u8; 32];

        h.update(secret_key.as_bytes());
        hash.copy_from_slice(h.finalize().as_slice());

        digest.copy_from_slice(&hash[..32])
        PublicKey::mangle_scalar_bits_and_multiply_by_basepoint_to_produce_public_key(&mut digest)
    }
}

fn mangle_scalar_bits_and_multiply_by_basepoint_to_produce_public_key(
    bits: &mut [u8; 32],
) -> PublicKey {
    bits[0] &= 248;
    bits[31] &= 127;
    bits[31] |= 64;

    let point = &Scalar::from_bits(*bits) * &constants::ED25519_BASEPOINT_TABLE;
    let compressed = point.compress();

    PublicKey(compressed, point)
}

Sign

Here, we can mention the previously mentioned Fiat Shamir trick, which actually just requires replacing all random numbers provided by Verifier with the result of a hash function. Please see the code comments for details.

pub fn sign(&self, message: &[u8], public_key: &PublicKey) -> ed25519::Signature {
    let mut h: Sha512 = Sha512::new();
    let R: CompressedEdwardsY;
    let r: Scalar;
    let s: Scalar;
    let k: Scalar;

    h.update(&self.nonce);
    h.update(&message);

    r = Scalar::from_hash(h); // r在我们交互式算法中是一个随机数，但是这里我们用了哈希。
    R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r]B

    h = Sha512::new();
    h.update(R.as_bytes());
    h.update(public_key.as_bytes());
    h.update(&message);

    k = Scalar::from_hash(h);   // h = Sha512(R || A || M)
    s = &(&k * &self.key) + &r; // s = r + h * a，h原本是随机数

    InternalSignature { R, s }.into()
}

Verify

impl Verifier<ed25519::Signature> for PublicKey {
    #[allow(non_snake_case)]
    fn verify(
        &self,
        message: &[u8],
        signature: &ed25519::Signature
    ) -> Result<(), SignatureError>
    {
        let signature = InternalSignature::try_from(signature)?;

        let mut h: Sha512 = Sha512::new();
        let R: EdwardsPoint;
        let k: Scalar;
        let minus_A: EdwardsPoint = -self.1;

        h.update(signature.R.as_bytes());
        h.update(self.as_bytes());
        h.update(&message);

        k = Scalar::from_hash(h); // h的计算和sign中一样，h=Sha512(R||A||M)
        R = EdwardsPoint::vartime_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R’ = [s]B - [h]A

        if R.compress() == signature.R { // 如果R’==R，那么验证结果为真。
            Ok(())
        } else {
            Err(InternalError::VerifyError.into())
        }
    }
}

ed25519-dalek/public.rs at 97c22f2d07b3c260726b90c55cd45f34ec34a037 ·…

Malleability Issues

There are many things to be careful about in the implementation and use of cryptographic algorithms. When we say a digital signature algorithm is secure, it generally means that even if an attacker can obtain the signature of any message (Chosen Message Attack), the attacker still cannot forge a signature. Ed25519 satisfies this property, but that doesn’t mean Ed25519 is absolutely secure. The original paper also mentions that malleability issues are acceptable and the original algorithm has this problem.

Malleability refers to the ability to change a signature corresponding to a message m and public key pk, given a signature sig, to create a new signature sig’ such that Verify(pk, sig’, m)=1.

In the previous section, we mentioned that the signature is composed of R and s. We just need to add l to s to construct a new signature.

sig’=(R,s+l)

Remember that l is the order of our group, so [l]B=0, and the following equation holds:

[s’]B=[s+l]B=[s]B

In this way, both the newly constructed signature and the old signature can be successfully verified. The malleability issue tells us that signatures are not relative to a message and public key. If the signature algorithm has a malleability issue and the code assumes that the signature is determined, there is likely a vulnerability.

According to the standard (https://datatracker.ietf.org/doc/html/rfc8032#autoid-37), Ed25519 actually has no malleability issue because we will check whether s is less than l during the verification process. If the check result is false, the verification fails. However, the standard (https://datatracker.ietf.org/doc/html/rfc8032) appeared later than the paper (https://ed25519.cr.yp.to/ed25519-20110926.pdf), so there are still implementations of Ed25519 with malleability issues in the real world, which requires us to check the implementation of Verify.

Summary

This article first introduces some group theory concepts, such as the definition and properties of a group, Abel group, cyclic group, subgroup, generator, and Lagrange’s theorem. Then it explains the Ed25519 implementation based on the rust library ed25519-dalek; KeyGen generates private and public keys; Sign generates signatures (R, s) and Verify checks whether the signature is valid for the message and public key. Finally, it points out the malleability issue of Ed25519 and how you can add l (the order of the group) to s to create a new valid signature (R, s+l ) for the same message and public key.

Acknowledgments

Thanks to the leading one-stop digital asset self-custody service provider Safeheron for their professional technical advice.