Daniel Collins's Avatar

Daniel Collins

@dcol.bsky.social

Postdoc at Texas A&M, previously Purdue/Georgia Tech, PhD from EPFL in cryptography https://dcol.me

166 Followers  |  112 Following  |  1 Posts  |  Joined: 03.08.2023  |  1.66

Latest posts by dcol.bsky.social on Bluesky

Abstract. The Nintendo DSi is a handheld gaming console released by Nintendo in 2008. In Nintendo’s line-up the DSi served as a successor to the DS and was later succeeded by the 3DS. The security systems of both the DS and 3DS have been fully analysed and defeated. However, for over 14 years the security systems of the Nintendo DSi remained standing and had not been fully analysed. To that end this work builds on existing research and demonstrates the use of a second-order fault injection attack to extract the ROM bootloaders stored in the custom system-on-chip used by the DSi. We analyse the effect of the induced fault and compare it to theoretical fault models. Additionally, we present a security analysis of the extracted ROM bootloaders and develop a modchip using cheap off-the-shelf components. The modchip allows to jailbreak the console, but more importantly allows to resurrect consoles previously assumed irreparable.

Abstract. The Nintendo DSi is a handheld gaming console released by Nintendo in 2008. In Nintendo’s line-up the DSi served as a successor to the DS and was later succeeded by the 3DS. The security systems of both the DS and 3DS have been fully analysed and defeated. However, for over 14 years the security systems of the Nintendo DSi remained standing and had not been fully analysed. To that end this work builds on existing research and demonstrates the use of a second-order fault injection attack to extract the ROM bootloaders stored in the custom system-on-chip used by the DSi. We analyse the effect of the induced fault and compare it to theoretical fault models. Additionally, we present a security analysis of the extracted ROM bootloaders and develop a modchip using cheap off-the-shelf components. The modchip allows to jailbreak the console, but more importantly allows to resurrect consoles previously assumed irreparable.

An in-depth security evaluation of the Nintendo DSi gaming console (pcy Sluys, Lennert Wouters, Benedikt Gierlichs, Ingrid Verbauwhede) ia.cr/2025/568

31.03.2025 00:50 — 👍 7    🔁 2    💬 0    📌 0
Preview
7 PhD positions (m/f/d) (salary level 13 TV-L) in Computer Science (full time) and 3 PhD position (m/f/d) (salary level 13 TV-L) in Law (part time, 75%)

Join our Applied Crypto group at FAU in Nürnberg as a PhD student or spread the word: we're hiring.

Our work covers many topics in real-world crypto, especially provable security and privacy of modern messaging protocols 🔐✉️

www.jobs.fau.de/jobs/7-phd-p...

05.03.2025 21:59 — 👍 9    🔁 12    💬 0    📌 0
Abstract. Ratcheted key exchange (RKE) is at the heart of modern secure messaging, enabling protocol participants to continuously update their secret material to protect against full state exposure through forward security (protecting past secrets and messages) and post-compromise security (recovering from compromise). However, many practical attacks only provide the adversary with partial access to a party’s secret state, an attack vector studied under the umbrella of leakage resilience. Existing models of RKE provide suboptimal guarantees under partial leakage due to inherent limitations in security under full state exposure. In this work, we initiate the study of leakage-resilient ratcheted key exchange that provides typical guarantees under full state exposure and additional guarantees under partial state exposure between ratchets of the protocol. We consider unidirectional ratcheted key exchange (URKE) where one party acts as the sender and the other as receiver. Building on the notions introduced by Balli, Rösler and Vaudenay (ASIACRYPT 2020), we formalise a key indistinguishability game under randomness manipulation and bounded leakage (KIND), which in particular enables the adversary to continually leak a bounded amount of the sender’s state between honest send calls. We construct a corresponding protocol from a key-updatable key encapsulation mechanism (kuKEM) and a leakage-resilient one-time MAC. By instantiating this MAC in the random oracle model (ROM), results from Balli, Rösler and Vaudenay imply that in the ROM, kuKEM and KIND-secure URKE are equivalent, i.e., can be built from each other. To address the strong limitations that key indistinguishability imposes on the adversary, we formalise a one-wayness game that also permits leakage on the receiver. We then propose a corresponding construction from leakage-resilient kuKEM, which we introduce, and a leakage-resilient one-time MAC. We further show that leakage-resilient kuKEM and one-way-secure URKE are equivalent in the ROM, highlighting the cost that strong one-way security entails. Our work opens exciting directions for developing leakage-resilient messaging protocols.

Abstract. Ratcheted key exchange (RKE) is at the heart of modern secure messaging, enabling protocol participants to continuously update their secret material to protect against full state exposure through forward security (protecting past secrets and messages) and post-compromise security (recovering from compromise). However, many practical attacks only provide the adversary with partial access to a party’s secret state, an attack vector studied under the umbrella of leakage resilience. Existing models of RKE provide suboptimal guarantees under partial leakage due to inherent limitations in security under full state exposure. In this work, we initiate the study of leakage-resilient ratcheted key exchange that provides typical guarantees under full state exposure and additional guarantees under partial state exposure between ratchets of the protocol. We consider unidirectional ratcheted key exchange (URKE) where one party acts as the sender and the other as receiver. Building on the notions introduced by Balli, Rösler and Vaudenay (ASIACRYPT 2020), we formalise a key indistinguishability game under randomness manipulation and bounded leakage (KIND), which in particular enables the adversary to continually leak a bounded amount of the sender’s state between honest send calls. We construct a corresponding protocol from a key-updatable key encapsulation mechanism (kuKEM) and a leakage-resilient one-time MAC. By instantiating this MAC in the random oracle model (ROM), results from Balli, Rösler and Vaudenay imply that in the ROM, kuKEM and KIND-secure URKE are equivalent, i.e., can be built from each other. To address the strong limitations that key indistinguishability imposes on the adversary, we formalise a one-wayness game that also permits leakage on the receiver. We then propose a corresponding construction from leakage-resilient kuKEM, which we introduce, and a leakage-resilient one-time MAC. We further show that leakage-resilient kuKEM and one-way-secure URKE are equivalent in the ROM, highlighting the cost that strong one-way security entails. Our work opens exciting directions for developing leakage-resilient messaging protocols.

Image showing part 2 of abstract.

Image showing part 2 of abstract.

Image showing part 3 of abstract.

Image showing part 3 of abstract.

Towards Leakage-Resilient Ratcheted Key Exchange (Daniel Collins, Simone Colombo, Sina Schaeffler) ia.cr/2025/332

25.02.2025 15:11 — 👍 1    🔁 1    💬 0    📌 0
Abstract. Secure Messaging apps have seen growing adoption, and are used by billions of people daily. However, due to imminent threat of a “Harvest Now, Decrypt Later” attack, secure messaging providers must react know in order to make their protocols hybrid-secure: at least as secure as before, but now also post-quantum (PQ) secure. Since many of these apps are internally based on the famous Signal’s Double-Ratchet (DR) protocol, making Signal hybrid-secure is of great importance. In fact, Signal and Apple already put in production various Signal-based variants with certain levels of hybrid security: PQXDH (only on the initial handshake), and PQ3 (on the entire protocol), by adding a PQ-ratchet to the DR protocol. Unfortunately, due to the large communication overheads of the Kyber scheme used by PQ3, real-world PQ3 performs this PQ-ratchet approximately every 50 messages. As we observe, the effectiveness of this amortization, while reasonable in the best-case communication scenario, quickly deteriorates in other still realistic scenarios; causing many consecutive (rather than 1 in 50) re-transmissions of the same Kyber public keys and ciphertexts (of combined size 2272 bytes!). In this work we design a new Signal-based, hybrid-secure secure messaging protocol, which significantly reduces the communication complexity of PQ3. We call our protocol “the Triple Ratchet” (TR) protocol. First, TR uses em erasure codes to make the communication inside the PQ-ratchet provably balanced. This results in much better worst-case communication guarantees of TR, as compared to PQ3. Second, we design a novel “variant” of Kyber, called Katana, with significantly smaller combined length of ciphertext and public key (which is the relevant efficiency measure for “PQ-secure ratchets”). For 192 bits of security, Katana improves this key efficiency measure by over 37%: from 2272 to 1416 bytes. In doing so, we identify a critical security flaw in prior suggestions to optimize communication complexity of lattice-based PQ-ratchets, and fix this flaw with a novel proof relying on the recently introduced hint MLWE assumption. During the development of this work we have been in discussion with the Signal team, and they are actively evaluating bringing a variant of it into production in a future iteration of the Signal protocol.

Abstract. Secure Messaging apps have seen growing adoption, and are used by billions of people daily. However, due to imminent threat of a “Harvest Now, Decrypt Later” attack, secure messaging providers must react know in order to make their protocols hybrid-secure: at least as secure as before, but now also post-quantum (PQ) secure. Since many of these apps are internally based on the famous Signal’s Double-Ratchet (DR) protocol, making Signal hybrid-secure is of great importance. In fact, Signal and Apple already put in production various Signal-based variants with certain levels of hybrid security: PQXDH (only on the initial handshake), and PQ3 (on the entire protocol), by adding a PQ-ratchet to the DR protocol. Unfortunately, due to the large communication overheads of the Kyber scheme used by PQ3, real-world PQ3 performs this PQ-ratchet approximately every 50 messages. As we observe, the effectiveness of this amortization, while reasonable in the best-case communication scenario, quickly deteriorates in other still realistic scenarios; causing many consecutive (rather than 1 in 50) re-transmissions of the same Kyber public keys and ciphertexts (of combined size 2272 bytes!). In this work we design a new Signal-based, hybrid-secure secure messaging protocol, which significantly reduces the communication complexity of PQ3. We call our protocol “the Triple Ratchet” (TR) protocol. First, TR uses em erasure codes to make the communication inside the PQ-ratchet provably balanced. This results in much better worst-case communication guarantees of TR, as compared to PQ3. Second, we design a novel “variant” of Kyber, called Katana, with significantly smaller combined length of ciphertext and public key (which is the relevant efficiency measure for “PQ-secure ratchets”). For 192 bits of security, Katana improves this key efficiency measure by over 37%: from 2272 to 1416 bytes. In doing so, we identify a critical security flaw in prior suggestions to optimize communication complexity of lattice-based PQ-ratchets, and fix this flaw with a novel proof relying on the recently introduced hint MLWE assumption. During the development of this work we have been in discussion with the Signal team, and they are actively evaluating bringing a variant of it into production in a future iteration of the Signal protocol.

Image showing part 2 of abstract.

Image showing part 2 of abstract.

Image showing part 3 of abstract.

Image showing part 3 of abstract.

Triple Ratchet: A Bandwidth Efficient Hybrid-Secure Signal Protocol (Yevgeniy Dodis, Daniel Jost, Shuichi Katsumata, Thomas Prest, Rolfe Schmidt) ia.cr/2025/078

18.01.2025 01:10 — 👍 8    🔁 3    💬 0    📌 1

👋 :)

20.11.2024 03:34 — 👍 5    🔁 0    💬 0    📌 0
Abstract. The parallel broadcast (PBC) problem generalises the classic Byzantine broadcast problem to the setting where all n nodes broadcast a message and deliver O(n) messages. PBC arises naturally in many settings including multi-party computation. Recently, Tsimos, Loss, and Papamanthou (CRYPTO 2022) showed PBC protocols with improved communication, against an adaptive adversary who can corrupt all but a constant fraction ϵ of nodes (i.e., f < (1−ϵ)n). However, their study is limited to single-bit messages, and their protocols have large polynomial overhead in the security parameter κ: their TrustedPBC protocol achieves Õ(n²κ⁴) communication and O(κlogn) rounds. Since these factors of κ are in practice often close (or at least polynomially related) to n, they add a significant overhead. In this work, we propose three parallel broadcast protocols for L-bit messages, for any size L, that significantly improve the communication efficiency of the state-of-the-art. We first propose a new extension protocol that uses a κ-bit PBC as a black box and achieves i) communication complexity of O(Ln²+𝒫(κ)), where 𝒫(κ) is the communication complexity of the κ-bit PBC, and ii) round complexity same as the κ-bit PBC. By comparison, the state-of-the-art extension protocol for regular broadcast (Nayak et al., DISC 2020) incurs O(n) additional rounds of communication. Next, we propose a protocol that is secure against a static adversary, for κ-bit messages with O(n²κ^(1 + K)+nκ³+κ⁴) communication and O(κ) round complexity, where K is an arbitrarily small constant such that 0 < K < 1. Finally, we propose an adaptively-secure protocol for κ-bit messages with Õ(n²κ²+nκ³) communication overhead and O(κlogn) round complexity by modifying and improving the next-best protocol TrustedPBC in several key ways. Notably, our latter two protocols are Õ(κ^(2 − K)) and O(κ²) times more communication-efficient, respectively, than the state-of-the-art protocols while achieving the same round complexity.

Abstract. The parallel broadcast (PBC) problem generalises the classic Byzantine broadcast problem to the setting where all n nodes broadcast a message and deliver O(n) messages. PBC arises naturally in many settings including multi-party computation. Recently, Tsimos, Loss, and Papamanthou (CRYPTO 2022) showed PBC protocols with improved communication, against an adaptive adversary who can corrupt all but a constant fraction ϵ of nodes (i.e., f < (1−ϵ)n). However, their study is limited to single-bit messages, and their protocols have large polynomial overhead in the security parameter κ: their TrustedPBC protocol achieves Õ(n²κ⁴) communication and O(κlogn) rounds. Since these factors of κ are in practice often close (or at least polynomially related) to n, they add a significant overhead. In this work, we propose three parallel broadcast protocols for L-bit messages, for any size L, that significantly improve the communication efficiency of the state-of-the-art. We first propose a new extension protocol that uses a κ-bit PBC as a black box and achieves i) communication complexity of O(Ln²+𝒫(κ)), where 𝒫(κ) is the communication complexity of the κ-bit PBC, and ii) round complexity same as the κ-bit PBC. By comparison, the state-of-the-art extension protocol for regular broadcast (Nayak et al., DISC 2020) incurs O(n) additional rounds of communication. Next, we propose a protocol that is secure against a static adversary, for κ-bit messages with O(n²κ^(1 + K)+nκ³+κ⁴) communication and O(κ) round complexity, where K is an arbitrarily small constant such that 0 < K < 1. Finally, we propose an adaptively-secure protocol for κ-bit messages with Õ(n²κ²+nκ³) communication overhead and O(κlogn) round complexity by modifying and improving the next-best protocol TrustedPBC in several key ways. Notably, our latter two protocols are Õ(κ^(2 − K)) and O(κ²) times more communication-efficient, respectively, than the state-of-the-art protocols while achieving the same round complexity.

Image showing part 2 of abstract.

Image showing part 2 of abstract.

Towards Optimal Parallel Broadcast under a Dishonest Majority (Daniel Collins, Sisi Duan, Julian Loss, Charalampos Papamanthou, Giorgos Tsimos, Haochen Wang) ia.cr/2024/974

17.06.2024 07:07 — 👍 6    🔁 1    💬 0    📌 0
Abstract. The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing post-quantum X3DH proposals use ring signatures (or equivalently a form of designated-verifier signatures) to provide authentication without compromising deniability as regular signatures would. Existing ring signature schemes, however, have some drawbacks. Notably, they are not generally proven secure in the quantum random oracle model (QROM) and so the quantum security of parameters that are proposed is unclear and likely weaker than claimed. In addition, they are generally slower than standard primitives like KEMs. In this work, we propose an efficient, deniable and post-quantum X3DH-like protocol that we call K-Waay, that does not rely on ring signatures. At its core, K-Waay uses a split-KEM, a primitive introduced by Brendel et al. [SAC 2020], to provide Diffie-Hellman-like implicit authentication and secrecy guarantees. Along the way, we revisit the formalism of Brendel et al. and identify that additional security properties are required to prove a split-KEM-based protocol secure. We instantiate split-KEM by building a protocol based on the Frodo key exchange protocol relying on the plain LWE assumption: our proofs might be of independent interest as we show it satisfies our novel unforgeability and deniability security notions. Finally, we complement our theoretical results by thoroughly benchmarking both K-Waay and existing X3DH protocols. Our results show even when using plain LWE and a conservative choice of parameters that K-Waay is significantly faster than previous work.

Abstract. The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing post-quantum X3DH proposals use ring signatures (or equivalently a form of designated-verifier signatures) to provide authentication without compromising deniability as regular signatures would. Existing ring signature schemes, however, have some drawbacks. Notably, they are not generally proven secure in the quantum random oracle model (QROM) and so the quantum security of parameters that are proposed is unclear and likely weaker than claimed. In addition, they are generally slower than standard primitives like KEMs. In this work, we propose an efficient, deniable and post-quantum X3DH-like protocol that we call K-Waay, that does not rely on ring signatures. At its core, K-Waay uses a split-KEM, a primitive introduced by Brendel et al. [SAC 2020], to provide Diffie-Hellman-like implicit authentication and secrecy guarantees. Along the way, we revisit the formalism of Brendel et al. and identify that additional security properties are required to prove a split-KEM-based protocol secure. We instantiate split-KEM by building a protocol based on the Frodo key exchange protocol relying on the plain LWE assumption: our proofs might be of independent interest as we show it satisfies our novel unforgeability and deniability security notions. Finally, we complement our theoretical results by thoroughly benchmarking both K-Waay and existing X3DH protocols. Our results show even when using plain LWE and a conservative choice of parameters that K-Waay is significantly faster than previous work.

Image showing part 2 of abstract.

Image showing part 2 of abstract.

K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures (Daniel Collins, Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, Serge Vaudenay) ia.cr/2024/120

29.01.2024 09:29 — 👍 4    🔁 2    💬 0    📌 0
Abstract. Developing end-to-end encrypted instant messaging solutions for group conversations is an ongoing challenge that has garnered significant attention from practitioners and the cryptographic community alike. Notably, industry-leading messaging apps such as WhatsApp and Signal Messenger have adopted the Sender Keys protocol, where each group member shares their own symmetric encryption key with others. Despite its widespread adoption, Sender Keys has never been formally modelled in the cryptographic literature, raising the following natural question: What can be proven about the security of the Sender Keys protocol, and how can we practically mitigate its shortcomings? In addressing this question, we first introduce a novel security model to suit protocols like Sender Keys, deviating from conventional group key agreement-based abstractions. Our framework allows for a natural integration of two-party messaging within group messaging sessions that may be of independent interest. Leveraging this framework, we conduct the first formal analysis of the Sender Keys protocol, and prove it satisfies a weak notion of security. Towards improving security, we propose a series of efficient modifications to Sender Keys without imposing significant performance overhead. We combine these refinements into a new protocol that we call Sender Keys+, which may be of interest both in theory and practice.

Abstract. Developing end-to-end encrypted instant messaging solutions for group conversations is an ongoing challenge that has garnered significant attention from practitioners and the cryptographic community alike. Notably, industry-leading messaging apps such as WhatsApp and Signal Messenger have adopted the Sender Keys protocol, where each group member shares their own symmetric encryption key with others. Despite its widespread adoption, Sender Keys has never been formally modelled in the cryptographic literature, raising the following natural question: What can be proven about the security of the Sender Keys protocol, and how can we practically mitigate its shortcomings? In addressing this question, we first introduce a novel security model to suit protocols like Sender Keys, deviating from conventional group key agreement-based abstractions. Our framework allows for a natural integration of two-party messaging within group messaging sessions that may be of independent interest. Leveraging this framework, we conduct the first formal analysis of the Sender Keys protocol, and prove it satisfies a weak notion of security. Towards improving security, we propose a series of efficient modifications to Sender Keys without imposing significant performance overhead. We combine these refinements into a new protocol that we call Sender Keys+, which may be of interest both in theory and practice.

Image showing part 2 of abstract.

Image showing part 2 of abstract.

WhatsUpp with Sender Keys? Analysis, Improvements and Security Proofs (David Balbás, Daniel Collins, Phillip Gajland) ia.cr/2023/1385

28.09.2023 12:13 — 👍 1    🔁 1    💬 0    📌 0
Post image

Last talk of the session: "On Active Attack Detection in Messaging with Immediate Decryption"

22.08.2023 00:37 — 👍 1    🔁 2    💬 1    📌 0
Post image

First Bluesky handle I've seen in a slide (albeit abbreviated). Hi @dcol.bsky.social!

22.08.2023 00:57 — 👍 4    🔁 2    💬 1    📌 0

@dcol is following 20 prominent accounts