Perfect secrecy with XOR & SHIFT?

Question

I have read that XOR provides perfect secrecy, when the key is perfectly random. However it's technically hard to generate truly random numbers, especially on computers, so that is why people use AES, Twofish and other cypthers.

So the conditions for using XOR are that the key has to be true random, and the keysize must be at least as big as the message.

---

What if we just use a very long key, to guarantee at least as much entropy as the message size?

For instance we need to encrypt 6 bits of message, then using a 32 bit pseudo random key, should have at least 6 bits of entropy in it. Or use even 512-bit key, if the RNG is very weak, to suit our needs. Then we XOR the first 6 bits.

Now the other 26 bits are leaking out, but if the attacker doesn't know the size of the input message, then it should not be a problem.

But if the attacker does know the size of the input, then we will also shift the output bits from the right to the left by n tiles, leaving p spaces between them. Lik this:

Obviously the n and p values are also random and secret choosen by us. So we would only need to keep the XOR key, the n and the p secret.

And after 1 shift operation, the message should be perfectly secret. The XOR already provides perfect secrecy, but the shift operation also hides the needle in the haystack.

Because how can an attacker brute force the original input if he doesn't even know what cypher we are using. So randomizing the cypher parameters is what I am suggesting here.

What is your opinion, is this a viable encryption system?

Answer 1

There are a few issues with the approach presented:

Or use even 512-bit key, if the RNG is very weak, to suit our needs.

If your RNG is broken, then using more of it will not help.

"If the attacker knows something, then we do something else"

As was mentioned by @tylo in the comments: "...(that idea) is fundamentally flawed: You can't make the encryption adaptive of what the adversary does or knows."

To elaborate on why:

• How would you know what one particular adversary does or does not know?

• Assuming somehow that you do know what one particular adversary does/does not know, how would you ensure that they receive the correct version of the algorithm that you designed and packaged up just for them?

• In addition to that, how would you prevent them from acquiring "weaker" copies of the software, intended for a less-knowledgeable adversay?

In order to protect against the worst case scenario, we have to assume the worst case scenario. Meaning that we need to assume that the adversary already knows everything other then the key.

Because how can an attacker brute force the original input if he doesn't even know what cypher we are using. So randomizing the cypher parameters is what I am suggesting here

As was mentioned in the answer by @Elias: Keeping the cipher secret is actually a poor strategy, which is a lesson that has been proven time and time again.

The problem is that you cannot get rid of the need for secrecy, which means you cannot get rid of the need for a key. Keeping the cipher algorithm secret means using the algorithm itself as the key. It is significantly more difficult to keep an algorithm secret then small, random chunk of data: Everyone who is to encrypt/decrypt will know the algorithm, which increases the probability of leakage for every participant.

"But what if I'm the only one that uses it then? Problem solved, right?"

Supposing you were only going to encrypt/decrypt messages with your secret algorithm for yourself: If the algorithm is the key, then you just posted your key online for all to see and comment on (and analyze and attack).

Randomizing cipher parameters and keeping the cipher secret are not the same thing: I would not actually describe your design as keeping the cipher secret (especially considering how it has been posted here for all to see).

Xor and Tranposition is broken

What if we just use a very long key, to guarantee at least as much entropy as the message size?

is this a viable encryption system?

If you happen to encrypt fewer message bits then you have key bits, then yes; But this would only be because it would effectively be equivalent to a basic One Time Pad and so is not a realistic answer.

Otherwise, for more realistic use cases, no: xor-with-key + transposition is always broken, even if the transposition is a secret as well. The problem stems from the fact that the degree of the equations does not increase; The expression that represents the output will consist of nothing but the XOR of some input terms. A secret transposition only serves to vary which terms constitute each output bit.

It is often times trivial to break such designs by first submitting a block of all 0 to be encrypted: The resultant ciphertext will consist of nothing but key bits. Secret transposition will not fix this, it only modifies which key bits constitute each output bit.

After you have the XOR-key, you can figure out the transposition key by submitting encryptions of weight 1 plaintexts (i.e. 1, 2, 4, 8, etc). After removing the XOR-key from each such ciphertext, the result will display which output bits contain the associated plaintext input bit. If the cipher has a blocksize of n-bits, then this attack would require only n chosen plaintexts to completely recover every bit of both keys.

It almost seems like you are trying to use the cipher's key schedule as a sort of mode of operation for the cipher (the mode of operation is usually responsible for ensuring subsequent blocks encrypt differently). If so, it's probably better to keep the two tasks separate.

Answer 2

Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to consider all the options for an attacker to learn parts of the system.

In general we don't analyze cipher designs on this website because it is too easy to come up with a random design which is probably broken but not totally obviously so. It wastes people's time to try and attack it. Cryptographers mostly don't care about new ciphers anyway. We already have good ciphers. Exceptions are made for very specific applications.