# Revealing random bit permutation

I am new in cryptography. I want to determine the complexity of revealing a random bit permutation which is used as block cipher for plaintexts (bitstrings of length n). An adversary catches different ciphertexts (the permuted bitstrings of length n) and he also knows the set of possible plaintexts. If he tries all possible inverse permutations at the end there are more permutations that result in legal plaintexts. The difference is that all of the remained permutations result in different sending order of the plaintexts. Is it possible to reveal the used permutation?

• Block ciphers are much more complex than bit-wise permutations. Commented Aug 6, 2014 at 4:33

I thought you were using a block cipher, i.e. a pseudorandom permutation. Instead as per your comment you are only permuting the order of the plaintext bits. This is not secure.

For example, you can imagine the bit permutation is an n-by-n square matrix, where each row and column has a single 1 and the rest 0s. The input and output are then vectors of size n.

Take a random input and output pair. If each has $\frac{n}{2}$ 1s and 0s on average, you get to know $\frac{n}{2}$ matrix evements from each row – those where the input is different from the output must be 0. So you get about half the matrix elements.

After two random pairs of plaintext and ciphertext you know on average about $\frac{3}{4}$ of the matrix. Then $\frac{7}{8}$, etc. You need on the order of $log_2(n)$ pairs to find the whole matrix. (With non-random plaintext it may take slightly more pairs than with random.)

Even before leaking the whole permutation, you will leak all sorts of information about the plaintext – for example, the number of 1 and 0 bits will be the same in the ciphertext. Two plaintexts that differ in $k$ bits will have ciphertexts differing in $k$ bits, etc.

Old answer based on using a block cipher:

Is it possible to reveal the used permutation?

Not if the keyspace is large enough. There are $2^n!$ different $n$-bit permutations, but a block cipher typically has only a 128-bit or 256-bit keyspace, so not all permutations are possible. Unless the cipher is broken, the only way to narrow it down is a brute force search of the keyspace, which is intractable for 128+ bits.

As an aside, you would be using the block cipher directly on plaintexts. Unless the plaintexts are random (or known unique) bitstrings of length $\le n$ bits, that is not a secure mode of operation, it is ECB and is not semantically secure.

• Maybe I explained wrongly, I permute the bit positions in the plaintext, so for n-bit plaintext there are n! possible permutations.
– Anna
Commented Aug 4, 2014 at 8:57
• @Anna, I misunderstood, answer updated. Why are you doing that?
– otus
Commented Aug 4, 2014 at 11:22
• yes, but the adversary only knows the set of possible plaintexts and the set of possible ciphertexts and does not know how the plaintexts and the ciphertexts are paired.
– Anna
Commented Aug 4, 2014 at 12:45
• @Anna, the attacker also knows all plaintexts with exactly $k$ bits set also have $k$ bits set in the ciphertext. That makes the attack less efficient, if there are a lot of plaintexts with the same number of bits set, but it is still possible. E.g. if all those plaintexts have bit $i$ set and all the possible ciphertexts have bit $j$ unset, then that element of the matrix is zero. Exact number of pairs and plaintext distribution affect whether it reveals the permutation fully or not.
– otus
Commented Aug 4, 2014 at 12:45
• @otus Would it help somewhat if the plaintext $p$ were to be expanded so that it becomes $p' = p \Vert \bar{p}$? (ie. concatenating the plaintext with its complement), this would make the number of 1s and 0s equal and its trivial to undo whilst "decrypting". Not trying to hijack the question, just trying to give it a little more depth.
– mpr
Commented Aug 5, 2014 at 13:13