XTEA Strong Encryption Implementation
Revision as of 20:16, 13 March 2007 by Morse Dillon (talk | contribs)
| LSL Portal | Functions | Events | Types | Operators | Constants | Flow Control | Script Library | Categorized Library | Tutorials |
//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);
}
}