Simple xor cipher extension

Question

Probably the simplest cipher is the xor cipher with a single integer. One can extend this to use more than one integer by several means. I'm wondering if there is any benefit to doing more than this:

Let $x_n$ be the $n$th data byte to encrypt and $p_k$ be the data stream (password or whatever) to encrypt with and $p_k$ is cylical.

Then the "standard" way of doing the encryption is

$$\large y_n = x_n \small\oplus\large\; p_k$$

But for certain functions $f,g,h$

$$\large y_n = x_{h(n)} \small\oplus\large\; f(p_{g(k,n)},n)$$

is invertible.

My question is:

Without knowing what formula and functions are used, would such a method make it much more difficult to "crack" an encryption? (Basically is there any real benefit to using a more complex formula. Ofcourse, if anyone has any theoretical insight in how these modifications "enhance" the encryption then by all means ;) My guess is that it is too difficult, mathematically, to understand in general. For example, if invertibility exists and f,g, and h have certain properties, do we end up with a more secure encryption than the standard xor cipher(which is easily attacked using frequency analysis)?)

Assume $f,g$ and $h$ are the best possible functions in whatever way is needed.

What I have noticed is that such complex formula seem to increase the "randomness" of the output over the standard method.

It would seem that if $f,g$ and $h$ are completely known to the cracker then it is equivalent to simply using a different $p_k$ and $x_n$ and equivalent to the standard method.

Answer 1

If the keystream $p$ is as long as the plaintext $x$ (and is not reused), then $y_n := x_n \oplus p_n$ is a one-time pad, which is theoretically unbreakable, and thus needs no further strengthening.

On the other hand, if $p$ is shorter than $x$, then what you have is basically equivalent to a Vigenère cipher, which is known to be quite weak. Thus, any additional obfuscation may well improve it, although it's still unlikely to produce a truly secure cipher.

It should be noted that your construction is almost general enough to encompass arbitrary synchronous stream ciphers, which are of the form $y_n := x_n \oplus f(p, n)$. The only difference is that stream ciphers are generally designed (with good reason) so that each byte (or bit) of the output of $f$ depends essentially on the entire key $p$.

Answer 2

Actually, your intuition is correct; if $f$, $g$ and $h$ are publicly known functions (and are unkeyed except for the $p_k$ inputs), then the more complex construction is not much stronger than the original simpler cipher. Indeed, it is vulnerable to ciphertext-only attacks just like the simpler method (assuming, of course, that the plaintext is longer than the key, and so some key bytes are used multiple times).

Here are two possible avenues of attack, assuming that the attacker has some ciphertext which corresponds to some nonrandom plaintext:

• Guess that key byte $p_i$ is a specific value; then, the attacker can scan through $g(n)$ (you have $g(k,n)$, however, you don't define what $k$ is there; the key length?) to find the values of $n$ where it takes on the value $i$, and for those $n$, reconstruct the plaintext bytes $x_{h(n)} = y_n \oplus f( p_i, n)$ He can then see if those revealed plaintext bytes make sense, and if they don't, then he can eliminate that specific value for the key byte.

• He can also work the other direction; he can guess the values of a few consecutive plaintext bytes, say that values $x_i, ..., x_{i+4}$ are the five characters " the ". He can then reconstruct the values of the key bytes that must be for that decryption to work (so that if $h(n) = i$, then $f( p_{g(n)}, n ) = y_n \oplus x_i$, and then use the above attack to figure out what other plaintext values are implied by those key bytes. If the plaintext values make sense, then it is likely that the guess is correct (and you also get the other plaintext bytes as well). Note: this general approach of guessing consecutive plaintext bytes is known as "crib dragging".

Because of these types of attacks, we generally follow the advice that Ilmari gives, that is, we make every output of the keystream depend on every byte of the key. If we don't do this, then the attacker can search on part of the key, and that's a lot cheaper for the attacker.