Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

XTEA Strong Encryption Implementation

Morse Dillon
Lifetime Member
Join date: 11 Dec 2003
Posts: 142
03-13-2007 21:22
I have written an implementation of the XTEA (eXtended Tiny Encryption Algorithm) using LSL and have released it under the GPL (GNU General Public License). With the dearth of true encryption in SL, I hope that the scripting public will find this implementation valuable. XTEA is unique in that it's a 'real' encryption algorithm akin to IDEA, but the computational requirements are relatively low. This makes it a perfect fit for LSL.

Although the source code is listed below, I would encourage all of you to visit the Wiki page and hold the discussion there. Please review the source thoroughly before commenting: https://wiki.secondlife.com/wiki/XTEA_Strong_Encryption_Implementation



CODE

//XTEA implementation in 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);
}
}
_____________________
King Morse Dillon
King of Second Life
Nada Epoch
The Librarian
Join date: 4 Nov 2002
Posts: 1,423
Discussion Thread
03-16-2007 04:51
/54/31/171735/1.html
_____________________
i've got nothing. ;)