Cryptographic implementations are routinely written to be "constant-cycle": the code executes a fixed number of processor cycles regardless of the secret key, precisely so that measuring how long it takes reveals nothing. This guarantee silently assumes the processor's clock frequency is fixed. It is not. Modern chips continuously adjust frequency through power-management hardware that responds to electrical and thermal conditions, and since dynamic power consumption depends on the data being processed, data-dependent power becomes data-dependent timing. Liu et al. demonstrated this concretely: on a constant-cycle AES implementation using AES-NI instructions, they recovered the full 128-bit key on an Intel Skylake in roughly 25 hours from 2 million timing traces, simply by forcing the chip to throttle (Frequency Throttling Side-Channel Attack). Crucially, temperature itself cannot change quickly. Heat moves by diffusion through physical material, so the die's thermal state drifts slowly and continuously — a property the literature on thermal cycle latency documents across scales, from robotic thermal actuators that need seconds to cool between switching events (Origami-based integration of robots that sense, decide, and respond) to phase-change materials whose liquid layers act as insulating bottlenecks (Macro-Encapsulated PCM Cylinder Module Based on Paraffin and Float Stones Macro-Encapsulated PCM Cylinder Module Based on Paraffin and Float Stones). Nobody, however, has put these two facts together inside a constraint solver.
This proposal makes a two-sided bet on that omission. First, on the offensive side: thermal throttling leaks have only been exploited by hand-crafted stressor threads and statistical correlation, whereas every other modern cryptanalytic weakness — related-key differentials in AES-192 (Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers), persistent S-box faults (Free Fault Leakages for Deep Exploitation: Algebraic Persistent Fault Analysis on Lightweight Block Ciphers), guess-and-determine backdoors (On Cryptographic Attacks Using Backdoors for SAT) — has been reformulated as an automated search over a declarative model. Second, on the defensive side: the same slow physics that creates the leak also shrinks the verification problem, because a rate-limited temperature trajectory can only visit a small number of distinct throttle states during one cipher execution. Thermal latency is thus both the vulnerability mechanism and the key to verifying it at full-cipher scale, which is where every existing formal tool in this space breaks down.
Core Claim
The claim is that thermal throttling leakage can be modeled as a bounded temporal constraint system — a cipher's logic unrolled alongside a temperature variable that moves slowly — and that this model simultaneously enables automated attack synthesis and scalable formal verification, where time-abstracted models are either unsound or intractable. Formally, we model an execution of $N$ steps, each with a data-dependent energy $e_i$, a cycle count $c_i$, and a thermal state $T_i$ governed by thermal inertia:
$$T_{i+1} \in [\,T_i - \delta_{\mathrm{cool}},\; T_i + \delta_{\mathrm{heat}}\,], \qquad t_{\mathrm{obs}} = \sum_{i=1}^{N} \frac{c_i}{f(T_i)}$$
where $\delta_{\mathrm{cool}}$ and $\delta_{\mathrm{heat}}$ are per-step bounds implied by heat diffusion (with $\delta_{\mathrm{cool}}$ typically much smaller, since cooling is passive), and $f$ is the power-management unit's temperature-to-frequency map, a small step function. The verification query asks whether two executions driven by different secrets can produce observably different $t_{\mathrm{obs}}$; the attack query searches for perturbation schedules (injected power load, placement within the execution) that maximize this difference. Because $f$ changes only at a handful of threshold temperatures and $T$ can drift by at most $\delta$ per step, the reachable set of $(T, f)$ configurations across a short cipher execution is tiny compared with the cipher's own Boolean state space — the temporal dimension adds almost nothing to the solver's burden once the rate bound is encoded. This is the exact opposite of the usual state-explosion story in formal verification (SI: Satisfiability Modulo Theories; JBMC: A Bounded Model Checking Tool for Verifying Java Bytecode), and it is what makes full-cipher verification plausible here.
Research Program
We will build one encoding and two consumers of it. The encoding pipeline translates a cipher's gate-level or instruction-level description into Conjunctive Normal Form following established practice — each wire a Boolean variable, XOR expanded into parity clauses, non-linear substitution boxes translated from truth tables (SAT-based Cryptanalysis of Authenticated Ciphers from the CAESAR Competition) — and then appends the thermal-throttle automaton as bounded sequential constraints. For the comparison of healthy versus leaking execution we adapt the gadget technique of FIRMER, which encodes both behaviors in a single formula with internal control variables and thereby verified fault countermeasures far faster than Binary Decision Diagram tools (SAT-based Formal Fault-Resistance Verification of Cryptographic Circuits). To survive the 8-bit substitution boxes that stall monolithic solvers — the very barrier documented for AES-128 in APFA (Free Fault Leakages...) — we adopt the hybrid partitioning lesson from QMVerif, where targeted brute-force enumeration of 8-bit field operations beat Z3 when the general-purpose solver crashed or timed out (Quantitative Verification of Masked Arithmetic Programs Against Side-Channel Attacks), and from HYBRIDCEC, where exact simulation spliced into SAT sweeping delivered up to 1000x speedups on XOR-dense datapaths (Integrating Exact Simulation into Sweeping for Datapath Combinational Equivalence Checking). Dense non-linear components get table-based enumeration; the temporal and linear structure goes to a CDCL engine such as Glucose or CryptoMiniSAT, with the partition decided by an XOR-density heuristic in the spirit of Chen et al.
The attack consumer applies automated search to the same model. Following Semenov et al.'s Inverse Backdoor Sets, which used Tabu search over a Monte Carlo "resistance function" to find minimal variable subsets that make CDCL solving tractable (On Cryptographic Attacks Using Backdoors for SAT), we will search over perturbation schedules — where in the execution window to place a stressor load, and of what magnitude — minimizing the expected number of timing observations needed for key recovery, then feed the pruned candidate set to the algebraic solver. The verification consumer answers the dual question: it computes a certificate of the maximum timing difference achievable over all secrets and all thermally admissible trajectories, or proves it is zero.
Baselines
The naive reference point is the assumption the industry actually operates under: that constant-cycle code is timing-safe. We will measure timing leakage on the target implementation with power-management interference disabled; on constant-cycle AES-NI code this should show essentially no signal, and any leakage that appears once throttling is enabled is then attributable to the thermal mechanism rather than to sloppy implementation. This "do nothing" baseline matters because it defines the vulnerability we claim to detect and exploit.
The strongest attack-side competitor is Liu et al.'s empirical pipeline: an unprivileged stressor thread on a neighboring core, timing measured with RDTSC, and Correlation Power Analysis over execution-time traces (Frequency Throttling Side-Channel Attack). Their reported result — full 128-bit AES key recovery on Intel Skylake in approximately 25 hours using 2 million traces, with only 14 of 16 key bytes recovered both inside an Intel SGX enclave and on AMD Ryzen — is the number to beat. For a fair comparison we will run their attack and ours on the same constant-cycle AES-NI target, on the same machine class (or a simulator calibrated so that their attack reproduces the 2-million-trace, 25-hour figure), with the same wall-clock and trace budgets and equivalent tuning effort for the search heuristics on each side. Beating it means full key recovery with at least an order of magnitude fewer traces, or full recovery in the constrained settings where their CPA stalls at 14 of 16 bytes.
The strongest verification-side competitor is FIRMER (SAT-based Formal Verification of Fault Injection Countermeasures for Cryptographic Circuits), which reported verifying 72 of 76 benchmark tasks in under 3 minutes across 33 cryptographic circuits ranging from 608 to over 68,000 gates, while the BDD-based FIVER timed out on 31 of 76 tasks after 24 hours. FIRMER cannot express our problem — its gadgets encode instantaneous combinational faults, not rate-limited sequential thermal dynamics — so the comparison has two parts. On FIRMER's own benchmark suite, run with the same Glucose solver and hardware, we check that adding the thermal layer costs little or nothing in runtime, establishing that we do not regress on their home ground. On our temporally augmented encodings, the comparison is against the best available time-abstracted approximation of FIRMER (throttle state fixed or freely changing at every step), and beating it means verifying instances where the abstraction is either unsound, certifying safety when a rate-limited trajectory actually leaks, or hopelessly over-conservative, flagging leaks that the thermal bound rules out.
The key ablation removes the thermal rate bound itself: the same engine run with unconstrained temperature transitions between steps. If the rate constraint is genuinely the scaling ingredient, this ablation should blow up in runtime or return vacuous results, and the contrast quantifies the contribution. A second ablation swaps the hybrid S-box treatment for a monolithic CNF encoding, where we expect the clause explosion on AES-128 documented by APFA.
Why not just…?
Why not just run Correlation Power Analysis on timing traces? This is the most serious objection, because CPA demonstrably works: Liu et al. recovered a full AES-128 key with it. But the cost profile is poor — 2 million traces, 25 hours, and incomplete recovery (14 of 16 bytes) in both the SGX and AMD settings (Frequency Throttling Side-Channel Attack) — and the analogous shift from statistical observation to algebraic solving has already paid off once in this literature: APFA reduced the faulty ciphertexts needed against SKINNY-64-64 from 1,550 to 10, a 155x reduction, and broke PRESENT-128 with 28 ciphertexts (Free Fault Leakages...). Still, we treat this as a genuine threat: our trace-count comparison against the CPA baseline on identical hardware is the decisive check, and if automated schedule synthesis plus algebraic recovery cannot beat 2 million traces, the offensive half of the proposal fails and we would report it as such. The defensive half — a leakage certificate no amount of CPA profiling provides — would stand independently.
Why not just lock the frequency or fuzz the power limits? Liu et al. analyzed exactly these mitigations and found they impose significant performance penalties and sacrifice the energy savings dynamic frequency scaling exists to deliver (Frequency Throttling Side-Channel Attack). Physical-design mitigation does not fully escape the problem either: thermal-aware floorplanning in 3D chips reduced power-temperature correlation by only 7.71% on average (up to 16.79% on larger designs) at a 5.38% power cost (On Mitigation of Side-Channel Attacks in 3D ICs), leaving residual correlation unaddressed and, importantly, unquantified. Our verifier supplies what neither workaround can: a per-implementation bound on residual leakage under a stated thermal budget, so a defender can choose where on the cost-leakage curve to sit. As a check, we will formally verify a locked-frequency variant (expected: certified leak-free) and a fuzzed-threshold variant (expected: bounded but nonzero leakage), converting the mitigation debate into measurable certificates.
Why not just use an off-the-shelf SMT solver or a BDD tool? The file's evidence rules both out for this problem class. Z3 crashed or ran indefinitely on 8-bit finite-field exponentiation that a hybrid enumeration pipeline handled easily (Quantitative Verification...), and monolithic SAT sweeping solved only 25 of 50 industrial datapath instances where a simulation-SAT hybrid solved 45 (Integrating Exact Simulation into Sweeping...). On the BDD side, FIVER timed out on 31 of 76 tasks after 24 hours where the SAT-based FIRMER finished 72 of 76 in under 3 minutes (SAT-based Formal Verification of Fault Injection Countermeasures...). We will still run Z3 and FIVER on our benchmark set as sanity baselines, and the monolithic-encoding ablation directly measures what a naive solver-only design would cost.
Why not just model throttling as one more transient fault in an existing tool like FIRMER? Because thermal dynamics are sequential and rate-limited, while FIRMER's fault gadgets are instantaneous and combinational. Abstracting time away forces a choice: treat the throttle state as freely switchable at every step, which is over-conservative and will flag leaks no physical trajectory can produce, or treat it as fixed, which is unsound and can certify as safe an implementation that leaks across a multi-step temperature rise. Both failure modes are checkable in our experiments — we can construct small instances where the time-abstracted approximation and the rate-constrained model disagree, and the physical calibration decides which is right — so this objection, unlike the CPA one, can be answered constructively rather than by argument.
Proposed Experiments
The first experiment establishes verification scalability. We take the 33-benchmark suite used by FIRMER — AES, CRAFT, LED, GIFT, PRESENT, and SIMON circuits from 608 to over 68,000 gates (SAT-based Formal Verification...) — and augment each with a calibrated thermal-throttle layer. The metrics are tasks verified within a 3-minute budget and within a 24-hour budget, peak memory, and the computed leakage bound. The comparison numbers are FIRMER's reported 72 of 76 tasks in under 3 minutes and FIVER's 31 of 76 timeouts at 24 hours; our target is to match FIRMER's throughput on the unaugmented circuits and to verify the temporally augmented versions, which neither tool can encode, in comparable time. The rate-bound ablation runs alongside: if removing the per-step thermal bound multiplies runtime by orders of magnitude or forces vacuous certificates, the core claim is directly supported.
The second experiment establishes attack efficiency. The target is the constant-cycle AES-NI implementation attacked by Liu et al., plus lightweight software implementations of PRESENT and SKINNY to test generality on ciphers from the APFA benchmark set (Free Fault Leakages...). We synthesize perturbation schedules with the Tabu-style search over the encoded model, then run algebraic recovery on the pruned candidate set. Metrics are traces to full key recovery and total wall-clock, compared head-to-head with the CPA baseline under identical conditions; the reference number is 2 million traces and approximately 25 hours on Intel Skylake, with 14 of 16 bytes as the bar in constrained settings. Where real hardware of the right generation is unavailable, we use a thermal/PMU simulator calibrated so the CPA baseline reproduces the reported figures, and validate the calibration on whatever comparable hardware we can obtain — an honest limitation we will state in any resulting report.
The third experiment is the decisive check on the physics-to-solver bridge: small, fully enumerable instances where we can compare the solver's leakage verdict against brute-force enumeration of all thermally admissible trajectories and all secret pairs. Agreement on these instances validates the encoding; disagreement would mean the abstraction of thermal inertia is wrong at the root and would falsify the approach. Together, these three experiments either establish that thermal rate constraints turn a messy physical side channel into a tractable, certifiable, and automatically exploitable object, or they localize precisely where the bridge between the physics and the solver breaks.
References
- Frequency Throttling Side-Channel Attack
- Origami-based integration of robots that sense, decide, and respond
- Macro-Encapsulated PCM Cylinder Module Based on Paraffin and Float Stones
- Macro-Encapsulated PCM Cylinder Module Based on Paraffin and Float Stones
- Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others
- Free Fault Leakages for Deep Exploitation: Algebraic Persistent Fault Analysis on Lightweight Block Ciphers
- On Cryptographic Attacks Using Backdoors for SAT
- Preface to the special issue "SI: Satisfiability Modulo Theories"
- JBMC: A Bounded Model Checking Tool for Verifying Java Bytecode
- SAT-based Cryptanalysis of Authenticated Ciphers from the CAESAR Competition
- SAT-based Formal Fault-Resistance Verification of Cryptographic Circuits
- Quantitative Verification of Masked Arithmetic Programs Against Side-Channel Attacks
- Integrating Exact Simulation into Sweeping for Datapath Combinational Equivalence Checking
- SAT-based Formal Verification of Fault Injection Countermeasures for Cryptographic Circuits
- On Mitigation of Side-Channel Attacks in 3D ICs: Decorrelating Thermal Patterns from Power and Activity