How secure is bit level permutation?

Question

Could anyone explain how secure is bit level permutation? What is the most serious threat against the security of this kind of cipher?

Answer 1

As a single transformation considered in isolation, a fixed bitwise permutation does not offer any security. If you examine the hamming weight (the quantity of '1' bits) of the data before and after a bitwise permutation, you will notice that it remains unchanged. A bitwise permutation simply shuffles the order of the bits of data. Repeated applications will not modify the hamming weight, and will just shuffle the bits more.

Since the permutation is fixed, we concede that anyone can calculate it at will, so anyone can calculate the inverse at will. This is pretty much the case for any fixed permutation. Since there is no additional variable that is kept secret (the key), anyone with the data and the permutation has all the information they need to invert it.

A single transformation is rarely "good enough" in cryptography, so that much can be said about almost anything. However, when considered in conjunction with other transformations, such as an s-box and a key addition layer, the result is equal to more then the sum of the components. Many strong modern ciphers are built from combinations of bitwise permutations combined with other operations.

Bitwise permutations are often the source of diffusion in modern ciphers, and diffusion is a critical part of the security of modern ciphers.

One potential downside of bitwise permutations is efficiency in software. Modern processors typically operate on words that are a minimum of 1 byte in size. To address the individual bits is possible via masking and shifting, but doing so requires more operations then we would like.

For example, a bitwise permutation that operates on 8 bytes (with 8 bits per byte) and spreads out each byte evenly among output bytes has good diffusion, but has a quadratic algorithmic complexity, which can easily make it the slowest single component of the cipher.