Small-order Ed25519 public keys reach a fatal internal arithmetic assertion
Closed, ResolvedPublic
Actions

Assigned To

Authored By

	• werner
	Tue, Aug 4, 4:50 PM

Description

Small-order Ed25519 public keys reach a fatal internal arithmetic assertion

Ed25519 verification checks that the supplied public point is on the curve but does not reject identity or other small-order points before scalar multiplication. A public gcry_pk_verify call with a degenerate attacker-supplied key can consequently reach log_bug in the field arithmetic and abort the entire process before signature validity is decided.

Vulnerable code

cipher/ecc-eddsa.c, _gcry_ecc_eddsa_verify:

c
  if (!_gcry_mpi_ec_curve_point (ec->Q, ec))
    {
      rc = GPG_ERR_BROKEN_PUBKEY;
      goto leave;
    }

The unchecked point is later consumed here:

c
  _gcry_mpi_ec_mul_point (&Ia, s, ec->G, ec);
  _gcry_mpi_ec_mul_point (&Ib, h, ec->Q, ec);
  _gcry_mpi_sub (Ib.x, ec->p, Ib.x);

mpi/ec.c, ec_mulm_25519, makes the failure fatal:

c
  if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize)
    log_bug ("mulm_25519: different sizes\n");

Why it matters

Signature-verifying services often accept both the signature and public key from an untrusted peer, certificate, or stored object. The audit's public-API harness first verified a normal Ed25519 vector, then supplied a small-order public key and reproducibly terminated with mulm_25519: different sizes and exit status 134. The crash is raised by libgcrypt itself, not by a sanitizer. This establishes reliable denial of service; it does not require a valid attacker signature.

Proposed fix

Apply the Ed25519 verification rule to public keys before hashing or multiplication: reject the identity and low-order/torsion points, and enforce the intended subgroup policy. Invalid keys must return GPG_ERR_BAD_PUBKEY or GPG_ERR_BROKEN_PUBKEY, never reach log_bug. Add public-API tests for the identity, all standard low-order encodings, non-canonical point encodings, and a known-valid key/signature pair.

Revisions and Commits

rC libgcrypt
	rC7004c17e28c3 mpi:ec:Edward: Make sure to have fixed length MPI for get_affine.
	rC659b22897536 mpi:ec:Edward: Make sure to have fixed length MPI for get_affine.

Related Objects
Search...

		Status	Assigned	Task
				Unknown Object (Maniphest Task)
		Resolved	• gniibe	T8380 Small-order Ed25519 public keys reach a fatal internal arithmetic assertion

Event Timeline

• werner triaged this task as High priority.Tue, Aug 4, 4:50 PM

• werner created this task.

• werner created this object with visibility "Public (No Login Required)".

• werner created this object with edit policy "Contributor (Project)".

• werner renamed this task from small order ed25519 public keys reach a fatal internal bug to mall-order Ed25519 public keys reach a fatal internal arithmetic assertion.Tue, Aug 4, 5:14 PM

• werner renamed this task from mall-order Ed25519 public keys reach a fatal internal arithmetic assertion to Small-order Ed25519 public keys reach a fatal internal arithmetic assertion.

• werner lowered the priority of this task from High to Normal.Thu, Aug 6, 9:19 AM

• werner added a project: Bug Report.

For Curve25519 and X448, in ec.c, we have _gcry_mpi_ec_bad_point. We can enhance this function to handle Ed25519 and Ed448.
Then use the feature by _gcry_mpi_ec_curve_point (modifying the semantics, a bit).

~~Application can easily add validation of public key against the identity point or small order points.~~ <-- not true, for use of SEXP API.

It would be good for libgcrypt to be responsible (to provide modified gcry_mpi_ec_curve_point, which will validate the point).

I found this for sodium: https://00f.net/2025/12/30/libsodium-vulnerability/

I changed my mind. Adding new internal function, say, _gcry_mpi_ec_validate_point for Ed25519 is better, than modifying the semantics of existing API. Then, use the check in gcry_pk_verify function.

Abort itself can be fixed by this patch:

diff --git a/mpi/ec.c b/mpi/ec.c
index 6f6a7f8d..c879ea01 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -1263,9 +1263,17 @@ _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
 	if (!mpi_cmp_ui (point->z, 1))
 	  {
 	    if (x)
-	      mpi_set (x, point->x);
+              {
+                mpi_set (x, point->x);
+                mpi_resize (x, ctx->p->nlimbs);
+                x->nlimbs = ctx->p->nlimbs;
+              }
 	    if (y)
-	      mpi_set (y, point->y);
+              {
+                mpi_set (y, point->y);
+                mpi_resize (y, ctx->p->nlimbs);
+                y->nlimbs = ctx->p->nlimbs;
+              }
 	    return 0;
 	  }

• gniibe claimed this task.Mon, Aug 10, 3:43 AM

• gniibe mentioned this in Unknown Object (Maniphest Task).Mon, Aug 10, 3:55 AM

In libgcrypt, there is no support for checking public key (yet).
It's good to have such an API, but currently, it's upper layer to do so, before calling libgcrypt functions.

So, the fix is only avoid the abort by non-compliant public key.

• gniibe added a commit: rC659b22897536: mpi:ec:Edward: Make sure to have fixed length MPI for get_affine..Wed, Aug 12, 4:49 AM

• gniibe changed the task status from Open to Testing.Wed, Aug 12, 4:54 AM

• werner added a commit: rC7004c17e28c3: mpi:ec:Edward: Make sure to have fixed length MPI for get_affine..Tue, Aug 18, 3:07 PM

• gniibe mentioned this in Unknown Object (Maniphest Task).Mon, Aug 24, 8:26 AM

• werner shifted this object from the Restricted Space space to the S1 Public space.Tue, Aug 25, 5:15 PM

• werner mentioned this in T8223: Release Libgcrypt 1.12.3.Wed, Aug 26, 10:40 AM

• werner closed this task as Resolved.Wed, Aug 26, 10:43 AM