7. Handshake Protocol
PALISADE uses a 1-RTT authenticated post-quantum handshake to establish a secure tunnel between a client and a server. The handshake performs mutual authentication, establishes shared secrets using post-quantum KEMs, and derives all traffic keys using the key schedule defined in Section 6.
Unless otherwise specified, all handshake messages described in this section are transmitted in cleartext but are cryptographically bound into the handshake transcript.
7.1 ClientHello
The ClientHello message is sent by the client to initiate a new PALISADE session.
A ClientHello MUST contain the following fields (fields appear in the order defined by the deterministic serialization rules in Appendix D):
- version — The highest PALISADE protocol version supported by the client.
- supported_kems[] — An ordered list of KEM identifiers supported by the client.
- supported_sigs[] — An ordered list of post-quantum signature algorithms supported by the client.
- supported_aeads[] — An ordered list of AEAD algorithms supported by the client.
- client_nonce — A cryptographically random 32-byte nonce generated by the client.
- K_c — The client's ephemeral KEM public key.
- client_certificate — The client's long-term post-quantum public key used for authentication. This field is mandatory for all full handshakes.
The ClientHello MUST NOT include application data.
The ClientHello MAY include extensions, subject to the constraints defined in Section 16 and the deterministic serialization rules defined in Appendix D.
7.2 ServerHello
Upon receipt of a valid ClientHello, the server responds with a ServerHello message.
The ServerHello MUST contain:
- version — The negotiated PALISADE protocol version.
- kem_choice — The KEM selected by the server from the client's offered list.
- sig_choice — The signature algorithm selected by the server from the client's offered list.
- aead_choice — The AEAD algorithm selected by the server from the client's offered list.
- server_nonce — A cryptographically random 32-byte nonce generated by the server.
- K_s — The server's ephemeral KEM public key.
- CT_c — The ciphertext resulting from encapsulation to the client's KEM public key K_c.
- CT_s — The ciphertext resulting from encapsulation to the server's KEM public key K_s.
- server_certificate — The server's long-term post-quantum public key.
- server_signature — A digital signature computed over the handshake transcript to this point, binding the ServerHello to the ClientHello.
The ServerHello MAY include extensions.
7.3 Handshake Completion
After transmitting the ServerHello:
- The client decapsulates CT_c to obtain ss_c.
- The client decapsulates CT_s to obtain ss_s.
- Both endpoints derive shared secrets and traffic keys using the key schedule defined in Section 6.
- Both endpoints verify all required signatures.
Upon successful verification and key derivation, the handshake is complete.
The first encrypted application data packet sent by the client implicitly confirms handshake completion.
The full handshake requires exactly one round trip (1-RTT).
If any verification step fails, the handshake MUST be aborted and all derived secrets MUST be securely erased.
Authentication and key derivation are bound to the handshake transcript as defined in Section 3.2.
7.4 Handshake Message Size Limits and Parsing Safety
To prevent memory-exhaustion and parsing-based denial-of-service attacks, PALISADE defines strict limits on handshake message sizes and mandates defensive parsing behavior.
7.4.1 Global Message Size Limits
Implementations MUST enforce the following absolute limits:
- ClientHello maximum size: 128,000 bytes (125 KB)
- ServerHello maximum size: 128,000 bytes (125 KB)
Any handshake message exceeding these limits MUST be rejected prior to full parsing with an appropriate error indication (e.g., ErrorPacketTooLarge), and all partially allocated resources MUST be released.
These limits are intentionally conservative and provide sufficient headroom for future extensions while preventing unbounded allocation.
7.4.2 Individual Field Size Limits
The following maximum sizes apply to individual fields within handshake messages:
| Field | Maximum Size | Rationale |
|---|---|---|
| Supported KEMs list | 16 entries | Bounds algorithm negotiation |
| Supported signature algorithms | 16 entries | Bounds algorithm negotiation |
| Supported AEAD algorithms | 16 entries | Bounds algorithm negotiation |
| KEM public key | 2,048 bytes | Covers ML-KEM-1024 with margin |
| KEM ciphertext | 2,048 bytes | Covers ML-KEM-1024 with margin |
| Certificate | 8,192 bytes | Covers Dilithium-class keys with margin |
| Signature | 4,096 bytes | Covers Dilithium-class signatures |
| Padding | 4,096 bytes | Bounds traffic analysis resistance |
| DoS cookie | 1,024 bytes | Sufficient entropy for stateless validation |
| Individual extension | 4,096 bytes | Prevents oversized extension abuse |
| Total extensions block | 65,536 bytes (64 KB) | Prevents extension-based memory exhaustion |
Any field exceeding its maximum size MUST cause immediate handshake rejection.
7.4.3 Defensive Parsing Requirements
Implementations MUST apply the following parsing rules:
- MUST validate the total message size before allocating buffers for parsing.
- MUST validate each individual length field before consuming the associated data.
- MUST immediately reject a message if any length field would cause the total parsed size to exceed the global limit.
- MUST NOT continue parsing after detecting a size violation.
- MUST securely erase any partially derived secrets on error paths.
These requirements are mandatory to prevent integer-overflow, buffer-overflow, and memory-exhaustion vulnerabilities.
7.4.4 Operational Guidance (Non-Normative)
Typical handshake sizes are significantly smaller than the allowed limits:
- Typical ClientHello: ~2–4 KB
- Typical ServerHello: ~6–8 KB
The 128 KB limit exists solely for robustness and future extensibility; implementations SHOULD log rejected oversized handshake attempts for security monitoring and anomaly detection.
7.5 Authentication and Signature Semantics
PALISADE provides mutual authentication during full handshakes using post-quantum digital signatures. Authentication semantics are tightly bound to the handshake transcript to ensure integrity, downgrade resistance, and correct key association. As a result, all full PALISADE handshakes provide cryptographically bound mutual authentication prior to the establishment of application traffic keys.
7.5.1 Client Authentication
In all full handshakes, the client MUST authenticate to the server.
The client MUST present a long-term post-quantum public key (the client certificate) in the ClientHello message. The client proves possession of the corresponding private key by generating a digital signature over the handshake transcript hash. For the purposes of this specification, a “certificate” refers to an authenticated public-key identity object and is treated as an opaque byte string. PALISADE does not require X.509.
The client signature is computed as:
client_signature = SIG_client_privkey( transcript_hash )
Where transcript_hash is defined in Section 3.2.
The client signature MUST NOT include itself as input to the transcript hash. This prevents circular dependencies and ensures deterministic transcript computation.
If the client certificate or signature is missing, malformed, or fails verification, the server MUST abort the handshake.
Client authentication is not required during resumption handshakes, as resumption security is instead provided by possession of a valid resumption ticket (see Section 11).
7.5.2 Server Authentication
The server MUST authenticate to the client in all handshakes.
The server MUST present a long-term post-quantum public key (the server certificate) in the ServerHello message and generate a digital signature over the handshake transcript hash:
server_signature = SIG_server_privkey( transcript_hash )
The server signature MUST NOT be included in the transcript hash itself.
The client MUST verify the server signature before accepting the handshake and deriving application traffic keys. Failure to verify the server’s identity MUST abort the handshake..
7.5.3 Certificate and Algorithm Requirements
PALISADE v1.1 mandates the use of post-quantum-only signature schemes for endpoint authentication.
Hybrid certificates containing both classical and post-quantum signatures MUST NOT be used in v1.1.
All certificates MUST correspond to a signature algorithm negotiated during the handshake.
Certificate formats are protocol-specific and are treated as opaque byte strings by PALISADE.
Future versions of PALISADE MAY introduce hybrid or alternative authentication mechanisms via extensions.
7.5.4 Security Properties
These authentication semantics ensure:
- Mutual Authentication: Both endpoints cryptographically verify each other's identities.
- Transcript Binding: Authentication is bound to the exact handshake parameters exchanged.
- Downgrade Resistance: Negotiated algorithms are included in the authenticated transcript.
- Key Binding: Session keys are cryptographically associated with the authenticated identities.
- Post-Quantum Security: Authentication remains secure against adversaries with large quantum computers.
7.5.5 Error Handling
If any authentication step fails, implementations MUST:
- Abort the handshake immediately.
- Securely erase all partially derived secrets.
- Release any allocated session state.
Authentication failures MUST NOT result in distinguishable error messages that could be used to infer valid certificates or keys.
PALISADE Protocol Specification Draft 00
INFORMATIONAL