PaperlayerView exact revision on arXiv

Source-linked AI summary

A Drop-in KEM Replacement for Client Signatures in Post-Quantum SSH

Hongbo Liu, Yufan Su, Jiangxia Ge, Qionglu Zhang, Zhaoxuan Li, Xianhui Lu, Li Song, Wenhua Gao, Li Zhou

arXiv:2608.24447v1cs.CR

TL;DR

Post-quantum SSH authentication largely inherits the size and computation costs of post-quantum signatures, motivating alternatives that retain SSH’s credential model without redesigning its transport. The paper presents KEMUAuth, a drop-in session-bound KEM proof, analyzes and implements it, and finds competitive performance with larger benefits under signature-heavy network or computation constraints.

  • Problem

    SSH authentication largely follows signature replacement, inheriting post-quantum signature size and computation overhead that can increase latency, traffic, and server-side load.

  • Method

    KEMUAuth replaces the client signature in SSH user authentication with a session-bound KEM challenge–response proof inside the existing authentication framework.

  • Results

    KEMUAuth is competitive with ML-DSA under common settings and, under small TCP initial windows, reduces median latency by 7.0–7.3% versus ML-DSA while lowering server-side online cryptographic cost by 59.1%.

  • Takeaways & Limitations

    KEMUAuth provides a practical, lightweight middle ground for post-quantum SSH authentication while preserving SSH’s transport semantics and incremental coexistence with existing methods.

  • Takeaways & Limitations

    Protocol-level ACCE security does not cover concrete implementation leakage; deployment additionally relies on constant-time decapsulation and broader side-channel and fault-injection assessment.

Abstract

from arXiv · show

The transition to post-quantum cryptography is reshaping the Secure Shell (SSH) protocol for remote administration. Post-quantum key exchange has been deployed in OpenSSH and is being standardized, while SSH authentication largely remains a signature-replacement effort. This path preserves the familiar public-key credential model, but inherits the size and computation overhead of post-quantum signatures, which can increase latency, traffic, and server-side load. KEM-based authentication offers a natural alternative to this signature-centric path, and SSH makes this especially attractive at the user-authentication layer, which is method-extensible, separated from transport-layer key exchange and host-key authentication, and already protected by the established channel. We present a drop-in KEM-based user-authentication method for SSH that replaces client public-key signatures with a session-bound challenge-response proof. The method fits into SSH's existing user-authentication framework, preserving the public-key credential model and enabling incremental deployment alongside existing methods. We provide a reduction-based security argument in the post-quantum ACCE framework, implement the design in OpenSSH using liboqs, and evaluate it under representative RTTs, TCP initial-window settings, and post-quantum migration configurations. Our results show that KEM-based authentication is competitive with compact signature-based authentication under representative network settings, while reducing median handshake latency by up to about 10% against large-signature hybrid baselines. The advantages are clearer when post-quantum signatures stress transmission or computation: median latency under small TCP initial windows falls by up to 7.3% versus ML-DSA and 17.9% versus SLH-DSA, while server-side online cryptographic cost is 59.1% lower than that for ML-DSA in the same NIST category.

I. INTRODUCTION

Post-quantum SSH has adopted KEMs for transport key exchange while user authentication largely replaces classical signatures with post-quantum signatures, inheriting their size and computation costs. This paper introduces a drop-in KEM-based user-authentication method, analyzes it in post-quantum ACCE, implements it in OpenSSH, and evaluates migration performance.

  • Post-quantum SSH key exchange is entering deployment and standardization, while authentication has largely retained public-key credentials with post-quantum signature replacements.
  • Up to 50% higher latency has been measured for signature-based post-quantum SSH handshakes.
  • SSH’s separated, method-extensible user-authentication layer runs inside the established protected channel, creating a local integration point for KEM authentication.
  • The paper studies KEMUAuth through post-quantum ACCE analysis, an OpenSSH implementation, and controlled evaluation across RTTs, TCP windows, and migration configurations.
  • KEMUAuth preserves SSH’s public-key credential model, replaces client signatures with a session-bound KEM proof, adds no SSH round trips, and supports existing multi-method policies.
  • Under small TCP initial windows, KEMUAuth reduces median handshake latency by 7.0–7.3% versus ML-DSA and lowers measured server-side online cryptographic cost by 59.1%.

B. KEMs

This section defines KEM primitives and the ACCE model used to describe SSH’s transport establishment, user authentication, and protected channel. The model requires negligible malicious-acceptance and channel-security advantages against quantum-polynomial adversaries.

  • KEMs: A KEM consists of KeyGen, Encap, and Decap algorithms that establish a shared secret with the holder of a corresponding secret key.
  • KEMs: KEM correctness requires Decap(sk, ct) to recover the encapsulated secret except with negligible probability.
  • KEMs: IND-CCA security permits decapsulation queries except on the challenge ciphertext, and requires negligible distinguishing advantage for every efficient adversary.
  • KEMs: The SSH analysis assumes IND-CPA security for ephemeral transport KEMs and IND-CCA security for long-term client KEM authentication.
  • SSH and ACCE: SSH’s transport layer establishes the session identifier and encrypted channel, while user authentication verifies the client inside that channel without changing the protocol layering.
  • SSH and ACCE: ACCE authentication requires that neither client nor server accepts without a unique honest matching peer session, with negligible probability for quantum-polynomial adversaries.
  • SSH and ACCE: ACCE channel security requires negligible advantage for fresh accepted test sessions after encryption and decryption interactions subject to freshness conditions.

III. KEM-BASED USER AUTHENTICATION FOR SSH

KEMUAuth replaces the client signature in SSH public-key authentication with a session-bound KEM challenge–response while leaving transport and host-key authentication unchanged. The server challenges an authorized public key, and the client returns a PRF-derived response tied to the SSH session and authentication transcript.

  • Design overview: KEMUAuth confines the change to the user-authentication proof and coexists with SSH’s existing signature-based publickey method.It runs after the transport layer establishes the encrypted channel and session identifier, leaving key exchange, host-key authentication, and connection semantics unchanged.
  • Protocol flow: The client begins with an encrypted publickey-kem request containing the username, service, algorithm identifier, and authorized KEM public key.The server maintains authorized public keys for usernames and proceeds with a KEM challenge when the key is authorized.
  • Session binding: The authentication context encodes the KEMUAuth transcript, including request fields, challenge fields, and the response message type, but not the response value.This provides an unambiguous representation of the authentication attempt.
  • Protocol flow: The server challenges the client with a ciphertext and computes the expected response from the encapsulated key, session identifier, and authentication context.The challenge echoes the algorithm and public key and carries the ciphertext; the client checks the echoed fields before decapsulation.
  • Session binding: The response is derived with PRFCA from the encapsulated key, session identifier, and encoded context, then returned in SSH_MSG_USERAUTH_KEM_RESPONSE.The server accepts only when its recomputed response matches the client’s response.
  • Security and deployment properties: Binding to the session identifier and context prevents cross-session replay and binds the proof to the selected authentication attempt, while server knowledge of the key makes it deniable.The method uses two method-specific user-authentication messages and preserves existing credentials and multi-method policies.

IV. SECURITY ANALYSIS

The security analysis extends SSH’s ACCE treatment to mutual authentication by adding the server’s acceptance of a KEMUAuth-authenticated client as the central new proof obligation. Game-based reductions connect this event to the client KEM’s IND-CCA security and the response PRF, and lift the argument to quantum adversaries.

  • Proof scope: KEMUAuth leaves transport key exchange, host-key authentication, and channel-key derivation unchanged, so the new proof obligation is server acceptance of a KEM-authenticated client.The analysis first proves mutual ACCE authentication and then composes it with existing SSH channel-security results.
  • Security definition: The authentication definition extends SSH ACCE malicious acceptance from one-way to mutual authentication across initiator and responder sessions.A session is maliciously accepted when it believes its peer is uncorrupted but lacks a unique matching opposite-role session.
  • Proof strategy: The mutual-authentication proof uses game hopping, excluding nonce and hash collisions, guessing the first accepting session, and splitting the analysis by accepting role.The collision and guessing terms depend on the transport cookies, party count, and session count.
  • Proof strategy: The malicious-client case reduces acceptance without a matching server session to host-key forgery or compromise of transport-layer KEM, key-schedule, and channel-encryption protections.The argument uses EUF-CMA security for the host-key signature, IND-CPA security for the transport KEM, PRF security for the key schedule, and authenticated-encryption security.
  • Proof strategy: In the malicious-server case, distinguishing the target encapsulated key yields an IND-CCA attack against the client KEM, while replacing the response with random yields a PRF security loss.The target response is evaluated at a fresh session-bound input, so the remaining acceptance probability is bounded by the underlying terms.
  • Quantum security: The post-quantum theorem assumes quantum security for the hash, signature, KEM, PRF, and authenticated-encryption primitives and applies the same reduction structure to QPT adversaries.The reductions are straight-line and black-box and do not use random-oracle programmability, rewinding, forking, or measurements of the adversary’s state.

B. ACCE Channel Security

The channel-security analysis reuses the existing post-quantum SSH proof because KEM-authentication messages occur only after channel keys are established and do not affect transport derivation. Security therefore reduces to the transport KEM, SSH key schedule, and channel encryption, conditioned on authentication security where needed.

  • Proof reuse: KEM-authentication messages are sent inside the encrypted channel after SSH_MSG_NEWKEYS and are absent from transport key exchange, session-identifier derivation, and channel-key derivation.This confines the protocol modification to user authentication and justifies composing with the existing SSH channel analysis.
  • Classical channel security: The classical channel-security proof aborts on malicious acceptance, then guesses the test session and partner before replacing the transport KEM secret and key-schedule output.The resulting channel is embedded into a BSAE challenger.
  • Post-quantum channel security: The post-quantum channel-security theorem treats execution-oracle sessions as honestly generated with matching partners, so no KEM-authentication malicious-acceptance abort is needed.The quantum proof replaces the transport KEM and key-schedule outputs and embeds the channel into a quantum-secure BSAE challenger.
  • Post-quantum channel security: The channel-security bound depends on the transport-layer KEM, SSH key schedule, and channel encryption rather than the KEM-authentication response layer.This follows because authentication messages occur only after channel keys are established.

C. Security Role of PRFCA

The paper derives PRFCA’s session-bound authentication role and evaluates KEMUAuth as an implementable SSH user-authentication method. Controlled measurements compare its latency and cost with signature-based alternatives across network and migration settings.

  • Security role of PRFCA: PRFCA binds the KEM shared secret to the SSH session and authentication context, reducing malicious-server acceptance to guessing an ℓ-bit response after IND-CCA and PRF reductions.The construction uses the session identifier and authentication context as inputs to the expected response.
  • Evaluation design: The evaluation measures primitive costs, end-to-end latency, TCP initial-window effects, and server-side online authentication cost under controlled OpenSSH experiments.The setup uses representative RTTs, repeated handshakes, and a fixed post-quantum transport key exchange unless otherwise specified.
  • Implementation: KEMUAuth is implemented as the coexistible publickey-kem SSH method using liboqs and ML-KEM-512, ML-KEM-768, and ML-KEM-1024 client credentials.The response is an HMAC-SHA-2 value over a fixed label, the SSH session identifier, and the canonical authentication context.
  • Isolated client authentication: 840.68 ms median latency for ML-KEM-768 remains within about 2 ms of Ed25519, ML-DSA, and Falcon at approximately 67 ms RTT.The comparison fixes Ed25519 server authentication and the mlkem768x25519-sha256 transport exchange; SLH-DSA reaches 929.32 ms and 1017.96 ms for its two listed variants.
  • Migration configurations: 9.8%, 8.6%, and 8.2% lower median handshake latency is reported for ML-KEM client authentication replacing SLH-DSA at close, intermediate, and long RTTs.The migration comparison uses the same SLH-DSA server authenticator, while multi-step configurations are slower because they add a serial authentication stage.

E. Transport Effects of Authentication Object Size

The evaluation isolates how authentication-object size affects SSH latency and server-side cryptographic cost. KEMUAuth shows its clearest advantages when large post-quantum signatures strain transmission or verification, while broader deployment boundaries remain relevant.

  • Transport effects: 7.3% lower median latency at 5 MSS: mk768 + md65 versus md65 + md65 under ML-DSA.At 3 MSS, the reduction is 7.0%; at 7 MSS and above, the difference remains within 0.3% with no consistent direction.
  • Transport effects: 17.9% lower median latency at 3 MSS: mk768 + sd192f versus sd192f + sd192f under SLH-DSA.The reduction is 13.5% at 5 MSS and 8.9% at the default 10 MSS.
  • Server-side cost: 0.009 ms per credential: ML-KEM-768 plus HMAC costs 59.1% less than ML-DSA-65 verification at 0.022 ms in NIST category 3.KEMUAuth has lower per-credential server-side cryptographic cost than all evaluated signature-verification baselines.
  • Server-side cost: 4.5% higher connection-completion rate at one worker: KEMUAuth versus ML-DSA-65 in the concurrent-load experiment.The gains are 3.3%, 1.4%, 1.1%, and 0.35% at 8, 16, 32, and 64 client workers, respectively.
  • Deployment scope: KEMUAuth is evaluated as a client-authentication method because SSH separates user authentication from transport key exchange and server authentication.Extending KEM authentication to the server would require broader changes and could add messages, especially affecting high-latency links.
  • Deployment scope: KEMUAuth is deniable and therefore suits online access control, whereas deployments requiring nonrepudiation should retain signatures or combine methods.The server can reproduce and simulate a valid transcript because it creates the challenge ciphertext and obtains the shared secret.

APPENDIX A CRYPTOGRAPHIC DEFINITIONS

The appendix defines the cryptographic primitives, security notions, and ACCE model used to analyze KEM-based client authentication in SSH. It specifies KEM correctness and indistinguishability, PRF and authenticated-encryption notions, and per-session protocol state.

  • Hash functions: A hash function maps arbitrary-length bit strings to fixed-length outputs, with collision resistance requiring negligible probability of finding distinct colliding messages.The appendix denotes this collision probability by H(A).
  • Pseudorandom functions: A PRF maps a key and input to a fixed-length output and is secure when oracle access is indistinguishable from access to a random function.The experiment gives the adversary adaptive oracle access before it guesses which oracle it received.
  • Authenticated encryption: A stateful authenticated-encryption scheme maintains state across initialization, encryption, and decryption while providing ciphertext indistinguishability and ciphertext integrity.Decryption returns either a plaintext or rejection together with an updated state.
  • Key encapsulation mechanisms: A KEM uses KeyGen, Encap, and Decap to generate keys, encapsulate a shared secret into a ciphertext, and recover it or reject.Correctness requires decapsulation to recover the encapsulated secret except with negligible probability; IND-CPA and IND-CCA are the stated indistinguishability notions.
  • ACCE model: The ACCE model captures classical and post-quantum SSH adversaries, including harvest-now-decrypt-later attacks through the OExecute oracle.Sessions track peer identity, status, channel keys, session identifier, and encryption or decryption state; handshake algorithms update these variables and eventually establish them.

B. Adversary interaction

The ACCE model gives the adversary controlled interaction with SSH sessions through execution, network, corruption, encryption, decryption, and reveal oracles. Security is defined through malicious acceptance and channel-challenge experiments, with post-quantum analysis restricting active interaction to honest executions.

  • Adversary interaction: The adversary can initiate, deliver, reorder, alter, or drop network messages through session-send interactions.These interactions create sessions when needed, process messages, and return protocol outputs.
  • Adversary interaction: Honest executions expose complete transcripts and model passive eavesdropping, including harvest-now, decrypt-later attacks.In the post-quantum ACCE model, honest execution replaces active sending.
  • Adversary interaction: The oracle interface also models session-key leakage, long-term private-key compromise, and authenticated encryption or decryption queries.Encryption and decryption queries apply after session acceptance during the channel phase.
  • Security experiments: Mutual-authentication security measures the probability that any initiator or responder accepts maliciously without the required matching session conditions.The post-quantum experiment uses a quantum polynomial-time adversary.
  • Security experiments: Post-quantum channel security uses OExecute, OReveal, OCorrupt, OEncrypt, and ODecrypt, with freshness conditions excluding specified reveals and premature corruption.Because OExecute creates both sides honestly, authentication is automatically satisfied and security reduces to channel security.

D. Mutual Auth. Mode Security

The mutual-authentication proof follows the Figure 6 protocol through a sequence of games that exclude nonce and hash collisions, signature forgery, KEM indistinguishability, PRF, and channel-authentication failures. The protocol runs inside BSAE using the established transport key.

  • Game sequence: The proof begins with the original ACCE authentication experiment and defines malicious acceptance as the event being bounded across successive games.The game sequence follows the protocol flow and state definitions in Figure 6.
  • Game sequence: Nonce-collision probability is bounded across at most nP nS sessions, while hash-collision events reduce to collision resistance.These exclusions establish unique session identifiers and distinct signed inputs.
  • Client case: A client’s malicious acceptance implies either a server-signature forgery or a failure of the transport KEM and PRF replacements.The reduction embeds IND-CPA challenges and replaces PRF-derived channel values with independent random strings.
  • Client case: After the game replacements, channel keys are independent random strings and malicious acceptance would require forging authenticated-encryption ciphertexts.The BSAE reduction therefore makes the final client-case bad event occur with probability 0.
  • Conclusion: The proof combines the client and server cases with losses from the preliminary games to obtain the final mutual-authentication bound.The server target cannot accept maliciously in the final game.
  • Server case: In the server case, the client authentication value is PRFCA(KC, y), where y binds the session identifier and authentication context.The reduction replaces the target value with a random string after hiding KC through an IND-CCA step.

KEMC (B6)

The KEMC proof replaces the target server authentication value with a random string after hiding the encapsulated key. A non-target simulation is unlikely to hit the same PRF input, so the target server rejects malicious responses.

  • KEMC (B6): The target server authentication value ca′ = PRFCA(KC, y) is replaced by a uniformly random string under PRF security.The target key KC is hidden from the adversary after the IND-CCA replacement.
  • KEMC (B6): The target PRF input combines the transport session identifier with the canonical authentication context, y⋆ = π⋆.sid ∥ctx⋆.The context includes the authentication request and challenge ciphertext.
  • KEMC (B6): The probability that a non-target simulation hits y⋆ is negligible because the transport exchange contains randomness protected by earlier collision exclusions.This probability is absorbed into the preceding bad-event bounds.
  • KEMC (B6): Since ca′ is independent of the adversary’s prior view, the final game always rejects the target authentication response and cannot accept maliciously.The games differ only if the target input is guessed.
  • KEMC (B6): Combining the server-case game transitions completes the KEMC proof.The result is incorporated into the overall mutual-authentication analysis.

APPENDIX C CONCURRENT SERVER EVALUATION

The concurrent server evaluation compares KEMUAuth with ML-DSA-65 under increasing worker concurrency. KEMUAuth provides modest throughput and CPU advantages, while latency and memory remain closely matched as the server saturates.

  • Evaluation setup: The evaluation fixes mlkem768x25519-sha256 for transport and ssh-mldsa-65 for server authentication, using five-run medians across concurrency levels N ∈ {1, 8, 16, 32, 64}.Tests use pinned CPU resources and measure throughput, latency, CPU time, and memory.
  • Throughput and CPU: KEMUAuth achieves slightly higher successful throughput and lower CPU time per completed connection across the tested concurrency levels.Its connection rate is 4.5% and 3.3% higher than ML-DSA-65 at N = 1 and N = 8.
  • Throughput and CPU: Throughput differences narrow to 1.4%, 1.1%, and 0.35% at N = 16, N = 32, and N = 64, respectively, producing closely matched saturated throughput.Common SSH processing costs dilute the primitive-level difference as CPU saturation increases.
  • Latency and memory: 95th-percentile latency rises from 79–83 ms at N = 1 to 665–680 ms at N = 64, while KEMUAuth remains slightly lower at each tested concurrency.Aggregate peak memory reaches 242.9 MB for KEMUAuth and 244.4 MB for ML-DSA-65 at N = 64.
  • Latency and memory: Pending-authentication memory is estimated using separate linear fits normalized to the same pending count rather than unmatched raw memory peaks.The procedure delays client responses so multiple authentication attempts remain pending simultaneously.

APPENDIX D DETAILED EVALUATION RESULTS

The appendix provides the numerical results underlying the detailed evaluation, covering handshake latency across configured RTTs, random packet loss, client-authentication algorithms, and TCP initial congestion-window sizes.

  • The appendix supplies numerical results underlying Section V and follows the setup described in Section V-B.
  • Tables VI and VII report end-to-end SSH handshake latency across configured RTTs and under random packet loss.
  • Table VIII provides raw end-to-end SSH handshake latency for different client-authentication algorithms.
  • Tables IX and X provide raw end-to-end SSH handshake latency under different RTT regimes and TCP initial congestion-window sizes.
Loading 2608.24447v1…