The Secure Shell (SSH) protocol is one of the first security protocols on the Internet to upgrade itself to resist attacks against future quantum computers, with the default adoption of the “quantum (otherwise, classically)” secure hybrid key exchange in OpenSSH from April 2022. However, there is a lack of a comprehensive security analysis of this quantum-resistant version of SSH in the literature: related works either focus on the hybrid key exchange in isolation and do not consider security of the overall protocol, or analyze the protocol in security models which are not appropriate for SSH, especially in the “post-quantum” setting. In this paper, we remedy the state of affairs by providing a thorough post-quantum cryptographic analysis of SSH. We follow a “top-down” approach wherein we first prove security of SSH in a more appropriate model, namely, our post-quantum extension of the so-called authenticated and confidential channel establishment (ACCE) protocol security model; our extension which captures “harvest now, decrypt later” attacks could be of independent interest. Then we establish the cryptographic properties of SSH's underlying primitives, as concretely instantiated in practice, based on our protocol-level ACCE security analysis: for example, we prove relevant cryptographic properties of “Streamlined NTRU Prime”, a key encapsulation mechanism (KEM) which is used in recent versions of OpenSSH and TinySSH, in the quantum random oracle model, and address open problems related to its analysis in the literature. Notably, our ACCE security analysis of post-quantum SSH relies on the weaker notion of IND-CPA security of the ephemeral KEMs used in the hybrid key exchange. This is in contrast to prior works which rely on the stronger assumption of IND-CCA secure ephemeral KEMs. Hence we conclude the paper with a discussion on potentially replacing IND-CCA secure KEMs in current post-quantum implementations of SSH with simpler and faster IND-CPA secure counterparts, and also provide the corresponding benchmarks.

This paper examines a security enhancement technique from a passively secure hierarchical identity-based identification (HIBI) protocol to a concurrently secure one. Two types of security enhancement techniques for the identification protocols have been proposed: one based on the OR-proof technique and the other using a chameleon hash function. The former has been examined in detail, while the latter has not been formulated in the HIBI protocol, and its close evaluation of applicability, especially in identity-selecting settings, and reduction efficiency has not been made public. We describe a transformation using a chameleon hash function and compare it with the others based on the OR-proof technique in applicability and reduction efficiency.

Lattices lead to promising practical post-quantum digital signatures, combining asymptotic efficiency with strong theoretical security guarantees. However, tuning their parameters into practical instantiations is a delicate task. On the one hand, NIST round~2 candidates based on Lyubashevsky's design (such as dilithium and qtesla) allow several tradeoffs between security and efficiency, but at the expense of a large bandwidth consumption. On the other hand, the hash-and-sign falcon signature is much more compact and is still very efficient, but it allows only two security levels, with large compactness and security gaps between them. We introduce a new family of signature schemes based on the falcon design, which relies on module lattices. Our concrete instantiation enjoys the compactness and efficiency of falcon, and allows an intermediate security level. It leads to the most compact lattice-based signature achieving a quantum security above 128 bits.

Comparable Encryption proposed by Furukawa (ESORICS 2013, CANS 2014) is a variant of order-preserving encryption (OPE) and order-revealing encryption (ORE); we cannot compare a ciphertext of v and another ciphertext of v', but we can compare a ciphertext of v and a token of b and compare a token of $b$ and another token of b'. Comparable encryption allows us to implement range and point queries while keeping the order of v's as secret as possible.

This paper discusses how to realize practical post-quantum authenticated key exchange (AKE) with strong security, i.e., CK+ security (Krawczyk, CRYPTO 2005). It is known that strongly secure post-quantum AKE protocols exist on a generic construction from IND-CCA secure key encapsulation mechanisms (KEMs) in the standard model.