Implementing better encryption

Your implementation is actually a tiny bit slower (about 0.001 seconds) but I believe you're right that it's memory usage is better. I've corrected a couple of small typos and integrated it into the code on the wiki, along with a small extra change to the algorithm which generates a far better spread of hash values.

Basically the extra code XORs all integers together into a quick and dirty 32-bit hash, if the required hash length is 32-bits then it simply uses this, otherwise it combines it with values used when shortening the data to the required length. The result is that a single bit of difference in the input data will completely change the output of the hash function, whereas before patterns would still remain depending where the change was located.

I'm going to spend some time today look at AES standards to try and see what I can do to have the LSL code work with actual AES implementations in standard libraries such as OpenSSL and so-on. I believe the basic algorithm is sound but I will need to support standard padding schemes and other modes of operation.

I'm also going to over-haul the link-message communication, and provide some helper functions to make it easier to use in other scripts. The main reason being is that in some cases I want to give base64 input (from SL) but get the ciphertext back as HEX for transmission to an outside source, in theory allowing it to be processed by industry standard implementations.

New communications structure is added, along with helper functions for ease-of-use since it's a little more confusing for users that just want to fire in a key, followed by a message, then send it somewhere =)

It is becoming quite a beastly page though, I may make a separate one for examples/usage once I'm happy enough with the implementation to no-longer consider it beta/work-in-progress.

I've posted a significant update to the AES LSL code which includes:
- FIPS-197 (the widely-used standard) compliance
- New modes of operation
- New padding modes

Partly these have been added in an attempt to bring the code in-line such that it will work correctly with the mcrypt PHP module/library which allows you to perform AES encryption at mostly native speeds. I still intend to produce a PHP port of the code for servers without mcrypt.

Currently I have not yet tested compatibility with mcrypt, my webserver does support it but I've other things I need to do. I shouldn't really have been working on my AES implementation, but I felt inspired and leapt into it =)

I've also restructured the wiki page into separate articles since the original one was HUGE with the code itself (1551 lines!), helper functions and examples all on one page. It means the main page is now currently a bit bare, but I'm hoping to flesh it out later.

https://wiki.secondlife.com/wiki/AES_Strong_Encryption

Summary of changes:
FIPS-197 compliance; didn't actually have to do anything, it already appears to be compliant as I've gone through the standard and checked it.

New modes of operation include ECB (encrypt each block individually and concatenate), CBC (encrypt each block XORed with the previous block to destroy recurring patterns), CFB (encrypt previous ciphertext block or input-vector then XOR with input), OFB (encrypt input-vector repeatedly, XORing with plaintext after each time). The advantages and disadvantages of each are summarised on the page for the LSL implementation I've produced.

New modes of padding include NONE (for CFB and OFB no padding is performed, EBC and CBC modes will use RBT padding), RBT (perform CFB encryption on final, incomplete block), NULLS (add null-characters/zero-bytes to input, trim on decrypt), ZEROES (add zero-bytes with a byte describing number added), RANDOM (same as ZEROES but random bytes are used).

[edit]

ACK! Looks like I may have to drop support for some things, likely on the block are the hash function, and support for ECB and OFB as CBC and CBF are more commonly used. With all support added there's only 1.5kb of memory left! Not good!

Okay, latest version has full FIPS-197 compliance (passes the test-vectors), though it now only supports CBC mode, and CBF mode.

The memory limit on it now is 1152 base64 characters so it can currently only process 864 bytes of data which is a bit disappointing. Looks like I'm going to have to go through with a fine-toothed comb and find any extra memory I can.

The main problem is that I've used unrolled loops working with a set of integers instead of a list. Thus a version with more memory using lists would probably also be a lot slower, damned trade-offs. If we had arrays we could have better memory and the same speed =(

I've added an example of using my LSL AES cryptography engine with Java's built-in cryptography suite. Am having a little trouble with working PHP's mcrypt but I should get it eventually =)

https://wiki.secondlife.com/wiki/AES_Java_Implementation

Managed to shave off 2kb by generating the SBox values on-the-fly, it's only marginally slower than using the pre-generated values due to the relative overhead of looking up list entries. It adds about 0.2 to 0.3 seconds to a large (1,248 character) message when encrypting/decrypting. I may attempt to calculate the rounds on-the-fly as well, though the list size only 12 entries long (128-bit key) to 14 entries long (256-bit key), so it may not make much of a difference at all.

The rest is all code, which I'm unlikely to trim unless there is demand for a slower version using a list for state which has more memory available. At this point though, 1024 characters was my target for my own personal use, and as far as I can tell it is fully compatible with Java's AES library, as such I'm considering my LSL implementation complete for now, and focusing my efforts on figuring out how to get PHP's mcrypt to play-fair =)

looking forward to see it Haravikk

xtea is *abit* heavy server side when decrypting alot of info

I believe XTEA is supported by mcrypt as well, though of course it may have the same trouble getting it to actually work between PHP and LSL. I've not really studied the LSL XTEA implementation so there be issues of standards compliance and padding issues too.

I've posted the issue on some PHP developer forums where hopefully people know what the problem may be, I suspect it's to do with character encoding but it's not something I've ever had to do in PHP before and randomly inserting functions hasn't work so far

Re: XTEA -- you really should be using Corrected Block TEA (XXTEA). Padding isn't specified but the safe option would be to follow SHA1 padding since that is reliably reversible.

the xtea works really nice except the load it creates on shared servers
with abit of fidling, i converted the code to a function to call in LSL while building the POST string and server side a function xtea_decrypt_string("$value";

there just isn`t much encryption options to use to encrypt everything in lsl and decrypt in php and return the values encrypted to decrypt in lsl again unless your a math wizzard (wich i`m not )

edit: was just hoping for something fast and lightweight

After almost year, I finally got around to porting this AES implementation to PHP so it can at last communicate with PHP sites. It seems PHP's mcrypt uses some silly character handling which mainstream AES implementations like Java and C#'s can emulate, but which unfortunately I don't think that my LSL implementation can do.

Anyway, I ported my LSL implementation to PHP instead, as I can ensure perfect compatibility (I hope) and the result is technically more compliant than the stupid mcrypt module.

The PHP5 class (with examples) can be found at:
https://wiki.secondlife.com/wiki/AES_PHP_Implementation

Also, I've ported the LSL AES implementation to LSL Plus which will be how I distribute it from now-on as I don't really want to maintain two copies in the same language, the current versions (both LSL pure and LSL+) are identical for now in terms of functionality and behaviour. For those of you that don't have LSL Plus, it's a great (but still alpha currently) Eclipse plug-in that allows more professional developing of LSL, including the use of code modules to share between scripts, and the ability to inline or reduce functions.
In LSL Plus the AES implementation, after the automatic optimisation, has almost 8kb of additional memory. It also has the addition of settings at the top that allow you to specify which modes and padding schemes you intend to support, and to enable/disable dynamic set-up (changing mode/padding), which allows you to quickly save more memory by disabling things you won't use, which can save as much as an additional 20kb!

The LSL Plus implementation can be found at:
https://wiki.secondlife.com/wiki/AES_LSL%2B_Implementation

Bonus update. I've added a new padding scheme, PAD_NULLS_SAFE, which is the more industry standard version of null-padding, opposed to PAD_NULLS which was foolishly intended for compatibility with stupid smelly mcrypt.

Anyway, PAD_NULLS simply adds null-bytes till it reaches a block boundary, and then strips them when decrypting, however there is no way to distinguish a null-byte added for padding from one which just happened to be in the string, so data can end up being lost. While not a common case in LSL (does anyone use null characters in their strings?!) it can happen as a result of the base64 conversion.

PAD_NULLS_SAFE uses the more common method of adding a single '1' bit before padding with nulls. This way the extra bit prevents the null-stripping from affecting any of the original data, and more crucially in this implementation it also allows us to get the exact number of bits that were in the original data provided for encryption. This prevents any chance of discrepancies that can occur due to the 6 <-> 8-bit conversions that occur due to the use of base64.

So, if you're sending regular string data you'll want to use base64 for speed/size, and PAD_NULLS_SAFE to ensure it is recovered correctly. If you're sending data that you are encoding as hex then there's no need to worry as all padding schemes will work perfectly, except for PAD_NULLS if you have null bytes at the end of the data.

The best example is the example code provided, the string "Hello world! I am a lovely message waiting to be encrypted!" converts into a 474-bit base64 string, but due to the bit conversion will end up being interpreted as a 480-bit piece of data when decrypted, which creates a null-character, or an 'A' in base64. Using PAD_NULLS_SAFE the data is correctly interpreted as 474-bits and recovered exactly as it was before encryption. Not a big deal in LSL as llBase64ToString() drops any null characters at the end, or in general I'm not sure, and I've guarded against it in the PHP version. But for the sake of absolute accuracy you'll want to use this.

All implementations have been updated, except for the Java implementation; the padding modes supported by Java's Cipher object are a bit limited, so I'll likely have to restructure the padding part of the Java implementation and code the ones that are missing.

I've now updated the LSL+ version into a module, with the broker now an example implementation using this module. It cuts down the memory of the broker a bit, but it still better off than the pure LSL version.

This is likely the last update for a while unless I find any errors or obvious parts for improvement, as I'm now going to merrily start using the module in my scripts =)