Recently it was shown that permutation-only multimedia ciphers can completely be broken in a chosen-plaintext scenario. Apparently, chosen-plaintext scenario models a very resourceful adversary and does not hold in many practical situations. To show that these ciphers are totally broken, we propose a cipher-text only attack on these ciphers. To that end, we investigate speech permutation-only ciphers and show that inherent redundancies of speech signal can pave the path for a successful cipher-text only attack. For this task different concepts and techniques are merged together. First, Short Time Fourier Transform (STFT) is employed to extract regularities of audio signal in both time and frequency. Then, it is shown that cipher-texts can be considered as a set of scrambled puzzles. Then different techniques such as estimation, image processing, branch and bound, and graph theory are fused together to create and solve these puzzles. After extracting the keys from the solved puzzles, they are applied on the scrambled signal. Conducted tests show that the proposed method achieves objective and subjective intelligibility of 87.8% and 92.9%. These scores are 50.9% and 34.6% higher than scores of previous method.