Source-linked AI summary
Black Box Cryptanalysis of AES128
Virendra Sule, Kunal Telangi
TL;DR
The paper asks whether AES128 key recovery under known plaintext can be made feasible without exhaustive key search. It formulates recovery as local inversion using forward black-box computations, then extrapolates partial-key experiments into a parallel period-search strategy for the full key. The reported results indicate feasible sequential recovery through 80 unknown bits and a potentially feasible full-128-bit attack, subject to empirical period assumptions and algorithmic limitations.
Problem
The paper studies the computational requirements of recovering an AES128 key from a known plaintext-ciphertext pair by local inversion of the encryption map.
Method
The approach generates local-inversion sequences using only forward black-box operations, then searches predicted full-key periods in parallel over a small 10-bit range.
Results
Complete recovery of up to 80 unknown key bits is reported as practically feasible by sequential computation, while the full-128-bit strategy is presented as having potential practical feasibility.
Takeaways & Limitations
The paper presents black-box local inversion as an empirical, broadly applicable approach to key recovery and map inversion problems.
Takeaways & Limitations
The approach can fail when the local inversion problem has a nonunique solution, and the full-key period estimate relies on extrapolation from lower-bit cases.
Abstract
from arXiv · showhide
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 high chance of success in practically feasible time. 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.
1 Introduction
The paper frames AES128 key recovery under known plaintext as local inversion using only forward black-box computations. It reports empirical feasibility for partial recovery and proposes a period-search strategy for the full 128-bit case.
- AES is widely deployed and has resisted algebraic, linear, and differential cryptanalysis across its versions.
- Known plaintext key recovery is formulated as solving the Local Inversion Problem for the forward map F(x) = E(x, P) given y = C.
- Black Box Cryptanalysis restricts computation to forward evaluations E(x, P), with feasible sequential computation and memory determining the search limits.
- The BBC algorithm generates an iterative sequence, detects a period or quasi-period, and uses the orbit inverse as a possible key solution.
- The method can use much less storage than brute force or conventional time-memory tradeoffs, but nonunique inverses can cause failure.
- For AES128, sequential period computation is infeasible, so the paper proposes parallel brute-force search over a small 10-bit period range extrapolated from lower-bit experiments.
2 Local Inversion for Partial Key Recovery
The paper formulates partial AES128 key recovery as local inversion of an iterative sequence using only forward black-box computations. Experiments for 64, 72, and 80 unknown bits motivate extrapolation of cycle periods for the full 128-bit case.
- Partial-key model: Partial key recovery solves for subarray X|U while the complementary bits X|U′ remain fixed or known.The unknown indices form a subset U of the full 128-bit master-key indices.
- Local inversion: The iterative sequence is initialized from one plaintext-ciphertext pair and updates unknown positions from the current state while preserving known key bits.The recovered unknown key portion is obtained as an orbit inverse of the generated sequence.
- Local inversion: For a periodic sequence of period N, the previous state Y(N−1)|U yields the unknown key bits.Sequential period computation is feasible only when N is of feasible order in the key length.
- Experimental results: The reported experiments examine SM4 recovery with 64 known and 64 unknown master-key bits, using 32 GB RAM and processors clocked up to 5.7 GHz.Fifteen independent random experiments recovered the master key in 11 cases; four produced a quasi-cycle.
3 Full key recovery of AES128
The proposed full-key strategy extrapolates feasible period ranges from lower-bit experiments, searches candidate periods in parallel, and recovers the key through fast powering of the forward map.
- Parallel period search: Each candidate period N is tested in parallel by verifying whether F^N(Y(0)) returns to the initial value.Fast powering computes each iterate, and the matching N is returned for subsequent key recovery.
- Predicted possible periods for 128 bit unknown key: 128-bit period candidates are extended to a 10-bit search range, producing a collection of 1024 possible periods.The extrapolated range is 2^54 to 2^64, widened from the stated 2^56 to 2^64 range.
- Key recovery: After finding a valid period, the algorithm computes N − 1 and applies the corresponding iterate to obtain the key.The stated recovery forms are K = F^(N−1)(Y(0)) or the analogous permuted-map expression.
- Fast powering of maps: The algorithm prepares squared-map codes and uses their compositions to evaluate F^N(Y(0)) in polynomial time.A polynomial-time forward-map implementation yields polynomial-time squared maps, enabling fast powering.
4 Appendix: Brief description of BBC
Black Box Cryptanalysis formulates known-plaintext key recovery as local inversion using only forward evaluations, then converts iterative sequences into usable cycles when necessary.
- Problem formulation: Under KPA, recovering the key from a plaintext-ciphertext pair is formulated as solving a Local Inversion Problem for F(x) = E(x, P).The input is y = C, and only forward evaluations of E(x, P) for candidate keys are permitted.
- Computational constraints: BBC restricts computations to black-box forward operations and a practically feasible number of evaluations and memory.Its empirical aim is to estimate how often key recovery succeeds under these resource constraints.
- Quasi-periodic case: For quasi-periodic sequences, a random bit permutation can produce a periodic sequence whose orbit inverse solves the original local inversion problem.If one permutation fails to produce a periodic sequence, another may be selected.
- Feasibility: Cycle detection can use sequential time proportional to the period and only one stored sequence element, making inversion feasible when periods are small enough.For sufficiently random maps, period-finding has a 50% detection chance in O(2^(n/2)), with periods approximately 1.25 × 2^(n/2).
5 Conclusions
The paper reports feasible sequential recovery through 80 unknown AES128 key bits and proposes parallel period search for the full 128-bit case, with verification by fast powering.
- Empirical recovery results: 64, 72, and 80 unknown-bit cases were recovered in practically feasible time and memory by sequential computation in random KPA settings.These results relied on iterative-sequence periods smaller than O(2^(n/2)) for up to 80 unknown bits.
- Full-key strategy: The lower-bit results are extrapolated to predict a narrow full-128-bit period band searchable with 10 free bits.The proposed full-key strategy searches candidate periods in parallel and verifies the actual period using fast powering.
- Conclusion: The paper concludes that AES128 key recovery from a single-pair KPA has a high chance of success in practically feasible time and memory.The conclusion is based on the reported period behavior, efficient AES forward computation, and fast powering.