Cryptographic Symmetric Stream Cipher

Question

Let me know a cryptographic symmetric stream cipher system with only two functions say S() and P() and it should satisfy the following conditions:

1. There will be two independent computers say M1 and M2 (no connection exists between them) and only one function should be stored in a machine.

   i.e. Function S() will be executed on machine M1 and the function P() on machine M2

2. User selects a random string of bits (say X) of desired length (L) as input

3. User selects a machine randomly (either M1 or M2) and executes the function with the selected random string X as input to it.

   i.e. If machine M1 is selected then the function S() will be executed to produce a output Y = S(X)

4. Then the user executes the other function P() with Y as input to produce the original random string X

   i.e. X = P(Y)

5. And again user repeats the process in reverse order using the same random string X as input

   i.e. The function P() in machine M2 will be executed to produces a output Z = P(X)

6. And again the user executes the other function S() with Z as input to produce the original random string X

   i.e. X = S(Z)

7. Length of outputs (Y and Z) should be equal to the length of input X

8. Outputs Y and Z should be nonlinear with respect to the input X and

9. Output of S(X) and P(X) should be different i.e. Y != Z

10. In simple, it should demonstrate S(P(X)) = P(S(X)) = X

    i.e. function S and P are inverses of each other.

A. How secure such a cipher?

B. I feel such functions output may be difficult for any known cryptanalysis, if not, why?

C. Is it easy/hard to design such a system?

Answer 1

Whenever you have two functions such that, for any X and any Y, X == S(P(X)) and also Y == P(S(Y)), then X and Y are bijective functions.

With modern secure communication systems, exactly the same plaintext message can be encrypted to many different ciphertext messages -- in particular, they are designed such that the message "attack" is unlikely to encrypt to the same ciphertext twice -- so therefore their "encryption" and "decryption" functions are not bijective.

Nevertheless, many classic ciphers are bijective, and often several of the parts inside a modern secure communication system are also bijective.

(The complete ciphertext message for a modern secure communication system typically begins with a random initialization vector or other nonce, has a "body" generated by some bijective function applied to the plaintext -- the particular bijective function is selected by a combination of the initialization vector and the encryption key -- and ends with a message authentication code.).

reciprocal ciphers

A cipher where P() and S() are not only bijective, but are the same function -- i.e., for any X, P(X) == S(X), and X == P(P(X)) -- is common, and known as a reciprocal cipher.

Some of the more famous reciprocal ciphers are:

• The Enigma machine was a reciprocal cipher machine
• ROT13
• Beaufort cipher
• Kama-sutra ciphers
• XOR-based stream ciphers
• One Time Pads (both XOR and Beaufort cipher versions)

Most mechanical cipher machines use a reciprocal cipher, so it wouldn't need a separate "encode mode" and "decode mode".

non-reciprocal bijective ciphers

Many classic ciphers are bijective, but not reciprocal: S(X) != P(X).

For example, the following ciphers are bijective but (usually) not reciprocal:

• monoalphabetic substitution ciphers (except for Kama-sutra ciphers), and in particular the Caesar cipher (except for ROT13).
• The standard Vigenère cipher, and the "variant Beaufort" cipher.
• One Time Pads (the Vigenère cipher version)
• transposition cipher (except for a few "paired-up" reciprocal transpositions)
• permutation cipher

Practically all modern ciphers are based on either stream ciphers (RC4, A5/2, Solitaire cipher, etc.) or single-block ciphers (AES, DES, etc.), which are bijective but (almost always) not reciprocal.

Many modern single-block ciphers are built with a Feistel network structure that, in each round, cascades a reciprocal permutation E ("swap the left and right half of the block") and a keyed reciprocal substitution cipher U, to build a non-reciprocal bijective encryption function S(x) == E(U(X)) != P(X) = U(E(X). It is widely believed that practically any non-linear function can give adequate security if it is iterated over enough rounds.

(Is it a coincidence that you used the names S() and P() that have the first letter of two common operations in cryptography, substitution and permutation, aka confusion and diffusion ?)

security

These bijective ciphers (both reciprocal and non-reciprocal) have a wide range of security, covering both ends of the spectrum:

• Monoalphabetic substitution ciphers (aka cryptograms) published in newspapers as puzzles that are daily cracked by amateurs.
• One-time pads which (in both reciprocal versions, and also the non-reciprocal version) are uncrackable.

Answer 2

Ignoring all the seemingly irrelevant fluff about randomly selected computers, it looks like you want two permutations $S$ and $P$ on the set of $L$-bit bitstrings, such that $S = P^{-1} \ne P$. Presumably, you also want these specific functions to be chosen from a large family of such functions, according to some key $K$, in such a way that they will appear indistinguishable from random permutations to some reasonable class of attackers who do not know $K$.

If $L$ is fixed, then any $L$-bit block cipher (used directly, i.e. in ECB mode) will satisfy your requirements; in particular, for certain values of $L$ such as $L = 128$, there are plenty of well studied options (like AES).

As for security, a secure block cipher is (supposed to be) a pseudorandom permutation, which is about the strongest security property we can demand of a deterministic permutation; however, like any other deterministic encryption scheme, it cannot achieve IND-CPA security.

If $L$ is variable (but still a whole number of bits), you could use a variable-length block cipher, such as XXTEA or the Hasty Pudding Cipher. More generally, for message spaces that might not consist of a whole number of bits (like $n$-digit decimal numbers), what you need is called format-preserving encryption. There are several known methods for constructing format-preserving encryption schemes out of ordinary fixed-length block ciphers; see the linked Wikipedia article for details.

---

Edit: A block cipher is a pair $(S,P)$ of pseudorandom permutations, chosen by a key, which are inverses of each other. The designation of one permutation in the pair as the encryption function and the other as the decryption function is, in general, completely arbitrary. If you want, it's quite possible to use the "decryption" permutation to encrypt a message and the "encryption" permutation to decrypt it.

However, note that, if the same permutation is used to both encrypt and decrypt messages, this could make certain types of attacks more powerful. For example, assume that person A uses the permutation $S$ both to encrypt messages to B and to decrypt messages from B. Now, if an attacker is able to trick A into encrypting a plaintext message of their choice for B and observe the corresponding ciphertext, then they can decrypt any message send from B to A simply by choosing it as the plaintext to inject.

Of course, deterministic encryption isn't secure against chosen-plaintext attacks anyway, so in a sense that's nothing new. However, being able to decrypt arbitrary messages using an encryption oracle is potentially a lot worse than simply being able to detect if the same plaintext is encrypted twice, which is the general way in which deterministic schemes fail IND-CPA.

All this really comes down to is that, if you feel you need to use some kind of oddball encryption scheme, you really need to carefully define what your security goals are and what capabilities potential attackers could have. Only then can you really tell if the scheme achieves those goals against such attackers or not.