0
$\begingroup$

Consider the following very simple cipher, where, to send length $n$ bit-strings, we randomly correspond the numbers $1, 2, 3, ..., N$ with $n$ bits, so the key is the correspondence between each integer and the bit value it maps to. Then, to share a bit-string, Alice will send Bob a permutation of the integers $1, 2, ..., N$.

Obviously this cipher is not good for use, but I am wondering the following: am I correct in assuming that so long as the adversary does not obtain any plaintext/ciphertext pairs, Alice and Bob can share multiple messages with the same key, as each new message, to the adversary, is just a permutation of the numbers $1, 2, ..., N$?

$\endgroup$
1
$\begingroup$

so long as the adversary does not obtain any plaintext/ciphertext pairs, Alice and Bob can share multiple messages with the same key

Even if Alice and Bob do not explicitly disclose plaintext/ciphertext pairs, if they care for confidentiality, they must not use this cipher, except maybe for essentially random plaintext and when leaking the Hamming weight of plaintext is no issue (e.g in re-encryption).

Problem is, the more ciphertext, the easier it is to reconstruct all or part of the permutation given some model of plaintext redundancy. For example, if the plaintext is known to be ASCII restricted to uppercase and space, then groups of 7 bits where one is rarely 1 and the others 6 are always 0 when that occurs must belong to the same character, and the rare 1 is the bit set in a space, coded 00100000 in binary (while letters are 010xxxxx). The bit among the remaining 6 that is 1 in all letters is identified by this characteristic. Then frequency analysis reveals the mapping of the remaining 5 bits, and the corresponding letters. Then all that remains from the cipher is a fixed substitution of symbols.

Even with a single block of $n$ bits, if we know that the plaintext is restricted to a small set (e.g. names as written on the class roll), the Hamming weight might allow decryption, and will likely narrow the possible names.

$\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.