International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Igors Stepanovs

Publications and invited talks

Year
Venue
Title
2025
EUROCRYPT
Analysis of the Telegram Key Exchange
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.
2025
RWC
Analyzing Chat Encryption in Group Messaging Applications
Joseph Jaeger Akshaya Kumar Igors Stepanovs
Secure group messaging applications have been widely deployed to protect the everyday conversations of billions of users worldwide. These applications use different cryptographic algorithms to provide varying privacy and authenticity guarantees. Due to their widespread use, particularly in sensitive contexts like protests and conflicts, analyzing the security of these applications has been the focus of numerous academic works. Most of these focus on analyzing the more "novel" key agreement primitive. Due to the inherent complexities, few works attempt to rigorously analyze an application as a whole, and even fewer focus on the chat encryption primitive specifically. The latter may be attributed to the assumption that, after decades of cryptographic research, encrypting conversations (using symmetric/asymmetric primitives) is well understood, rendering chat encryption a seemingly trivial or "folklore" primitive. Despite its perceived simplicity, throughout our work across two papers, we find that some widely used group messaging applications implement chat encryption insecurely, potentially exposing them to exploitable attacks. This talk highlights the importance of analyzing the compositions of symmetric encryption and digital signatures used in several group chat encryption algorithms. Isolating chat encryption allows one to systematically identify potential attacks that result from the lack of proper "binding" between the signing and encryption components. This is reflected in our analysis of chat encryption in three widely deployed group messaging applications: Keybase, MLS, and Session. While Keybase had a good intuition for combining symmetric encryption and digital signatures, their solution was brittle; its security relied on non-cryptographic elements such as message serialization formats. MLS and Session did not implement proper binding in their compositions, exposing them to attacks where a group member can impersonate another by replaying their messages. Additionally, Session is susceptible to message re-ordering attacks by non-group members such as the platform server. Independent analysis of chat encryption allowed us to narrowly target the corresponding security goals and specify a set of conditions required for proper binding between the signing and encryption components. Developers of chat encryption algorithms need only check that these conditions are met to ensure that the security goals are achieved.
2024
EUROCRYPT
Symmetric Signcryption and E2EE Messaging in Keybase
Joseph Jaeger Akshaya Kumar Igors Stepanovs
We introduce a new cryptographic primitive called symmetric signcryption, which differs from traditional signcryption because the sender and recipient share a secret key. We prove that a natural composition of symmetric encryption and signatures achieves strong notions of security against attackers that can learn and control many keys. We then identify that the core encryption algorithm of the Keybase encrypted messaging protocol can be modeled as a symmetric signcryption scheme. We prove the security of this algorithm, though our proof requires assuming non-standard, brittle security properties of the underlying primitives.
2022
RWC
Four Attacks and a Proof for Telegram
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.
2020
EUROCRYPT
Security under Message-Derived Keys: Signcryption in iMessage 📺
Mihir Bellare Igors Stepanovs
At the core of Apple's iMessage is a SignCryption scheme that involves symmetric encryption of a message under a key that is derived from the message itself. To capture this, we formalize a primitive we call Encryption under Message-Derived Keys (EMDK). We prove security of the EMDK scheme underlying iMessage. We use this to prove security of the SignCryption scheme itself, with respect to definitions of SignCryption we give that enhance prior ones to cover issues peculiar to messaging protocols. Our provable-security results are quantitative, and we discuss the practical implications for iMessage.
2018
CRYPTO
Optimal Channel Security Against Fine-Grained State Compromise: The Safety of Messaging 📺
Joseph Jaeger Igors Stepanovs
We aim to understand the best possible security of a (bidirectional) cryptographic channel against an adversary that may arbitrarily and repeatedly learn the secret state of either communicating party. We give a formal security definition and a proven-secure construction. This construction provides better security against state compromise than the Signal Double Ratchet Algorithm or any other known channel construction. To facilitate this we define and construct new forms of public-key encryption and digital signatures that update their keys over time.
2017
CRYPTO
2016
EUROCRYPT
2016
TCC
2016
TCC
2014
ASIACRYPT

Service

PKC 2022 Program committee