PaperlayerView exact revision on arXiv

Source-linked AI summary

On the security of a class of diffusion mechanisms for image encryption

Leo Yu Zhang, Yuansheng Liu, Kwok-Wo Wong, Fabio Pareschi, Yushu Zhang, Riccardo Rovatti, Gianluca Setti

arXiv:1512.09263v1cs.CR

TL;DR

Image cryptosystems using complex dynamics have been proposed, yet some have later proved insecure despite passing statistical tests. This paper analyzes shared diffusion mechanisms in three such ciphers under plaintext attacks. It finds that recovering the equivalent key stream can require only O(1) data complexity in the analyzed equations, regardless of the key-schedule process.

  • Problem

    Image ciphers based on complex dynamics have passed statistical tests but later been found insecure, motivating security analysis of their shared cryptographic components.

    Source: §1 · p. 2

  • Method

    The paper analyzes the modulo-addition/XOR diffusion equation and a variant, then applies the analysis to three image ciphers under known- or chosen-plaintext attacks.

    Source: §1 · p. 3, §2 · p. 4

  • Results

    Under known-plaintext assumptions, the data complexity for revealing k in the equation variant is O(1).

    Source: §5.2 · p. 10

  • Takeaways & Limitations

    The analyzed diffusion mechanisms in the three ciphers provide substantially less security against plaintext attacks than desired.

    Source: §1 · p. 3

    For the modulo-addition equation, the most significant bit of k cannot be determined; k and k ⊕ 2^(n−1) are equivalent solutions.

    Source: §4.1 · p. 6

Abstract

from arXiv · show

The need for fast and strong image cryptosystems motivates researchers to develop new techniques to apply traditional cryptographic primitives in order to exploit the intrinsic features of digital images. One of the most popular and mature technique is the use of complex ynamic phenomena, including chaotic orbits and quantum walks, to generate the required key stream. In this paper, under the assumption of plaintext attacks we investigate the security of a classic diffusion mechanism (and of its variants) used as the core cryptographic rimitive in some image cryptosystems based on the aforementioned complex dynamic phenomena. We have theoretically found that regardless of the key schedule process, the data complexity for recovering each element of the equivalent secret key from these diffusion mechanisms is only O(1). The proposed analysis is validated by means of numerical examples. Some additional cryptographic applications of our work are also discussed.

1. Introduction

Image ciphers built around complex dynamics often use Fridrich’s permutation-diffusion architecture, but schemes that pass statistical tests have still proved insecure under attack. This paper analyzes shared diffusion mechanisms in three ciphers and evaluates their resistance to plaintext attacks.

1. Introduction

  • Fridrich’s architecture iterates permutation, which transposes image elements, and diffusion, which modifies their values.The paper focuses on schemes based on complex dynamic phenomena, including chaotic behavior and quantum walks.Source: §1 · pp. 1–2
  • Diffusion designs combine modulo addition with XOR, and some also use modulo multiplication or real-number arithmetic.The paper describes real-number arithmetic as increasing computational cost through more complicated operations.Source: §1 · p. 2
  • Image ciphers using complex dynamics have passed statistical tests yet later proved insecure, while cryptanalysis has usually been conducted case by case [41].Earlier general evaluations instead studied permutation-only encryption and the period distribution of the generalized discrete Cat map.Source: §1 · pp. 2–3
  • Three schemes are examined by analyzing their shared diffusion mechanisms under plaintext attacks, including cases where α and β cannot be freely chosen.The analysis derives a sufficient condition for solving the diffusion equation and evaluates its data complexity in known-plaintext settings.Source: §1 · p. 3
  • The paper presents three contributions: relating popular diffusion mechanisms to a differential equation of modulo addition, analyzing when it can be solved, and assessing three ciphers’ security.It also reports an experimental known-plaintext attack on an equation variant and notes that similar equations occur in other designs.Source: §1 · p. 3

2. Notations and main assumptions

The paper sets notation for image elements, arithmetic operations, and key scheduling, then defines known- and chosen-plaintext attack capabilities. Its analyses focus on recovering the key stream generated from the secret seed.

2. Notations and main assumptions

  • The default integer width is n = 8, and ∔, .−, ⊕, ∧, and ∥ denote modulo 2^n addition, modulo 2^n subtraction, XOR, bitwise AND, and bitwise OR.The notation also uses floor and ceiling for the nearest integers below and above a real number.Source: §2 · p. 3
  • KS denotes the operations of a specific algorithm’s key schedule, while KS(Seed) denotes generating its required key streams from a secret seed.The image and cipher-image are represented in both two-dimensional and one-dimensional formats.Source: §2 · pp. 3–4
  • In known-plaintext attacks, the adversary has plaintexts and corresponding ciphertexts; in chosen-plaintext attacks, the adversary can obtain ciphertexts for chosen plaintexts.In either model, the goal is to recover information about the secret seed or its generated key stream; the paper focuses on key-stream recovery.Source: §2 · p. 4

3. Image cryptosystems review

The three reviewed ciphers use different key-schedule processes but share similar diffusion mechanisms. Their encryption pipelines combine diffusion and permutation in different arrangements.

3. Image cryptosystems review

  • Despite different key schedules, all three schemes share a very similar diffusion mechanism, which the paper casts into a common form for security evaluation.The review’s stated scope includes Parvin’s, Norouzi’s, and Yang’s schemes.Source: §3 · p. 4
  • Parvin’s cipher uses chaotic functions for key scheduling and applies row and column circular permutations before sequential pixel diffusion.Its key streams include permutation values for rows and columns and pixel values for diffusion.Source: §3 · p. 4
  • Norouzi’s cipher uses a hyper-chaotic key schedule and performs a single bidirectional diffusion process.It generates an 8-bit key stream and computes cipher-image pixels sequentially.Source: §3 · p. 4
  • Yang’s cipher derives its key schedule from a two-particle discrete-time quantum random walk and extends Norouzi’s encryption process with diffusion and permutation.Its key streams include pixel-diffusion values and row and column permutation values; the diffusion uses the bidirectional technique.Source: §3 · p. 5

4. Problem formulation

The section formulates attacks on diffusion mechanisms while setting permutation effects aside. It reduces key-stream recovery in the examined designs to analyzing the differential equation of modulo addition (DEA).

4. Problem formulation

  • Permutation effects are set aside initially by assuming zero permutation streams for Parvin and identity permutations for Yang; whole-cipher security is deferred.The permutation schemes are considered later alongside the security of the complete cryptosystems.Source: §4 · p. 5
  • Parvin’s diffusion key-stream recovery under a known-plaintext attack (KP) is reduced to solving the DEA, while Norouzi and Yang’s schemes are reduced to it under chosen-plaintext attacks (CP).The section also investigates Norouzi and Yang’s diffusion security under KP attacks.Source: §4 · p. 5

4.1. Parvin’s di

  • For Parvin’s scheme, two plaintext–ciphertext pairs yield known parameters for solving the DEA, and recovering the remaining key-stream elements allows reconstruction of the full stream.The problem is recast for each index; k(0) and then the full stream can be calculated after the other elements are revealed.Source: §4.1 · pp. 5–6
  • The most significant bit of k is indeterminate because the modulo operation discards its carry, leaving only the n − 1 least significant bits as the recovery target.k and k ⊕ 2^(n−1) are equivalent solutions.Source: §4.1 · p. 6
  • Earlier results show that two groups of chosen queries suffice when α and β can be freely selected, but ciphertext-derived α and β cannot be freely chosen in these attacks.The section therefore analyzes the equation for known, attacker-unselectable α and β.Source: §4.1 · p. 6

4.2. Norouzi and Yang’s di

  • For Norouzi and Yang’s schemes, the section asks whether computationally intensive additions to XOR and modulo addition improve security and represents the diffusion using a plaintext-derived real-number sequence.The diffusion scheme is rewritten using the sequence associated with the plaintext image.Source: §4.2 · p. 6
  • Under CP attack, changing one plaintext pixel makes the ciphertext difference at that location coincide with the DEA, reducing equivalent key-stream recovery to solving it.The attacker’s second plaintext differs from the first at a single location.Source: §4.2 · p. 6
  • Under KP attack, the real-number sequence is independent of the secret key, and recovery becomes a nonlinear equation problem with non-negative real β.The function is g(β, k) = ⌊β · (10^8 · k)⌋ mod 256.Source: §4.2 · pp. 6–7

5. Main results

The analyses find that both the basic modulo-addition diffusion equation and its bidirectional variant remain vulnerable to plaintext attacks. For the basic equation, bit-level inference and an efficient recovery algorithm expose the key; the variant’s key stream is recovered with few known images, although incomplete recovery may not yield good visual quality.

5.1. Cryptographic strength of the equation (α ∔k) ⊕(β ∔k) = y

  • A single known triple can confirm some least significant bits of k when y has consecutive trailing ones, and can solve the equation for certain oracle outputs.The stated special outputs are 2^n − 1 and 2^(n−1) − 1.Source: §5.1 · p. 7
  • O((n −1) · g) computation produces one candidate k, improving on the brute-force algorithm’s O(2^(n−1) · g) complexity.The algorithm groups known triples by bit planes of y and uses them to update the bits of k.Source: §5.1 · pp. 7–8
  • With g = 3, the probability of confirming the first i least significant bits is relatively high for small i; tests also use 2 and 4 known image pairs.The recovered key stream is used to decrypt the Baboon cipher image.Source: §5.1 · p. 8, Figure 2 · p. 9, Figure 3 · p. 9

5.2. Cryptographic strength of the equation (α ∔k) ⊕g(β, k) = y

  • O(1) known parameter groups suffice to reveal k in the bidirectional scheme under a known-plaintext attack, so it does not improve the basic equation’s security in that setting.For the chosen-plaintext attack, the basic equation is also weak, with data complexity O(L) to break the cipher in.Source: §5.2 · pp. 9–10
  • The bidirectional scheme’s key-stream recovery rate rises from close to 67% with 1 known image to 100% with 3, but high recovery alone does not ensure acceptable visual quality.At 100% key-stream recovery, the intercepted cipher image is perfectly reconstructed; wrongly decrypted pixels spread errors to successive decryption.Source: §5.2 · pp. 10–11, Figure 5 · p. 11

6. Cryptographic applications

This section applies the analyses of Eqs. (10) and (13) to plaintext attacks on the full cryptosystems in, then discusses further security implications.

  • The section presents plaintext attacks on the full cryptosystems proposed in, drawing on the analyses of Eqs. (10) and (13).Source: §6 · p. 11
  • It briefly discusses other security implications related to the analyses.Source: §6 · p. 11

A. Cryptanalysis of Parvin’s cryptosystem

For Parvin’s cryptosystem, chosen plaintexts isolate the equivalent row and column permutation streams, which can then be recovered with data complexity O(1) + max(H, W) with overwhelming probability.

A. Cryptanalysis of Parvin’s cryptosystem

B. Cryptanalysis of Norouzi’s and Yang’s cryptosystems

Norouzi’s scheme is vulnerable in a known-plaintext attack, while chosen plaintexts recover Yang’s equivalent permutation streams.

B. Cryptanalysis of Norouzi’s and Yang’s cryptosystems

C. Other cryptographic implications

Grouping pixels to enlarge the key space does not remedy the chosen-plaintext vulnerability of Norouzi’s and Yang’s schemes; the paper also discusses implications for related diffusion mechanisms.

C. Other cryptographic implications

  • Composite-pixel representation is futile as a remedy because Norouzi’s and Yang’s schemes can still be cast into the analyzed equation under chosen-plaintext attack.Source: C. Other cryptographic implications · p. 12
  • The analyzed diffusion equation has a key-search loophole that reducing the key space to O(1) cannot fix by choosing a larger n.The authors recommend stronger diffusion schemes against known- and chosen-plaintext attacks.Source: C. Other cryptographic implications · p. 13

7. Conclusion

The paper analyzes two diffusion equations in three ciphers and finds that equivalent key streams can be recovered with O(1) known plaintexts, regardless of the key-scheduling process.

7. Conclusion

  • O(1) known plaintexts suffice to solve both studied diffusion equations, as confirmed by the algorithms and numerical experiments.The equations are (α ∔k) ⊕(β ∔k) = y and (α ∔k) ⊕g(β, k) = y.Source: §7 · p. 13
  • The three case-study ciphers are weak under plaintext attacks despite using key schedules based on chaotic, hyper-chaotic, or quantum-computation processes.The equivalent key streams can be retrieved from a small number of plain-images.Source: §7 · p. 13
  • The authors conclude that most image ciphers with a single-round permutation-diffusion architecture are insecure against plaintext attacks.They also identify diffusion equations involving modulo multiplication as a possible extension of the analysis.Source: §7 · p. 13

Appendix A. Proof of Theorem 2

The proof rewrites Eq. (10), derives the next-bit relation, and uses a condition on the observed values and carry to determine key bits by induction.

Appendix A. Proof of Theorem 2

  • Eq. (10) is recast in an equivalent form, and the next bit of ˜y is computed from preceding bits and carry values.The derivation uses α_i, β_i, k_i, c_i, and ˜c_i for i ∈ [0, n−2].Source: Appendix A · p. 13
  • The proof defines c_i as the carry for (α ∔k) and ˜c_i as ˜y_i ⊕ c_i.Table A.3 lists ˜y_{i+1} for all possible values of α_i, β_i, ˜y_i, k_i, and c_i.Source: Appendix A · p. 14, Table A.3 · p. 14
  • When y_i = ˜y_i ⊕ α_i ⊕ β_i = 1 and c_i is known, the table indicates that k_i can be determined.This condition identifies the relevant table columns used in the proof.Source: Appendix A · p. 14, Table A.3 · p. 14
  • The induction starts with i = 0, then assumes the m least significant bits of k are confirmed and extends the argument to i = m + 1.The proof uses known parameters and carry values from the previous induction step to determine the next key bit.Source: Appendix A · p. 14
  • The induction is completed, proving the theorem.Source: Appendix A · p. 14
Loading 1512.09263v1…