CS Paper Radar

Black Box Cryptanalysis of AES128

Virendra Sule, Kunal Telangi

cs.CR ·submitted 2026-08-24 07:38 UTC · v2
unusual

Abstract

This paper presents computational results of cryptanalysis of AES using the Local Inversion by Black Box computations of the forward encryption and utilizes these results to develop a practically feasible approach for the key recovery of the full scale AES128 under Known Plaintext Attack (KPA). It is shown that complete recovery of unknown key bits is possible upto $80$ bits in a practically feasible time and memory in random KPA situation by sequential computation when remaining $48$ bits are known. The results of key recovery in $64$, $72$ and $80$ bit unknown cases are extrapolated to predict the period of the iterative sequence generated in the local inversion approach for the full $128$ bit unknown key case and a strategy is proposed to search the actual period by brute force parallel search of the sequence period with $10$ free bits defining the search space. Then it is shown that the actual key can be verified in polynomial time by fast powering of the forward encryption map. Hence this strategy shows that the key recovery problem for AES128 under KPA has a chance of success in practically feasible time for a majority of the plaintexts. Local inversion approach to cryptanalysis using black box computations is a universal method applicable to a vast variety of key recovery and map inversion problems. Hence the results presented in this paper are representative of estimates of cryptanalysis of other ciphers which can be considered almost as strong as AES128 as encryption functions.

Comment
14 pages, two figures, 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Symmetric Cryptography via Dirichlet Convolution

cs.CR cs.IT ·2026-10-02 ·Artur Sowa, Elias Hassani Sangani, Francis Bui, Grant Harris, Jonathan Norton
similarity 0.56
Abstract · 19 pages, 2 figures, 1 table

We discuss a new symmetric-key cipher for digital data encryption. Its implementation is fast, memory efficient, and resilient against classical, AI-assisted, and quantum attacks. Let $x$, $k$, and $c$ be elements of a finite abelian group $G$ with operation $+$ and neutral element $0$. Suppose one is given ciphertext $c=x+k$. Retrieving the plaintext $x=c-k$ from the ciphertext is trivial when the key $k$ is known. Without the key, however, recovering $x$ amounts to a blind search. Even if an efficient criterion were available for identifying the plaintext among all group elements, the average number of trials would remain prohibitively large when the group is sufficiently large. The challenge in constructing a practical cryptosystem is therefore to identify a sufficiently rich group $G$, together with efficient algorithms that enable an immersion of \emph{real digital data} into $G$ and efficient evaluation of the group operations. The proposed cipher is based on generalized Dirichlet convolution over finite fields. We investigate its security against plaintext attacks from an information-theoretic perspective. The nonlocal structure of Dirichlet convolution naturally permits plaintext salting, providing protection against plaintext attacks while allowing controlled key reuse. We establish perfect masking properties over finite fields and prove that the resulting cipher achieves information-theoretic security under key reuse when the underlying arithmetic is carried out in $\mathbb{F}_p$ with $p>2$. For arithmetic over $\mathbb{F}_2$, some information leakage remains, leading to a finite key-reuse budget.

0.41

Function Inversion Reporting

cs.DS ·2026-11-09 ·Itai Dinur, Alexander Golovnev, Chao Yan, Yiding Zhu
similarity 0.52
Abstract

In the Function Inversion problem, the goal is to invert a function $f:[N] \to [N]$ in two phases. In the preprocessing phase, the offline algorithm computes an advice string of length $S$ bits. In the online phase, the online algorithm receives the advice and a challenge $y \in [N]$, and the goal is to find a preimage $x \in [N]$ such that $f(x) = y$ in time $T$. The problem was initially studied in cryptography, but in recent years it has found various applications to data structure problems. Yet, several of the applications require a variant of Function Inversion, known as Function Inversion Reporting, where the goal is to output all preimages of the challenge $y$. In this paper, we study the Function Inversion Reporting problem in a systematic way by unifying and improving existing algorithms. As a result, we obtain improved data structures for several problems including 3SUM-Indexing Reporting, Range Reporting, Approximate Nearest Neighbor, Jumbled Indexing Reporting, and Gapped String Indexing Reporting.

0.19

Bilinear Compressive Security with Finitely Many Samples

cs.CR cs.ITeess.SP ·2026-10-14 ·Axel Flinth, Semira Einsele, Matilda Kylberg, Hubert Orlicki, Gerhard Wunder
similarity 0.50
Abstract

Bilinear Compressive Security (BCS) is a lightweight encryption scheme that combines compressed sensing with a fresh random convolution filter to improve resistance against key-recovery attacks under key reuse. Previous work derived information-theoretic guarantees for BCS by relating key identifiability to phase retrieval under the assumption that an adversary has access to the full ciphertext distribution induced by the random filter. In practice, however, an adversary only observes finitely many encryptions, leaving the security of BCS in the finite-sample regime largely unexplored. In this paper, we study key recovery from only finitely many observations. We first develop a covariance-based attack that estimates the linear measurements from repeated encryptions of the same plaintext and subsequently recovers the secret measurement matrix. We analyze the estimation procedure and derive finite-sample guarantees together with corresponding sample-complexity bounds. We further investigate the complete attack experimentally and compare its observed recovery behavior with the previously established information-theoretic identifiability results. Our experiments show two qualitatively different recovery regimes on the structure of the measurement matrix. For dense matrices, including Gaussian matrices, the number of measurements required for successful recovery appears to grow linearly with the signal dimension. This differs from the worst-case behavior suggested by information theory. In contrast, for matrices with sparse rows, we observe a quadratic growth consistent with the theoretical bound. These results suggest that the sparsity structure of the measurement matrix plays an important role in the security of BCS and should be taken into account when selecting parameters and designing practical instances of the scheme.

0.22

How to break the Miranda signature scheme over matrix Gabidulin codes

cs.CR ·2026-09-25 ·Adrien Vinçotte
similarity 0.50
Abstract · 21 pages, 3 tables, 2 algorithms

The Miranda signature scheme relies on masking a matrix code which disposes of a masked underlying structure, and the knowledge of which allows for efficient error decoding. We consider a Gabidulin code which is expanded into a matrix code, that is only \Fq-linear. An additional masking is then applied to it. The attack proposed here shares similarities with that of [Le26, https://arxiv.org/abs/2608.03328] on the EGMC encryption scheme, which also follows the paradigm described above. It consists in recovering the Fqm-linear structure of a masked matrix Gabidulin code by reducing to a MinRank instance to be solved over the extension field Fqm, but where the matrices have coefficients in Fq. Such an instance can be efficiently solved. However, unlike the previous attack, it is possible to reduce in polynomial time to such a MinRank instance in the case of the Miranda signature scheme. This results in a particularly efficient key recovery attack against the parameters proposed for Miranda. For example, for the proposed parameter set with m=79, the complexity drops from 146 bits to 46 bits in this attack.

0.31

Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence

cs.CR ·2026-10-22 ·Ramses Fernandez
similarity 0.49
Abstract

For the last two years, classical structural attacks on McEliece with binary Goppa codes progressed further, at the parameters of Classic McEliece, than in the previous four decades: a subexponential and then a quasi-polynomial distinguisher, key recoveries for public challenges with brute-force labels up to $254$, and conditional key-recovery estimates of about $2^{89}$ to $2^{128}$ per run of a large sparse linear-algebra computation, depending on the parameter set and on whether and how memory access is charged. On September 2026 the German BSI advised against new deployments of the scheme. This paper gives a version-aware critical assessment of these results. It separates proved distinguishers, conditional cost estimates and actual recoveries; analyses in detail Saarinen's HOVER algorithm, his conditional cost analysis and his recovery of the TII-254 challenge, together with Weis's cost study of Holdout/Hermite key recovery; and compares the other key-recovery routes and the objections raised against them. Our own analysis finds that the cost model is now the main quantitative uncertainty, with about thirty bits between the cheapest and the most expensive model for the same computation; that for the four larger parameter sets every model considered leaves the conditional estimates far below the targeted levels, whereas for mceliece348864 the shortfall is of the order of the spread between models; that the structural estimates are lower than Grover-accelerated information-set decoding for the four larger sets in essentially every model and comparable for mceliece348864; and that none of this is a demonstrated attack, since the underlying heuristics have been tested only on instances tens of thousands to hundreds of thousands of times smaller than the target. We close with open questions.

0.32

ML Models Are Not Ciphers: Power Analysis for Weight Extraction Is Harder Than You Think

cs.CR ·2026-11-09 ·Mohammed Qaiss, Peter Horvath, Michal Shagam, Lejla Batina, Zhuoran Liu +3 more
similarity 0.49
Abstract

Can power-analysis techniques reveal secret weights of machine-learning models? Multiple recent works demonstrate proof-of-concept attacks that can partially recover such weights. To that end, these works build on techniques from cryptographic engineering, treating the model as a ``cipher'' and its secret weights as keys. We question the basic assumption behind such straightforward adaptations of cryptographic attacks and highlight the challenges arising when applying past techniques to fully recover all layers of deep neural networks. Unlike past works, which extract only a few weights, typically from shallow layers, we investigate the recovery of complete networks. Moreover, we target fully trained and functional models, rather than untrained, randomly initialized networks. To focus on fundamental challenges, we assume an unrealistically strong side-channel adversary that can directly observe the output of the leakage model without any added noise. With this adversary, we show that machine-learning models differ significantly from cryptographic implementations, giving rise to unique challenges that have not been observed in the prior art. We observe two main differences between machine-learning models and ciphers. First, in contrast to the high-diffusion nonlinear integer arithmetic prevalent in cryptographic schemes, machine-learning models tend to use limited-precision floating-point arithmetic and low-diffusion linear operations. We show that these operations introduce difficulties in weight recovery, often requiring an unexpectedly large number of traces, even under ideal channel conditions. Second, we observe that, unlike ciphers, which aim to increase the data entropy, machine-learning models aim to reduce it. This reduces data variability as the algorithm progresses, hampering weight recovery in deep layers of the model. (details can be found in the paper)

0.23

ROBBIN: Rowhammer-Based Backdoor Injection during Inference

cs.CR ·2026-08-24 ·Saion K. Roy, Yufei Wang, A. Adam Ding, Yunsi Fei
published similarity 0.48
Abstract · International Conference on Computer-Aided Design (ICCAD) 2026

Existing Rowhammer-based inference-time backdoor attacks design their bit-flip strategies purely at the algorithmic level, without accounting for the bit-flips that the underlying DRAM hardware will actually produce. This disconnection between the algorithmic backdoor construction and its hardware realization leads to unreliable attack performance, as collateral bit-flips at unintended locations degrade both the attack success rate (ASR) on triggered inputs and the test accuracy (TA) for normal inputs. Consequently, the performance of such attacks varies significantly across different DRAM devices, as each device presents a unique set of exploitable bit-flip locations. This work presents ROBBIN, a hardware-aware Rowhammer-based backdoor injection attack that integrates the device-specific vulnerability into the backdoor construction process. ROBBIN first characterizes the bit-flip patterns of a target DRAM and uses this information to iteratively select DRAM \textit{page} mappings for the model weights that would maximize ASR while preserving TA under Rowhammering. By treating every hammering-induced bit-flip as an integral part of the attack design rather than first constructing a hardware-agnostic backdoor and dismissing collateral flips as side effects, ROBBIN produces backdoors that remain robust across devices. Evaluated on ResNet-20 and VGG-16 with CIFAR-10 across three commodity DDR4 chips, ROBBIN consistently achieves close to 90\% ASR while maintaining TA above 83\%, demonstrating reliable backdoor efficacy across diverse DRAM devices.

0.24

AI Grinding for Fun and Cryptanalysis

cs.CR ·2026-08-22 ·Lukasz Olejnik, Bartosz Naskrecki
similarity 0.46
Abstract

We present an autonomous cryptanalysis workflow in which agents generate, test, and refine hypotheses before human review. The autonomous stage returns reproducible candidates with exact witnesses, controls, code, and run records. A researcher then decides whether the evidence establishes a break, defect, or coverage gap. Two failure modes recur. First, a public algebraic map or input representation erases or exposes a relation that a construction must hide. Examples include multiplication by zero, boundary coefficients of a polynomial product, quotients, characters, Schur squares, and variable-length byte encodings without boundaries. Second, a simulator, error law, or parameter certification uses a distribution different from the one claimed. Several targets fail in both ways. Every result has an exact witness and a discriminating control; every stated boundary has a proof. Three further targets yielded no attack but support narrower guarantees than a generic reading suggests. Eight published constructions fail at stated parameters or claims. A Ring-LWR commitment opens to every message with probability one. One ciphertext reveals two middle-product encryption rows. A lattice e-voting protocol loses receipt-freeness. A permutation-recovery attack against updatable encryption extends by linear algebra to the old decryption key. An explicit normal basis splits a degree-63 instance into seven degree-nine instances. A signature hash outside the lattice setting maps two printable equal-length messages to the same digest. A rerandomisable scheme's accept bit is a threshold oracle on its decryption noise. Separately, a group-ring decision claim and a multivariate MinRank hardening fail at the assumption or accounting level rather than as complete construction breaks. Each failure occurs one level above its supporting assumption.

0.28