CS Paper Radar

DM-RSA-OAEP: Formal Treatment of a Dual-Modulus Fault-Detection Countermeasure Based on Physical Diversity

Ramamonjy Andriamifidisoa, Rufine Marius Lalasoa

cs.CR cs.IT ·submitted 2026-10-19 16:03 UTC · v1
theoryunusual

Abstract

We revisit DM-RSA, an RSA variant that uses two independent moduli, whose original version was broken by Håstad's attack and contained an incorrect compromise-tolerance claim. We give a formal treatment of its repaired variant, DM-RSA-OAEP: (i) a complete IND-CCA2 security proof in the random-oracle model via a two-step hybrid argument, upper-bounding the security of the scheme by that of the weaker underlying RSA-OAEP instance, with an explicit simulation loss; (ii) a fault-detection theorem in an explicit adversary model that covers computation, key, and verification faults, including safe-error attacks, under a clearly stated physical-diversity assumption; (iii) an explicit analysis of why the countermeasure degrades to uselessness when the diversity assumption is violated (common-mode faults on a single chip). We position the scheme against the countermeasure landscape and against the broken dual-modulus literature. The contribution is deliberately framed as a fault countermeasure with a provable detection guarantee, not as a computationally stronger RSA. We conclude with a concrete instantiation and a detailed measurement protocol.

Comment
9 pages

Closest papers

Nearest neighbours by meaning across the whole index.

From if to Oops: Turning a conditional into a key-recovery oracle

cs.CR ·2026-10-29 ·Gustavo Banegas, Nia Dimitrova, Monika Trimoska
position similarity 0.61
Abstract

Deterministic variants of CSIDH remove randomness from the group action, either through implementation techniques or, as in Houben's deterministic CSIDH and OSIDH-LD, by design. Since earlier fault attacks on CSIDH mostly target random point sampling, determinism seems to close that avenue. We show that it opens another: every secret-dependent step occurs at a fixed, public point of every execution, so an attacker can fault the same step repeatedly. Our attack forces the mask that selects which of two lanes computes the next isogeny to zero, for example by skipping one instruction. Whether the output changes reveals whether a secret exponent reaches a chosen threshold, and a binary search over these thresholds recovers the full key with one fault per execution: at most 297 oracle queries for OSIDH-LD and 222 for deterministic CSIDH with CSIDH-512-sized keys. We recover full OSIDH-LD keys in a software fault simulation of the reference implementation, and show on a ChipWhisperer-Lite that the targeted instruction is skipped with probability at least 0.94 at an isolated fault position. Finally, we argue that fault resistance requires giving up determinism, and propose countermeasures relying on randomization.

0.37

Keel: A Verified In-Kernel Proof Checker for Proof Carrying BPF

cs.PL ·2026-11-08 ·Yalu Cai, Tung-Che Chang, Santosh Nagarakatte
theory similarity 0.56
Abstract · 66 pages

Recent systems such as the eBPF Certificate Framework (BCF) and Proof-Carrying BPF address the imprecision in the Linux eBPF verifier with proof-carrying code. When the verifier's abstract domains cannot prove a safety condition, an in-kernel proof checker checks an untrusted user-space refutation proof. A single bug in this checker can compromise the security of the entire kernel. While formalizing BCF's in-kernel checker, we discovered 13 bugs such as unsound rewrite rules, silently unchecked proof steps, and memory safety errors. We demonstrate that forged certificates can trick the kernel to accept arbitrary unsafe eBPF programs. To address this problem, we propose Keel, a formally verified in-kernel proof checker for the Linux eBPF verifier. First, we specify the checker as a pure functional program in Lean and prove its soundness against bit-vector semantics. We decouple the steps of the proof certificate checker from the mathematical rewrite rules, which enables us to extend the rewrite rules without the need to change the checker. Second, we implement the checker in EmbC, a deeply embedded C fragment, and prove that our C implementation refines the functional specification without undefined behavior or memory leaks. Third, using an amortized potential argument, we prove linear time and memory bounds for the C checker. Keel is correct-by-construction while also being faster than the BCF checker inside the kernel, 1.3X in total and 2.0X on the slowest 1.4% of certificates.

0.14

Generator-Independent Runtime Assurance under Partial Observation

cs.AI ·2026-09-05 ·Guangxi Wan, Yongbo Xie, Yuqi Liu, Qingwei Dong, Qingxin Li +2 more
theory similarity 0.56
Abstract

Proposal-based controllers---learned policies, language-model planners, and other black-box \emph{generators}---are increasingly deployed behind runtime verification gates. We ask when the closed-loop safety guarantee decouples from the generator. The prevailing per-candidate certification pattern does not compose: under retry or best-of-$k$ selection a per-candidate false-admission level $α$ can inflate to $1-(1-α)^{k}$. Our main theorem shows that \emph{simultaneous setwise soundness}---certifying a set of admissible proposals containing no nonviable action---is necessary and sufficient for generator-independent \emph{admission soundness}, the worst case over all generators of executing a nonviable proposal equalling the probability of setwise failure; together with a design-time certificate and a no-bypass rule it is sufficient for \emph{contract safety}, with violation bound $Γ+\sum_t\varepsilon_t+η$ invariant under arbitrary, even adversarial, replacement of the generator. A second theorem bounds every admission mechanism under partial observation: for a fixed probing and admission policy, if two state hypotheses whose information laws lie within total-variation distance $δ$ require different safe decisions, then $\abar+β+δ\ge1$. A sequential risk ledger makes the guarantee implementable with time-uniform confidence tubes, and shows that deterministic admission computations concentrate all statistical risk in state estimation. Simplex-style runtime assurance and control-barrier-function filtering are recovered as degenerate cases.

0.32

A Bleichenbacher bit-by-bit oracle attack from partial message knowledge

cs.CR ·2026-11-15 ·Juan Carlos García Escartín
similarity 0.55
Abstract · Comments welcome

Oracle attacks show the importance of a correct implementation of cryptographic standards when translated into code. A notable example is the Bleichenbacher attack on RSA with PKCS#1 v1.5 padding and all the improvements that have been suggested over the decades. This paper shows how an attacker knowing a few least significant bytes of an RSA message can take advantage of a server with an oracle side-channel to decrypt the full message bit by bit. We will consider two oracles that can be tested with chosen ciphertexts: one revealing whether the decrypted message starts with the 00 02 bytes and a second one revealing if the decrypted message is fully PKCS compliant. For an attacker knowing the three least significant bytes of the message, the first oracle provides an attack where one oracle call gives the next least significant bit of the message and the second an attack which requires, with high probability, a small constant number of oracle calls to the oracle, with a constant which depends on the length of the message and the desired probability of success. The attack divides the message bits into two sections, one with the known part and one with the unknown part, and then chooses transformations that will keep the unknown part, except for the last unknown bit, orders of magnitude below the integer coming from the known part. The resulting string either gives a valid padding or not depending on the value of the unknown bit. The attacker can minimize the number of oracle calls at the cost of some local computation. Finally, the same method is adapted to show how it can also be used to extract the few least significant bytes of the message with an increased cost where the main complexity is finding a second valid message with a correct padding starting from the original captured ciphertext.

0.37

LLM-Assisted Automatic Security Proofs for Cryptographic Protocols: How Far Are We?

cs.CR cs.SE ·2026-09-28 ·Tianjian Liu, Shicheng Feng, Jin'ao Shang, Xiaoting Lyu, Bin Wang +3 more
similarity 0.54
Abstract · 12 pages, 12 figures

Large language models (LLMs) have shown strong potential for assisting software and security analysis tasks, yet their effectiveness in cryptographic symbolic protocol verification remains insufficiently understood. In this paper, we conduct the first systematic evaluation of the capability of state-of-the-art LLMs in cryptographic symbolic protocol verification. To quantify this capability, we propose \textsc{CRoST} (Coverage Rate of Solve Tree), a proof-based metric derived from the verifier's proof skeleton that measures the similarity between generated lemmas and reference lemmas. We then establish the rationale of \textsc{CRoST} through both theoretical analysis and empirical validation. The evaluation results show that state-of-the-art models achieve 38.82\% coverage on average, with 14.4\% of generated lemmas exceeding 80\% coverage, indicating that LLMs can already generate useful lemmas to a certain extent. However, they still exhibit non-trivial failure modes on complex multi-phase protocols, show diminishing returns under naive scaling, and incur substantial verification overhead. These findings clarify the practical potential and limitations of LLMs for protocol verification and motivate future work on complex real-world protocols.

0.22

Beyond Local Accuracy: A Protocol-Level Identifiability Audit for Controlled LLM Reasoning Evaluation

cs.CL ·2026-08-13 ·Junhao Luo, Ning Huang, Ziqi Sha, Wenxuan Tang, Wei Deng
benchmark similarity 0.54
Abstract · 15 pages, 9 figures. Ning Huang, Ziqi Sha, and Wenxuan Tang contributed equally as second authors. Wei Deng is the corresponding author

LLM benchmark scores can be precise even when the observation protocol does not identify the behavioral property they are intended to measure. In a controlled, solver-grounded setting, we formalize a protocol-level identifiability audit over a finite behavioral policy class: given policies H, observation support O, and estimand $τ$, we test whether O separates every pair with different $τ$. The audit requires zero model calls and resolves our diagnostic case: base-only observation collapses seven frozen deterministic policies into one equivalence class; full support yields seven classes and no cross-estimand collisions; every leave-one-out support retains a constructive collision witness. Empirically, both constrained-generation variants have pair-validity 1.0, yet base accuracy and selective-response fidelity diverge - 0.620 versus 0.324 across six balanced oracle-transition directions (cluster-bootstrap 95% CI [0.600, 0.642] vs. [0.304, 0.345]) - and the gap recurs on a second deterministic source (0.646 vs. 0.331). The audit also synthesizes a minimum identifying support $O^*$ for the frozen policy class: two cells instead of the full 36-cell tensor. This case shows how evaluation-design validity can be checked structurally before model inference and why base correctness does not determine intervention-response fidelity.

0.10

Cryptanalysis and Repair of "Decentralized Multi-authority ABE for NC$^1$ from BDH"

cs.CR ·2026-10-21 ·Xingwang Wang
theory similarity 0.54
Abstract

We present a plaintext-recovery attack on both the DBDH-based construction and the CBDH-based variant of Datta, Komargodski, and Waters (Journal of Cryptology, 2023). The attack succeeds with probability one in the claimed static security model using one corrupt authority and two users, each unauthorized even when granted the corrupt authority's attribute. The flaw is an invalid extension of the LSSS matrix-normalization lemma originating with Rouselakis and Waters (FC,~2015): preserving complete-share distributions does not preserve coordinate-wise ciphertext masks, which a corrupt authority can expose to remove identity binding from other users' shares. For both variants, replacing these masks with independent full linear sharings of zero preserves correctness and restores ciphertext-distribution invariance. We prove static security of both repaired variants in the random oracle model under their respective BDH assumptions, using the original hardcore-bit convention for the CBDH variant. Both proofs allow adaptive identity-hash queries. The modification retains the original matrix-width and row-labeling restrictions, keys, decryption, and ciphertext size, requiring only additional encryption randomness and finite-field arithmetic. We also attack both multi-authority attribute-based inner-product functional encryption constructions of Datta and Pal (PKC, 2023) and establish correctness and matrix-substitution invariance of the same repair. We prove static security of the repaired small-universe construction under asymmetric DBDH. For the large-universe construction, we identify a missing source-group encoding in the original reduction and give a complete static security proof under an augmented $L$-DBDH assumption, whose generic bilinear group hardness we establish.

0.22

CHERI under Fault Injection: An Emulation-Based Security Evaluation of Capability Hardware Enhanced RISC Instructions

cs.CR cs.AR ·2026-11-15 ·Eva Sophia Schreyer
similarity 0.53
Abstract · Submitted to KTH Royal Institute on Technology as a Master Thesis

Memory-safety vulnerabilities continue to dominate real-world exploit chains despite decades of research into software mitigations. CHERI is a hardware architecture that enforces spatial and temporal memory safety by augmenting pointers with hardware-checked metadata, thus preventing software-based exploitation, but its threat model explicitly excludes fault injection. This thesis investigates whether targeted fault injection can undermine CHERI's memory-safety guarantees in a pure-capability CHERI-RISC-V environment. Two fault classes are considered: bit flips corrupting capability metadata, and fault-induced check skipping on capability store instructions. We implement fault injection primitives in a QEMU-based emulation environment, which enables deterministic, repeatable experiments without specialised hardware. With them, we demonstrate four attack scenarios: buffer overflows, control-flow hijacking, data-only attacks, and use-after-free. Each succeeds with one or two targeted faults (lower bounds under the emulation-based setting). Check skipping offers an alternative route to control-flow hijacking and data-only attacks, with a minimum of one fault. These results show that CHERI's guarantees depend on the physical integrity of capability metadata, the uninterrupted execution of metadata checks, and the integrity of the revocation bitmap: a single targeted fault can circumvent spatial safety, temporal safety, or control-flow integrity. CHERI still raises the cost of exploitation, since fault injection is a prerequisite for every attack and the sentry mechanism forces an attacker to supply a valid tagged capability or spend a second fault restoring the tag. Based on these findings, we propose mitigations: ECC-protected capability memory, capability field authentication codes, redundant execution of security-critical checks, and revocation bitmap integrity verification.

0.29