International Association
for Cryptologic Research

We describe, formally model, and prove the security of Telegram's key exchange protocols for client-server communications. To achieve this, we develop a suitable multi-stage key exchange security model along with pseudocode descriptions of the Telegram protocols that are based on analysis of Telegram's specifications and client source code. We carefully document how our descriptions differ from reality and justify our modelling choices. Our security proofs reduce the security of the protocols to that of their cryptographic building blocks, but the subsequent analysis of those building blocks requires the introduction of a number of novel security assumptions, reflecting many design decisions made by Telegram that are suboptimal from the perspective of formal analysis. Along the way, we provide a proof of IND-CCA security for the variant of RSA-OEAP+ used in Telegram and identify a hypothetical attack exploiting current Telegram server behaviour (which is not captured in our protocol descriptions). Finally, we reflect on the broader lessons about protocol design that can be taken from our work.

Users increasingly store their data in the cloud, thereby benefiting from easy access, sharing, and redundancy. To additionally guarantee security of the outsourced data even against a server compromise, some service providers have started to offer end-to-end encrypted (E2EE) cloud storage. With this cryptographic protection, only legitimate owners can read or modify the data. However, recent attacks on the largest E2EE providers have highlighted the lack of solid foundations for this emerging type of service. In this paper, we address this shortcoming by initiating the formal study of E2EE cloud storage. We give a formal syntax to capture the core functionality of a cloud storage system, capturing the real-world complexity of such a system’s constituent interactive protocols. We then define game-based security notions for confidentiality and integrity of a cloud storage system against a fully malicious server. We treat both selective and fully adaptive client compromises. Our notions are informed by recent attacks on E2EE cloud storage providers. In particular we show that our syntax is rich enough to capture the core functionality of MEGA and that recent attacks on it arise as violations of our security notions. Finally, we present an E2EE cloud storage system that provides all core functionalities and that is both efficient and provably secure with respect to our selective security notions. Along the way, we discuss challenges on the path towards bringing the security of cloud storage up to par with other end-to-end primitives, such as secure messaging and TLS.

One of the most popular symmetric encryption schemes in use on the Internet is ChaCha20-Poly1305. It is the default choice in tools like OpenSSH and Wireguard, and one of only three supported ciphersuites in TLS 1.3. ChaCha20Poly1305 utilizes a polynomial-based hash function for constructing Message Authentication Codes via the Wegman-Carter MAC construction. This entails evaluating the polynomial hash over the data, and blinding the output with a pseudorandom value obtained by enciphering a nonce with a blockcipher. More specifically, it uses Poly1305, originally designed with specific hardware in mind. Today, nearly 20 years later, we ask the following question: Given today's advancements and applications would we still converge to this same design?

We provide an extensive cryptographic analysis of Threema, a Swiss-based encrypted messaging application with more than 10 million users and 7000 corporate customers. We present seven different attacks against the protocol in three different threat models. As one example, we present a cross-protocol attack which breaks authentication in Threema and which exploits the lack of proper key separation between different sub-protocols. As another, we demonstrate a compression-based side-channel attack that recovers users' long-term private keys through observation of the size of Threema encrypted backups. From our analysis, we draw three wider lessons for developers of secure protocols.

MEGA is a large-scale cloud storage and communication platform that aims to provide end-to-end encryption for stored data. A recent analysis by Backendal, Haller and Paterson (IEEE S\&P 2023) invalidated these security claims by presenting practical attacks against MEGA that could be mounted by the MEGA service provider. In response, the MEGA developers added lightweight sanity checks on the user RSA private keys used in MEGA, sufficient to prevent the previous attacks. We analyse these new sanity checks and show how they themselves can be exploited to mount novel attacks on MEGA that recover a target user's RSA private key with only slightly higher attack complexity than the original attacks. We identify the presence of an ECB encryption oracle under a target user's master key in the MEGA system; this oracle provides our adversary with the ability to partially overwrite a target user's RSA private key with chosen data, a powerful capability that we use in our attacks. We then present two distinct types of attack, each type exploiting different error conditions arising in the sanity checks and in subsequent cryptographic processing during MEGA's user authentication procedure. The first type appears to be novel and exploits the manner in which the MEGA code handles modular inversion when recomputing $u=q^{-1} \bmod p$. The second can be viewed as a small subgroup attack (van Oorschot and Wiener, EUROCRYPT 1996, Lim and Lee, CRYPTO 1998). We prototype the attacks and show that they work in practice. As a side contribution, we show how to improve the RSA key recovery attack of Backendal-Haller-Paterson against the unpatched version of MEGA to require only 2 logins instead of the original 512. We conclude by discussing wider lessons about secure implementation of cryptography that our work surfaces.

As privacy-awareness rises, demand for end-to-end encrypted (E2EE) services is increasing. However, not all systems live up to their advertised security guarantees. MEGA—the largest provider of E2EE cloud storage with over 260 million users—failed to protect the confidentiality and integrity of their customers’ data, as our recent paper “MEGA: Malleable Encryption Goes Awry” showed. In this talk, we take a step back and discuss why it is surprisingly challenging to design a privacy-preserving cloud storage protocol that is secure even when the cloud provider is actively malicious. Recent academic effort focused on building file sharing systems which hide metadata. However, systems in practice still face much more fundamental challenges including key management, asynchronously coalescing updates stemming from collaboration on shared E2EE files, and cryptographic agility. We briefly discuss the approach of MEGA and how it was susceptible to a key recovery attack that allowed a malicious cloud provider to decrypt user files, among other vulnerabilities. Based on the attacks on MEGA, we suggest best practices for designing secure E2EE cloud storage systems. Unfortunately, it is infeasible for MEGA to completely redesign their system due to scale and backward compatibility. Even if a redesign was possible, the security they currently aim to provide still falls short of offering desirable properties like post-compromise security, forward security, and key rotation. With this in mind, we point out open questions for future work and advocate for a standardization process for a cloud storage design.

A core goal of the NIST PQC competition is to produce PKE schemes which, even if attacked with a large-scale quantum computer, maintain the security guarantees needed by applications. The main security focus in the NIST PQC context has been IND-CCA security, but other applications demand that PKE schemes provide 'anonymity' (Bellare et al., ASIACRYPT 2001), and 'robustness' (Abdalla et al., TCC 2010). Examples of such applications include anonymous cryptocurrencies, searchable encryption, and auction protocols. However, almost nothing is known about how to build post-quantum PKE schemes offering these security properties. In particular, the status of the NIST PQC candidates with respect to anonymity and robustness is unknown. This paper initiates a systematic study of anonymity and robustness for post-quantum PKE schemes. Firstly, we identify implicit rejection as a crucial design choice shared by most post-quantum KEMs, show that implicit rejection renders prior results on anonymity and robustness for KEM-DEM PKEs inapplicable, and transfer prior results to the implicit-rejection setting where possible. Secondly, since they are widely used to build post-quantum PKEs, we examine how the Fujisaki-Okamoto (FO) transforms (Fujisaki and Okamoto, Journal of Cryptology 2013) confer robustness and enhance weak anonymity of a base PKE. We then leverage our theoretical results to study the anonymity and robustness of three NIST KEM finalists---Saber, Kyber, and Classic McEliece---and one alternate, FrodoKEM. Overall, our findings for robustness are definitive: we provide positive robustness results for Saber, Kyber, and FrodoKEM, and a negative result for Classic McEliece. Our negative result stems from a striking property of KEM-DEM PKE schemes built with the Classic McEliece KEM: for any message 'm', we can construct a single hybrid ciphertext 'c' which decrypts to the chosen 'm' under any Classic McEliece private key. Our findings for anonymity are more mixed: we identify barriers to proving anonymity for Saber, Kyber, and Classic McEliece. We also found that in the case of Saber and Kyber, these barriers lead to issues with their IND-CCA security claims. We have worked with the Saber and Kyber teams to fix these issues, but they remain unresolved. On the positive side, we were able to prove anonymity for FrodoKEM and a variant of Saber introduced by D'Anvers et al. (AFRICACRYPT 2018). Our analyses of these two schemes also identified technical gaps in their IND-CCA security claims, but we were able to fix them.

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 long-term key for generating session tickets gets compromised. This extends and corrects a recent work of Aviram, Gellert, and Jager (Journal of Cryptology, 2021). Second, we show how to use PKW to build a protected file storage system with file shredding, wherein a client can outsource encrypted files to a potentially malicious or corrupted cloud server whilst achieving strong forward-security guarantees, relying only on local key updates.

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 positive side, we formally and in detail model a slight variant of Telegram's ``record protocol'' and prove that it achieves security in a suitable secure channel model, albeit under unstudied assumptions. In this abstract we focus on the negative results. First, we motivate our modelling deviation from MTProto by giving two attacks -- one of practical, one of theoretical interest -- against MTProto without our modifications. We then also give a third attack exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of salt and id fields that are established by Telegram's key exchange protocol. To recover these, we chain the third attack with a fourth one against the implementation of the key exchange protocol on Telegram's servers. Our results provide the first comprehensive study of MTProto's use of symmetric cryptography.

Cryptographic agility frameworks enable the transition from one cryptographic algorithm or implementation to another in a computing system or application. As quantum safe algorithms (PQC) steadily progress through the NIST-led standardization process, we ask whether the research community has done enough to map and expand cryptographic deployment paradigms, most developed decades ago, to modern compute infrastructures. The problem is acutely felt by the operators of such infrastructures where applications and systems are highly distributed, involve many software and hardware components, bring together multiple stakeholders, and require policy-driven control. Since the security, performance, and manageability of cryptography matters, we contend that these are not extraneous concerns that lack connection to the applied research community.

This talk introduces a new direction of research for searchable symmetric encryption (SSE). In contrast to previous research in SSE which focussed only on leakage from the encrypted index component of SSE, we consider the system-wide security of SSE schemes, encompassing both encrypted indices and encrypted documents. The SWiSSSE scheme that we present provably meets a strong, system-side security definition; our proof is complemented by cryptanalysis showing that the residual leakage does not render SWiSSSE vulnerable to known attacks. We believe that by taking a system-wide view of security for SSE, we can provide greater confidence to practitioners considering deployment of SSE schemes.

We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ DDH assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ κ -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ e : G κ ⟶ G T for prime-order groups $${\mathbb {G}}$$ G and $${\mathbb {G}}_T$$ G T . To establish the hardness of the $$\kappa $$ κ -linear $${\text {DDH}} $$ DDH problem, we rely on the existence of a base group for which the $$\kappa $$ κ -strong $${\text {DDH}} $$ DDH assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ e : G 1 × ⋯ × G κ ⟶ G T for a collection of $$\kappa +1$$ κ + 1 prime-order groups $${\mathbb {G}}_i$$ G i and $${\mathbb {G}}_T$$ G T , and relies only on the 1-strong $${\text {DDH}} $$ DDH assumption in its base group. In both constructions, the linearity $$\kappa $$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ Z N + . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

Boldyreva et al. (Eurocrypt 2012) defined a fine-grained security model capturing ciphertext fragmentation attacks against symmetric encryption schemes. The model was extended by Albrecht et al. (CCS 2016) to include an integrity notion. The extended security model encompasses important security goals of SSH that go beyond confidentiality and integrity to include length hiding and denial-of-service resistance properties. Boldyreva et al. also defined and analysed the InterMAC scheme, while Albrecht et al. showed that InterMAC satisfies stronger security notions than all currently available SSH encryption schemes. In this work, we take the InterMAC scheme and make it fully ready for use in practice. This involves several steps. First, we modify the InterMAC scheme to support encryption of arbitrary length plaintexts and we replace the use of Encrypt-then-MAC in InterMAC with modern noncebased authenticated encryption. Second, we describe a reference implementation of the modified InterMAC scheme in the form of the library libInterMAC. We give a performance analysis of libInterMAC. Third, to test the practical performance of libInterMAC, we implement several InterMAC-based encryption schemes in OpenSSH and carry out a performance analysis for the use-case of file transfer using SCP. We measure the data throughput and the data overhead of using InterMAC-based schemes compared to existing schemes in OpenSSH. Our analysis shows that, for some network set-ups, using InterMAC-based schemes in OpenSSH only moderately affects performance whilst providing stronger security guarantees compared to existing schemes.

We consider the problem of constructing Diffie-Hellman (DH) parameters which pass standard approaches to parameter validation but for which the Discrete Logarithm Problem (DLP) is relatively easy to solve. We consider both the finite field setting and the elliptic curve setting.For finite fields, we show how to construct DH parameters (p, q, g) for the safe prime setting in which $$p=2q+1$$ is prime, q is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and g is of order q mod p. The construction involves modifying and combining known methods for obtaining Carmichael numbers. Concretely, we provide an example with 1024-bit p which passes OpenSSL’s Diffie-Hellman validation procedure with probability $$2^{-24}$$ (for versions of OpenSSL prior to 1.1.0i). Here, the largest factor of q has 121 bits, meaning that the DLP can be solved with about $$2^{64}$$ effort using the Pohlig-Hellman algorithm. We go on to explain how this parameter set can be used to mount offline dictionary attacks against PAKE protocols. In the elliptic curve case, we use an algorithm of Bröker and Stevenhagen to construct an elliptic curve E over a finite field $${\mathbb {F}}_p$$ having a specified number of points n. We are able to select n of the form $$h\cdot q$$ such that h is a small co-factor, q is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and E has a point of order q. Concretely, we provide example curves at the 128-bit security level with $$h=1$$ , where q passes a single random-base Miller-Rabin primality test with probability 1/4 and where the elliptic curve DLP can be solved with about $$2^{44}$$ effort. Alternatively, we can pass the test with probability 1/8 and solve the elliptic curve DLP with about $$2^{35.5}$$ effort. These ECDH parameter sets lead to similar attacks on PAKE protocols relying on elliptic curves.Our work shows the importance of performing proper (EC)DH parameter validation in cryptographic implementations and/or the wisdom of relying on standardised parameter sets of known provenance.

Statistical analysis of ciphertexts has been recently used to carry out devastating inference attacks on deterministic encryption (Naveed, Kamara, and Wright, CCS 2015), order-preserving/revealing encryption (Grubbs et al., S&P 2017), and searchable encryption (Pouliot and Wright, CCS 2016). At the heart of these inference attacks is classical frequency analysis. In this paper, we propose and evaluate another classical technique, homophonic encoding, as a means to combat these attacks. We introduce and develop the concept of frequency-smoothing encryption (FSE) which provably prevents inference attacks in the snapshot attack model, wherein the adversary obtains a static snapshot of the encrypted data, while preserving the ability to efficiently and privately make point queries. We provide provably secure constructions for FSE schemes, and we empirically assess their security for concrete parameters by evaluating them against real data. We show that frequency analysis attacks (and optimal generalisations of them for the FSE setting) no longer succeed.

In this work, we consider the ring- and module- variants of the LWE problem and investigate cold boot attacks on cryptographic schemes based on these problems, wherein an attacker is faced with the problem of recovering a scheme’s secret key from a noisy version of that key. The leakage resilience of cryptography based on the learning with errors (LWE) problem has been studied before, but there are only limited results considering the parameters observed in cold boot attack scenarios. There are two main encodings for storing ring- and module-LWE keys, and, as we show, the performance of cold boot attacks can be highly sensitive to the exact encoding used. The first encoding stores polynomial coefficients directly in memory. The second encoding performs a number theoretic transform (NTT) before storing the key, a commonly used method leading to more efficient implementations. We first give estimates for a cold boot attack complexity on the first encoding method based on standard algorithms; this analysis confirms that this encoding method is vulnerable to cold boot attacks only at very low bit-flip rates. We then show that, for the second encoding method, the structure introduced by using an NTT is exploitable in the cold boot setting: we develop a bespoke attack strategy that is much cheaper than our estimates for the first encoding when considering module-LWE keys. For example, at a 1% bit-flip rate (which corresponds roughly to what can be achieved in practice for cold boot attacks when applying cooling), a cold boot attack on Kyber KEM parameters has a cost of 243 operations when the second, NTT-based encoding is used for key storage, compared to 270 operations with the first encoding. On the other hand, in the case of the ring-LWE-based KEM, New Hope, the cold boot attack complexities are similar for both encoding methods.