Source-linked AI summary
Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks
Chengqing Li, Kwok-Tung Lo
TL;DR
The paper asks whether a chaos-based image scrambling algorithm built from binary permutations can withstand known- or chosen-plaintext attacks. It constructs an optimal tree-based attack, extends it to general permutation-only schemes, and reports low spatial and computational complexities while discussing performance limitations.
Problem
The paper analyzes the security of a chaos-based image permutation algorithm and the broader vulnerability of permutation-only multimedia encryption schemes.
Method
The paper constructs a binary-tree attack for the binary scheme and extends the approach with a multi-branch tree to general permutation-only encryption.
Results
The binary attack has spatial complexity O(32 · MN) and computational complexity O(16 · n0 · MN), while the general attack has spatial complexity O(MN) and computational complexity O(⌈log_L(MN)⌉ · MN).
Takeaways & Limitations
Permutation-only multimedia encryption schemes can be efficiently broken with O(⌈log_L(MN)⌉) known/chosen-plaintexts under the stated attack model.
Takeaways & Limitations
The studied algorithm uses Logistic-map sequences whose randomness is not considered adequate by the cited analysis, and it does not consider plaintext-change sensitivity.
Abstract
from arXiv · showhide
Recently, an image scrambling encryption algorithm of pixel bit based on chaos map was proposed. Considering the algorithm as a typical binary image scrambling/permutation algorithm exerting on plaintext of size $M\times (8N)$, this paper proposes a novel optimal method to break it with some known/chosen-plaintexts. The spatial complexity and computational complexity of the attack are only $O(32\cdot MN)$ and $O(16\cdot n_0\cdot MN)$ respectively, where $n_0$ is the number of known/chosen-plaintexts used. The method can be easily extended to break any permutation-only encryption scheme exerting on plaintext of size $M\times N$ and with $L$ different levels of values. The corresponding spatial complexity and computational complexity are only $O(MN)$ and $O(\lceil\log_L(MN)\rceil \cdot MN)$ respectively. In addition, some specific remarks on the performance of the image scrambling encryption algorithm are presented.
1. Introduction
The paper examines a chaos-based binary image permutation algorithm and develops attacks that exploit its permutation-only structure. It also extends the attack to broader permutation-only multimedia encryption schemes and assesses the studied algorithm’s performance.
- The studied algorithm scrambles binary pixel bits using a pseudo-random sequence generated by a chaotic logistic map.
- The paper proposes an optimal known/chosen-plaintext attack against the studied image permutation algorithm.
- The attack is extended to permutation-only encryption schemes operating on elements with different value levels.
- The paper also provides remarks on the performance of the studied image permutation algorithm.
2. The image permutation algorithm under study
The studied scheme encrypts grayscale images by representing pixels as a binary matrix and applying repeated vertical and horizontal permutations driven by a chaotic logistic-map sequence. Its secret key and initialization procedures generate the permutation controls used across encryption rounds.
- The plaintext is a grayscale M × N image represented in the value domain Z256.
- The image is further represented as an M × (8N) binary matrix for bit-level permutation.
- The secret key contains positive integers m, n, and T, plus the logistic-map initial condition x0 and control parameter µ.
- Initialization generates a chaotic sequence from x0 and derives permutation vectors and matrices by ranking sequence elements.
- Each encryption round performs vertical permutation followed by horizontal permutation, then repeats the operations for T − 1 additional rounds.
- Decryption reverses the encryption-round order, swaps the two permutation-step orders, and exchanges the corresponding equation sides.
3. Cryptanalysis
The paper breaks the binary image permutation scheme by constructing a binary tree from known plaintext–ciphertext pairs, estimating the permutation matrix, and evaluating attack performance. It also reports practical recovery behavior, complexity, and weaknesses in the underlying encryption design.
- Known-plaintext attack: Known-plaintext attacks compare plaintext and ciphertext bit positions to construct a binary tree whose leaves constrain the secret permutation.Each node stores plaintext and ciphertext position sets; repeated pairs update and expand the tree.
- Known-plaintext attack: The estimated permutation matrix has Π_i=1^P(|B_i|!) possible assignments, and this uncertainty decreases as the number of known images increases.A leaf determines a mapping uniquely when |B_i|=1; otherwise, the remaining assignments must be guessed.
- Experimental performance: For 256 × 256 images, more than 19 known images are required for the theoretical condition, while 20-image recovery restores visual information despite only 35.8% of pixels being exactly correct.Natural-image redundancy and visual tolerance make many incorrect pixels close to their true values.
- Experimental performance: Breaking performance is good when n0 ≥20, but improvement becomes nearly flat when n0 ≥25 because neighboring natural-image bit patterns are highly redundant.The experiments also show that the uniform-distribution analysis applies to ordinary natural images.
- Complexity: The attack requires spatial complexity O(32 · MN) and computational complexity O(16 · n0 · MN).These bounds apply to the proposed known-plaintext attack on the binary image permutation scheme.
- Performance remarks: The scheme has weak randomness because its permutation vectors depend on Logistic-map sequences, and it lacks sensitivity to plaintext changes.The paper also notes that the permutation algorithm does not provide the ideal one-half probability of ciphertext-bit changes after a single plaintext-bit change.
4. Known/chosen-plaintext attack on any permutation-only multimedia encryption schemes
The paper replaces costly set-intersection attacks on permutation-only multimedia encryption with a multi-branch tree that estimates the permutation matrix from known or chosen plaintexts. The resulting attack uses O(⌈log_L(MN)⌉) plaintexts, O(MN) spatial complexity, and O(⌈log_L(MN)⌉·MN) computational complexity.
- General permutation-only model: Permutation-only multimedia encryption can be represented by a permutation matrix W over plaintext positions, with L denoting the number of different plaintext values.The matrix maps each plaintext entry to its secret ciphertext position.
- Baseline attack: The baseline attack compares plaintext–ciphertext pairs, intersects candidate-position sets, and selects a position from each final set to estimate W.Its set-intersection step has computational complexity O(n0·MN^2).
- Multi-branch tree attack: The proposed multi-branch tree replaces set intersections with 2L child branches that group plaintext and ciphertext positions by their values.Each node stores child pointers, two position sets, and one cardinality; construction updates these sets and resets processed nodes.
- Multi-branch tree attack: After iterative updates and expansions, mapping the two sets at every leaf estimates the permutation matrix W.The tree is expanded by finding nodes whose cardinality exceeds one and applying the same grouping operations.
- Complexity result: O(⌈log_L(MN)⌉) known/chosen plaintexts, O(MN) spatial complexity, and O(⌈log_L(MN)⌉·MN) computational complexity are sufficient to break the scheme.This computational cost is lower than the O(⌈log_L(MN)⌉·MN^2) complexity estimated for the earlier attack.
5. Conclusion
The paper analyzes an image permutation encryption algorithm and proposes an optimal attack with an extension to broader permutation-only multimedia schemes. It also presents performance remarks and argues that secure image encryption should combine traditional cryptography with image-specific properties.
- The paper analyzes the security of an image permutation encryption algorithm.
- It proposes an optimal attack on the binary image permutation algorithm and extends the method to permutation-only multimedia encryption schemes.
- The paper provides performance remarks and concludes that image encryption security should combine traditional cryptography with image-specific properties.