Encryption in LSL

I've been trying to locate a nice, safe, lean encryption algorithm that I can actually use under LSL. Unfortunately, the best I've been able to find so far is the llXorBase64StringsCorrect () function, which doesn't actually provide much security. I know there is llModPow(), but you can only do 1 integer per second with that API. I've tried implementing DES, AES, and Blowfish, but the memory limit blows-up well before I can actually encrypt anything.

The reason I'd like something like this is for financial transactions between two objects with different owners, such that neither can explicitly trust the other. In other words I can imagine too many scenarios where dishonest people could exploit the transaction and steal your money.

I'm curious if others have had success with real encryption security and if so how?

Otherwise, I'd like to propose that LL provide us with some encryption API's. I've already setup a voting request for them to do that:

https://secondlife.com/vote/index.php?get_id=1571

But I can revoke it if I'm missing something and there is some wonderly slick solution out there that I'm oblivious to.

I wrote an XTEA implementation, which is fairly secure and lightweight, but it is still HORRIBLY slow.

It takes upwards of 8-10 seconds to encrypt a 100-character message, and 4-5 seconds to decrypt it. Most of that time is spent converting the text to/from binary so the encryption algorithm can run on it.

I agree that they need some industrial-strength encryption functions in the library. Those things need to run natively rather than being written with LSL.

I agree. LL needs to put in better encryption. However, I would rather them work on bug fixes and the Linux client first.

In the case of financial transactions, you should consider if it's encryption or signing you need. In other words, do you want to stop someone reading/understanding the message, or stop them reproducing it? If it's reproducing, pure encryption won't help, as someone can simply copy the encrypted message and repeat it over and over again without needing to understand its contents.

Signing is generally easier than encryption in SL, because of llMD5String.

There's been a 'manual' version of that function posted recently in another thread, and since it's missing the 1 sec penalty it's likely to work faster, overall:

/54/be/115545/1.html#post1105711

didn't verify the code posted, though... just presuming it's doing what's supposed to do ^^;

Try these:

/54/99/59579/1.html
/54/96/59358/1.html
/54/52/73984/1.html

You may find them useful, or not.

Either way, I tried.

Thanks for the insights and thoughts folks! I very much apprecaite it.

Yumi: Yes, signing is defintiely a piece of this that I'm thinking about and is something I intend to use here, however since I can't pass the nonce (because then it would be public) the same problem could still exist even with a signed string. i.e., the hacker just sends you a copy of the string message and the MD5 sign for it. So really what I need is public/private key. I could make block cipher work, but you're right there are potential attacks here. The more I'm getting into this, I'm beginning to wonder how secure some of the in-system "games" are and if there are security attacks that could be performed on them. I see some fundamental problems with the security model on scripts & prim permissions.

Examples:
llSay/llShout() - Hackers can scan channels, once they find the channel they decode the messages and can then send their own.

llLinkedMessage/llEmail() - Hackers can link in their own objects and get your messages. If you have a no mod script in a no mod prim, they can just move your script into a new prim and then they can get to the linked message. Even if your code checks to make sure that you are the creator on the script and prim and checks for permissions on that prim. They buy an obect from you with mod permissions, take the script from the no mod prim and drop it into the mod prim, add their magic code, then change permissions and give it to an alt. No way for you to detect

The method I see around this is an encrypted and signed string with a time stamp and a secret password or password pair. All of the main work and encryption has to happen inside of 1 script, since you can't pass the strings around to say your special handy-dandy "encrypt" script (see linked message attack above). After the encryption is done, THEN and only then you can pass it around.

Jonnah: Thanks for the pointer to ModPow() code. Yea, I figured it could be implemented faster than the 1 second penalty. However the problem still remains that you need two really big prime numbers. Having an API - llReallyBigPrime() would be necessary or I guess some way to generate big primes outside of game would work.

Everyone: Thanks for the responses and thoughts. I hope Linden adds this to their work list at some point.

Again. Look over what we came up with in those threads. Wegot around that to some degree.

On the issue of encryption actually, how secure would you say an llXorBase64StringsCorrect() system is assuming the second string you supply changes with each communication?
ie: is it possible to decode the message without knowing the code used?

I'm likely going to have a few extra levels of security to mangle up the messages, but still
The main issue being that better encryption seems to be far too slow for my needs, so this method seems to win for speed atm.

It seems like the problem with XOR is that it's easy to brute force. Doing an string XOR is really quick, so you can try out tons of keys.

What you're describing is very similar to a one-time pad, which is very strong.

Wikipedia says: http://en.wikipedia.org/wiki/One-time_pad

One-time pads are the only cryptographic algorithm which is perfect - that is to say it is unbreakable, regardless of how smart you are or how much computing power you have. It relies on a symmetric cypher, and that the key length is as long as the plaintext. This is unfeasable in many circumstances.

I posted an encryption algorithm a couple years ago, which uses repeated MD5-summing as a one-time pad. (So this would be a 128 bit symmetric cypher) While I wouldn't guarantee it's unbreakable, I'd bet anyone who could crack the algorithm is a published cryptographer.
/15/c2/13580/1.html

The big caveat is that it ain't fast - to convert an MD5sum (which is represented as an ascii string) to a base64 encoded string in LSL is really slow. I haven't yet heard of anyone who found a way of using LSL to do fast strong encryption without having many many notecards full of random strings.

(I believe Adam Zaius implemented a one-time-pad in LSL, but you had go around and replenish the keys every now and then by hand)

What would be really nice is if LSL provided an API into libcrypto, so we could have encryption done by native code, instead of interpreted. I've suggested it a few times before, but noone's really reacted with enthusiasm :|

Maybe in SL 1.100.85(23) when they finally implement MONO we'll have some strong encryption algorythims, but untill then lets keep searching for those undiscovered LSL hacks that make life easier.

Just curious, but wouldn't combining it with transposition(s) of sorts applied to plaintext ... reduce the easiness of brute force guess? ^^;

Francis, how do you mean it's slow? I've been testing a fairly simple llXorBase64StringCorrect which just takes the current time, MD5's it and uses it to encrypt a message, thus both the message and the MD5 hash are base 64 encoded before XORing. It seems to be fairly quick for messages about the length I want. My intended method was just to have the code determined by the server, basically you have a starting code with some determined method of generating it that the server can also work out, this is used to login.
The server then sends back confirmation of your login, which you decrypt with your original key, and on the end of it is a new key to encrypt with (and the server has saved so it can decrypt). The server likely wouldn't have any particular generation scheme, since it wouldn't be needed. ie:

Object sends msg "LOGIN:HARAVIKKASSWORD", encrypted using the md5 hash of it's UUID.
Server receives message, finds object is not logged in and decrypts using object's UUID (passed by the HTML request).
Server confirms log-in details and replies with the message "CONNECTED:12345678"
Object now changes its encryption code to 12345678. Server keeps a note of it in its database.
Object says another message, now using the md5 hash of 12345678 which the server can decrypt because it knows that code.

That's basic, the log-in information would be encrypted separately with no real method to it (done once and stored rather than re-doing it), so instead of that coherent message you'd maybe get a mess, with the "LOGIN" keyword likely being a mess too, e.g "e8134b" just to be nice.
Plus newly received codes would likely have something done with them too, I said MD5 above but it would be more confusing than that.

Basically imagine the client and server being two closed boxes with the above being the basics of the communication, what happens to parts between being sent back and forth is known only to the server and client, and hopefully not easily guessable.

You realize that there are over 2 billion llSay/Shout channels?

And one-time pads:
I could probably almost maybe not do it in LSL, but there's a way of creating one-time pads with a program, and I've done it in C++, the only issue with making it in LSL is the lack of arrays (the function, called Solitaire, relies HEAVILY on array manipulation).
It works something like this:

Take two decks of cards, new and unshuffled. Number the cards 1-26 (twice each deck, skip the jokers, letter them A and B).
Shuffle them so they are identicle in order, send one to a friend.
--if is handy to create some pre-arranged shuffling method so that more than one message can be transmitted.
(Doing this from memory, might not quuite be what teh Cryptonomicon had)
Move joker A down one card
Move joker B down two cards (these two steps do matter in order)
Spit the deck around the jokers (top, joker-middle-joker, bottom) and sawp the top and bottom
Look at the bottom card, take the value (written number) and count off that many cards from the top of the deck and put them on the bottom (leave the bottom card the bottom card so the process can be reversed)
Look at the vaue of the top card, count off that many cards from the top
Take the calue of the next card and add it to the letter of your message to be encrypted.
A + 1 = B
A + 2 = C
...
Y + 1 = Z
Y + 2 = A
etc.
Put the counted off cards back on top
Repeat.

You'll end up with a string of complete gibberish, albeit with maintained spaces. You friend would follow the same procedure, but subtract the value from letter to be decoded. You now have an effective One-Time code encryption method, the shuffle of the deck won't be the same twice and there are 54! (54 factorial) possible encryptions.


Now, what do you need the authentication for? I do know one method of one-time use verification that can't be copied. Uses the llBased64 stuff and a script that upon verifying the prim-holder with the system calls llDie. It's gone. Kaput. And the script and the prim are no-copy. If you're interested in this system, IM Nargus Asturias and ask about how he verifies people to get avatar upgrades (his licence card system).

In the code I posted: /15/c2/13580/1.html
Check out the base16ToBase64 function.

If you're just using the raw output of llMD5String and feeding it into llXorBase64String, then you're only getting 3 bits/byte of entropy. Which is pretty weak.

The base16ToBase64 converts the output from llMD5String and reencodes it as binary in base64 bit representation. Which gives you 8 bits/byte of entropy. Which is pretty strong.

base16ToBase64 doesn't run very quickly.

I'm under the impression that base 64 xors pad the shorter string if needed, so surely that ensures that it that insecure? As the person trying to brute force still needs to guess the code used up to the length of the message, assuming the message itself has no recurring patterns then there should be no way to find a pattern in it, so the full key used would still be needed, whether it turns out to be a load of repeated chunks or not?

ie the first letter of your code xored with the letter A may give Z, but xored with B later on may give C, so surely the method would be as easy to brute force regardless of the length of the code (ignoring really short ones)?

Hrmm, so while a longer encryption key would be better for recurring data patterns, surely making a huge one is really wasted effort in a sense? Even then, to make a larger key you can just use any long string. e.g you use the code you've got interspersed with characters from your object's key, e.g your code is 123456, and your key is abcdef, therefore your final code is 1a2b3c4d5e6f. Your other object will know the code/password and the object ID it's receiving from, so can calculate the exact same thing.

I dunno, while your method seems quite clever, is it really necessary? For four times the protection, can't several strings just be combined?