Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

    For example: 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. For example: 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.

    For example: X = P(Y).

  5. And again user repeats the process in reverse order using the same random string X as input. For example: 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. For example: 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 non-linear with respect to the input X, and

  9. Output of S(X) and P(X) should be different. For example: Y != Z.

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

    For example: function S and P are inverses of each other.

My questions:

  1. How secure such a cipher?
  2. I feel such functions output may be difficult for any known cryptanalysis, if not, why?
  3. Is it easy/hard to design such a system?
share|improve this question
    
We'd need to know more about these S() and P() functions in order to tell you how secure they are. –  Joe Z. Jan 26 '13 at 19:10
    
Are S and P inverses of each other? What are you trying to do here? –  Joe Z. Jan 26 '13 at 19:11
    
Yes, S and P are inverses of each other. And I feel such functions output may be difficult for any known cryptanalysis. –  Auth Jan 26 '13 at 19:28
    
What is the point of requiring two "independent" computers? Wouldn't one computer be sufficient in any case? –  Mok-Kong Shen Jan 26 '13 at 21:49
4  
Is this homework? Smells like it... –  Dan Jan 26 '13 at 23:17
show 1 more comment

2 Answers 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.

share|improve this answer
    
Use-Case: In a Client-Server communication, Server uses only one function say S() and all Clients use only the other function say P() for secure communication. i.e. Server uses only S() function for encryption (sending data) and also for decryption of received cipher data from Client, similarly Client uses only P() function for encryption (sending data) and also for decryption of received cipher data from Server. Does any block ciphers like AES, DES etc support the said use-case? –  Auth Jan 30 '13 at 10:48
    
@Auth: Technically, yes. However, note that, with symmetric crypto, anyone who can compute $P$ can also compute $S$, and vice versa. If this is not desirable, you'd need to use some kind of asymmetric encryption scheme. Your question, however, did not mention anything about that. –  Ilmari Karonen Jan 30 '13 at 21:33
    
@Karonen: Do you mean to say that practically Server with only AES-Encryp() function (i.e. without AES-Decryp()) and Client with only AES-Decryp() function (i.e. without AES-Encryp()) can communicate securely? –  Auth Jan 31 '13 at 16:21
    
@Auth: Yes, as long as no-one else knows the key. AES is a symmetric block cipher, i.e. a pair of pseudorandom permutations, chosen by a key, that 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 completely arbitrary. (However, note that such reuse makes the analysis of chosen plaintext/ciphertext attacks more complicated. Still, if all ciphertexts are authenticated and there's no way for an attacker to inject chosen plaintext, this may not matter.) –  Ilmari Karonen Jan 31 '13 at 17:53
add comment

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.
share|improve this answer
    
Use-Case: In a Client-Server communication, Server uses only one function say S() and all Clients use only the other function say P() for secure communication. i.e. Server uses only S() function for encryption (sending data) and also for decryption of received cipher data from Client, similarly Client uses only P() function for encryption (sending data) and also for decryption of received cipher data from Server. Does any block ciphers like AES, DES etc support the said use-case? –  Auth Jan 30 '13 at 10:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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