💻 computer science

Every keyed DNA operation is affine: algebraic limits of DNA diffusion layers in image encryption

This paper proves that every keyed DNA operation used in image encryption is structurally affine over the binary field, rendering such diffusion layers algebraically weak and vulnerable to attacks, while proposing a verified, zero-cost replacement to overcome these inherent limitations.

Original authors: Ihab Shakir, Hossein Kheiri

Published 2026-10-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ihab Shakir, Hossein Kheiri

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 digital world, protecting an image from prying eyes often involves scrambling its data so thoroughly that the original picture becomes unrecognizable. For over fifteen years, a popular method for doing this has borrowed a concept from biology: DNA. Just as biological DNA uses four chemical bases to store genetic instructions, these encryption schemes treat the four bases—Adenine, Cytosine, Guanine, and Thymine—as a secret code for image pixels. The process works by translating the numbers that make up a picture into these four letters, mixing them with a chaotic, unpredictable key, and then translating them back. The hope has been that this biological metaphor adds a layer of complexity that makes the image impossible to crack. Researchers have spent years designing these systems, testing them with standard statistical checks to ensure the scrambled images look random and that changing a single pixel in the original picture causes a massive, chaotic change in the encrypted version.

However, a new analysis suggests that this entire field has been built on a structural misunderstanding. A team of mathematicians at the University of Tabriz has discovered that the very feature designers believed made these systems flexible—the ability to rearrange the four DNA letters in any order—is actually a fatal weakness. They found that because there are only four letters in the alphabet, every possible way of rearranging them follows a simple, predictable mathematical pattern. It is as if, no matter how you shuffle a deck of four cards, the result is always a variation of a single, basic rule. This realization means that for more than a decade, the encryption methods relying on this DNA layer have been mathematically linear, a property that allows them to be broken with elementary techniques, regardless of how complex the rest of the system appears.

The researchers did not just point out a flaw in one specific design; they examined the entire design space. They looked at every single possible table of operations that could be used to mix the DNA letters, covering hundreds of thousands of variations, and tested them under every possible encoding rule and scheduling method. Their conclusion is absolute: every single one of these operations is mathematically "affine," a term that describes a relationship that is essentially a straight line. In the world of cryptography, straight lines are dangerous because they can be solved easily. The team proved that no matter how many times a designer repeats the process or how they shuffle the rules, the result remains a straight line. This explains why so many different encryption schemes, proposed by different groups over the years, have fallen to nearly identical attacks. The failure was not an accident of a bad design choice; it was an inevitable consequence of using an alphabet with only four symbols.

The study also investigated a newer approach where designers tried to fix this by mixing two different parts of the image together, hoping to create a more complex, non-linear effect. While this method does raise the complexity slightly, the researchers found that it hits a hard ceiling. Even with two inputs, the mathematical complexity cannot rise beyond a very low level. Furthermore, the specific operations used in recent designs suffer from a second problem: they are "associative," meaning the order in which the mixing happens does not matter. This property causes the entire chain of mixing to collapse into a simple sum, accumulating hidden patterns that an attacker can detect without needing to know the secret key. The researchers identified that half of the operations currently in use are completely linear, and the other half, while slightly more complex, still fail to provide the necessary protection.

To address these issues, the team proposed a simple, zero-cost replacement. They identified a specific set of mixing rules that are not associative and that allow the complexity to grow as the mixing chain gets longer. This new method removes the hidden patterns and ensures that the system does not rely on chance to be secure. When they tested this replacement on real medical images, the results were verified to be perfectly reversible, meaning the original image could be recovered exactly, while the security properties were significantly improved. Crucially, the standard statistical tests used by the field to judge security failed to distinguish between the broken designs and the improved one. The standard tests showed the same "ideal" results for all of them, proving that these common metrics are blind to the algebraic weaknesses that actually determine security.

The paper concludes that the field has been looking in the wrong place for evidence of strength. The researchers argue that the community should stop relying solely on statistical checks and start measuring the algebraic complexity of the mixing operations directly. This measurement can be done in seconds and would immediately reveal whether a design is fundamentally secure or doomed to fail. They found that in over a hundred design papers, the concept of algebraic complexity was never mentioned, while the number of possible DNA arrangements was cited repeatedly as a sign of variety. The researchers showed that this number, which designers thought represented freedom, actually represents a trap. By moving beyond the four-letter alphabet or by carefully selecting non-associative operations, designers can escape this trap, but the current reliance on the four-letter DNA metaphor has created a structural barrier that no amount of statistical tweaking can overcome.

Technical Summary: "Every keyed DNA operation is affine: algebraic limits of DNA diffusion layers in image encryption"

Problem Statement
For over fifteen years, image encryption schemes have utilized DNA coding combined with chaotic systems. Despite extensive statistical evaluations (entropy, histograms, correlation), these schemes have been repeatedly broken by strikingly similar algebraic attacks. The literature has treated the $4! = 24$ possible encoding rules as an inventory of options, but has failed to recognize that this number corresponds to the order of the affine group $AGL(2, 2)$ . Consequently, the fundamental algebraic weakness of the DNA diffusion layer—specifically its lack of nonlinearity—has been overlooked. The paper addresses the structural question: what algebraic degrees are attainable within the DNA design space, and why have previous cryptanalyses consistently succeeded?

Methodology
The authors employ a structural algebraic analysis rather than scheme-specific cryptanalysis. The study is grounded in the following working hypotheses reflecting published constructions:

Alphabet: The layer operates on a 4-symbol alphabet ( $\Sigma = \{A, C, G, T\}$ ), identified with $\mathbb{F}_2^2$ .
Operation: Diffusion is performed symbol-wise via a $4 \times 4$ operation table.
Decryptability: The operation must be invertible in the first argument (a bijection for fixed keys).
Balance: In chained constructions, the operation must be balanced in the second argument (a bijection for fixed plaintexts).

The methodology involves:

Group Theoretic Proof: Comparing the size of the symmetric group $Sym(\Sigma)$ with the affine group $AGL(2, 2)$ to determine the nature of all possible bijections.
Exhaustive Enumeration: Machine-checked verification of all 331,776 admissible operation tables and all 576 Latin square operations (satisfying both invertibility and balance).
Algebraic Indicators: Computing the algebraic degree, differential uniformity (DU), and nonlinearity (NL) for all admissible operations.
Comparative Analysis: Evaluating recent "chained" designs (where current blocks depend on previous blocks) and proposing a zero-cost replacement operation.
Corpus Analysis: A bibliometric review of 154 documents to assess the adoption of algebraic metrics in the field.

Key Contributions

Impossibility Theorem (Theorem 1): The paper proves that every decryptable keyed DNA operation is affine. Since $|AGL(2, 2)| = 24 = |Sym(\Sigma)|$ , every bijection of the DNA alphabet is an affine map over $\mathbb{F}_2$ . Consequently, any composition of encoding rules, key schedules, and rounds results in an affine transformation with algebraic degree 1. This explains why previous attacks (e.g., [4, 13, 14]) succeeded; they were not exploiting specific flaws but the inherent structure of the design space.
Ceiling Theorem (Theorem 6): The authors investigate the only potential escape route: using two plaintext-dependent operands (chaining). They prove that even in this case, the algebraic degree is capped at 2. Furthermore, for all 576 admissible operations (Latin squares of order 4), the differential uniformity is pinned at its worst possible value ( $DU=16$ ) and nonlinearity is zero ( $NL=0$ ). No choice of operation can improve these metrics.
Boundary Theorem (Theorem 8): The obstruction is identified as a property of the alphabet size, not the operations. The paper proves that $AGL(m, 2) = Sym(\Sigma_m)$ if and only if $m \le 2$ . Thus, the 4-letter DNA alphabet is the largest size for which every bijection is affine. Larger alphabets (e.g., 8 letters) allow for abundant non-affine substitutions.
Diagnosis of Chained Designs: The paper analyzes four recent schemes using a chained construction. It identifies two defects:
- Affine Menu: Half of the operation menu (XOR, XNOR) remains affine even with two operands, leaving the chain's nonlinearity to chance.
- Associative Collapse: The use of associative operations (like $Z_4$ addition) causes the chain to collapse into a prefix sum, accumulating $2^k - 1$ image-independent linear structures.
Zero-Cost Replacement: A specific non-associative, degree-2 operation is proposed. It maintains the same table size and decryption cost but ensures the chain's algebraic degree grows with its length and limits linear structures to a constant (3), removing the specific defects of the associative designs.
Experimental Validation: The authors demonstrate that standard statistical batteries (entropy, NPCR, UACI) are blind to these algebraic distinctions. The "avalanche effect" reported in literature is shown to be an artifact of image-hash seeding (which changes the keystream entirely) rather than the diffusion layer itself. When the seed is fixed, the layer's diffusion is negligible.

Results

Affinity: All 331,776 admissible keyed operations are affine (degree 1).
Chaining Limits: Even with two plaintext operands, the maximum degree is 2, and $DU=16, NL=0$ for all admissible operations.
Linear Structures: Associative chaining accumulates $2^k - 1$ linear structures, whereas the proposed non-associative replacement holds them constant at 3.
Statistical Blindness: The three variants (published, restricted, replacement) are statistically indistinguishable using standard metrics, despite having vastly different algebraic properties.
Corpus Gap: In a review of 122 design papers, the terms "algebraic degree," "differential uniformity," and "algebraic weakness" appear zero times. The knowledge exists in reference works but has not reached the design community.

Significance and Claims
The paper claims that the algebraic degree is the critical metric missing from the evaluation of DNA-based image encryption. It argues that:

The repeated failures of DNA schemes are not accidents but inevitable consequences of the 4-letter alphabet's algebraic structure.
The standard statistical battery is insufficient to detect these structural weaknesses.
The proposed "certificate" (computing degree, DU, and NL) is computationally cheap (seconds) and should be included in evaluation tables.
The field must either restrict/replace operations within the 4-letter alphabet (improvement, not repair) or abandon the 4-letter alphabet entirely to achieve nonlinearity.

The authors are modest in their claims, stating that the proposed replacement operation is an "improvement, not a repair," as the fundamental limits of the 4-letter alphabet (degree $\le 2$ , $DU=16$ , $NL=0$ ) cannot be overcome without changing the alphabet size. The work serves as a design-side diagnosis rather than a new attack vector.

Technical Summary: "Every keyed DNA operation is affine: algebraic limits of DNA diffusion layers in image encryption"

More like this