I’ve finally gotten through some major break throughs with encryption. I am using a cipher called XTEA (eXtended Tiny Encryption Algorithm). Its strength is speed in embedded systems with limited memory and processing power. LSL scripts are perfect being that they have a 16 kb memory limit and have a lmited amount of processing power on the sim.
Morse Dillon posted an LSL implementation of XTEA on the Second Life wiki. It was great groundwork to start off with. I have identified some limitations and bugs that I have been working on for quite some time now. Morse Dillon posted the LSL scripts with the GNU license. I am still looking into what this means, but I believe I’ll be posting my version of the XTEA implimentation as well and crediting him and his work. This is great news for any other scripter interested in cryptography for “mostly secure” communications.
Last night, I got my implementation to encrypt and decrypt data properly so that what ever I fed into the cypher, I got the same thing out of it when I decrypted it. That is not to say that the cipher was working properly. I needed a way to confirm what I had was working correctly. I searched the internet and found a XTEA implentation as part of The Bouncy Castle Cryptographic C#® API.
The C# API was perfect because I’ll end up communicating with a wabsite running on the .net framework eventually. Going forward, I found that the code that they provided had some test vectors. I was able to test my implementation of XTEA for LSL to verify the data was comming through ok.
Encrypted data was different. Among other things, I noticed that the rounds were only at six. As Morse explained in the LSL comments, this was done due to the limitation of low execution speed. I bumped it up to 32 as most implementations have and didn’t notice much of a difference in speed.
Now that the number of rounds matched, the encrypted data still had problems. I started working on writing out the values of each word as they were processed in each cycle. The first cycle matched fine, but every cycle afterwards failed to match. Looking a bit closer at the C# code, I noticed portions where they were converting an integer to an unsigned integer.
Unsigned and signed integers are tricky. “signed” simply means that you can have negative values. A signed integer in LSL ranges from
-2,147,438,648 to 2,147,438,647. LSL does not unsigned integers. These would range from 0 to 4,294,967,295. With the introduction of mono on the beta grid, there is potential that we will get support for unsigned integers in the future.
Ok, enough with the education on signed vs unsigned integers. I had a problem. The purpose that the unsigned integer was needed was to poperly shift bits to the right. Shifting bits on a negative number does not shift the bit indicating of the value is negative. Instead, I had to work on shifting that bit manually.
I created a function to return the nomal shift result if the value was positive. For negative values, I first remove the negative bit flag. I then moved the bits with a regular bit shift. The last part was to put the bit that I removed back into the value, but at the new shifted position.
// right shift doesn’t work well for signed integers.
// we essentially perform the operation as if it was
// an unsigned integer.
integer rightShift(integer value, integer bits)
{
// positive numbers are fine
if(value >= 0)
return value >> bits;
// remove bit sign
value = value ^ 0×80000000;
// move bits
value = value >> bits;
// inject signed bit to new location
value = value | (integer)(llPow(2, 31 - bits));
return value;
}
Once this was put into place, everything matched up against the C# code. This essentially means that I can have two systems communicate with each other using XTEA encryption. I am trusting that the C# version is implemented correctly. If I canfind one other implementation such as PHP or javascript to confirm the test vectors, then I would be more comforatable that I have a fully working implentation.
I’m not done yet. Rite now, I have an overuse of lists to work with bytes and words in my code. I’ve started to convert things over to work with base64 strings directly with the help of Strife Onizuka.
This is some pretty deep work here figuring this kind of stuff out. Getting it right is very important. If I can’t trust the data is encrypted properly, then the whole thing is pointless.
