-1
$\begingroup$

This question is related to this:

When all shares of a secret are given to adversary as a permuted matrix

I think the below question is a simplified version of that.

Assume we have a 40-bit message $m$ (or 40-bit string). The message is picked from a universe of size one; so $m \in U$, where $|U|=1$.

We permute the bits in $m$. So we would have a 40-bit string, $m'$

Question: Given the message $m'$ can the adversary learn the original message, $m$, with a non-negligible probability?

| improve this question | |
$\endgroup$
  • $\begingroup$ Surely |U| is 2^40, if U is the set of all 40-bit binary numbers? $\endgroup$ – r3mainer Jan 28 '16 at 19:35
  • $\begingroup$ @squeamishossifrage It depends how to look at it. For simplicity I defined the message domain as $U$. consider $U$ as a small domain of valid English name. So not all $2^{40}$ are valid names. Here I assumed that there exists only one valid name. $\endgroup$ – user153465 Jan 28 '16 at 20:37
  • $\begingroup$ "Non-negligible" is meaningless if the key size is fixed, as is the case here (the key is a permutation of a finite set). $\endgroup$ – fkraiem Jan 29 '16 at 4:09
  • $\begingroup$ @fkraiem What if I mix the message original bit with some random bits (e.g. 40-bit) and then shuffle all? $\endgroup$ – user153465 Jan 29 '16 at 10:03
4
$\begingroup$

I'm not sure I understand your question entirely. If there is only one possible message, then the ciphertext can be trivially decrypted simply by choosing this message.

I'll assume instead that the ciphertext contains the shuffled bit pattern of a name chosen from a set of more than one name. The problem with bit shuffling is that the number of set bits doesn't change. This significantly reduces the number of plaintexts that could correspond to a particular ciphertext.

For example, when the 200 most popular baby names of 2015 are written in uppercase ASCII, the number of set bits in these names is distributed as follows:

(Who needs Excel when we have Google Sheets to play with?

AVA is the only name that has 8 set bits, and even in the worst case of names that have 15 set bits, there are only 20 names to choose from (down from a total of 200). In other words, we can eliminate at least 90% of the possible plaintexts simply by counting the number of bits in the ciphertext.

If you use the same technique to encrypt more than one message, then you'll leak additional information about the exact permutation you're using. This will make the codebreaker's job even easier.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.