MPI-SP researchers publish 10 papers at USENIX

Scientists at MPI-SP published 10 research papers at the 35th USENIX Security Symposium, which will take place this week in Baltimore

Orbit: Optimizing Rescale and Bootstrap Placement with Integer Linear Programming Techniques for Secure Inference

Authors: Zikai Zhou, William Seo, Edward Chen, Alex Ozdemir, Fraser Brown, Wenting Zheng

Abstract: Fully Homomorphic Encryption (FHE) allows computation on encrypted data without decrypting it. In theory, FHE makes privacy-preserving machine learning possible. In practice, however, it remains impractically slow for real workloads. A major source of slowdown is bootstrap operations; in CKKS, a popular FHE scheme for tensor workloads, the slowdown is compounded by scale management and rescale operations.

FHE compilers for machine learning inference aim to make bootstrap placement and scale management efficient and easy by compiling high-level tensor programs into optimized CKKS computations. Unfortunately, existing approaches miss crucial optimization opportunities because they overlook a key property of CKKS programs: bootstrap and rescale placement are fundamentally coupled through the level budget. In this paper, we present Orbit, an FHE compiler that jointly optimizes bootstrap and rescale placement through a novel Integer Linear Programming (ILP) formulation that reasons about both ciphertext level and scale constraints. To make this formulation tractable for structured tensor workloads, particularly convolutional neural networks, we introduce three techniques that reduce ILP complexity while preserving optimality. Across five workloads and multiple cryptographic parameter configurations, Orbit achieves a geometric mean speedup of 19% over DaCapo, 73% over Orion, and 52% over ReSBM, keeps compilation under 6 minutes, and retains model accuracy within 0.3% of plaintext execution.

Original publication:https://www.usenix.org/conference/usenixsecurity26/presentation/zhou

Principled Design of Indexing Functions for Memory Coloring

Authors: Stephan Dübler, Jana Hofmann, Boris Köpf, Stavros Volos

Abstract: On shared multi-core CPUs, memory coloring achieves microarchitectural isolation by partitioning resources between trust domains. Previous work has shown that memory coloring can, in principle, be used to isolate multiple components simultaneously, e.g., both the last-level (L3) cache and DRAM. The number of colors obtained by these methods depends on the algebraic properties of the indexing functions, though, and today's off-the-shelf CPU designs are often not suited for multi-component memory coloring. 

We develop algorithms to automatically synthesize indexing functions that guarantee a minimum number of colors. Given a set of typical workloads and some context on the CPU design, our algorithms compute a new linear indexing function that supports the requested number of colors while maximizing the performance on the workloads. Our approach is based on the observation that the number of colors depends on the overlap of the algebraic kernels of the involved indexing functions. Building on this observation, we translate the requirements that the CPU design imposes on the function into algebraic constraints that our algorithms enforce. 

In a case study on a 16-core server-class CPU, we show that our framework yields a coloring scheme that partitions the L3 cache and DRAM banks, increasing the number of colors from 1 to 16 while incurring less than 2.5% performance overhead, on average across SPEC and PARSEC benchmarks.

Original publication:https://www.usenix.org/conference/usenixsecurity26/presentation/duebler

FLOSS: Fast Linear Online Secret-Shared Shuffling

Authors: Ian Chang, Sela Navot, Alex Ozdemir, Nirvan Tyagi

Abstract: Randomly permuting secret data vectors is a core building block in many privacy-preserving protocols, including those for analytics, advertising, and communication. Existing approaches either rely on computation-heavy public key cryptography and zero-knowledge proofs or scale poorly for large vectors due to use of a quasilinear-sized permutation network. This work presents a preprocessing approach to enable fast linear-time online shuffles in the malicious-secure two-party computation (2PC) setting. We propose FLOSS, a 2PC protocol for securely computing any interactive arithmetic permutation circuit, a notion we introduce to capture how higher level protocols are built on secret-shared field arithmetic and permutations. We show how secret-shared sorting (a subprotocol in data analytics) can be described as an arithmetic permutation circuit, and can thus be compiled to an efficient online 2PC protocol using FLOSS. Our implementation and evaluation confirm FLOSS performs online shuffles fast: shuffling 2^20 elements in under 500ms, greater than 800× faster than state-of-the-art alternatives.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/chang-ian

Cross-National Information Attacks: A Two-Decade Analysis of Troll Behavior in Korea

Authors: Jaehong Kim,  Hyeonseung Kim; Jiseon Kim,  Alice Oh, Thorsten Holz,  Wonjae Lee,  Meeyoung Cha

Abstract: Coordinated foreign influence operations pose a growing threat to online platforms, but detecting state-linked troll activity and tracking its evolution remain challenging. This paper presents an explainable machine learning framework for theory-guided detection and longitudinal analysis of suspected trolling within Korean online news comment sections. Our hierarchical model classifies comments along three dimensions central to influence campaigns: foreign origin, moral-emotional framing, and target country. To support explainability, it also extracts brief span-level textual evidence that provides human-interpretable rationales. We apply the approach to 112M South Korean news comments authored by 4M users over nearly 20 years, identifying 23,998 accounts exhibiting behavior consistent with coordinated manipulation. Analyzing these accounts, we find that they predominantly rely on morally condemning rhetoric rather than direct promotion of foreign-aligned narratives; this rhetoric receives significantly higher user engagement. Among the highest-engagement comments, the moral condemnation most frequently targets domestic political figures (e.g., presidents or party leaders) on both the left and the right, potentially amplifying polarization. Our framework supports transparent platform governance through explainable, evidence-based moderation. These observed rhetorical and engagement patterns can inform how platforms and observatories prioritize defenses and intervene before harmful narrative-target combinations achieve widespread reach.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/kim-jaehong

Message Injection Attacks Against Signal

Authors: Kien Tuong Truong; Noemi Terzo,  Kenneth G. Paterson

Abstract: Signal is a secure messaging app offering end-to-end security for pairwise and group communications. It has tens of millions of users, and has heavily influenced the design of other secure messaging apps (including WhatsApp). Signal has been heavily analysed and, as a result, is rightly regarded as setting the "gold standard" for messaging apps by the scientific community. We present two practical attacks that break the integrity properties of Signal in its advertised threat model. Each attack arises from different features of Signal that are poorly documented and have eluded formal security analyses. The first attack, affecting Android and Desktop, arises from Signal's introduction of identities based on usernames (instead of phone numbers) in early 2022. We show that the protocol for resolving identities based on usernames and on phone numbers introduced a vulnerability that allows a malicious server to inject arbitrary messages into one-to-one conversations under specific circumstances. The injection causes a user-visible alert about a change of safety numbers, but if the users compare their safety numbers, they will be correct. The second attack is even more severe. It arises from Signal's Sealed Sender (SSS) feature, designed to allow sender identities to be hidden. We show that a combination of two errors in the SSS implementation in Android allows a malicious server to inject arbitrary messages into both one-to-one and group conversations. The errors relate to missing key checks and the loss of context when cryptographic processing is distributed across multiple software components. The attack is undetectable by users and can be mounted at any time, without any preconditions. As far as we can tell, the vulnerability has been present since the introduction of SSS in 2018. We disclosed both attacks to the engineers at Signal who promptly developed and deployed patches. Beyond presenting these devastating attacks on Signal's end-to-end security guarantees, we discuss more broadly what can be learned about the challenges of deploying new security features in complex software projects.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/truong

SMASH: Scalable Maliciously Secure Hybrid Multi-party Computation Framework for Privacy-Preserving Large Language Models

Authors: Yunlv Lv, Rui Zhang, Zhiyuan Zhang, Ziyi Wan, Lanxue Zhang, Minhui Xue, Jiangtao Li, Yanan Cao

Abstract: The meteoric rise of Large Language Models (LLMs) has sparked an urgent need for privacy-preserving inference. However, existing maliciously secure multi-party computation (MPC) frameworks face a "performance collapse" when scaling to large models, primarily due to the quadratic (O(n2)) communication overhead of nonlinear operators and expensive share conversions. This paper presents SMASH, a highly scalable, maliciously secure hybrid MPC framework that shatters these bottlenecks. SMASH introduces a novel DFT-based rotation technique and a lightweight zero-knowledge proof of knowledge (ZKPoK) construction to evaluate nonlinear operations. For the first time, this approach achieves linear communication complexity (O(n)) relative to the party count, independent of function complexity. Furthermore, SMASH provides a suite of high-efficiency conversion protocols (A2L/L2A and SM-LUT-based A2B/B2A) that bridge arithmetic and Boolean domains without relying on costly cryptographic primitives. Extensive benchmarks demonstrate that SMASH outperforms state-of-the-art frameworks (e.g., MP-SPDZ, MD-ML) by up to 18.9× in runtime and achieves a communication reduction of up to 103×. With its constant-round online phase and low WAN sensitivity, SMASH paves the way for secure, geographically distributed LLM deployments, achieving an unprecedented balance between adversarial robustness and practical efficiency.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/lv

End-to-End Encrypted Collaborative Documents

Authors: Christian Knabenhans, Zayd Maradni, Carmela Troncoso

Abstract: Collaborative documents (e.g., Google Docs, Microsoft 365) often contain sensitive information such as personal or financial data. In this work, we extend the protection of E2EE encryption, currently (mostly) restricted to the use case of messaging, to collaborative documents. We elicit and formalize the security and functional requirements of End-to-End-Encrypted Collaborative Documents. We then put forth a generic framework to realize E2EE-CD, by combining an end-to-end encrypted asynchronous broadcast channel with any edit reconciliation mechanism which ensures globally consistent views of a document. We give formal proofs that directly relate the security of our E2EE-CD solution to the security of the underlying end-to-end encrypted communication channel. We then elicit additional deployment requirements for E2EE-CD for investigative journalists and design SignalCD, an E2EE-CD system built on top of Signal's group messaging protocol tailored for this setting. We analyze the security guarantees of SignalCD, implement a prototype, and empirically show that our solution is efficient enough to permit real-time collaboration.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/knabenhans

Shadowfax: Hybrid Security and Deniability for AKEMs

Authors: Phillip Gajland, Vincent Hwang, Jonas Janneck

Abstract: As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining classical and post-quantum assumptions. This shift often sacrifices efficiency, compactness, or even security. One such property is deniability, which enables users to plausibly deny authorship of potentially incriminating messages. While classical protocols like X3DH key agreement (used in Signal and WhatsApp) provide deniability, post-quantum protocols like PQXDH and Apple's iMessage with PQ3 do not.

This work addresses this gap by investigating how to efficiently preserve deniability in post-quantum protocols. Specifically, we propose two hybrid schemes for authenticated key encapsulation mechanisms (AKEMs). The first is a black-box construction that preserves deniability when both constituent AKEMs are deniable. The second is Shadowfax, a non-black-box AKEM that achieves hybrid security, integrating a classical non-interactive key exchange, a post-quantum key encapsulation mechanism, and a post-quantum ring signature. Shadowfax satisfies deniability in both dishonest and honest receiver settings, relying on statistical security in the former and on a single pre- or post-quantum assumption in the latter.

Finally, we provide several portable implementations of Shadowfax. When instantiated with standardised components (ML-KEM and Falcon), Shadowfax yields ciphertexts of 1728 bytes and public keys of 2036 bytes, with encapsulation and decapsulation costs of 1.8M and 0.7M cycles on an Apple M1 Pro.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/gajland

Silicon Heist: (Ransom) Attacks for Cloud FPGAs via Privilege Escalation

Authors: Simon Klix, Felix Hahn, Maik Ender, Nils Albartus, and Christof Paar; Russell Tessier

Abstract: Cloud-based FPGAs have become a billion-dollar industry, allowing users to deploy custom hardware designs with the scalability and flexibility of cloud infrastructure. Running user designs on hardware owned by the cloud service provider (CSP) introduces risks, including intentional hardware damage and Denial-of-Service (DoS) attacks against the host. To mitigate these risks, CSPs enforce security mechanisms that restrict user designs and prevent unauthorized behavior. We present a novel privilege escalation path on AMD FPGAs using (i) the Internal Configuration Access Port (ICAP) to circumvent provider defenses, (ii) incrementally escalate attacker capabilities to remote JTAG access, and (iii) investigate the resulting threat vectors.

Any typical cloud customer can maliciously acquire such ICAP access to reconfigure parts of the FPGA fabric without restrictions – re-enabling traditional cloud FPGA attacks. Through the ICAP, a user can ultimately gain remote control of the hardware's low-level JTAG interface, which enables access to the device's eFuses. This access, in turn, allows attackers to irreversibly program encryption settings, thereby disabling future reconfiguration and locking the CSPs out of their own devices. An attacker could leverage such escalated privileges for a ransomware attack in which cloud providers must pay a ransom for decryption keys to regain control of their devices – effectively introducing the first ransomware for FPGAs. Following the investigation of this novel privilege escalation path, we demonstrate its feasibility on Amazon's EC2 F1 and F2 instances and explore the impact of enabled attack vectors. We thereby expose the neglected threat of unsecured low-level hardware components in cloud environments.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/klix

OS-Sanitizer: System-wide Latent Defect Inference in Linux Applications

Authors: Addison Crump, Sahil Sihag, Florian Bauckholt, and Keno Hassler; Thorsten Holz

Abstract: Dynamic testing has historically focused on finding situations in which software does something unwanted, typically by triggering failure or undesirable states. However, such testing is often limited to finding these scenarios by example. Can we determine that software could do something unwanted by inspecting benign behavior? In this paper, we explore this question by leveraging eBPF for dynamic defect inference in Linux applications. eBPF is uniquely positioned as a system introspection tool that accrues data from both user- and kernelspace events and processes them as programs in the kernel. Our prototype, OS-Sanitizer, implements such eBPF programs using heuristics which report the suspected presence of defects in all applications across the entire system. Conceptually, OS-Sanitizer brings the idea of code smells from static testing into dynamic testing, while simultaneously profiting from the insights of runtime events. In doing so, we infer the presence of latent contextual defects in software that would only induce a failure in certain environments or are otherwise difficult to test for. We consider and evaluate the strengths and weaknesses of this approach from the perspectives of performance, complexity, maintainability, and usage, differentiating the theoretical limits of eBPF versus the specific limits of our prototype. Targeting well-known types of software defects, we were able to identify more than 40 issues (including severe vulnerabilities) in widely used applications, some of which are older than a decade and present on a majority of Linux distributions. Our findings demonstrate that dynamic defect inference is both feasible and effective, highlighting opportunities for expanding this underexplored direction in software testing.

Original publication: https://www.usenix.org/conference/usenixsecurity26/presentation/crump