Chosen Public Keys: Subgroups, Invalid Curves and Acceptance Rules

Every Diffie-Hellman security proof contains a quiet assumption: the value the other side sends is what it claims to be, an honestly generated element of the right group. Real protocols cannot enforce honesty, only validity, and validity has to be checked. When it is not, an attacker who plays the role of a peer can choose a public value deliberately, one that lives in a small subgroup or, for elliptic curves, on a different and much weaker curve, and use the victim's own computation as a measuring instrument. If the victim reuses its private key across exchanges and reveals anything that depends on the shared result, each crafted value yields a few bits of that key, and the bits combine into the whole. These attacks were described in the late 1990s and early 2000s, by Lim and Lee for small subgroups and by Biehl, Meyer and Müller for invalid curves, and they have resurfaced in deployed systems since. This article sets out precisely when they work, why different groups impose different acceptance obligations, and how those obligations translate to the many key exchanges inside AI agent platforms.

The assumption every key exchange makes

In finite-field Diffie-Hellman, parties work in a group of numbers modulo a prime, and security analysis assumes all values lie in a subgroup of large prime order. In elliptic-curve Diffie-Hellman, they work in the group of points on a specified curve, and the analysis assumes all points lie on that curve and in its large prime-order subgroup. A party computes the shared secret by applying its private scalar to the peer's public value. Nothing in that computation checks where the peer's value came from.

The literature calls the countermeasure public-key validation. NIST SP 800-56A distinguishes full validation, which confirms that a value is in range, satisfies the group's defining equation where applicable, and lies in the correct prime-order subgroup, from partial validation, which omits the subgroup membership test when the group structure makes it unnecessary. Whether partial validation is enough depends on the group, which is the main subject of this article.

Throughout, this article distinguishes two kinds of private keys. An ephemeral key is generated fresh for one exchange and discarded. A static key is reused across many exchanges, as in some TLS 1.2 configurations, many embedded protocols, and long-lived service identities. The attacks discussed here depend almost entirely on the second kind.

Small subgroups in finite fields

A multiplicative group modulo a prime has an order equal to the prime minus one, which always has small factors, at least two. For every small factor, there is a subgroup of that size. If a victim with a static private key computes the shared secret using a peer value chosen from a subgroup of small size, the result can only be one of a handful of values, and which one it is depends only on the victim's private key modulo that small size.

Lim and Lee described in 1997 how an attacker exploits this. The attacker sends such a value, then observes something that depends on the resulting shared secret, for example a message the victim encrypts or authenticates with a key derived from it, and tests each of the few possible secrets until one matches. That reveals the private key modulo the subgroup size. Repeating with subgroups of other small sizes yields the private key modulo each, and the Chinese remainder theorem combines the residues into the private key modulo their product. If the small factors of the group order multiply to something at least as large as the private key, the attacker recovers it completely.

Three conditions must therefore hold together: the private key is reused, the attacker can observe a function of the shared secret, and the group order has enough small factors. Removing any one defeats the attack. Safe primes, for which the prime minus one is twice a prime, leave only subgroups of size one and two, so at most one bit leaks; prime-order subgroup checks remove even that.

Invalid curves: when the attacker chooses the curve

Elliptic curves introduce a stronger version of the same attack. The standard formulas for adding and doubling points on a short Weierstrass curve, the form used by P-256, use the curve's linear coefficient but never its constant term. An implementation that performs scalar multiplication on a received point without checking the curve equation will therefore compute correctly on a point that lies on a different curve, one sharing the linear coefficient but with a different constant. The attacker, not the protocol, chooses that curve.

Biehl, Meyer and Müller showed in 2000 that this lets the attacker pick curves whose groups contain points of small order, then proceed as in the small-subgroup attack: send a point of small order on a chosen curve, observe a function of the result, learn the private scalar modulo that order, repeat across many curves, and combine. Unlike the finite-field case, the attacker is not limited to the factors of one group order; by searching for suitable curves, they can collect as many small residues as needed.

A small example illustrates the mechanism. On the toy curve whose equation is y squared equals x cubed plus two x plus two, modulo 17, the point one, zero does not satisfy the equation. It does lie on the curve with constant fourteen instead of two, where it has order two, so multiplying it by a secret scalar yields either the point itself or the point at infinity according to the scalar's parity. The arithmetic never notices the substitution. Jager, Schwenk and Somorovsky reported in 2015 that several TLS libraries performing static elliptic-curve Diffie-Hellman were vulnerable to exactly this class of attack, enabling recovery of server private keys.

Different groups, different acceptance obligations

The required checks are not universal; they follow from group structure. For finite-field groups, the received value must lie strictly between one and the prime minus one, and, unless the group is a safe-prime group where at most one bit could leak, it must also lie in the prime-order subgroup, which is confirmed by raising it to the subgroup order and checking that the result is one. This is full validation in the sense of SP 800-56A.

P-256 has a group of prime order with cofactor one. A point that is correctly encoded, has coordinates in range and satisfies the curve equation is automatically in the right group, so partial validation, the equation check without a separate subgroup test, is sufficient. Omitting the equation check, however, opens the full invalid-curve attack described above.

X25519, specified in RFC 7748, was designed to need almost none of this. It computes only on x-coordinates using a Montgomery ladder, so any 32-byte input corresponds either to a point on Curve25519 or to one on its quadratic twist, and both were chosen to have no exploitable small subgroups beyond the cofactor of eight, a property known as twist security. Private scalars are clamped to multiples of eight, which maps every small-order component to the identity. The remaining obligation is narrower: a handful of low-order inputs force an all-zero output, and RFC 7748 notes that protocols may check for it; TLS 1.3 requires that check. Edwards-curve and other settings carry their own variants, especially around cofactors, which is a reminder that each group's rules must be learned on its own terms.

Where the checks get skipped

Validation logic is easy to specify and surprisingly easy to lose. This article's synthesis of the cases above identifies four recurring patterns. The first is the performance shortcut: a check is removed or made optional because it costs time, typically the subgroup exponentiation in finite fields. The second is the generic code path: a library supports many curves through one routine and validates only some of them, or validates in the parsing layer while a separate code path accepts raw coordinates. The third is the trusted-peer assumption: validation is skipped for values that arrive from a supposedly trusted source, such as a pinned server, without recognising that keys and channels can be compromised. The fourth is format conversion: a point decoded from a compressed form, or converted between libraries, bypasses the routine that would normally have checked it.

Each pattern produces code that interoperates perfectly with honest peers, which is why such defects survive functional testing. Detection requires tests that deliberately send invalid values and confirm they are rejected, which is the basis of the conformance method at the end of this article.

Exposure in AI agent platforms

The three preconditions for chosen-public-key attacks, static keys, observable results and weak acceptance, appear naturally in AI agent platforms, which this article presents as an exposure analysis rather than documented incidents. Tool servers that agents call, especially those built quickly on custom transports, sometimes hold long-lived key-agreement keys for performance or simplicity. Agent-to-agent channels may use key exchanges designed by the platform rather than standard TLS, and their implementations may parse public keys from JSON fields with ad hoc code, which is the format-conversion pattern in its purest form. And an agent that can be steered by injected instructions can be used to initiate exchanges with a server and report observable outcomes, providing the observation channel the attack needs.

The defensive response is mostly a matter of not inventing protocols. Use TLS 1.3 for agent and tool traffic, which uses ephemeral key shares, requires the all-zero check for X25519 and mandates validation of received shares. Where custom key exchange is unavoidable, use a library API that accepts encoded public keys and validates them before any arithmetic, prefer X25519, and never hold static key-agreement keys in agent-facing services. Code assistants generating such glue code should be constrained to those APIs.

Conformance testing and limitations

Acceptance rules can be tested from the outside without implementing any key-recovery algorithm. A conformance suite sends, to a test deployment holding a test key, a fixed catalogue of invalid inputs: out-of-range values, values in small subgroups, points not on the curve, points at infinity and, for X25519, the known low-order inputs. Each must be rejected, or for X25519 must produce the protocol-required abort, before any key-dependent behaviour is observable. Published test vector collections exist for several of these cases, and the method is a natural fit for continuous integration.

This article's analysis is limited to the classical attacks named and to the groups discussed. It does not cover every curve family, such as Edwards curves with cofactor handling subtleties, or post-quantum key-encapsulation mechanisms, which have their own validation rules. The agent-platform exposure is reasoned from the preconditions and the documented behaviour of injected agents, not measured. Finally, a passing conformance suite demonstrates correct behaviour on the tested inputs only, which is why it should be paired with the design choices above that remove static keys altogether.

SETUP  test deployment, test-only key agreement keys
CATALOGUE per group:
    finite_field: [0, 1, p_minus_1, small_subgroup_elements, out_of_range]
    p256:         [off_curve_points, point_at_infinity, bad_encoding, coords_ge_p]
    x25519:       [known_low_order_inputs]
FOR each input in catalogue(group):
    result = handshake(test_endpoint, peer_public=input)
    EXPECT result in {rejected, aborted} before any key-dependent message
REPORT any accepted input as a DEFECT

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

for group in supported_groups(test_endpoint):
    for bad in invalid_catalogue(group):
        r = handshake(test_endpoint, peer_public=bad)
        assert r.status in ('rejected', 'aborted')
        assert not r.emitted_key_dependent_message
report()

agent_and_tool_traffic:
  protocol: tls_1_3_only
  key_shares: [X25519, X25519MLKEM768, P-256]
  static_key_agreement: forbidden
custom_exchange_exception:
  curve: X25519
  public_key_input: library_decode_and_validate_only
  all_zero_check: required
  review: security_team

Glossary

Public-key validation

Checks that a received public value is in range, satisfies the group's equation and lies in the intended subgroup.

Static key

A private key reused across many key exchanges rather than generated fresh for each.

Small-subgroup attack

Sending values from small subgroups to learn a static private key modulo small numbers.

Invalid-curve attack

Sending points that lie on a different, weaker curve so a victim's computation leaks key bits.

Cofactor

The ratio between the total number of points on a curve and the order of its large prime subgroup.

Twist security

The property that a curve's quadratic twist is also free of exploitable small subgroups.

Clamping

Fixing bits of an X25519 private scalar so it is a multiple of the cofactor and has a fixed length.

Contributiveness

The property that each party's input influences the shared secret, so neither can force a known value.

References

1. C. H. Lim, P. J. Lee, A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup, CRYPTO 1997
2. I. Biehl, B. Meyer, V. Müller, Differential Fault Attacks on Elliptic Curve Cryptosystems, CRYPTO 2000
3. T. Jager, J. Schwenk, J. Somorovsky, Practical Invalid Curve Attacks on TLS-ECDH, ESORICS 2015
4. NIST SP 800-56A Rev. 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography
5. RFC 7748: Elliptic Curves for Security (IETF)
6. RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS (IETF)
7. RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3 (IETF)