XTEA Strong Encryption Implementation

//XTEA Strong Encryption Implementation - Linden Scripting Language (LSL)
//Version 1.0
//Copyright (C) 2007 by Morse Dillon (morse@morsedillon.com)
//
//This program is free software; you can redistribute it and/or
//modify it under the terms of the GNU General Public License
//as published by the Free Software Foundation; either version 2
//of the License, or (at your option) any later version.
//
//This program is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You should have received a copy of the GNU General Public License
//along with this program; if not, write to the Free Software
//Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
//02110-1301, USA.
//========================================================================
//
//Included at the end of this source listing is a small bit of example 
//code that shows the usage.  If you wish to include this implementation 
//in your own work, just replace the example code with your own.  Also, 
//please do not reuse or redistribute this work without including the 
//above text attributing this code to its author Morse Dillon, the above
//GPL statement, and this documentation.
//
//This is an implentation of the XTEA (eXtended Tiny Encryption Algorithm) 
//block cypher.  (X)TEA is a very good choice of cipher when security
//is important but computational power is limited.  Although I did a
//lot of work on this implementation, enormous amounts of credit must
//be given to the creators of the algorithm and those who came before
//me to implement it in other languages and computing environments.
//
//
//ABOUT TEA AND XTEA
//------------------
//TEA was originally designed by David Wheeler and Roger Needham 
//of the Cambridge Computer Laboratory.  The algorithm itself is not
//subject to any patents.  While the original TEA was found to have
//some minor weaknesses, XTEA (implemented herein) addresses these.  
//
//TEA and its derivatives consist of 64-bit block Feistel network 
//with a 128-bit key.  This implementation uses six cycles, or rounds,
//which is less than one would like but still provides a reasonable
//level of security (16 is sufficient while 8 is enough for most 
//applications).  Six is said to achieve theoretically good dispersion, 
//but should more security be desired the number of cycles can easily be 
//modified by changing the CYCLES global variable.  Due to the low 
//execution speed of LSL scripts, it's suggested to make this as low as 
//your comfort level allows.  Encryption time scales linearly with the 
//number of cycles.
//
//For more information about XTEA, see the following:
//
//Original Paper by Walker and Needham
//http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html
//
//Wikipedia on TEA
//http://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm
//
//
//ABOUT THIS IMPLEMENTATION
//-------------------------
//This is a barebones implementation, and is meant to be included in
//the body of the script needing encryption facilities or wrapped
//in a link message handler.  If the latter approach is desired, care
//should be taken to only send link messages to the prim containing
//this implementation.  If ALL_PRIMS is used as the destination,
//one could link a link message listener to the object and intercept
//cleartext communications.  
//
//If you plan to place this code into the same script as that needing
//encryption facilities, you need only call the following functions:
//
//string Encrypt(string cleartext)
//string Decrypt(string cyphertext)
//
//Simple as that.
//
//This implementation does not provide any secure key exchange, so in
//terms of key generation and exchange you're on your own.
//
//The 128-bit key is contained in four LSL integers:  KEY1, KEY2, KEY3,
//and KEY4.  These are global variables at the beginning of the source
//and can be set using a method that works for you.
//
//
//**************IF YOU READ ONE THING IN HERE, READ THIS*******************
//It is VERY important to remember that there is no such thing as
//'cookbook cryptography'!  Simply using this cypher does not guarantee
//security.  Security is an end-to-end concern and responsibility lies
//with you to thoroughly examine your project from all possible angles
//if valuable data is at risk.  If you doubt this, ask any thief how they'd
//rather break into your house - futzing about with picking a high-security
//deadbolt on the front door or walking in through the back door that you 
//left open.




//******************USER-CONFIGURABLE GLOBALS BEGIN HERE*******************

//ENCRYPTION KEYS KEY[1-4]
//These together make up the 128-bit XTEA encryption key.  See the above 
//documentation for details.  Whatever you do, don't leave them as the default.
integer KEY1 = 11111111;
integer KEY2 = 22222222;
integer KEY3 = 33333333;
integer KEY4 = 44444444;

//DEBUG_FLAG
//If set to 1, will cause debug text to be printed containing some 
//intermediate cleartext/cyphertext and the resultant cyphertext/cleartext.  
//Do not leave this enabled in production environments!!!!
integer DEBUG_FLAG = 0;

//COMM_CHANNEL
//Specifies which channel should be used for debug and test harness communication.
integer COMM_CHANNEL = 0;

//CYCLES
//Specifies the number of rounds to be used.  See the above documentation for
//details.
integer CYCLES = 6;

//******************USER-CONFIGURABLE GLOBALS END HERE*********************

//Other Globals
list cypherkey = [];
integer delta = 0x9E3779B9;



//Function: ord
//Returns the index of an ASCII character
integer ord(string chr)
{
    string ASCII = "             \n                    !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
    if(llStringLength(chr) != 1) return -1;
    if(chr == " ") return 32;
    return llSubStringIndex(ASCII, chr);
}



//Function: chr
//Returns the ASCII character correspondent to index i
string chr(integer i)
{
    string ASCII = "             \n                    !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
    i %= 127;
    return llGetSubString(ASCII, i, i);
}

   
                     
//Function:  DWord2Hex
//Converts a dword containted in a LSL integer to hexadecimal format.        
string DWord2Hex(integer m){
    
    string result;
    integer i = 0;
    integer index = 0;
    
    //Define character string [0-F] for use in building the hex.
    string characters = "0123456789ABCDEF";   
    
    //Step through 8 times, for a total of 32 bits, 8 nibbles, and 8 hexadecimal digits.
    for (i = 0; i < 8; i++){
        //Get a nibble by right-shifting and masking off 4 bits.
        index  = (m >> (i * 4)) & 0xF;
        //Grab character from the characters string at index position and add it to the result string.
        result = llInsertString(result, 0, llGetSubString(characters,index,index));
    }
    
    return result;
}



//Function:  Hex2DWword
//Converts a string containing a hexadecimal number to a dword contained in a LSL integer.
integer Hex2DWord(string m){
    integer result = 0;
    integer i = 0;
    string digit;
    integer value;
    integer index;
    
    string characters = "0123456789ABCDEF";
    
    for (i = 0; i < 8; i++){
        
        index = 8 - (i + 1);
        digit = llGetSubString(m,index,index);
        
        value = llSubStringIndex(characters, digit);
                        
        result = result | value << (i * 4);
        
    }
    
    return result;
}



//Function: Encrypt
//Takes cleartext string, pads and bitpacks it, then encrypts it using TEAEncrypt().
string Encrypt(string cleartext){
        
        //Initialize variables.
        integer dword1 = 0;
        integer dword2 = 0;
        integer cyphertext_numeric;
        list cypherblock;
        string cyphertext = "";

        //Pad cleartext string to the nearest multiple of 8.
        while(llStringLength(cleartext) & 0x7) {
            cleartext += " ";
        }
        
        //Define more variables pertaining to while loop.
        integer stringlength = llStringLength(cleartext); 
        integer i=0;
        integer character;
        
        //Step through cleartext string, encrypting it in 64-bit (8 character) blocks.
        while (i < stringlength){
            
            //Pack dword1 with 4 bytes.  Do so by bit-shifting in each character.
            //4th byte winds up in the most-significant position.
            dword1 =  ord(llGetSubString(cleartext,i,i));
            i++;
            dword1 =  dword1 | (ord(llGetSubString(cleartext,i,i)) << 8);
            i++;
            dword1 =  dword1 | (ord(llGetSubString(cleartext,i,i)) << 16);
            i++;
            dword1 =  dword1 | (ord(llGetSubString(cleartext,i,i)) << 24);
            i++;
            
            //Do it again, this time for dword2                            
            dword2 =  ord(llGetSubString(cleartext,i,i));
            i++;
            dword2 =  dword2 | ord(llGetSubString(cleartext,i,i)) << 8;
            i++;
            dword2 =  dword2 | ord(llGetSubString(cleartext,i,i)) << 16;
            i++;
            dword2 =  dword2 | ord(llGetSubString(cleartext,i,i)) << 24;
            i++;

            //Call TEAencrypt() with dword1, dword2, and the cypher key and store result in cypherblock.
            cypherblock = TEAEncrypt(dword1,dword2,cypherkey);
 
            //Convert dword values from cypherblock to hex and append to cyphertext.
            cyphertext = cyphertext + DWord2Hex(llList2Integer(cypherblock,0)) + DWord2Hex(llList2Integer(cypherblock,1));
                    
            //Reset variables for the next round, just to be safe.
            dword1 = 0;
            dword2 = 0;
            cypherblock = [];
            
            if(DEBUG_FLAG){
                llOwnerSay("Pre-Crypt DWords: " + (string)dword1 + "," + (string)dword2);
                llOwnerSay("Post-Crypt DWords: " + (string)llList2Integer(cypherblock,1) + "," + (string)llList2Integer(cypherblock,2));    
                llOwnerSay("Post-Crypt Hex: " + DWord2Hex(llList2Integer(cypherblock,1)) + "," + DWord2Hex(llList2Integer(cypherblock,2)));
            }
            
        }  
        
        return cyphertext;        
}  



//Function: Decrypt
//Takes cyphertext, decrypts it with TEADecrypt(), and unpacks it into a string.
string Decrypt(string cyphertext){
        
        //Initialize variables.
        string hexvalue1 = "";
        string hexvalue2 = "";
        integer dword1 = 0;
        integer dword2 = 0;
        list clearblock = []; //res
        string cleartext = "";
        integer i;
        
        
        //Step through cyphertext string, descrypting it block by block.
        while (i < llStringLength(cyphertext)){
            
            //Pull first 32 bits worth of hexadecimal into hexvalue1
            hexvalue1 += llGetSubString(cyphertext,i,i + 7);
            i = i + 8;
            
            //Pull second 32 bits worth of hexadecimal into hexvalue2
            hexvalue2 += llGetSubString(cyphertext,i,i + 7);
            i = i + 8;

            //Convert hexvalues to dwords contained in LSL integers.
            dword1 = Hex2DWord(hexvalue1);
            dword2 = Hex2DWord(hexvalue2); 
    
            //Call TEADecrypt() with dword1, dword2, and the cypher key and store result in clearblock list.
            clearblock = TEADecrypt(dword1, dword2, cypherkey);
            
            //Append first 4 characters of ASCII to cleartext string.
            //This is done by pulling the decrypted dwords from the clearblock list and looking up their ASCII values.
            cleartext += chr( llList2Integer(clearblock,0) & 0x000000FF);
            cleartext += chr( (llList2Integer(clearblock,0) & 0x0000FF00)  >> 8);
            cleartext += chr( (llList2Integer(clearblock,0) & 0x00FF0000)  >> 16);
            cleartext += chr( (llList2Integer(clearblock,0) & 0xFF000000)  >> 24);

            //Append second 4 characters of ASCII to cleartext string.
            cleartext += chr( llList2Integer(clearblock,1) & 0x000000FF);
            cleartext += chr( (llList2Integer(clearblock,1) & 0x0000FF00)  >> 8);
            cleartext += chr( (llList2Integer(clearblock,1) & 0x00FF0000)  >> 16);
            cleartext += chr( (llList2Integer(clearblock,1) & 0xFF000000)  >> 24);

            //Reset variables for the next two blocks of decrypt.            
            hexvalue1 = "";
            hexvalue2 = "";
            dword1 = 0;
            dword2 = 0;
            clearblock = [];
            
            if(DEBUG_FLAG){
                llOwnerSay("Pre-Decrypt Hex: " + hexvalue1 + "," + hexvalue2);
                llOwnerSay("Pre-Decrypt DWords: " + (string)dword1 + "," + (string)dword2);
                llOwnerSay("Post-Decrypt DWords: " + (string)llList2Integer(clearblock,1) + "," + (string)llList2Integer(clearblock,2));
            }
             
        }
                
        return cleartext;        
}



//Function: TEADecrypt
//This is the implementation of XTEA proper.  It takes a block of cleartext
//consisting of two dwords contained in LSL integers and a 128-bit key 
//contained in an LSL list of 4 integers and returns the cyphertext in an LSL 
//list of two integers.
list TEAEncrypt(integer dword1, integer dword2,list cypherkey){
    
            list cryptlist = [];
            
            //Set n to the number of cycles given in the CYCLES global variable
            integer n = CYCLES;
                        
            integer sum = 0;
            
            //Operate for the specified number of cycles.
            while (n-- > 0){
                dword1 = dword1 + ( ( dword2 << 4 ^ dword2 >> 5 ) + dword2 ^ sum + llList2Integer(cypherkey, (sum & 3) ) );
                sum += delta;
                dword2 = dword2 + ( ( dword1 << 4 ^ dword1 >> 5 ) + dword1 ^ sum + llList2Integer(cypherkey, (sum >> 11 & 3) ) );
            }
            
            cryptlist = [dword1,dword2];

            return cryptlist;
}



//Function: TEADecrypt
//This is the implementation of XTEA proper.  It takes a block of cyphertext
//consisting of two dwords contained in LSL integers and a 128-bit key 
//contained in an LSL list of 4 integers and returns the cleartext in an LSL 
//list of two integers.
list TEADecrypt(integer dword1, integer dword2,list cypherkey){
    
            list cryptlist = [];
            
            //Set n to the number of cycles given in the CYCLES global variable
            integer n = CYCLES;
                        
            integer sum = delta * CYCLES;

            //Operate for the specified number of cycles.        
            while (n-- > 0){
                dword2 = dword2 - ( ( dword1 << 4 ^ dword1 >> 5 ) + dword1 ^ sum + llList2Integer(cypherkey, (sum >> 11 & 3) ) );
                sum -= delta;
                dword1 = dword1 - ( ( dword2 << 4 ^ dword2 >> 5 ) + dword2 ^ sum + llList2Integer(cypherkey, (sum & 3) ) );        
            }
            
            cryptlist = [dword1,dword2];
            return cryptlist;
}



//XTEA Usage Example
//Listens on COMM_CHANNEL for a message and encrypts it, then turns around and decrypts the resultant cyphertext.
//Object than says the encrypted and decrypted messages to the owner.
default
{
    state_entry()
    {
        llListen(COMM_CHANNEL, "", NULL_KEY, "");
        cypherkey = [KEY1,KEY2,KEY3,KEY4];
        
        string temp = DWord2Hex(250);
    }

    listen(integer channel, string name, key id, string message)
    {
        string temp_cyphertext = Encrypt(message);
        
        string temp_cleartext = Decrypt(temp_cyphertext);
        
        llOwnerSay("\nOriginal Cleartext: " + message + "\nCyphertext: " + temp_cyphertext + "\nDecrypted Cleartext: " + temp_cleartext);
    }
}