0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by e-sushi, otus, poncho, Maarten Bodewes, D.W. Aug 31 '14 at 6:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ What research did you do? See: Why not the one-time pad with pseudo-number generator $\endgroup$ – e-sushi Aug 27 '14 at 20:27
  • $\begingroup$ Googling for "fast random secure" wasn't helpful as all algorithms used a lot of bit-shifting, so I came up with the one above myself. However as a total crypto-noob I cannot tell at all if this is secure or not or to what grade. $\endgroup$ – TwoThe Aug 27 '14 at 21:15
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, these are very interesting links, I will work through them as soon as I can find the time. The ones I looked over so far did use almost no bit operations, which is exactly what I am looking for. $\endgroup$ – TwoThe Aug 28 '14 at 9:08
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The 32-bit seed is actually enforced as the bit operations on the hash can only work with 32 bit. In my head a brute-force decoding attempt would have to run (worst-case) through all 32 bits, which would take some time even if only the first few bytes are decoded. Or is there a much more sophisticated way that improves the time by so much that it takes only a few seconds? $\endgroup$ – TwoThe Aug 27 '14 at 19:45
  • 1
    $\begingroup$ @TwoThe, you can search a 32-bit key space in a few minutes, so you don't really need a more sophisticated attack. However, Lua random uses the rand of the underlying C library, for which you can usually calculate the next number from previous ones, allowing at least a known plaintext attack. $\endgroup$ – otus Aug 28 '14 at 9:22
2
$\begingroup$

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).

$\endgroup$

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