💻 computer science

Limiting Cross-Session Reuse of Table-Specific Attack Information: Session Diversification of S-Boxes with Per-Instance Cryptographic Guarantees

This paper introduces QSD-SBox, a session-diversification scheme that constructs unique $(8\times8)$ S-boxes for each session using seed-derived affine permutations to effectively prevent the cross-session reuse of table-specific attack information while maintaining rigorous per-instance cryptographic guarantees without runtime search overhead.

Original authors: Annas Malik, Ghulam Mustafa, You-Rak Choi, Ki-Il Kim

Published 2026-10-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Annas Malik, Ghulam Mustafa, You-Rak Choi, Ki-Il Kim

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of digital security, the most common way to hide a message relies on a specific, unchanging rulebook for scrambling letters. Imagine a giant, fixed dictionary where every letter of the alphabet is permanently swapped for another specific letter. This tool, known in cryptography as a substitution box, is the engine that makes modern encryption difficult to crack. For decades, the most trusted version of this tool has been a single, static table used by billions of devices. The problem is that because this table never changes, a skilled attacker who studies it once can build a detailed map of its weaknesses. Once that map is drawn, it can be reused again and again to break different messages, even if the secret key used to lock them changes. The table itself remains the same, so the vulnerabilities it holds remain open.

A team of researchers has proposed a solution that keeps the strength of the original tool while eliminating the danger of reusing old maps. They developed a system called QSD-SBox, which generates a completely new, unique scrambling table for every single communication session. Instead of relying on a single, fixed dictionary, the system creates a fresh one every time two devices start talking. Crucially, these new tables are not random guesses; they are mathematically guaranteed to be just as strong as the original, trusted version. By changing the concrete table with every session, the researchers found that any detailed knowledge an attacker might have gathered about a previous session becomes useless. The specific weaknesses of the old table do not transfer to the new one, forcing the attacker to start their work from scratch every time.

The researchers built this system by taking the mathematical core of the trusted, static table and wrapping it in a layer of randomization that changes with every session. They used a source of randomness derived from quantum physics—specifically, the behavior of subatomic particles—to ensure that the new tables are truly unpredictable. This process involves taking the raw data from these quantum events, cleaning it up to remove any small biases, and then using it to shuffle the input and output of the scrambling process. The result is a new table that looks different on the surface but retains the same deep, mathematical armor as the original. The team tested this approach by generating nearly one million pairs of sessions to see if patterns found in one could be used to break the next. The results were clear: the specific attack patterns that worked on the first session failed completely on the second, performing no better than random guessing.

To prove that this method works in the real world, the team built a prototype system for securing audio calls. In this test, two devices established a secure connection and began exchanging voice data. Every few seconds, they automatically switched to a new scrambling table, synchronized perfectly without the user noticing. The system successfully protected the audio, even when the network dropped packets or introduced delays. The researchers measured how long it took to create a new table and found that a standard computer could generate a fresh one in just 136 microseconds, a speed fast enough to handle real-time conversations without any lag. This demonstrated that the security upgrade does not come at the cost of performance or usability.

The study also addressed a common concern about dynamic systems: that making things change might accidentally make them weaker. The researchers rigorously checked the mathematical properties of every new table they generated. They confirmed that each one maintained the highest possible levels of resistance against known types of mathematical attacks. The new tables were not just different; they were equally robust. The only thing that changed was the specific arrangement of the numbers, which meant that the detailed "fingerprints" of the old table could not be applied to the new one. This approach effectively limits the value of an attacker's previous work, turning a long-term advantage into a series of short, isolated challenges.

While the system showed great promise in simulations and controlled tests, the researchers were careful to note its boundaries. The security of the new tables relies on the secrecy of the seed used to generate them, and the current prototype assumes that the quantum source used to create these seeds is trusted. The team also pointed out that while the system defeats attacks based on the specific layout of the table, it does not protect against attacks that target the input data before it is scrambled. Furthermore, the tests were conducted in a simulated environment, and the researchers plan to verify the results on physical hardware devices in the future. Despite these limitations, the work provides a clear path forward for a type of security that evolves with every conversation, ensuring that the tools used to protect our digital lives remain one step ahead of those who would try to break them.

Technical Summary: Limiting Cross-Session Reuse of Table-Specific Attack Information

Problem Statement
Fixed substitution boxes (S-boxes), such as the one used in AES, allow for thorough cryptographic analysis but create a vulnerability regarding the cross-session reuse of attack information. Once an attacker profiles a specific S-box—generating differential characteristics, linear approximations, favorable trails, or side-channel templates—this information remains valid across all subsequent sessions and keys, provided the S-box remains unchanged. Rekeying alone does not mitigate this risk. While dynamic S-box schemes exist to diversify tables, many rely on chaotic maps, heuristics, or runtime searches that often compromise cryptographic quality (e.g., nonlinearity or differential uniformity) or fail to provide per-instance guarantees. There is a gap in schemes that simultaneously offer provable cryptographic guarantees for every generated instance and explicitly evaluate the reduction of cross-session transfer of table-specific attack data.

Methodology: QSD-SBox
The paper introduces QSD-SBox, a session-diversification scheme for 8×8 S-boxes. The core construction generates a distinct S-box for every session using the formula $S = A_{out} \circ I \circ A_{in}$ , where:

$I$ is the multiplicative inversion in $GF(2^8)$ (the underlying primitive of the AES S-box).
$A_{in}$ and $A_{out}$ are invertible affine permutations derived from a session seed.
The seed is derived from a Quantum Random Number Generator (QRNG) based on the OTQuSbox framework, though the scheme is agnostic to the seed source (validated against CSPRNGs).

Key Technical Features:

Affine Equivalence: By constructing the S-box as an affine transformation of the inversion function, the scheme ensures that every generated instance belongs to the same affine equivalence class as the AES S-box.
Per-Instance Guarantees: Because cryptographic properties are invariant under affine equivalence, every session S-box mathematically guarantees:
- Nonlinearity (NL) = 112
- Differential Uniformity ( $\delta$ ) = 4
- Algebraic Degree = 7
- Boomerang Uniformity = 6
  These properties are achieved without runtime search or optimization.
Seed Conditioning: The seed generation pipeline involves health tests (SP 800-90B), XOR whitening to reduce bias, and conditioning via SHAKE-256 to produce a 128-byte seed. This seed drives the derivation of the affine maps and constants ( $\alpha, \beta$ ).
Implementation: A C implementation generates a session S-box in approximately 136 $\mu$ s. The scheme was integrated into a cipher (QSD-BC) mirroring AES-128 structure and a feasibility case study (QSD-Audio) for post-quantum authenticated audio.

Key Contributions

Session Diversification with Provable Guarantees: Unlike prior dynamic S-boxes that trade security for diversity, QSD-SBox provides a distinct table for every session while maintaining the established cryptographic bounds of the inversion construction.
Quantitative Evaluation of Cross-Session Transfer: The paper explicitly measures how much "table-specific" information transfers between sessions. It distinguishes between invariant information (which remains transferable by design) and table-specific information (positions of best characteristics, specific trails, side-channel templates).
Empirical Validation:
- Cryptographic Bounds: Verified over 1,000 simulated sessions and 488 hardware-seeded sessions.
- Cross-Session Analysis: Evaluated 999,000 ordered pairs of sessions.
- Side-Channel Simulation: Conducted template attacks comparing static AES S-boxes against QSD-SBox.

Results

Cryptographic Strength: Every generated S-box maintained NL=112, $\delta$ =4, degree=7, and boomerang uniformity=6. The minimum number of active S-boxes over two rounds matched the AES bound (5 active S-boxes) in all tested sessions.
Cross-Session Transfer:
- Differential characteristics, linear approximations, and two-round trails profiled on one session transferred to another only at the "chance level."
- In a simulated template attack using a static AES S-box, 50 traces were sufficient to recover a full key. When using QSD-SBox, a profile built on one session recovered no more key bytes than random guessing in the next session, even with 2,000 traces.
- The paper notes that attacks relying solely on affine invariants or S-box input leakage (which does not involve the table) remain effective, as intended; the goal is specifically to invalidate table-specific profiling.
Performance: The C implementation generates an S-box in 136 $\mu$ s. In the QSD-Audio prototype, the overhead of S-box rotation was negligible (real-time factor of $6.1 \times 10^{-4}$ in C), though Python implementations were significantly slower.
Formal Verification: The QSD-Audio handshake and frame logic were verified using ProVerif, proving authentication, secrecy, and forward secrecy properties. A replay flaw in the prototype (regarding frame index handling) was identified and fixed during this process.

Significance and Claims
The paper modestly claims that QSD-SBox is not a new nonlinear primitive designed to be stronger than the AES S-box. Instead, its significance lies in being a session-diversification mechanism that:

Preserves established per-instance cryptographic guarantees for every session.
Effectively limits the reuse of table-specific attack information (differential, linear, trail, and side-channel profiles) across sessions to the level of chance.
Demonstrates that such diversification can be achieved practically with low computational cost and without relying on heuristics that compromise security.

The authors emphasize that the security objective is narrower than claiming a "stronger" cipher; rather, it is to ensure that knowledge gained about one session's concrete table does not automatically apply to the next, forcing an attacker to re-profile for every session while the underlying algebraic strength remains constant.

More like this