Security of very simple XOR with random? [duplicate]

Question

I am currently trying to implement a very fast and simple encryption algorithm in Lua for the purpose of using it with ComputerCraft.

The main problem is that bitwise operations in Lua (5.2 at least) are very slow and the implementation ComputerCraft can only handle 32 bit integers in their bit-library, so implementing standard algorithms isn't easy.

On the other hand this is only a game and encryption is merely used to keep others from simply controlling your devices or reading your messages. There is no critical data associated with this, so the encryption can be very weak.

I currently implemented a combination of XOR and random in the following form (pseudo-code):

random.seed( hash(key) ) -- 32 bit seed
for i = 1 to str.length do
  result[i] = str[i] XOR random.nextByte()
end

The good thing about this is that it only uses a single bit-operation and is guaranteed to never exceed 32 bit. Also this is very fast.

Aside from external problems like random entropy, what is an approximate time someone would need to decrypt this using a standard desktop PC? (sophisticated guess is ok, I just want to get an idea)

And if this is just too weak, is there any other algorithm that is more secure, but fast and can be implemented with a minimum amount of bit operations fitting in 32-bit?

Answer 1

Rather than LuaCrypto or some other Lua binding to some (blazing fast) low-level cryptographic library in some other language; I'm assuming that you want a "pure Lua" implementation. Would one of the following work for you?

• ARCFOUR in pure Lua (a) (b) (c) (d)
• Lua wiki: Cryptography (b)
• Pure LUA encryption (d)
• "Very simple string Encryption"(w) (k)
• yet another home-brewed encryption algorithm in pure Lua (w)
• AES Encryption in pure Lua(x) (b)
• Lua crypt API v0.2(z)
• lrandom: Mersenne Twister random number generator in Lua (f)

While I like the extreme simplicity of the original version of this algorithm, I see 4 ways to make it better:

• Most people prefer using the secret key for more than one message. Many encryption algorithms are specifically designed to remain secure even when millions of messages are encrypted using the same key; but streaming ciphers like this XOR algorithm is vulnerable to "two-time pad" attacks. See How does one attack a two-time pad (i.e. one time pad with key reuse)? ; Many time pad attack ; "Beware the Two-Time Pad"(x); "Cryptanalysis for beginners"(y); etc. This is one reason that CipherSaber and many other XOR-based streaming encryption algorithms use a (public) "initialization vector" at the beginning of each encrypted message -- to make it immune to "two-time pad" attacks. For other reasons, see Why, or when, to use an Initialization Vector?
• random.nextByte() is not cross-platform compatible -- even when given exactly the same seed, it gives a different sequence of bytes on different platforms, possibly even the same platform after upgrading to a new version of libc.
• Many people think the built-in "random" function in libc is "not random enough". The Mersenne Twister is much better; but even better would be a CSPRNG.
• Have you considered using authentication?

Keep on learning.

Answer 2

Your cipher is a synchronous stream cipher build on a random number generator.

For cryptographically secure random number generators (CSRNG), this is a secure stream cipher.

The problem is, that your random seed is way too small for any security. Trying all possible seeds and seeing if the decryption result makes some sense (assuming the plaintext makes sense) is possible in some seconds, I guess, even with non-specialized hardware.

Also, the random number generator used by your program is quite likely not a CSRNG (otherwise it would not have a 32-bit seed), so there might even be other ways to attack it.

Also, as you don't have any initialization vector, you have the usual stream cipher problem: As soon as you reuse a key twice, you have the same keystream twice. Then the attacker can XOR both ciphertexts and get $c_1 \oplus c_2 = (p_1 \oplus k) \oplus (p_2 \oplus k) = p_1 \oplus p_2$ – and from this we often can extract parts of the plaintexts, especially if these are longer messages.

Answer 3

Paŭlo Ebermann has given a good answer from a strict cryptographic perspective, and David Cary has given many useful engineering considerations. I want to add, or maybe prefix, these answers with some more engineering considerations.

The main problem is that bitwise operations in Lua (5.2 at least) are very slow and the implementation ComputerCraft can only handle 32 bit integers in their bit-library, so implementing standard algorithms isn't easy.

Lua 5.2 adds support for bitwise operations. It seems that ComputerCraft provides a different API.

A limit to 32-bit integers is not a problem to implement proper cryptography. All low-level languages and many high-level languages have such limits! A symmetric cryptographic key is not an integer anyway, it's an array of bits. For example, an AES key consists of 128 bits, and they are usually represented as an array of 16 bytes (each byte being an 8-bit value), or as an array of 4 words (each word being a 32-bit value). Implementing common symmetric cryptographic algorithms is no harder in Lua (excluding older versions without bitwise operations) than in other languages.

If you do your own cryptography, I bet you that it's broken. Maybe you can't break it, maybe I can't break it, but unless professional cryptographers have taken shots at it for years and their bullets have glanced off it without leaving an impact, if I see a homemade encryption algorithm in a code review, it's an instant fail. If you don't care that much about your data, send it in plaintext.

Thus, do the normal thing: use AES with a proper mode of operation (CBC or CTR if you only want confidentiality, GCM or CCM or EAX if you want authentication as well).