Paper 2004/374 Original: eprint.iacr.org/2004/374 ↗

A general quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks

Abstract

In recent years secret permutations have been widely used for protecting different types of multimedia data, including speech files, digital images and videos. Based on a general model of permutation-only multimedia ciphers, this paper performs a quantitative cryptanalysis on the performance of these kind of ciphers against plaintext attacks. When the plaintext is of size $M\times N$ and with $L$ different levels of values, the following quantitative cryptanalytic findings have been concluded under the assumption of a uniform distribution of each element in the plaintext: 1) all permutation-only multimedia ciphers are practically insecure against known/chosen-plaintext attacks in the sense that only $O(log_L(MN))$ known/chosen plaintexts are sufficient to recover not less than (in an average sense) half elements of the plaintext; 2) the computational complexity of the known/chosen-plaintext attack is only $O(n\cdot(MN)^2)$, where n is the number of known/chosen plaintexts used. When the plaintext has a non-uniform distribution, the number of required plaintexts and the computational complexity is also discussed. Experiments are given to demonstrate the real performance of the known-plaintext attack for a typical permutation-only image cipher.