Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks

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×(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·MN)O(32·MN) and O(16·n0·MN)O(16·n0·MN) respectively, where n0 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×N and with L different levels of values. The corresponding spatial complexity and computational complexity are only O(MN  ) and O(⌈logL(MN)⌉·MN)O(⌈logL(MN)⌉·MN) respectively. In addition, some specific remarks on the performance of the image scrambling encryption algorithm are presented.