Lately, a number of image encryption algorithms that are either based on pixel level or bit level encryption have been proposed. However, not only pixel level permutation, but also bit level permutation has its intrinsic drawbacks. This paper proposes a new cryptosystem to address these drawbacks. Different kinds of permutation algorithms are first comprehensively analyzed and compared. Because, from a bit level perspective, an image can be considered as a natural three-dimensional (3D) bit matrix (width, height, and bit length), a new 3D bit matrix permutation is proposed, in which the Chen system is used to develop a random visiting mechanism to the bit level of the plain-image. By combining aspects of the Chen system with a 3D Cat map in the permutation stage, a new mapping rule is developed to map one random position to another random position (that is, double random position permutation) in the 3D matrix rather than using traditional sequential visiting to the plain-image. Simulations are carried out and the results confirm the security and efficiency of our new cryptosystem. •The problems of pixel- or bit-level permutation are analyzed.•A 3D bit level permutation is proposed.•A random visiting to plain-image is proposed.