279 results sorted by ID
Proxying is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability
Zhongtang Luo, Yanxue Jia, Yaobin Shen, Aniket Kate
TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client...
Unstructured Inversions of New Hope
Ian Malloy
Attacks and cryptanalysis
Introduced as a new protocol implemented in “Chrome Canary” for the Google Inc. Chrome browser,
“New Hope” is engineered as a post-quantum key exchange for the TLS 1.2 protocol. The structure of
the exchange is revised lattice-based cryptography. New Hope incorporates the key-encapsulation
mechanism of Peikert which itself is a modified Ring-LWE scheme. The search space used to introduce
the closest-vector problem is generated by an intersection of a tesseract and hexadecachoron, or the...
The 2Hash OPRF Framework and Efficient Post-Quantum Instantiations
Ward Beullens, Lucas Dodgson, Sebastian Faller, Julia Hesse
Cryptographic protocols
An Oblivious Pseudo-Random Function (OPRF) is a two-party protocol for jointly evaluating a Pseudo-Random Function (PRF), where a user has an input x and a server has an input k. At the end of the protocol, the user learns the evaluation of the PRF using key k at the value x, while the server learns nothing about the user's input or output.
OPRFs are a prime tool for building secure authentication and key exchange from passwords, private set intersection, private information retrieval,...
ORIGO: Proving Provenance of Sensitive Data with Constant Communication
Jens Ernstberger, Jan Lauinger, Yinnan Wu, Arthur Gervais, Sebastian Steinhorst
Applications
Transport Layer Security ( TLS ) is foundational for safeguarding client-server communication. However, it does not extend integrity guarantees to third-party verification of data authenticity. If a client wants to present data obtained from a server, it cannot convince any other party that the data has not been tampered with.
TLS oracles ensure data authenticity beyond the client-server TLS connection, such that clients can obtain data from a server and ensure provenance to any third...
Security of Symmetric Ratchets and Key Chains - Implications for Protocols like TLS 1.3, Signal, and PQ3
John Preuß Mattsson
Cryptographic protocols
Symmetric ratchets and one-way key chains play a vital role in numerous important security protocols such as TLS 1.3, DTLS 1.3, QUIC, Signal, MLS, EDHOC, OSCORE, and Apple PQ3. Despite the crucial role they play, very little is known about their security properties. This paper categorizes and examines different ratchet constructions, offering a comprehensive overview of their security. Our analysis reveals notable distinctions between different types of one-way key chains. Notably, the type...
The impact of data-heavy, post-quantum TLS 1.3 on the Time-To-Last-Byte of real-world connections
Panos Kampanakis, Will Childs-Klein
Cryptographic protocols
It has been shown that post-quantum key exchange and authentication with ML-KEM and ML-DSA, NIST’s postquantum algorithm picks, will have an impact on TLS 1.3 performance used in the Web or other applications. Studies so far have focused on the overhead of quantum-resistant algorithms on TLS time-to-first-byte (handshake time). Although these works have been important in quantifying the slowdown in connection establishment, they do not capture the full picture regarding real-world TLS 1.3...
Limits on Authenticated Encryption Use in TLS
Atul Luykx, Kenneth G. Paterson
Cryptographic protocols
This technical note presents limits on the security (as a function of the number of plaintext bytes encrypted and the number of forgery attempts made by an adversary) for the main Authenticated Encryption schemes available in TLS 1.2 and the draft of TLS 1.3. These limits are derived from security proofs for the considered schemes available in the literature. Our intention is to provide considered technical input to on-going discussions in the TLS Working Group of the IETF concerning,...
YouChoose: A Lightweight Anonymous Proof of Account Ownership
Aarav Varshney, Prashant Agrawal, Mahabir Prasad Jhanwar
Cryptographic protocols
We explore the issue of anonymously proving account ownership (anonymous PAO). Such proofs allow a prover to prove to a verifier that it owns a valid account at a server without being tracked by the server or the verifier, without requiring any changes at the server's end and without even revealing to it that any anonymous PAO is taking place. This concept is useful in sensitive applications like whistleblowing. The first introduction of anonymous PAOs was by Wang et al., who also introduced...
Automated Issuance of Post-Quantum Certificates: a New Challenge
Alexandre Augusto Giron, Frederico Schardong, Lucas Pandolfo Perin, Ricardo Custódio, Victor Valle, Víctor Mateu
The Automatic Certificate Management Environment protocol (ACME) has significantly contributed to the widespread use of digital certificates in safeguarding the authenticity and privacy of Internet data. These certificates are required for implementing the Transport Layer Security (TLS) protocol. However, it is well known that the cryptographic algorithms employed in these certificates will become insecure with the emergence of quantum computers. This study assesses the challenges in...
SoK: Post-Quantum TLS Handshake
Nouri Alnahawi, Johannes Müller, Jan Oupický, Alexander Wiesmaier
Cryptographic protocols
Transport Layer Security (TLS) is the backbone security protocol of the Internet. As this fundamental protocol is at risk from future quantum attackers, many proposals have been made to protect TLS against this threat by implementing post-quantum cryptography (PQC). The widespread interest in post-quantum TLS has given rise to a large number of solutions over the last decade. These proposals differ in many aspects, including the security properties they seek to protect, the efficiency and...
Compromising sensitive information through Padding Oracle and Known Plaintext attacks in Encrypt-then-TLS scenarios
Daniel Espinoza Figueroa
Attacks and cryptanalysis
Let's consider a scenario where the server encrypts data using AES-CBC without authentication and then sends only the encrypted ciphertext through TLS (without IV). Then, having a padding oracle, we managed to recover the initialization vector and the sensitive data, doing a cybersecurity audit for a Chilean company.
Everlasting ROBOT: the Marvin Attack
Hubert Kario
Attacks and cryptanalysis
In this paper we show that Bleichenbacher-style attacks on RSA decryption are not only still possible, but also that vulnerable implementations are common. We have successfully attacked multiple implementations using only timing of decryption operation and shown that many others are vulnerable. To perform the attack we used more statistically rigorous techniques like the sign test, Wilcoxon signed-rank test, and bootstrapping of median of pairwise differences. We publish a set of tools for...
Comparse: Provably Secure Formats for Cryptographic Protocols
Théophile Wallez, Jonathan Protzenko, Karthikeyan Bhargavan
Cryptographic protocols
Data formats used for cryptographic inputs have historically been the source of many attacks on cryptographic protocols, but their security guarantees remain poorly studied. One reason is that, due to their low-level nature, formats often fall outside of the security model. Another reason is that studying all of the uses of all of the formats within one protocol is too difficult to do by hand, and requires a comprehensive, automated framework.
We propose a new framework, “Comparse”, that...
Janus: Fast Privacy-Preserving Data Provenance For TLS 1.3
Jan Lauinger, Jens Ernstberger, Andreas Finkenzeller, Sebastian Steinhorst
Cryptographic protocols
Web users can gather data from secure endpoints and demonstrate the provenance of sensitive data to any third party by using privacy-preserving TLS oracles. In practice, privacy-preserving TLS oracles are practical in verifying private data up to 1 kB in size selectively, which limits their applicability to larger sensitive data sets. In this work, we introduce a new oracle protocol for TLS, which reaches new scales in selectively verifying the provenance of confidential web data. The...
Automated Analysis of Protocols that use Authenticated Encryption: How Subtle AEAD Differences can impact Protocol Security
Cas Cremers, Alexander Dax, Charlie Jacomme, Mang Zhao
Foundations
Many modern security protocols such as TLS, WPA2, WireGuard, and Signal use a cryptographic primitive called Authenticated Encryption (optionally with Authenticated Data), also known as an AEAD scheme. AEAD is a variant of symmetric encryption that additionally provides authentication. While authentication may seem to be a straightforward additional requirement, it has in fact turned out to be complex: many different security notions for AEADs are still being proposed, and several recent...
Moving a Step of ChaCha in Syncopated Rhythm
Shichang Wang, Meicheng Liu, Shiqi Hou, Dongdai Lin
Attacks and cryptanalysis
The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient...
DiStefano: Decentralized Infrastructure for Sharing Trusted Encrypted Facts and Nothing More
Sofía Celi, Alex Davidson, Hamed Haddadi, Gonçalo Pestana, Joe Rowell
Applications
We design DiStefano: an efficient, maliciously-secure framework for generating private commitments over TLS-encrypted web traffic, for a designated third-party. DiStefano provides many improvements over previous TLS commitment systems, including: a modular protocol specific to TLS 1.3, support for arbitrary verifiable claims over encrypted data, inherent ring privacy for client browsing history, and various optimisations to ensure fast online performance of the TLS 1.3 session. We build a...
DIDO: Data Provenance from Restricted TLS 1.3 Websites
Kwan Yin Chan, Handong Cui, Tsz Hon Yuen
Cryptographic protocols
Public data can be authenticated by obtaining from a trustworthy website with TLS. Private data, such as user profile, are usually restricted from public access. If a user wants to authenticate his private data (e.g., address) provided by a restricted website (e.g., user profile page of a utility company website) to a verifier, he cannot simply give his username and password to the verifier. DECO (CCS 2020) provides a solution for liberating these data without introducing undesirable trust...
Zombie: Middleboxes that Don’t Snoop
Collin Zhang, Zachary DeStefano, Arasu Arun, Joseph Bonneau, Paul Grubbs, Michael Walfish
Applications
Zero-knowledge middleboxes (ZKMBs) are a recent paradigm in which clients get privacy while middleboxes enforce policy: clients prove in zero knowledge that the plaintext underlying their encrypted traffic complies with network policies, such as DNS filtering. However, prior work had impractically poor performance and was limited in functionality.
This work presents Zombie, the first system built using the ZKMB paradigm. Zombie introduces techniques that push ZKMBs to the verge of...
Lightweight Authentication of Web Data via Garble-Then-Prove
Xiang Xie, Kang Yang, Xiao Wang, Yu Yu
Cryptographic protocols
Transport Layer Security (TLS) establishes an authenticated and confidential channel to deliver data for almost all Internet applications. A recent work (Zhang et al., CCS'20) proposed a protocol to prove the TLS payload to a third party, without any modification of TLS servers, while ensuring the privacy and originality of the data in the presence of malicious adversaries. However, it required maliciously secure Two-Party Computation (2PC) for generic circuits, leading to significant...
Generalized Initialization of the Duplex Construction
Christoph Dobraunig, Bart Mennink
Secret-key cryptography
The duplex construction is already well analyzed with many papers proving its security in the random permutation model. However, so far, the first phase of the duplex, where the state is initialized with a secret key and an initialization vector ($\mathit{IV}$), is typically analyzed in a worst case manner. More detailed, it is always assumed that the adversary is allowed to choose the $\mathit{IV}$ on its will. In this paper, we analyze how the security changes if restrictions on the choice...
Limits in the Provable Security of ECDSA Signatures
Dominik Hartmann, Eike Kiltz
Foundations
Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model.
In this work, we study the question whether these...
Hidden Stream Ciphers and TMTO Attacks on TLS 1.3, DTLS 1.3, QUIC, and Signal
John Preuß Mattsson
Cryptographic protocols
Transport Layer Security (TLS) 1.3 and the Signal protocol are very important and widely used security protocols. We show that the key update function in TLS 1.3 and the symmetric key ratchet in Signal can be modeled as non-additive synchronous stream ciphers. This means that the efficient Time Memory Tradeoff Attacks for stream ciphers can be applied. The implication is that TLS 1.3, QUIC, DTLS 1.3, and Signal offer a lower security level against TMTO attacks than expected from the key...
Randomness of random in Cisco ASA
Ryad Benadjila, Arnaud Ebalard
Attacks and cryptanalysis
It all started with ECDSA nonces and keys duplications in a large amount of X.509 certificates generated by Cisco ASA security gateways, detected through TLS campaigns analysis.
After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces.
The current article describes our...
When Messages are Keys: Is HMAC a dual-PRF?
Matilda Backendal, Mihir Bellare, Felix Günther, Matteo Scarlata
Secret-key cryptography
In Internet security protocols including TLS 1.3, KEMTLS, MLS and Noise, HMAC is being assumed to be a dual-PRF, meaning a PRF not only when keyed conventionally (through its first input), but also when "swapped" and keyed (unconventionally) through its second (message) input. We give the first in-depth analysis of the dual-PRF assumption on HMAC.
For the swap case, we note that security does not hold in general, but completely characterize when it does; we show that HMAC is swap-PRF...
Optimizations and Practicality of High-Security CSIDH
Fabio Campos, Jorge Chavez-Saab, Jesús-Javier Chi-Domínguez, Michael Meyer, Krijn Reijnders, Francisco Rodríguez-Henríquez, Peter Schwabe, Thom Wiggers
Public-key cryptography
In this work, we assess the real-world practicality of CSIDH, an isogeny-based non-interactive key exchange. We provide the first thorough assessment of the practicality of CSIDH in higher parameter sizes for conservative estimates of quantum security, and with protection against physical attacks.
This requires a three-fold analysis of CSIDH. First, we describe two approaches to efficient high-security CSIDH implementations, based on SQALE and CTIDH. Second, we optimize such high-security...
SMAUG: Pushing Lattice-based Key Encapsulation Mechanisms to the Limits
Jung Hee Cheon, Hyeongmin Choe, Dongyeon Hong, MinJune Yi
Public-key cryptography
Recently, NIST has announced Kyber, a lattice-based key encapsulation mechanism (KEM), as a post-quantum standard. However, it is not the most efficient scheme among the NIST's KEM finalists. Saber enjoys more compact sizes and faster performance, and Mera et al. (TCHES '21) further pushed its efficiency, proposing a shorter KEM, Sable. As KEM are frequently used on the Internet, such as in TLS protocols, it is essential to achieve high efficiency while maintaining sufficient security....
TLS → Post-Quantum TLS: Inspecting the TLS landscape for PQC adoption on Android
Dimitri Mankowski, Thom Wiggers, Veelasha Moonsamy
Cryptographic protocols
The ubiquitous use of smartphones has contributed to more and more users conducting their online browsing activities through apps, rather than web browsers. In order to provide a seamless browsing experience to the users, apps rely on a variety of HTTP-based APIs and third-party libraries, and make use of the TLS protocol to secure the underlying communication. With NIST's recent announcement of the first standards for post-quantum algorithms, there is a need to better understand the...
Stealth Key Exchange and Confined Access to the Record Protocol Data in TLS 1.3
Marc Fischlin
Cryptographic protocols
We show how to embed a covert key exchange sub protocol within a regular TLS 1.3 execution, generating a stealth key in addition to the regular session keys. The idea, which has appeared in the literature before, is to use the exchanged nonces to transport another key value. Our contribution is to give a rigorous model and analysis of the security of such embedded key exchanges, requiring that the stealth key remains secure even if the regular key is under adversarial control. Specifically...
Energy Consumption Evaluation of Post-Quantum TLS 1.3 for Resource-Constrained Embedded Devices
George Tasopoulos, Charis Dimopoulos, Apostolos P. Fournaris, Raymond K. Zhao, Amin Sakzad, Ron Steinfeld
Cryptographic protocols
Post-Quantum cryptography (PQC), in the past few years, constitutes the main driving force of the quantum resistance transition for security primitives, protocols and tools. TLS is one of the widely used security protocols that needs to be made quantum safe. However, PQC algorithms integration into TLS introduce various implementation overheads compared to traditional TLS that in battery powered embedded devices with constrained resources, cannot be overlooked. While there exist several...
Batch Signatures, Revisited
Carlos Aguilar-Melchor, Martin R. Albrecht, Thomas Bailleux, Nina Bindel, James Howe, Andreas Hülsing, David Joseph, Marc Manzano
Cryptographic protocols
We revisit batch signatures (previously considered in a draft RFC, and used in multiple recent works), where a single, potentially expensive, "inner" digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties.
We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST's post-quantum project, to high...
Four Attacks and a Proof for Telegram
Martin R. Albrecht, Lenka Mareková, Kenneth G. Paterson, Igors Stepanovs
Cryptographic protocols
We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram's equivalent of the TLS record protocol. We give positive and negative results. On the one hand, we formally and in detail model a slight variant of Telegram's "record protocol" and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our...
A study of KEM generalizations
Bertram Poettering, Simon Rastikian
Public-key cryptography
The NIST, in its recent competition on quantum-resilient confidentiality primitives, requested the submission of exclusively KEMs. The task of KEMs is to establish secure session keys that can drive, amongst others, public key encryption and TLS-like secure channels. In this work we test the KEM abstraction in the context of constructing cryptographic schemes that are not subsumed in the PKE and secure channels categories. We find that, when used to construct a key transport scheme or when...
Attacking the IETF/ISO Standard for Internal Re-keying CTR-ACPKM
Orr Dunkelman, Shibam Ghosh, Eran Lambooij
Attacks and cryptanalysis
Encrypting too much data using the same key is a bad practice from a security perspective. Hence, it is customary to perform re-keying after a given amount of data is transmitted. While in many cases, the re-keying is done using a fresh execution of some key exchange protocol (e.g., in IKE or TLS), there are scenarios where internal re-keying, i.e., without exchange of information, is performed, mostly due to performance reasons.
Originally suggested by Abdalla and Bellare, there are...
Password-Authenticated TLS via OPAQUE and Post-Handshake Authentication
Julia Hesse, Stanislaw Jarecki, Hugo Krawczyk, Christopher Wood
Cryptographic protocols
OPAQUE is an Asymmetric Password-Authenticated Key Exchange (aPAKE) protocol being standardized by the IETF (Internet Engineering Task Force) as a more secure alternative to the traditional ``password-over-TLS'' mechanism prevalent in current practice. OPAQUE defends against a variety of vulnerabilities of password-over-TLS by dispensing with reliance on PKI and TLS security, and ensuring that the password is never visible to servers or anyone other than the client machine where the password...
On TLS for the Internet of Things, in a Post Quantum world
Michael Scott
Cryptographic protocols
The TLS (Transport Layer Security) protocol is the most important, most attacked, most analysed and most used cryptographic protocol in the world today. TLS is critical to the integrity of the Internet, and if it were to be broken e-commerce would become impossible, with very serious implications for the global economy. Furthermore TLS is likely to assume even greater significance in the near future with the rapid growth of an Internet of Things (IoT) -- a multiplicity of internet connected...
Portunus: Re-imagining access control in distributed systems
Watson Ladd, Tanya Verma, Marloes Venema, Armando Faz Hernandez, Brendan McMillion, Avani Wildani, Nick Sullivan
Applications
TLS termination, which is essential to network and security infrastructure providers, is an extremely latency sensitive operation that benefits from access to sensitive key material close to the edge. However, increasing regulatory concerns prompt customers to demand sophisticated controls on where their keys may be accessed. While traditional access-control solutions rely on a highly available centralized process to enforce access, the round-trip latency and
decreased fault tolerance make...
The Security of ChaCha20-Poly1305 in the Multi-user Setting
Jean Paul Degabriele, Jérôme Govinden, Felix Günther, Kenneth G. Paterson
Secret-key cryptography
The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and...
DY Fuzzing: Formal Dolev-Yao Models Meet Cryptographic Protocol Fuzz Testing
Max Ammann, Lucca Hirschi, Steve Kremer
Cryptographic protocols
Critical and widely used cryptographic protocols have repeatedly been found to contain flaws in their design and their implementation. A prominent class of such vulnerabilities is logical attacks, e.g. attacks that exploit flawed protocol logic. Automated formal verification methods, based on the Dolev-Yao (DY) attacker, formally define and excel at finding such flaws, but operate only on abstract specification models. Fully automated verification of existing protocol implementations is...
Post-Quantum Security of Key Encapsulation Mechanism against CCA Attacks with a Single Decapsulation Query
Haodong Jiang, Zhi Ma, Zhenfeng Zhang
Public-key cryptography
Recently, in post-quantum cryptography migration, it has been shown that an IND-1-CCA-secure key encapsulation mechanism (KEM) is required for replacing an ephemeral Diffie-Hellman (DH) in widely-used protocols, e.g., TLS, Signal, and Noise. IND-1-CCA security is a notion similar to the traditional IND-CCA security except that the adversary is restricted to one single decapsulation query. At EUROCRYPT 2022, based on CPA-secure public-key encryption (PKE), Huguenin-Dumittan and Vaudenay...
PECO: methods to enhance the privacy of DECO protocol
Manuel B. Santos
Applications
The DECentralized Oracle (DECO) protocol enables the verifiable provenance of data from Transport Layer Security (TLS) connections through secure two-party computation and zero-knowledge proofs. In this paper, we present PECO, an extension of DECO that enhances privacy features through the integration of two new private three-party handshake protocols (P3P-HS). PECO allows any web user to prove to a verifier the properties of data from TLS connections without disclosing the identity of the...
Formal Analysis of SPDM: Security Protocol and Data Model version 1.2
Cas Cremers, Alexander Dax, Aurora Naska
Cryptographic protocols
DMTF is a standards organization by major industry players in IT infrastructure including AMD, Alibaba, Broadcom, Cisco, Dell, Google, Huawei, IBM, Intel, Lenovo, and NVIDIA, which aims to enable interoperability, e.g., including cloud, virtualization, network, servers and storage. It is currently standardizing a security protocol called SPDM, which aims to secure communication over the wire and to enable device attestation, notably also explicitly catering for communicating hardware...
KEMTLS vs. Post-Quantum TLS: Performance On Embedded Systems
Ruben Gonzalez, Thom Wiggers
Implementation
TLS is ubiquitous in modern computer networks. It secures transport for high-end desktops and low-end embedded devices alike. However, the public key cryptosystems currently used within TLS may soon be obsolete as large-scale quantum computers, once realized, would be able to break them. This threat has led to the development of post-quantum cryptography (PQC). The U.S. standardization body NIST is currently in the process of concluding a multi-year search for promising post-quantum...
Careful with MAc-then-SIGn: A Computational Analysis of the EDHOC Lightweight Authenticated Key Exchange Protocol
Felix Günther, Marc Ilunga Tshibumbu Mukendi
Cryptographic protocols
EDHOC is a lightweight authenticated key exchange protocol for IoT communication, currently being standardized by the IETF. Its design is a trimmed-down version of similar protocols like TLS 1.3, building on the SIGn-then-MAc (SIGMA) rationale. In its trimming, however, EDHOC notably deviates from the SIGMA design by sending only short, non-unique credential identifiers, and letting recipients perform trial verification to determine the correct communication partner. Done naively, this can...
Backdooring Post-Quantum Cryptography: Kleptographic Attacks on Lattice-based KEMs
Prasanna Ravi, Shivam Bhasin, Anupam Chattopadhyay, Aikata, Sujoy Sinha Roy
Public-key cryptography
Post-quantum Cryptography (PQC) has reached the verge of standardization competition, with Kyber as a winning candidate. In this work, we demonstrate practical backdoor insertion in Kyber through kleptrography. The backdoor can be inserted using classical techniques like ECDH or post-quantum Classic Mceliece. The inserted backdoor targets the key generation procedure where generated output public keys subliminally leak information about the secret key to the owner of the backdoor. We...
Jolt: Recovering TLS Signing Keys via Rowhammer Faults
Koksal Mus, Yarkın Doröz, M. Caner Tol, Kristi Rahman, Berk Sunar
Attacks and cryptanalysis
Digital Signature Schemes such as DSA, ECDSA, and RSA are widely deployed to protect the integrity of security protocols such as TLS, SSH, and IPSec. In TLS, for instance, RSA and (EC)DSA are used to sign the state of the agreed upon protocol parameters during the handshake phase. Naturally, RSA and (EC)DSA implementations have become the target of numerous attacks, including powerful side-channel attacks. Hence, cryptographic libraries were patched repeatedly over the years.
Here we...
Post-Quantum Hybrid KEMTLS Performance in Simulated and Real Network Environments
Alexandre Augusto Giron, João Pedro Adami do Nascimento, Ricardo Custódio, Lucas Pandolfo Perin
Applications
Adopting Post-Quantum Cryptography (PQC) in network protocols is a challenging subject. Larger PQC public keys and signatures can significantly slow the Transport Layer Security (TLS) protocol. In this context, KEMTLS is a promising approach that replaces the handshake signatures by using PQC Key Encapsulation Mechanisms (KEMs), which have, in general, smaller sizes. However, for broad PQC adoption, hybrid cryptography has its advantages over PQC-only approaches, mainly about the confidence...
Intermediate Certificate Suppression in Post-Quantum TLS: An Approximate Membership Querying Approach
Dimitrios Sikeridis, Sean Huntley, David Ott, Michael Devetsikiotis
Cryptographic protocols
Quantum computing advances threaten the security of today's public key infrastructure, and have led to the pending standardization of alternative, quantum-resistant key encapsulation and digital signature cryptography schemes. Unfortunately, authentication algorithms based on the new post-quantum (PQ) cryptography create significant performance bottlenecks for TLS due to larger certificate chains which introduce additional packets and round-trips. The TLS handshake slowdown will be...
Privacy-Preserving Authenticated Key Exchange: Stronger Privacy and Generic Constructions
Sebastian Ramacher, Daniel Slamanig, Andreas Weninger
Cryptographic protocols
Authenticated key-exchange (AKE) protocols are an important class of protocols that allow two parties to establish a common session key over an insecure channel such as the Internet to then protect their communication. They are widely deployed in security protocols such as TLS, IPsec and SSH. Besides the confidentiality of the communicated data, an orthogonal but increasingly important goal is the protection of the confidentiality of the identities of the involved parties (aka privacy). For...
Puncturable Key Wrapping and Its Applications
Matilda Backendal, Felix Günther, Kenneth G. Paterson
Secret-key cryptography
We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's...
A tale of two models: formal verification of KEMTLS via Tamarin
Sofía Celi, Jonathan Hoyland, Douglas Stebila, Thom Wiggers
Public-key cryptography
KEMTLS is a proposal for changing the TLS handshake to authenticate the handshake using long-term key encapsulation mechanism keys instead of signatures, motivated by trade-offs in the characteristics of post-quantum algorithms. Prior proofs of security of KEMTLS and its variant KEMTLS-PDK have been hand-written proofs in the reductionist model under computational assumptions. In this paper, we present computer-verified symbolic analyses of KEMTLS and KEMTLS-PDK using two distinct Tamarin...
One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval
Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, Vinod Vaikuntanathan
Cryptographic protocols
We present SimplePIR, the fastest single-server private information retrieval scheme known to date. SimplePIR’s security holds under the learning-with-errors assumption. To answer a client’s query, the SimplePIR server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte. SimplePIR achieves 10 GB/s/core server throughput, which approaches the memory bandwidth of the
machine and the performance of the fastest two-server private-information-retrieval schemes...
Sapic+: protocol verifiers of the world, unite!
Vincent Cheval, Charlie Jacomme, Steve Kremer, Robert Künnemann
Cryptographic protocols
Symbolic security protocol verifiers have reached a high degree of automation and maturity. Today, experts can model real-world protocols, but this often requires model-specific encodings and deep insight into the strengths and weaknesses of each of those tools. With Sapic+ , we introduce a protocol verification platform that lifts this burden and permits choosing the right tool for the job, at any development stage. We build on the existing compiler from Sapic to Tamarin, and extend it with...
Proof-of-possession for KEM certificates using verifiable generation
Tim Güneysu, Philip Hodges, Georg Land, Mike Ounsworth, Douglas Stebila, Greg Zaverucha
Cryptographic protocols
Certificate authorities in public key infrastructures typically require entities to prove possession of the secret key corresponding to the public key they want certified. While this is straightforward for digital signature schemes, the most efficient solution for public key encryption and key encapsulation mechanisms (KEMs) requires an interactive challenge-response protocol, requiring a departure from current issuance processes. In this work we investigate how to non-interactively prove...
Improving the Privacy of Tor Onion Services
Edward Eaton, Sajin Sasy, Ian Goldberg
Applications
Onion services enable bidirectional anonymity for parties that communicate over the Tor network, thus providing improved privacy properties compared to standard TLS connections. Since these services are designed to support server-side anonymity, the entry points for these services shuffle across the Tor network periodically. In order to connect to an onion service at a given time, the client has to resolve the .onion address for the service, which requires querying volunteer Tor nodes called...
Provably Secure Identity-Based Remote Password Registration
Csanád Bertók, Andrea Huszti, Szabolcs Kovács, Norbert Oláh
Cryptographic protocols
One of the most significant challenges is the secure user authentication. If it becomes breached, confidentiality and integrity of the data or services may be compromised. The most widespread solution for entity authentication is the password-based scheme. It is easy to use and deploy. During password registration typically users create or activate their account along with their password through their verification email, and service providers are authenticated based on their SSL/TLS...
On the Concrete Security of TLS 1.3 PSK Mode
Hannah Davis, Denis Diemert, Felix Günther, Tibor Jager
Cryptographic protocols
The pre-shared key (PSK) handshake modes of TLS 1.3 allow for the performant, low-latency resumption of previous connections and are widely used on the Web and by resource-constrained devices, e.g., in the Internet of Things. Taking advantage of these performance benefits with optimal and theoretically-sound parameters requires tight security proofs. We give the first tight security proofs for the TLS 1.3 PSK handshake modes.
Our main technical contribution is to address a gap in prior...
Cache-22: A Highly Deployable End-To-End Encrypted Cache System with Post-Quantum Security
Keita Emura, Shiho Moriai, Takuma Nakajima, Masato Yoshimi
Cryptographic protocols
Cache systems are crucial for reducing communication overhead on the Internet. The importance of communication privacy is being increasingly and widely recognized; therefore, we anticipate that nearly all end-to-end communication will be encrypted via secure sockets layer/transport layer security (SSL/TLS) in the near future. Herein we consider a catch-22 situation, wherein the cache server checks whether content has been cached or not, i.e., the cache server needs to observe it, thereby...
Practical (Post-Quantum) Key Combiners from One-Wayness and Applications to TLS
Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenneth G. Paterson, Eyal Ronen, Eylon Yogev
The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even...
Does Fully Homomorphic Encryption Need Compute Acceleration?
Leo de Castro, Rashmi Agrawal, Rabia Yazicigil, Anantha Chandrakasan, Vinod Vaikuntanathan, Chiraag Juvekar, Ajay Joshi
The emergence of cloud-computing has raised important privacy questions about the data that users share with remote servers. While data in transit is protected using standard techniques like Transport Layer Security (TLS), most cloud providers have unrestricted plaintext access to user data at the endpoint. Fully Homomorphic Encryption (FHE) offers one solution to this problem by allowing for arbitrarily complex computations on encrypted data without ever needing to decrypt it....
A PKI-based Framework for Establishing Efficient MPC Channels
Daniel Masny, Gaven Watson
Public-key cryptography
The Transport Layer Security (TLS) protocol is a fundamental building block for ensuring security on Internet. It provides an easy to use framework for the purposes of establishing an authenticated and secure channel between two parties that have never physically met. Nevertheless, TLS only provides a simple cryptographic functionality compared to more advanced protocols such as protocols for secure multiparty computation (MPC).
In this work, we provide a framework for efficiently...
Towards Post-Quantum Security for Cyber-Physical Systems: Integrating PQC into Industrial M2M Communication
Sebastian Paul, Patrik Scheible, Friedrich Wiemer
Implementation
The threat of a cryptographically relevant quantum computer contributes to an increasing interest in the field of post-quantum cryptography (PQC). Compared to existing research efforts regarding the integration of PQC into the Transport Layer Security (TLS) protocol, industrial communication protocols have so far been neglected. Since industrial cyber-physical systems (CPS) are typically deployed for decades, protection against such long-term threats is needed.
In this work, we propose two...
Performance Evaluation of Post-Quantum TLS 1.3 on Resource-Constrained Embedded Systems
George Tasopoulos, Jinhui Li, Apostolos P. Fournaris, Raymond K. Zhao, Amin Sakzad, Ron Steinfeld
Cryptographic protocols
Transport Layer Security (TLS) constitutes one of the most widely used protocols for securing Internet communications and has also found broad acceptance in the Internet of Things (IoT) domain. As we progress toward a security environment resistant to quantum computer attacks, TLS needs to be transformed to support post-quantum cryptography. However, post-quantum TLS is still not standardised, and its overall performance, especially in resource-constrained, IoT-capable, embedded devices, is...
QC-MDPC codes DFR and the IND-CCA security of BIKE
Valentin Vasseur
Public-key cryptography
The aim of this document is to clarify the DFR (Decoding Failure Rate) claims made for BIKE, a third round alternate candidate KEM (Key Encapsulation Mechanism) to the NIST call for post-quantum cryptography standardization. For the most part, the material presented here is not new, it is extracted from the relevant scientific literature, in particular [V21].
Even though a negligible DFR is not needed for a KEM using ephemeral keys (e.g. TLS) which only requires IND-CPA security, it seems...
An In-Depth Symbolic Security Analysis of the ACME Standard
Karthikeyan Bhargavan, Abhishek Bichhawat, Quoc Huy Do, Pedram Hosseyni, Ralf Kuesters, Guido Schmitz, Tim Wuertele
Cryptographic protocols
he ACME certificate issuance and management protocol, standardized as IETF RFC 8555, is an essential element of the web public key infrastructure (PKI). It has been used by Let’s Encrypt and other certification authorities to issue over a billion certificates, and a majority of HTTPS connections are now secured with certificates issued through ACME. Despite its importance, however, the security of ACME has not been studied at the same level of depth as other protocol standards like TLS 1.3...
Mixed Certificate Chains for the Transition to Post-Quantum Authentication in TLS 1.3
Sebastian Paul, Yulia Kuzovkova, Norman Lahr, Ruben Niederhagen
Implementation
Large-scale quantum computers will be able to efficiently solve the underlying mathematical problems of widely deployed public key cryptosystems in the near future. This threat has sparked increased interest in the field of Post-Quantum Cryptography (PQC) and standardization bodies like NIST, IETF, and ETSI are in the process of standardizing PQC schemes as a new generation of cryptography. This raises the question of how to ensure a fast, reliable, and secure transition to upcoming PQC...
Curve448 on 32-bit ARM Cortex-M4
Hwajeong Seo, Reza Azarderakhsh
Implementation
Public key cryptography is widely used in key exchange and digital signature protocols. Public key cryptography requires expensive primitive operations, such as finite-field and group operations. These finite-field and group operations require a number of clock cycles to exe- cute. By carefully optimizing these primitive operations, public key cryp- tography can be performed with reasonably fast execution timing. In this paper, we present the new implementation result of Curve448 on 32-bit ARM...
An Efficient Data Protection Scheme Based on Hierarchical ID-Based Encryption for Message Queueing Telemetry Transport
Chun-I Fan, Cheng-Han Shie, Yi-Fan Tseng, Hui-Chun Huang
Cryptographic protocols
As Internet of Things (IoT) thriving over the whole world, more and more IoT devices and IoT-based protocols have been designed and proposed in order to meet people's needs. Among those protocols, message queueing telemetry transport (MQTT) is one of the most emerging and promising protocol, which provides many-to-many message transmission based on the ``publish/subscribe'' mechanism. It has been widely used in industries such as the energy industry, chemical engineering, self-driving,...
On Fingerprinting Attacks and Length-Hiding Encryption
Kai Gellert, Tibor Jager, Lin Lyu, Tom Neuschulten
It is well-known that already the length of encrypted messages may reveal sensitive information about encrypted data. Fingerprinting attacks enable an adversary to determine web pages visited by a user and even the language and phrases spoken in voice-over-IP conversations.
Prior research has established the general perspective that a length-hiding padding which is long enough to improve security significantly incurs an unfeasibly large bandwidth overhead. We argue that this perspective is...
Zero-Knowledge Middleboxes
Paul Grubbs, Arasu Arun, Ye Zhang, Joseph Bonneau, Michael Walfish
Applications
This paper initiates research on zero-knowledge middleboxes (ZKMBs). A ZKMB is a network middlebox that enforces network usage policies on encrypted traffic. Clients send the middlebox zero-knowledge proofs that their traffic is policy-compliant; these proofs reveal nothing about the client’s communication except that it complies with the policy. We show how to make ZKMBs work with unmodified encrypted-communication protocols (specifically TLS 1.3), making ZKMBs invisible to servers. As a...
Implementing and Measuring KEMTLS
Sofía Celi, Armando Faz-Hernández, Nick Sullivan, Goutam Tamvada, Luke Valenta, Thom Wiggers, Bas Westerbaan, Christopher A. Wood
Implementation
KEMTLS is a novel alternative to the Transport Layer Security (TLS) handshake that integrates post-quantum algorithms. It uses key encapsulation mechanisms (KEMs) for both confidentiality and authentication, achieving post-quantum security while obviating the need for expensive post-quantum signatures. The original KEMTLS paper presents a security analysis, Rust implementation, and benchmarks over emulated networks. In this work, we provide full Go implementations of KEMTLS and other...
A Formal Security Analysis of Session Resumption Across Hostnames
Kai Gellert, Tobias Handirk
Cryptographic protocols
The TLS 1.3 session resumption handshakes enables a client and a server to resume a previous connection via a shared secret, which was established during a previous session. In practice, this is often done via session tickets, where the server provides a "self-encrypted" ticket containing the shared secret to its clients. A client may resume its session by sending the ticket to the server, which allows the server to retrieve the shared secret stored within the ticket.
Usually, a ticket is...
2021/887
Last updated: 2021-12-23
Authenticated Key Exchange Protocol in the Standard Model under Weaker Assumptions
Janaka Alawatugoda, Taechan Kim
Cryptographic protocols
A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the various kind of malicious behaviors of the adversaries, there have been lots of efforts to define the security models. Amongst them, the extended Canetti-Krawczyk (eCK) security model is considered as one of the strongest ones and widely...
KHAPE: Asymmetric PAKE from Key-Hiding Key Exchange
Yanqi Gu, Stanislaw Jarecki, Hugo Krawczyk
Cryptographic protocols
OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the security of the OPRF. If the latter breaks (by cryptanalysis,...
A note on IND-qCCA security in the ROM and its applications: CPA security is sufficient for TLS 1.3
Loïs Huguenin-Dumittan, Serge Vaudenay
Bounded IND-CCA security (IND-qCCA) is a notion similar to the traditional IND-CCA security, except the adversary is restricted to a constant number q of decryption/decapsulation queries.
We show in this work that IND-qCCA is easily obtained from any passively secure PKE in the (Q)ROM. That is, simply adding a confirmation hash or computing the key as the hash of the plaintext and ciphertext holds an IND-qCCA KEM. In particular, there is no need for derandomization or re-encryption as in...
OpenSSLNTRU: Faster post-quantum TLS key exchange
Daniel J. Bernstein, Billy Bob Brumley, Ming-Shing Chen, Nicola Tuveri
Implementation
Google's CECPQ1 experiment in 2016 integrated a post-quantum
key-exchange algorithm, newhope1024, into TLS 1.2. The Google-Cloudflare
CECPQ2 experiment in 2019 integrated a more efficient key-exchange
algorithm, ntruhrss701, into TLS 1.3.
This paper revisits the choices made in CECPQ2, and shows how to achieve
higher performance for post-quantum key exchange in TLS 1.3 using a
higher-security algorithm, sntrup761. Previous work had indicated that
ntruhrss701 key generation was much faster...
P2DPI: Practical and Privacy-Preserving Deep Packet Inspection
Jongkil Kim, Seyit Camtepe, Joonsang Baek, Willy Susilo, Josef Pieprzyk, Surya Nepal
Applications
The amount of encrypted Internet traffic almost doubles every year thanks to the wide adoption of end-to-end traffic encryption solutions such as IPSec, TLS and SSH. Despite all the benefits of user privacy the end-to-end encryption provides, the encrypted internet traffic blinds intrusion detection system (IDS) and makes detecting malicious traffic hugely difficult. The resulting conflict between the user's privacy and security has demanded solutions for deep packet inspection (DPI) over...
More efficient post-quantum KEMTLS with pre-distributed public keys
Peter Schwabe, Douglas Stebila, Thom Wiggers
Cryptographic protocols
While server-only authentication with certificates is the most widely used mode of operation for the Transport Layer Security (TLS) protocol on the world wide web, there are many applications where TLS is used in a different way or with different constraints. For example, embedded Internet-of-Things clients may have a server certificate pre-programmed and be highly constrained in terms of communication bandwidth or computation power. As post-quantum algorithms have a wider range of...
KEMTLS with Delayed Forward Identity Protection in (Almost) a Single Round Trip
Felix Günther, Simon Rastikian, Patrick Towa, Thom Wiggers
Cryptographic protocols
The recent KEMTLS protocol (Schwabe, Stebila and Wiggers,CCS’20) is a promising design for a quantum-safe TLS handshake protocol. Focused on the web setting, wherein clients learn server public-key certificates only during connection establishment, a drawback of KEMTLS compared to TLS 1.3 is that it introduces an additional round trip before the server can send data, and an extra one for the client as well in the case of mutual authentication. In many scenarios, including IoT and embedded...
Automated Detection of Side Channels in Cryptographic Protocols: DROWN the ROBOTs!
Jan Peter Drees, Pritha Gupta, Eyke Hüllermeier, Tibor Jager, Alexander Konze, Claudia Priesterjahn, Arunselvan Ramaswamy, Juraj Somorovsky
Cryptographic protocols
Currently most practical attacks on cryptographic protocols like TLS are based on side channels, such as padding oracles. Some well-known recent examples are DROWN, ROBOT and Raccoon (USENIX Security 2016, 2018, 2021). Such attacks are usually found by careful and time-consuming manual analysis by specialists.
In this paper, we consider the question of how such attacks can be systematically detected and prevented before (large-scale) deployment. We propose a new, fully automated approach,...
Key-schedule Security for the TLS 1.3 Standard
Chris Brzuska, Antoine Delignat-Lavaud, Christoph Egger, Cédric Fournet, Konrad Kohbrok, Markulf Kohlweiss
Cryptographic protocols
We analyze the security of the TLS 1.3 key establishment protocol, as specified at the end of its rigorous standardization process. We define a core key-schedule and reduce its security to concrete assumptions against an adversary that controls client and server configurations and adaptively chooses some of their keys. Our model supports all key derivations featured in the standard, including its negotiated modes and algorithms that combine an optional Diffie-Hellman exchange for...
MPCAuth: Multi-factor Authentication for Distributed-trust Systems
Sijun Tan, Weikeng Chen, Ryan Deng, Raluca Ada Popa
Applications
Systems with distributed trust have attracted growing research attention and seen increasing industry adoptions. In these systems, critical secrets are distributed across N servers, and computations are performed privately using secure multi-party computation (SMPC). Authentication for these distributed-trust systems faces two challenges. The first challenge is ease-of-use. Namely, how can an authentication protocol maintain its user experience without sacrificing security? To avoid a...
Oblivious TLS via Multi-Party Computation
Damiano Abram, Ivan Damgård, Peter Scholl, Sven Trieflinger
Cryptographic protocols
In this paper, we describe Oblivious TLS: an MPC protocol that we prove UC secure against a majority of actively corrupted parties. The protocol securely implements TLS 1.3. Thus, any party P who runs TLS can communicate securely with a set of servers running Oblivious TLS; P does not need to modify anything, or even be aware that MPC is used.
Applications of this include communication between servers who offer MPC services and clients, to allow the clients to easily and securely provide...
Classic McEliece Implementation with Low Memory Footprint
Johannes Roth, Evangelos Karatsiolis, Juliane Krämer
Public-key cryptography
The Classic McEliece cryptosystem is one of the most trusted quantum-resistant cryptographic schemes. Deploying it in practical applications, however, is challenging due to the size of its public key. In this work, we bridge this gap. We present an implementation of Classic McEliece on an ARM Cortex-M4 processor, optimized to overcome memory constraints. To this end, we present an algorithm to retrieve the public key ad-hoc. This reduces memory and storage requirements and enables the...
Privacy-Preserving Authenticated Key Exchange and the Case of IKEv2
Sven Schäge, Jörg Schwenk, Sebastian Lauer
Cryptographic protocols
In this paper, we present a strong, formal, and general-purpose cryptographic model for privacy-preserving authenticated key exchange (PPAKE) protocols. PPAKE protocols are secure in the traditional AKE sense but additionally guarantee the confidentiality of the identities used in communication sessions. Our model has several useful and novel features, among others: it is a proper extension of classical AKE models, guarantees in a strong sense that the confidentiality of session keys is...
Single-Message Credential-Hiding Login
Kevin Lewi, Payman Mohassel, Arnab Roy
The typical login protocol for authenticating a user to a web service involves the client sending a password over a TLS-secured channel to the service, occasionally deployed with the password being prehashed. This widely-deployed paradigm, while simple in nature, is prone to both inadvertent logging and eavesdropping attacks, and has repeatedly led to the exposure of passwords in plaintext.
Partly to address this problem, symmetric and asymmetric PAKE protocols were developed to ensure that...
ASAP: Algorithm Substitution Attacks on Cryptographic Protocols
Sebastian Berndt, Jan Wichelmann, Claudius Pott, Tim-Henrik Traving, Thomas Eisenbarth
Cryptographic protocols
The security of digital communication relies on few cryptographic protocols that are used to protect internet traffic, from web sessions to instant messaging. These protocols and the cryptographic primitives they rely on have been extensively studied and are considered secure. Yet, sophisticated attackers are often able to bypass rather than break security mechanisms.
Kleptography or algorithm substitution attacks (ASA) describe techniques to place backdoors right into cryptographic...
LURK: Server-Controlled TLS Delegation
Ioana Boureanu, Daniel Migault, Stere Preda, Hyame Assem Alamedine, Sanjay Mishra, Frederic Fieau, Mohammad Mannan
Cryptographic protocols
By design, TLS (Transport Layer Security) is a 2-party, end-to-end protocol.
Yet, in practice, TLS delegation is often deployed: that is, middlebox proxies inspect and even modify TLS traffic between the endpoints.
Recently, industry-leaders (e.g., Akamai, Cloudflare, Telefonica, Ericcson), standardization bodies (e.g., IETF, ETSI), and academic researchers have proposed numerous ways of achieving safer TLS delegation.
We present LURK the LURK (Limited Use of Remote Keys) extension for...
Towards Post-Quantum Security for Cyber-Physical Systems: Integrating PQC into Industrial M2M Communication
Sebastian Paul, Patrik Scheible
Applications
The threat of a cryptographically relevant quantum computer contributes to an increasing interest in the field of post-quantum cryptography (PQC). Compared to existing research efforts regarding the integration of PQC into the Transport Layer Security (TLS) protocol, industrial communication protocols have so far been neglected. Since industrial cyber-physical systems (CPS) are typically deployed for decades, protection against such long-term threats is needed. In this work, we propose two...
MultiTLS: Secure communication channels with cipher suite diversity
Ricardo Moura, David R. Matos, Miguel Pardal, Miguel Correia
Implementation
TLS ensures confidentiality, integrity, and authenticity of communications. However, design, implementation, and cryptographic vulnerabilities can make TLS communication channels insecure. We need mechanisms that allow the channels to be kept secure even when a new vulnerability is discovered.
We present MultiTLS, a middleware based on diversity and tunneling mechanisms that allows keeping communication channels secure even when new vulnerabilities are discovered. MultiTLS creates a secure...
Raccoon Attack: Finding and Exploiting Most-Significant-Bit-Oracles in TLS-DH(E)
Robert Merget, Marcus Brinkmann, Nimrod Aviram, Juraj Somorovsky, Johannes Mittmann, Jörg Schwenk
Cryptographic protocols
Diffie-Hellman key exchange (DHKE) is a widely adopted method for exchanging cryptographic key material in realworld protocols like TLS-DH(E). Past attacks on TLS-DH(E) focused on weak parameter choices or missing parameter validation. The confidentiality of the computed DH share, the premaster secret, was never questioned; DHKE is used as a generic method to avoid the security pitfalls of TLS-RSA.
We show that due to a subtle issue in the key derivation of all TLS-DH(E) cipher suites in...
Automated enumeration of block cipher differentials: An optimized branch-and-bound GPU framework
Wei-Zhu Yeoh, Je Sen Teh, Jiageng Chen
Secret-key cryptography
Block ciphers are prevalent in various security protocols used daily such as TLS, OpenPGP, and SSH. Their primary purpose is the protection of user data, both in transit and at rest. One of the de facto methods to evaluate block cipher security is differential cryptanalysis. Differential cryptanalysis observes the propagation of input patterns (input differences) through the cipher to produce output patterns (output differences). This probabilistic propagation is known as a differential; the...
A Cryptographic Analysis of the TLS 1.3 Handshake Protocol
Benjamin Dowling, Marc Fischlin, Felix Günther, Douglas Stebila
Cryptographic protocols
We analyze the handshake protocol of the Transport Layer Security (TLS) protocol, version 1.3. We address both the full TLS 1.3 handshake (the one round-trip time mode, with signatures for authentication and (elliptic curve) Diffie–Hellman ephemeral ((EC)DHE) key exchange), and the abbreviated resumption/"PSK" mode which uses a pre-shared key for authentication (with optional (EC)DHE key exchange and zero round-trip time key establishment). Our analysis in the reductionist security framework...
Tighter Proofs for the SIGMA and TLS 1.3 Key Exchange Protocols
Hannah Davis, Felix Günther
Cryptographic protocols
We give new, fully-quantitative and concrete bounds that justify the SIGMA and TLS 1.3 key exchange protocols not just in principle, but in practice. By this we mean that, for standardized elliptic curve group sizes, the overall protocol actually achieves the intended security level.
Prior work gave reductions of both protocols' security to the underlying building blocks that were loose (in the number of users and/or sessions), so loose that they gave no guarantees for practical...
Forward-Secure 0-RTT Goes Live: Implementation and Performance Analysis in QUIC
Fynn Dallmeier, Jan P. Drees, Kai Gellert, Tobias Handirk, Tibor Jager, Jonas Klauke, Simon Nachtigall, Timo Renzelmann, Rudi Wolf
Implementation
Modern cryptographic protocols, such as TLS 1.3 and QUIC, can send cryptographically protected data in "zero round-trip times (0-RTT)", that is, without the need for a prior interactive handshake. Such protocols meet the demand for communication with minimal latency, but those currently deployed in practice achieve only rather weak security properties, as they may not achieve forward security for the first transmitted payload message and require additional countermeasures against replay...
The Provable Security of Ed25519: Theory and Practice
Jacqueline Brendel, Cas Cremers, Dennis Jackson, Mang Zhao
Public-key cryptography
A standard requirement for a signature scheme is that it is existentially unforgeable under chosen message attacks (EUF-CMA), alongside other properties of interest such as strong unforgeability (SUF-CMA), and resilience against key substitution attacks.
Remarkably, no detailed proofs have ever been given for these security properties for EdDSA, and in particular its Ed25519 instantiations. Ed25519 is one of the most efficient and widely used signature schemes, and different instantiations...
The Memory-Tightness of Authenticated Encryption
Ashrujit Ghoshal, Joseph Jaeger, Stefano Tessaro
Secret-key cryptography
This paper initiates the study of the provable security of authenticated encryption (AE) in the memory-bounded setting. Recent works – Tessaro and Thiruvengadam (TCC '18), Jaeger and Tessaro (EUROCRYPT '19), and Dinur (EUROCRYPT '20) – focus on confidentiality, and look at schemes for which trade-offs between the attacker's memory and its data complexity are inherent. Here, we ask whether these results and techniques can be lifted to the full AE setting, which additionally asks for...
On the Tight Security of TLS 1.3: Theoretically-Sound Cryptographic Parameters for Real-World Deployments
Denis Diemert, Tibor Jager
Cryptographic protocols
We consider the theoretically-sound selection of cryptographic parameters, such as the size of algebraic groups or RSA keys, for TLS 1.3 in practice. While prior works gave security proofs for TLS 1.3, their security loss is quadratic in the total number of sessions across all users, which due to the pervasive use of TLS is huge. Therefore, in order to deploy TLS 1.3 in a theoretically-sound way, it would be necessary to compensate this loss with unreasonably large parameters that would be...
Robust Channels: Handling Unreliable Networks in the Record Layers of QUIC and DTLS 1.3
Marc Fischlin, Felix Günther, Christian Janson
Cryptographic protocols
The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not---and in fact...
Quantifying the Security Cost of Migrating Protocols to Practice
Christopher Patton, Thomas Shrimpton
Cryptographic protocols
We give a framework for relating the concrete security of a “reference” protocol (say, one appearing in an academic paper) to that of some derived, “real” protocol (say, appearing in a cryptographic standard). It is based on the indifferentiability framework of Maurer, Renner, and Holenstein (MRH), whose application has been exclusively focused upon non-interactive cryptographic primitives, e.g., hash functions and Feistel networks. Our extension of MRH is supported by a clearly defined...
TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client...
Introduced as a new protocol implemented in “Chrome Canary” for the Google Inc. Chrome browser, “New Hope” is engineered as a post-quantum key exchange for the TLS 1.2 protocol. The structure of the exchange is revised lattice-based cryptography. New Hope incorporates the key-encapsulation mechanism of Peikert which itself is a modified Ring-LWE scheme. The search space used to introduce the closest-vector problem is generated by an intersection of a tesseract and hexadecachoron, or the...
An Oblivious Pseudo-Random Function (OPRF) is a two-party protocol for jointly evaluating a Pseudo-Random Function (PRF), where a user has an input x and a server has an input k. At the end of the protocol, the user learns the evaluation of the PRF using key k at the value x, while the server learns nothing about the user's input or output. OPRFs are a prime tool for building secure authentication and key exchange from passwords, private set intersection, private information retrieval,...
Transport Layer Security ( TLS ) is foundational for safeguarding client-server communication. However, it does not extend integrity guarantees to third-party verification of data authenticity. If a client wants to present data obtained from a server, it cannot convince any other party that the data has not been tampered with. TLS oracles ensure data authenticity beyond the client-server TLS connection, such that clients can obtain data from a server and ensure provenance to any third...
Symmetric ratchets and one-way key chains play a vital role in numerous important security protocols such as TLS 1.3, DTLS 1.3, QUIC, Signal, MLS, EDHOC, OSCORE, and Apple PQ3. Despite the crucial role they play, very little is known about their security properties. This paper categorizes and examines different ratchet constructions, offering a comprehensive overview of their security. Our analysis reveals notable distinctions between different types of one-way key chains. Notably, the type...
It has been shown that post-quantum key exchange and authentication with ML-KEM and ML-DSA, NIST’s postquantum algorithm picks, will have an impact on TLS 1.3 performance used in the Web or other applications. Studies so far have focused on the overhead of quantum-resistant algorithms on TLS time-to-first-byte (handshake time). Although these works have been important in quantifying the slowdown in connection establishment, they do not capture the full picture regarding real-world TLS 1.3...
This technical note presents limits on the security (as a function of the number of plaintext bytes encrypted and the number of forgery attempts made by an adversary) for the main Authenticated Encryption schemes available in TLS 1.2 and the draft of TLS 1.3. These limits are derived from security proofs for the considered schemes available in the literature. Our intention is to provide considered technical input to on-going discussions in the TLS Working Group of the IETF concerning,...
We explore the issue of anonymously proving account ownership (anonymous PAO). Such proofs allow a prover to prove to a verifier that it owns a valid account at a server without being tracked by the server or the verifier, without requiring any changes at the server's end and without even revealing to it that any anonymous PAO is taking place. This concept is useful in sensitive applications like whistleblowing. The first introduction of anonymous PAOs was by Wang et al., who also introduced...
The Automatic Certificate Management Environment protocol (ACME) has significantly contributed to the widespread use of digital certificates in safeguarding the authenticity and privacy of Internet data. These certificates are required for implementing the Transport Layer Security (TLS) protocol. However, it is well known that the cryptographic algorithms employed in these certificates will become insecure with the emergence of quantum computers. This study assesses the challenges in...
Transport Layer Security (TLS) is the backbone security protocol of the Internet. As this fundamental protocol is at risk from future quantum attackers, many proposals have been made to protect TLS against this threat by implementing post-quantum cryptography (PQC). The widespread interest in post-quantum TLS has given rise to a large number of solutions over the last decade. These proposals differ in many aspects, including the security properties they seek to protect, the efficiency and...
Let's consider a scenario where the server encrypts data using AES-CBC without authentication and then sends only the encrypted ciphertext through TLS (without IV). Then, having a padding oracle, we managed to recover the initialization vector and the sensitive data, doing a cybersecurity audit for a Chilean company.
In this paper we show that Bleichenbacher-style attacks on RSA decryption are not only still possible, but also that vulnerable implementations are common. We have successfully attacked multiple implementations using only timing of decryption operation and shown that many others are vulnerable. To perform the attack we used more statistically rigorous techniques like the sign test, Wilcoxon signed-rank test, and bootstrapping of median of pairwise differences. We publish a set of tools for...
Data formats used for cryptographic inputs have historically been the source of many attacks on cryptographic protocols, but their security guarantees remain poorly studied. One reason is that, due to their low-level nature, formats often fall outside of the security model. Another reason is that studying all of the uses of all of the formats within one protocol is too difficult to do by hand, and requires a comprehensive, automated framework. We propose a new framework, “Comparse”, that...
Web users can gather data from secure endpoints and demonstrate the provenance of sensitive data to any third party by using privacy-preserving TLS oracles. In practice, privacy-preserving TLS oracles are practical in verifying private data up to 1 kB in size selectively, which limits their applicability to larger sensitive data sets. In this work, we introduce a new oracle protocol for TLS, which reaches new scales in selectively verifying the provenance of confidential web data. The...
Many modern security protocols such as TLS, WPA2, WireGuard, and Signal use a cryptographic primitive called Authenticated Encryption (optionally with Authenticated Data), also known as an AEAD scheme. AEAD is a variant of symmetric encryption that additionally provides authentication. While authentication may seem to be a straightforward additional requirement, it has in fact turned out to be complex: many different security notions for AEADs are still being proposed, and several recent...
The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient...
We design DiStefano: an efficient, maliciously-secure framework for generating private commitments over TLS-encrypted web traffic, for a designated third-party. DiStefano provides many improvements over previous TLS commitment systems, including: a modular protocol specific to TLS 1.3, support for arbitrary verifiable claims over encrypted data, inherent ring privacy for client browsing history, and various optimisations to ensure fast online performance of the TLS 1.3 session. We build a...
Public data can be authenticated by obtaining from a trustworthy website with TLS. Private data, such as user profile, are usually restricted from public access. If a user wants to authenticate his private data (e.g., address) provided by a restricted website (e.g., user profile page of a utility company website) to a verifier, he cannot simply give his username and password to the verifier. DECO (CCS 2020) provides a solution for liberating these data without introducing undesirable trust...
Zero-knowledge middleboxes (ZKMBs) are a recent paradigm in which clients get privacy while middleboxes enforce policy: clients prove in zero knowledge that the plaintext underlying their encrypted traffic complies with network policies, such as DNS filtering. However, prior work had impractically poor performance and was limited in functionality. This work presents Zombie, the first system built using the ZKMB paradigm. Zombie introduces techniques that push ZKMBs to the verge of...
Transport Layer Security (TLS) establishes an authenticated and confidential channel to deliver data for almost all Internet applications. A recent work (Zhang et al., CCS'20) proposed a protocol to prove the TLS payload to a third party, without any modification of TLS servers, while ensuring the privacy and originality of the data in the presence of malicious adversaries. However, it required maliciously secure Two-Party Computation (2PC) for generic circuits, leading to significant...
The duplex construction is already well analyzed with many papers proving its security in the random permutation model. However, so far, the first phase of the duplex, where the state is initialized with a secret key and an initialization vector ($\mathit{IV}$), is typically analyzed in a worst case manner. More detailed, it is always assumed that the adversary is allowed to choose the $\mathit{IV}$ on its will. In this paper, we analyze how the security changes if restrictions on the choice...
Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model. In this work, we study the question whether these...
Transport Layer Security (TLS) 1.3 and the Signal protocol are very important and widely used security protocols. We show that the key update function in TLS 1.3 and the symmetric key ratchet in Signal can be modeled as non-additive synchronous stream ciphers. This means that the efficient Time Memory Tradeoff Attacks for stream ciphers can be applied. The implication is that TLS 1.3, QUIC, DTLS 1.3, and Signal offer a lower security level against TMTO attacks than expected from the key...
It all started with ECDSA nonces and keys duplications in a large amount of X.509 certificates generated by Cisco ASA security gateways, detected through TLS campaigns analysis. After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces. The current article describes our...
In Internet security protocols including TLS 1.3, KEMTLS, MLS and Noise, HMAC is being assumed to be a dual-PRF, meaning a PRF not only when keyed conventionally (through its first input), but also when "swapped" and keyed (unconventionally) through its second (message) input. We give the first in-depth analysis of the dual-PRF assumption on HMAC. For the swap case, we note that security does not hold in general, but completely characterize when it does; we show that HMAC is swap-PRF...
In this work, we assess the real-world practicality of CSIDH, an isogeny-based non-interactive key exchange. We provide the first thorough assessment of the practicality of CSIDH in higher parameter sizes for conservative estimates of quantum security, and with protection against physical attacks. This requires a three-fold analysis of CSIDH. First, we describe two approaches to efficient high-security CSIDH implementations, based on SQALE and CTIDH. Second, we optimize such high-security...
Recently, NIST has announced Kyber, a lattice-based key encapsulation mechanism (KEM), as a post-quantum standard. However, it is not the most efficient scheme among the NIST's KEM finalists. Saber enjoys more compact sizes and faster performance, and Mera et al. (TCHES '21) further pushed its efficiency, proposing a shorter KEM, Sable. As KEM are frequently used on the Internet, such as in TLS protocols, it is essential to achieve high efficiency while maintaining sufficient security....
The ubiquitous use of smartphones has contributed to more and more users conducting their online browsing activities through apps, rather than web browsers. In order to provide a seamless browsing experience to the users, apps rely on a variety of HTTP-based APIs and third-party libraries, and make use of the TLS protocol to secure the underlying communication. With NIST's recent announcement of the first standards for post-quantum algorithms, there is a need to better understand the...
We show how to embed a covert key exchange sub protocol within a regular TLS 1.3 execution, generating a stealth key in addition to the regular session keys. The idea, which has appeared in the literature before, is to use the exchanged nonces to transport another key value. Our contribution is to give a rigorous model and analysis of the security of such embedded key exchanges, requiring that the stealth key remains secure even if the regular key is under adversarial control. Specifically...
Post-Quantum cryptography (PQC), in the past few years, constitutes the main driving force of the quantum resistance transition for security primitives, protocols and tools. TLS is one of the widely used security protocols that needs to be made quantum safe. However, PQC algorithms integration into TLS introduce various implementation overheads compared to traditional TLS that in battery powered embedded devices with constrained resources, cannot be overlooked. While there exist several...
We revisit batch signatures (previously considered in a draft RFC, and used in multiple recent works), where a single, potentially expensive, "inner" digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties. We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST's post-quantum project, to high...
We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram's equivalent of the TLS record protocol. We give positive and negative results. On the one hand, we formally and in detail model a slight variant of Telegram's "record protocol" and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our...
The NIST, in its recent competition on quantum-resilient confidentiality primitives, requested the submission of exclusively KEMs. The task of KEMs is to establish secure session keys that can drive, amongst others, public key encryption and TLS-like secure channels. In this work we test the KEM abstraction in the context of constructing cryptographic schemes that are not subsumed in the PKE and secure channels categories. We find that, when used to construct a key transport scheme or when...
Encrypting too much data using the same key is a bad practice from a security perspective. Hence, it is customary to perform re-keying after a given amount of data is transmitted. While in many cases, the re-keying is done using a fresh execution of some key exchange protocol (e.g., in IKE or TLS), there are scenarios where internal re-keying, i.e., without exchange of information, is performed, mostly due to performance reasons. Originally suggested by Abdalla and Bellare, there are...
OPAQUE is an Asymmetric Password-Authenticated Key Exchange (aPAKE) protocol being standardized by the IETF (Internet Engineering Task Force) as a more secure alternative to the traditional ``password-over-TLS'' mechanism prevalent in current practice. OPAQUE defends against a variety of vulnerabilities of password-over-TLS by dispensing with reliance on PKI and TLS security, and ensuring that the password is never visible to servers or anyone other than the client machine where the password...
The TLS (Transport Layer Security) protocol is the most important, most attacked, most analysed and most used cryptographic protocol in the world today. TLS is critical to the integrity of the Internet, and if it were to be broken e-commerce would become impossible, with very serious implications for the global economy. Furthermore TLS is likely to assume even greater significance in the near future with the rapid growth of an Internet of Things (IoT) -- a multiplicity of internet connected...
TLS termination, which is essential to network and security infrastructure providers, is an extremely latency sensitive operation that benefits from access to sensitive key material close to the edge. However, increasing regulatory concerns prompt customers to demand sophisticated controls on where their keys may be accessed. While traditional access-control solutions rely on a highly available centralized process to enforce access, the round-trip latency and decreased fault tolerance make...
The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and...
Critical and widely used cryptographic protocols have repeatedly been found to contain flaws in their design and their implementation. A prominent class of such vulnerabilities is logical attacks, e.g. attacks that exploit flawed protocol logic. Automated formal verification methods, based on the Dolev-Yao (DY) attacker, formally define and excel at finding such flaws, but operate only on abstract specification models. Fully automated verification of existing protocol implementations is...
Recently, in post-quantum cryptography migration, it has been shown that an IND-1-CCA-secure key encapsulation mechanism (KEM) is required for replacing an ephemeral Diffie-Hellman (DH) in widely-used protocols, e.g., TLS, Signal, and Noise. IND-1-CCA security is a notion similar to the traditional IND-CCA security except that the adversary is restricted to one single decapsulation query. At EUROCRYPT 2022, based on CPA-secure public-key encryption (PKE), Huguenin-Dumittan and Vaudenay...
The DECentralized Oracle (DECO) protocol enables the verifiable provenance of data from Transport Layer Security (TLS) connections through secure two-party computation and zero-knowledge proofs. In this paper, we present PECO, an extension of DECO that enhances privacy features through the integration of two new private three-party handshake protocols (P3P-HS). PECO allows any web user to prove to a verifier the properties of data from TLS connections without disclosing the identity of the...
DMTF is a standards organization by major industry players in IT infrastructure including AMD, Alibaba, Broadcom, Cisco, Dell, Google, Huawei, IBM, Intel, Lenovo, and NVIDIA, which aims to enable interoperability, e.g., including cloud, virtualization, network, servers and storage. It is currently standardizing a security protocol called SPDM, which aims to secure communication over the wire and to enable device attestation, notably also explicitly catering for communicating hardware...
TLS is ubiquitous in modern computer networks. It secures transport for high-end desktops and low-end embedded devices alike. However, the public key cryptosystems currently used within TLS may soon be obsolete as large-scale quantum computers, once realized, would be able to break them. This threat has led to the development of post-quantum cryptography (PQC). The U.S. standardization body NIST is currently in the process of concluding a multi-year search for promising post-quantum...
EDHOC is a lightweight authenticated key exchange protocol for IoT communication, currently being standardized by the IETF. Its design is a trimmed-down version of similar protocols like TLS 1.3, building on the SIGn-then-MAc (SIGMA) rationale. In its trimming, however, EDHOC notably deviates from the SIGMA design by sending only short, non-unique credential identifiers, and letting recipients perform trial verification to determine the correct communication partner. Done naively, this can...
Post-quantum Cryptography (PQC) has reached the verge of standardization competition, with Kyber as a winning candidate. In this work, we demonstrate practical backdoor insertion in Kyber through kleptrography. The backdoor can be inserted using classical techniques like ECDH or post-quantum Classic Mceliece. The inserted backdoor targets the key generation procedure where generated output public keys subliminally leak information about the secret key to the owner of the backdoor. We...
Digital Signature Schemes such as DSA, ECDSA, and RSA are widely deployed to protect the integrity of security protocols such as TLS, SSH, and IPSec. In TLS, for instance, RSA and (EC)DSA are used to sign the state of the agreed upon protocol parameters during the handshake phase. Naturally, RSA and (EC)DSA implementations have become the target of numerous attacks, including powerful side-channel attacks. Hence, cryptographic libraries were patched repeatedly over the years. Here we...
Adopting Post-Quantum Cryptography (PQC) in network protocols is a challenging subject. Larger PQC public keys and signatures can significantly slow the Transport Layer Security (TLS) protocol. In this context, KEMTLS is a promising approach that replaces the handshake signatures by using PQC Key Encapsulation Mechanisms (KEMs), which have, in general, smaller sizes. However, for broad PQC adoption, hybrid cryptography has its advantages over PQC-only approaches, mainly about the confidence...
Quantum computing advances threaten the security of today's public key infrastructure, and have led to the pending standardization of alternative, quantum-resistant key encapsulation and digital signature cryptography schemes. Unfortunately, authentication algorithms based on the new post-quantum (PQ) cryptography create significant performance bottlenecks for TLS due to larger certificate chains which introduce additional packets and round-trips. The TLS handshake slowdown will be...
Authenticated key-exchange (AKE) protocols are an important class of protocols that allow two parties to establish a common session key over an insecure channel such as the Internet to then protect their communication. They are widely deployed in security protocols such as TLS, IPsec and SSH. Besides the confidentiality of the communicated data, an orthogonal but increasingly important goal is the protection of the confidentiality of the identities of the involved parties (aka privacy). For...
We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's...
KEMTLS is a proposal for changing the TLS handshake to authenticate the handshake using long-term key encapsulation mechanism keys instead of signatures, motivated by trade-offs in the characteristics of post-quantum algorithms. Prior proofs of security of KEMTLS and its variant KEMTLS-PDK have been hand-written proofs in the reductionist model under computational assumptions. In this paper, we present computer-verified symbolic analyses of KEMTLS and KEMTLS-PDK using two distinct Tamarin...
We present SimplePIR, the fastest single-server private information retrieval scheme known to date. SimplePIR’s security holds under the learning-with-errors assumption. To answer a client’s query, the SimplePIR server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte. SimplePIR achieves 10 GB/s/core server throughput, which approaches the memory bandwidth of the machine and the performance of the fastest two-server private-information-retrieval schemes...
Symbolic security protocol verifiers have reached a high degree of automation and maturity. Today, experts can model real-world protocols, but this often requires model-specific encodings and deep insight into the strengths and weaknesses of each of those tools. With Sapic+ , we introduce a protocol verification platform that lifts this burden and permits choosing the right tool for the job, at any development stage. We build on the existing compiler from Sapic to Tamarin, and extend it with...
Certificate authorities in public key infrastructures typically require entities to prove possession of the secret key corresponding to the public key they want certified. While this is straightforward for digital signature schemes, the most efficient solution for public key encryption and key encapsulation mechanisms (KEMs) requires an interactive challenge-response protocol, requiring a departure from current issuance processes. In this work we investigate how to non-interactively prove...
Onion services enable bidirectional anonymity for parties that communicate over the Tor network, thus providing improved privacy properties compared to standard TLS connections. Since these services are designed to support server-side anonymity, the entry points for these services shuffle across the Tor network periodically. In order to connect to an onion service at a given time, the client has to resolve the .onion address for the service, which requires querying volunteer Tor nodes called...
One of the most significant challenges is the secure user authentication. If it becomes breached, confidentiality and integrity of the data or services may be compromised. The most widespread solution for entity authentication is the password-based scheme. It is easy to use and deploy. During password registration typically users create or activate their account along with their password through their verification email, and service providers are authenticated based on their SSL/TLS...
The pre-shared key (PSK) handshake modes of TLS 1.3 allow for the performant, low-latency resumption of previous connections and are widely used on the Web and by resource-constrained devices, e.g., in the Internet of Things. Taking advantage of these performance benefits with optimal and theoretically-sound parameters requires tight security proofs. We give the first tight security proofs for the TLS 1.3 PSK handshake modes. Our main technical contribution is to address a gap in prior...
Cache systems are crucial for reducing communication overhead on the Internet. The importance of communication privacy is being increasingly and widely recognized; therefore, we anticipate that nearly all end-to-end communication will be encrypted via secure sockets layer/transport layer security (SSL/TLS) in the near future. Herein we consider a catch-22 situation, wherein the cache server checks whether content has been cached or not, i.e., the cache server needs to observe it, thereby...
The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even...
The emergence of cloud-computing has raised important privacy questions about the data that users share with remote servers. While data in transit is protected using standard techniques like Transport Layer Security (TLS), most cloud providers have unrestricted plaintext access to user data at the endpoint. Fully Homomorphic Encryption (FHE) offers one solution to this problem by allowing for arbitrarily complex computations on encrypted data without ever needing to decrypt it....
The Transport Layer Security (TLS) protocol is a fundamental building block for ensuring security on Internet. It provides an easy to use framework for the purposes of establishing an authenticated and secure channel between two parties that have never physically met. Nevertheless, TLS only provides a simple cryptographic functionality compared to more advanced protocols such as protocols for secure multiparty computation (MPC). In this work, we provide a framework for efficiently...
The threat of a cryptographically relevant quantum computer contributes to an increasing interest in the field of post-quantum cryptography (PQC). Compared to existing research efforts regarding the integration of PQC into the Transport Layer Security (TLS) protocol, industrial communication protocols have so far been neglected. Since industrial cyber-physical systems (CPS) are typically deployed for decades, protection against such long-term threats is needed. In this work, we propose two...
Transport Layer Security (TLS) constitutes one of the most widely used protocols for securing Internet communications and has also found broad acceptance in the Internet of Things (IoT) domain. As we progress toward a security environment resistant to quantum computer attacks, TLS needs to be transformed to support post-quantum cryptography. However, post-quantum TLS is still not standardised, and its overall performance, especially in resource-constrained, IoT-capable, embedded devices, is...
The aim of this document is to clarify the DFR (Decoding Failure Rate) claims made for BIKE, a third round alternate candidate KEM (Key Encapsulation Mechanism) to the NIST call for post-quantum cryptography standardization. For the most part, the material presented here is not new, it is extracted from the relevant scientific literature, in particular [V21]. Even though a negligible DFR is not needed for a KEM using ephemeral keys (e.g. TLS) which only requires IND-CPA security, it seems...
he ACME certificate issuance and management protocol, standardized as IETF RFC 8555, is an essential element of the web public key infrastructure (PKI). It has been used by Let’s Encrypt and other certification authorities to issue over a billion certificates, and a majority of HTTPS connections are now secured with certificates issued through ACME. Despite its importance, however, the security of ACME has not been studied at the same level of depth as other protocol standards like TLS 1.3...
Large-scale quantum computers will be able to efficiently solve the underlying mathematical problems of widely deployed public key cryptosystems in the near future. This threat has sparked increased interest in the field of Post-Quantum Cryptography (PQC) and standardization bodies like NIST, IETF, and ETSI are in the process of standardizing PQC schemes as a new generation of cryptography. This raises the question of how to ensure a fast, reliable, and secure transition to upcoming PQC...
Public key cryptography is widely used in key exchange and digital signature protocols. Public key cryptography requires expensive primitive operations, such as finite-field and group operations. These finite-field and group operations require a number of clock cycles to exe- cute. By carefully optimizing these primitive operations, public key cryp- tography can be performed with reasonably fast execution timing. In this paper, we present the new implementation result of Curve448 on 32-bit ARM...
As Internet of Things (IoT) thriving over the whole world, more and more IoT devices and IoT-based protocols have been designed and proposed in order to meet people's needs. Among those protocols, message queueing telemetry transport (MQTT) is one of the most emerging and promising protocol, which provides many-to-many message transmission based on the ``publish/subscribe'' mechanism. It has been widely used in industries such as the energy industry, chemical engineering, self-driving,...
It is well-known that already the length of encrypted messages may reveal sensitive information about encrypted data. Fingerprinting attacks enable an adversary to determine web pages visited by a user and even the language and phrases spoken in voice-over-IP conversations. Prior research has established the general perspective that a length-hiding padding which is long enough to improve security significantly incurs an unfeasibly large bandwidth overhead. We argue that this perspective is...
This paper initiates research on zero-knowledge middleboxes (ZKMBs). A ZKMB is a network middlebox that enforces network usage policies on encrypted traffic. Clients send the middlebox zero-knowledge proofs that their traffic is policy-compliant; these proofs reveal nothing about the client’s communication except that it complies with the policy. We show how to make ZKMBs work with unmodified encrypted-communication protocols (specifically TLS 1.3), making ZKMBs invisible to servers. As a...
KEMTLS is a novel alternative to the Transport Layer Security (TLS) handshake that integrates post-quantum algorithms. It uses key encapsulation mechanisms (KEMs) for both confidentiality and authentication, achieving post-quantum security while obviating the need for expensive post-quantum signatures. The original KEMTLS paper presents a security analysis, Rust implementation, and benchmarks over emulated networks. In this work, we provide full Go implementations of KEMTLS and other...
The TLS 1.3 session resumption handshakes enables a client and a server to resume a previous connection via a shared secret, which was established during a previous session. In practice, this is often done via session tickets, where the server provides a "self-encrypted" ticket containing the shared secret to its clients. A client may resume its session by sending the ticket to the server, which allows the server to retrieve the shared secret stored within the ticket. Usually, a ticket is...
A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the various kind of malicious behaviors of the adversaries, there have been lots of efforts to define the security models. Amongst them, the extended Canetti-Krawczyk (eCK) security model is considered as one of the strongest ones and widely...
OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the security of the OPRF. If the latter breaks (by cryptanalysis,...
Bounded IND-CCA security (IND-qCCA) is a notion similar to the traditional IND-CCA security, except the adversary is restricted to a constant number q of decryption/decapsulation queries. We show in this work that IND-qCCA is easily obtained from any passively secure PKE in the (Q)ROM. That is, simply adding a confirmation hash or computing the key as the hash of the plaintext and ciphertext holds an IND-qCCA KEM. In particular, there is no need for derandomization or re-encryption as in...
Google's CECPQ1 experiment in 2016 integrated a post-quantum key-exchange algorithm, newhope1024, into TLS 1.2. The Google-Cloudflare CECPQ2 experiment in 2019 integrated a more efficient key-exchange algorithm, ntruhrss701, into TLS 1.3. This paper revisits the choices made in CECPQ2, and shows how to achieve higher performance for post-quantum key exchange in TLS 1.3 using a higher-security algorithm, sntrup761. Previous work had indicated that ntruhrss701 key generation was much faster...
The amount of encrypted Internet traffic almost doubles every year thanks to the wide adoption of end-to-end traffic encryption solutions such as IPSec, TLS and SSH. Despite all the benefits of user privacy the end-to-end encryption provides, the encrypted internet traffic blinds intrusion detection system (IDS) and makes detecting malicious traffic hugely difficult. The resulting conflict between the user's privacy and security has demanded solutions for deep packet inspection (DPI) over...
While server-only authentication with certificates is the most widely used mode of operation for the Transport Layer Security (TLS) protocol on the world wide web, there are many applications where TLS is used in a different way or with different constraints. For example, embedded Internet-of-Things clients may have a server certificate pre-programmed and be highly constrained in terms of communication bandwidth or computation power. As post-quantum algorithms have a wider range of...
The recent KEMTLS protocol (Schwabe, Stebila and Wiggers,CCS’20) is a promising design for a quantum-safe TLS handshake protocol. Focused on the web setting, wherein clients learn server public-key certificates only during connection establishment, a drawback of KEMTLS compared to TLS 1.3 is that it introduces an additional round trip before the server can send data, and an extra one for the client as well in the case of mutual authentication. In many scenarios, including IoT and embedded...
Currently most practical attacks on cryptographic protocols like TLS are based on side channels, such as padding oracles. Some well-known recent examples are DROWN, ROBOT and Raccoon (USENIX Security 2016, 2018, 2021). Such attacks are usually found by careful and time-consuming manual analysis by specialists. In this paper, we consider the question of how such attacks can be systematically detected and prevented before (large-scale) deployment. We propose a new, fully automated approach,...
We analyze the security of the TLS 1.3 key establishment protocol, as specified at the end of its rigorous standardization process. We define a core key-schedule and reduce its security to concrete assumptions against an adversary that controls client and server configurations and adaptively chooses some of their keys. Our model supports all key derivations featured in the standard, including its negotiated modes and algorithms that combine an optional Diffie-Hellman exchange for...
Systems with distributed trust have attracted growing research attention and seen increasing industry adoptions. In these systems, critical secrets are distributed across N servers, and computations are performed privately using secure multi-party computation (SMPC). Authentication for these distributed-trust systems faces two challenges. The first challenge is ease-of-use. Namely, how can an authentication protocol maintain its user experience without sacrificing security? To avoid a...
In this paper, we describe Oblivious TLS: an MPC protocol that we prove UC secure against a majority of actively corrupted parties. The protocol securely implements TLS 1.3. Thus, any party P who runs TLS can communicate securely with a set of servers running Oblivious TLS; P does not need to modify anything, or even be aware that MPC is used. Applications of this include communication between servers who offer MPC services and clients, to allow the clients to easily and securely provide...
The Classic McEliece cryptosystem is one of the most trusted quantum-resistant cryptographic schemes. Deploying it in practical applications, however, is challenging due to the size of its public key. In this work, we bridge this gap. We present an implementation of Classic McEliece on an ARM Cortex-M4 processor, optimized to overcome memory constraints. To this end, we present an algorithm to retrieve the public key ad-hoc. This reduces memory and storage requirements and enables the...
In this paper, we present a strong, formal, and general-purpose cryptographic model for privacy-preserving authenticated key exchange (PPAKE) protocols. PPAKE protocols are secure in the traditional AKE sense but additionally guarantee the confidentiality of the identities used in communication sessions. Our model has several useful and novel features, among others: it is a proper extension of classical AKE models, guarantees in a strong sense that the confidentiality of session keys is...
The typical login protocol for authenticating a user to a web service involves the client sending a password over a TLS-secured channel to the service, occasionally deployed with the password being prehashed. This widely-deployed paradigm, while simple in nature, is prone to both inadvertent logging and eavesdropping attacks, and has repeatedly led to the exposure of passwords in plaintext. Partly to address this problem, symmetric and asymmetric PAKE protocols were developed to ensure that...
The security of digital communication relies on few cryptographic protocols that are used to protect internet traffic, from web sessions to instant messaging. These protocols and the cryptographic primitives they rely on have been extensively studied and are considered secure. Yet, sophisticated attackers are often able to bypass rather than break security mechanisms. Kleptography or algorithm substitution attacks (ASA) describe techniques to place backdoors right into cryptographic...
By design, TLS (Transport Layer Security) is a 2-party, end-to-end protocol. Yet, in practice, TLS delegation is often deployed: that is, middlebox proxies inspect and even modify TLS traffic between the endpoints. Recently, industry-leaders (e.g., Akamai, Cloudflare, Telefonica, Ericcson), standardization bodies (e.g., IETF, ETSI), and academic researchers have proposed numerous ways of achieving safer TLS delegation. We present LURK the LURK (Limited Use of Remote Keys) extension for...
The threat of a cryptographically relevant quantum computer contributes to an increasing interest in the field of post-quantum cryptography (PQC). Compared to existing research efforts regarding the integration of PQC into the Transport Layer Security (TLS) protocol, industrial communication protocols have so far been neglected. Since industrial cyber-physical systems (CPS) are typically deployed for decades, protection against such long-term threats is needed. In this work, we propose two...
TLS ensures confidentiality, integrity, and authenticity of communications. However, design, implementation, and cryptographic vulnerabilities can make TLS communication channels insecure. We need mechanisms that allow the channels to be kept secure even when a new vulnerability is discovered. We present MultiTLS, a middleware based on diversity and tunneling mechanisms that allows keeping communication channels secure even when new vulnerabilities are discovered. MultiTLS creates a secure...
Diffie-Hellman key exchange (DHKE) is a widely adopted method for exchanging cryptographic key material in realworld protocols like TLS-DH(E). Past attacks on TLS-DH(E) focused on weak parameter choices or missing parameter validation. The confidentiality of the computed DH share, the premaster secret, was never questioned; DHKE is used as a generic method to avoid the security pitfalls of TLS-RSA. We show that due to a subtle issue in the key derivation of all TLS-DH(E) cipher suites in...
Block ciphers are prevalent in various security protocols used daily such as TLS, OpenPGP, and SSH. Their primary purpose is the protection of user data, both in transit and at rest. One of the de facto methods to evaluate block cipher security is differential cryptanalysis. Differential cryptanalysis observes the propagation of input patterns (input differences) through the cipher to produce output patterns (output differences). This probabilistic propagation is known as a differential; the...
We analyze the handshake protocol of the Transport Layer Security (TLS) protocol, version 1.3. We address both the full TLS 1.3 handshake (the one round-trip time mode, with signatures for authentication and (elliptic curve) Diffie–Hellman ephemeral ((EC)DHE) key exchange), and the abbreviated resumption/"PSK" mode which uses a pre-shared key for authentication (with optional (EC)DHE key exchange and zero round-trip time key establishment). Our analysis in the reductionist security framework...
We give new, fully-quantitative and concrete bounds that justify the SIGMA and TLS 1.3 key exchange protocols not just in principle, but in practice. By this we mean that, for standardized elliptic curve group sizes, the overall protocol actually achieves the intended security level. Prior work gave reductions of both protocols' security to the underlying building blocks that were loose (in the number of users and/or sessions), so loose that they gave no guarantees for practical...
Modern cryptographic protocols, such as TLS 1.3 and QUIC, can send cryptographically protected data in "zero round-trip times (0-RTT)", that is, without the need for a prior interactive handshake. Such protocols meet the demand for communication with minimal latency, but those currently deployed in practice achieve only rather weak security properties, as they may not achieve forward security for the first transmitted payload message and require additional countermeasures against replay...
A standard requirement for a signature scheme is that it is existentially unforgeable under chosen message attacks (EUF-CMA), alongside other properties of interest such as strong unforgeability (SUF-CMA), and resilience against key substitution attacks. Remarkably, no detailed proofs have ever been given for these security properties for EdDSA, and in particular its Ed25519 instantiations. Ed25519 is one of the most efficient and widely used signature schemes, and different instantiations...
This paper initiates the study of the provable security of authenticated encryption (AE) in the memory-bounded setting. Recent works – Tessaro and Thiruvengadam (TCC '18), Jaeger and Tessaro (EUROCRYPT '19), and Dinur (EUROCRYPT '20) – focus on confidentiality, and look at schemes for which trade-offs between the attacker's memory and its data complexity are inherent. Here, we ask whether these results and techniques can be lifted to the full AE setting, which additionally asks for...
We consider the theoretically-sound selection of cryptographic parameters, such as the size of algebraic groups or RSA keys, for TLS 1.3 in practice. While prior works gave security proofs for TLS 1.3, their security loss is quadratic in the total number of sessions across all users, which due to the pervasive use of TLS is huge. Therefore, in order to deploy TLS 1.3 in a theoretically-sound way, it would be necessary to compensate this loss with unreasonably large parameters that would be...
The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not---and in fact...
We give a framework for relating the concrete security of a “reference” protocol (say, one appearing in an academic paper) to that of some derived, “real” protocol (say, appearing in a cryptographic standard). It is based on the indifferentiability framework of Maurer, Renner, and Holenstein (MRH), whose application has been exclusively focused upon non-interactive cryptographic primitives, e.g., hash functions and Feistel networks. Our extension of MRH is supported by a clearly defined...
