Skip to content

PATTERN Cited by 2 sources

Protocol algorithm negotiation

Shape

Protocol algorithm negotiation is the protocol-design pattern where each side of a connection advertises its supported algorithms (by name, in preference order), and the handshake selects the highest-preference algorithm in the intersection of the two lists. The selection happens at connection establishment; the outcome is a single, mutually-supported algorithm used for the rest of the session.

Client  → advertise: [alg1, alg2, alg3, ...]
Server  ← advertise: [alg2, alg4, alg5, ...]
Both    → negotiate:  alg2   (first mutual match in preference order)

This is structurally distinct from version negotiation (which picks one monotonic version number) because the algorithm set can grow, shrink, and reorder independently of any version scheme.

Why it matters: non-breaking rollout of new primitives

The dominant value of this pattern is crypto-agility without a flag day. When a new primitive (post-quantum KEX, a new symmetric cipher, a new signature algorithm) is ready for deployment:

  1. Server adds the new algorithm to its supported list (usually at high preference).
  2. Clients that already support it (because the library vendor shipped it earlier) auto-select it.
  3. Clients that don't support it negotiate the best classical algorithm they share with the server.

No client-side configuration. No connection breakage. No coordinated rollout. The installed base rolls forward as client libraries update.

"If your SSH client supports sntrup761x25519-sha512@openssh.com or sntrup761x25519-sha512 (for example, OpenSSH 9.0 or newer), it will automatically choose the new algorithm by default if your client prefers it. No configuration change should be necessary unless you modified your client's defaults."

"If you use an older SSH client, your client should fall back to an older key exchange algorithm. That means you won't experience the security benefits of using a post-quantum algorithm until you upgrade, but your SSH experience should continue to work as normal, since the SSH protocol automatically picks an algorithm that both sides support." (Source: sources/2025-09-15-github-post-quantum-security-for-ssh-access-on-github)

Canonical instances

  • SSH key-exchange negotiation. KEXINIT message carries a comma-separated list of KEX algorithms; both sides send, first mutual match wins. GitHub's 2025 sntrup761x25519-sha512 rollout is a textbook instance. (Source: sources/2025-09-15-github-post-quantum-security-for-ssh-access-on-github)
  • TLS cipher suite negotiation (TLS 1.2) / supported_groups + key_share (TLS 1.3). PQ hybrid groups like X25519MLKEM768 roll out the same way.
  • HTTP content negotiation. Accept-Encoding: gzip, br, zstd — same shape, for compression algorithms.
  • WebRTC codec negotiation. SDP offer/answer lists codecs (VP8, VP9, H.264, AV1); session picks the intersection.
  • DNS message algorithm-list (DNSSEC: signer advertises supported algorithms in DNSKEY; resolver picks).
  • SMTP STARTTLS + EHLO-advertised extensions — same pattern for transport encryption upgrade.

Three design requirements

1. Algorithm names are globally unique strings. The negotiation requires both sides to agree on what alg2 means. In SSH these are strings like ssh-rsa, ecdsa-sha2-nistp256, sntrup761x25519-sha512. Vendor extensions use a namespace prefix (@openssh.com during the pre-standard era) that gets dropped when the algorithm is promoted to standard name — both names often coexist for a transition window so older clients still match.

2. Preference order drives rollout. The server's preference order is what determines which mutually-supported algorithm is picked when several match. Placing the new primitive at the top of preference lets it take effect as soon as clients support it; placing it at the bottom makes it a fallback only.

3. Empty-intersection failure must be diagnosable. If neither side has any algorithm the other supports, the handshake fails. The error needs to identify what each side offered so the operator can see which library needs updating. SSH's kex_exchange_identification error with full algorithm lists is a good example.

Four failure modes

  • Downgrade attacks. An MITM can strip strong algorithms from the advertised list to force selection of a weaker one. Mitigation: authenticate the handshake transcript so any tampering is detected (SSH binds the KEXINIT into the exchange-hash; TLS 1.3 signs the transcript). This is why SSH's key-exchange hash includes both KEXINIT messages verbatim.
  • Preference disagreement deadlocks. Rare but real: if client and server have different preference orderings over the same algorithm set, and the protocol uses server preference, a poorly designed server might pick an algorithm the client technically supports but intended only as a fallback. Usually mitigated by the protocol spec choosing one side as authoritative (SSH defaults to client order; TLS 1.3 defaults to server order).
  • Algorithm list as fingerprint. The advertised list is a client fingerprint (JA3/JA4 in TLS). Not a security failure of the negotiation itself, but a privacy consideration — clients that advertise unusual algorithm sets are trivially tracked.
  • Algorithm-string parsing bugs. A malformed or pathological algorithm name in the list can crash parsers. Not unique to this pattern but worth noting.

Regional / policy-driven list filtering

A server can legitimately advertise different algorithm lists in different deployments — the FIPS-boundary case (concepts/fips-cryptographic-boundary) is the canonical instance. The negotiation pattern lets policy-driven filtering happen server- side without client awareness: the FIPS-region server just doesn't include non-FIPS-approved algorithms in its advertised list, and clients negotiate the best remaining match.

This is why GitHub can roll sntrup761x25519-sha512 to non-US regions but not to US-region GHEC: same protocol, same product, different advertised list.

Contrast with alternatives

  • Flag-day rollout. Ship new algorithm to clients first, then flip server on a fixed date. Breaks if any client isn't updated — untenable for a heterogeneous installed base.
  • Per-user configuration. Users manually pick which algorithm to use. Terrible UX, no default-safe behaviour.
  • Tunnel upgrade. Establish a classical connection, upgrade mid- session to the new primitive. Works in some protocols (STARTTLS is this shape) but adds round-trip latency and complexity.

Algorithm negotiation is strictly better than all three for rolling out new primitives into an installed base.

Relationship to concepts/backward-compatibility

Algorithm negotiation is one of the strongest forms of backward compatibility — grammar-level inclusion at the protocol layer. Old and new algorithms coexist in the same protocol grammar; the handshake is the "parser" that picks which to use. A client that only speaks old algorithms still parses and completes the handshake successfully.

The three-layer validation frame in concepts/backward-compatibility maps cleanly: grammar inclusion ≈ algorithm coexistence; test-suite re-run ≈ handshake test matrix across client/server version combos; dark-ship ≈ monitoring the negotiated-algorithm distribution in production.

Seen in

Last updated · 200 distilled / 1,178 read