XTEA Encryption/Decryption

[cesarcesar]

I am trying to decrypt a code encrypted with XTEA. I have been using a script found here, http://goo.gl/xCpgs and it works within its own encrypt/decrypt example. The problem is that it will not decrypt a code given to me by my client. In the code examples description it says the "key" is 16 characters, but the key I have from my client is 32 characters so I think this may be part of the problem, but I cannot find out in the code how to make it work with a 32 char key (if that is even the issue).

 

Below is the class from the link above and below that are sample encrypt and decrypt strings. If anyone can provide help or a better solution, it is greatly appreciated. My guess is that it is only allowing 16 of my 32 char key. I tried to use a 32 char key, but the code still seemed to only want 16. Help!

 

I also read something about XTEA only working within the same code language each side of the crypt was made. Can anyone validate this?

 

<?php
/* PHP Implementation of XTEA (www.php-einfach.de)
*
* XTEA was designed in 1997 by David Wheeler and Roger Needham
* of the Cambridge Computer Laboratory.
* It is not subject to any patents.
*
* It is a 64-bit Feistel cipher, consisting of 64 rounds.
* XTA has a key length of 128 bits.
*
*
* ***********************
* Diese Implementierung darf frei verwendet werden, der Autor uebernimmt keine
* Haftung fuer die Richtigkeit, Fehlerfreiheit oder die Funktionsfaehigkeit dieses Scripts.
* Benutzung auf eigene Gefahr.
*
* Ueber einen Link auf www.php-einfach.de wuerden wir uns freuen.
*
* ************************
* Usage:
*
* include("xtea.class.php");
*
* $xtea = new XTEA("secret Key");
* $cipher = $xtea->Encrypt("Hello World"); //Encrypts 'Hello World'
* $plain = $xtea->Decrypt($cipher); //Decrypts the cipher text
*
* echo $plain;
*
*/

class XTEA {

   //Private
var $key;

// CBC or ECB Mode
// normaly, CBC Mode would be the right choice
var $cbc = 1;

   function XTEA($key) {
      $this->key_setup($key);
   }

   //encrypt
   function encrypt($text) {
      $n = strlen($text);
      if($n%8 != 0) $lng = ($n+(8-($n%));
      else $lng = 0;

      $text = str_pad($text, $lng, ' ');
      $text = $this->_str2long($text);

      //Initialization vector: IV
      if($this->cbc == 1) {
         $cipher[0][0] = time();
         $cipher[0][1] = (double)microtime()*1000000;
      }

      $a = 1;
      for($i = 0; $i<count($text); $i+=2) {
         if($this->cbc == 1) {
            //$text with last ciphertext XOR
            //$text is XORed with the previous ciphertext
            $text[$i] ^= $cipher[$a-1][0];
            $text[$i+1] ^= $cipher[$a-1][1];
         }

         $cipher[] = $this->block_encrypt($text[$i],$text[$i+1]);
         $a++;
      }

      $output = "";
      for($i = 0; $i<count($cipher); $i++) {
         $output .= $this->_long2str($cipher[$i][0]);
         $output .= $this->_long2str($cipher[$i][1]);
      }

      return base64_encode($output);
   }




   //decipher
   function decrypt($text) {
      $plain = array();
      $cipher = $this->_str2long(base64_decode($text));

      if($this->cbc == 1)
         $i = 2; //Message start at second block
      else
         $i = 0; //Message start at first block

      for($i; $i<count($cipher); $i+=2) {
         $return = $this->block_decrypt($cipher[$i],$cipher[$i+1]);

         //Xor Linkage of $return and ciphertext from the last two blocks or sections
         //XORed $return with the previous ciphertext
         if($this->cbc == 1)
            $plain[] = array($return[0]^$cipher[$i-2],$return[1]^$cipher[$i-1]);
         else          //EBC Mode
            $plain[] = $return;
      }

      for($i = 0; $i<count($plain); $i++) {
         $output .= $this->_long2str($plain[$i][0]);
         $output .= $this->_long2str($plain[$i][1]);
      }

      return $output;
   }

   //Prepare the key to decrypt ver / front
   function key_setup($key) {
	if(is_array($key))
      		$this->key = $key;
	else if(isset($key) && !empty($key))
		$this->key = $this->_str2long(str_pad($key, 16, $key));
	else
		$this->key = array(0,0,0,0);
   }


//Performs a benchmark
function benchmark($length=1000) {
	//1000 Byte String
	$string = str_pad("", $length, "text");


	//Key-Setup
	$start1 = time() + (double)microtime();
	$xtea = new XTEA("key");
	$end1 = time() + (double)microtime();

	//Encryption
	$start2 = time() + (double)microtime();
	$xtea->Encrypt($string);
	$end2 = time() + (double)microtime();



	echo "Encrypting ".$length." bytes: ".round($end2-$start2,2)." seconds (".round($length/($end2-$start2),2)." bytes/second)<br>";


}

//verify the correct implementation of the blowfish algorithm
function check_implementation() {

	$xtea = new XTEA("");
	$vectors = array(
		array(array(0x00000000,0x00000000,0x00000000,0x00000000), array(0x41414141,0x41414141), array(0xed23375a,0x821a8c2d)),
		array(array(0x00010203,0x04050607,0x08090a0b,0x0c0d0e0f), array(0x41424344,0x45464748), array(0x497df3d0,0x72612cb5)),

	);

	//Correct implementation?
	$correct = true;
	//Test vectors, see http://www.schneier.com/code/vectors.txt
	foreach($vectors AS $vector) {
      	$key = $vector[0];
		$plain = $vector[1];
		$cipher = $vector[2];

		$xtea->key_setup($key);
		$return = $xtea->block_encrypt($vector[1][0],$vector[1][1]);

		if((int)$return[0] != (int)$cipher[0] || (int)$return[1] != (int)$cipher[1])
			$correct = false;

	}

	return $correct;

}



/***********************************
		Some internal functions
 ***********************************/
   function block_encrypt($y, $z) {
   $sum=0;
   $delta=0x9e3779b9;


   /* start cycle */
   for ($i=0; $i<32; $i++)
      {
      $y      = $this->_add($y,
                        $this->_add($z << 4 ^ $this->_rshift($z, 5), $z) ^
                            $this-> _add($sum, $this->key[$sum & 3]));

      $sum    = $this->_add($sum, $delta);

      $z      = $this->_add($z,
                        $this->_add($y << 4 ^ $this->_rshift($y, 5), $y) ^
                              $this->_add($sum, $this->key[$this->_rshift($sum, 11) & 3]));

      }

   /* end cycle */
   $v[0]=$y;
   $v[1]=$z;

   return array($y,$z);

   }

   function block_decrypt($y, $z) {
   $delta=0x9e3779b9;
   $sum=0xC6EF3720;
   $n=32;

   /* start cycle */
   for ($i=0; $i<32; $i++)
      {
      $z      = $this->_add($z,
                	-($this->_add($y << 4 ^ $this->_rshift($y, 5), $y) ^
                  	$this->_add($sum, $this->key[$this->_rshift($sum, 11) & 3])));
      $sum    = $this->_add($sum, -$delta);
      $y      = $this->_add($y,
                          -($this->_add($z << 4 ^ $this->_rshift($z, 5), $z) ^
                                    $this->_add($sum, $this->key[$sum & 3])));

      }
   /* end cycle */

   return array($y,$z);
    }




  	function _rshift($integer, $n) {
        // convert to 32 bits
        if (0xffffffff < $integer || -0xffffffff > $integer) {
            $integer = fmod($integer, 0xffffffff + 1);
        }

        // convert to unsigned integer
        if (0x7fffffff < $integer) {
            $integer -= 0xffffffff + 1.0;
        } elseif (-0x80000000 > $integer) {
            $integer += 0xffffffff + 1.0;
        }

        // do right shift
        if (0 > $integer) {
            $integer &= 0x7fffffff;                     // remove sign bit before shift
            $integer >>= $n;                            // right shift
            $integer |= 1 << (31 - $n);                 // set shifted sign bit
        } else {
            $integer >>= $n;                            // use normal right shift
        }

        return $integer;
    }


    function _add($i1, $i2) {
        $result = 0.0;

        foreach (func_get_args() as $value) {
            // remove sign if necessary
            if (0.0 > $value) {
                $value -= 1.0 + 0xffffffff;
            }

            $result += $value;
        }

        // convert to 32 bits
        if (0xffffffff < $result || -0xffffffff > $result) {
            $result = fmod($result, 0xffffffff + 1);
        }

        // convert to signed integer
        if (0x7fffffff < $result) {
            $result -= 0xffffffff + 1.0;
        } elseif (-0x80000000 > $result) {
            $result += 0xffffffff + 1.0;
        }

        return $result;
    }


   //Einen Text in Longzahlen umwandeln
   //Covert a string into longinteger
   function _str2long($data) {
       $n = strlen($data);
       $tmp = unpack('N*', $data);
       $data_long = array();
       $j = 0;

       foreach ($tmp as $value) $data_long[$j++] = $value;
       return $data_long;
   }

   //Longzahlen in Text umwandeln
   //Convert a longinteger into a string
   function _long2str($l){
       return pack('N', $l);
   }

}
?>

 

 

[xyph]

In hex, 32 "characters" = 128 bits. So if your characters are only 0-9,a-f, you've got a 128 bit HEX string.

To convert this to 16 characters:

 

<?php

$hex_string = md5('some string');

echo "Source HEX string: $hex_string<br> Size: ".strlen($hex_string)."<br>";

$ascii_string = '';
foreach( str_split($hex_string,2) as $chunk )
$ascii_string .= chr(hexdec($chunk));

echo "Converted to ASCII: $ascii_string<br> Size: ".strlen($ascii_string)."<br>";

echo "Confirm: ".hash('md5','some string',TRUE);


?>

 

This isn't a good place to ask for advice on home-brew cryptographic implementations. Most PHP devs would use mcrypt(), and usually through a wrapper.

 

I would suggest using AES, Twofish, TripleDES, etc via mcrypt() for PHP. Most languages should have implementations of those ciphers in a package.

[cesarcesar]

Thanks fro that info. I tried it out using $ascii_string as the new key, but no luck.

 

The key is like "28d75A09ec63zxcv1e870fad25e79b8c". The string to decode (originally encrypted in JAVA) looks like

 

B09F4FB46AD4418E51E4E09C6C11AA3A36628FBD1CC2D8AF6AD3F01467CA3910231CA851D639402758D57D49CC7D12EF8C7B215B4B50A2C8FF97A29EEEA5F575F7A8628BDB39776747E244FE5B69D8CD63A4DC805360F0CB4B894CA86B56E89099B547FEA38D16A90203FF6D6E4C64B6CA7B2B33184046E7E8646A302F636FA349C3EEF8C45C3A7443030255292B31AA22CD3A45E7722D706F31EBD7CEB0B6ED5BC160EB1CD62FAE36E845E7857C9D203430578A3C3DEBAC808F0BED62C8DF20292A5B145FA991C5

 

The string with just XTEA encoding "should" look like

T6L9PQABsNEFMyM5Tp80eC9qrjAwS+YeEWJddowFHt1DWIEHZ9ZhuB76sjWB7exkRJI8a4jon/0ZpkSqPvgyhbhHXD/CyHT0K+2+HLP5+nkuPtPo/hH9yL5i44hW6wDgADW0oWYaaSasfUmaXwTk+M5Xv2KjvWTVJVnBEDBPWrBiLrecYHeo4aJCOxanIwCfNMjTNcbRnq66a1+ENi1u1bFv+LUuZKe9NcUeKwdh1LamHkwrnqkW+2gKVZpX/8YQkK9eaILx93RJ7bceXdpXyQ==

[xyph]

[edit] Tested the class. The values decrypt fine when plugged in to the JavaScript implementation, and vice-versa. It still throws the undefined variable notice, though [/edit]

 

Your top string is hex, or base16

 

Your bottom string is base64.

 

<?php

$hex_string = 'B09F4FB46AD4418E51E4E09C6C11AA3A36628FBD1CC2D8AF6AD3F01467CA3910231CA851D639402758D57D49CC7D12EF8C7B215B4B50A2C8FF97A29EEEA5F575F7A8628BDB39776747E244FE5B69D8CD63A4DC805360F0CB4B894CA86B56E89099B547FEA38D16A90203FF6D6E4C64B6CA7B2B33184046E7E8646A302F636FA349C3EEF8C45C3A7443030255292B31AA22CD3A45E7722D706F31EBD7CEB0B6ED5BC160EB1CD62FAE36E845E7857C9D203430578A3C3DEBAC808F0BED62C8DF20292A5B145FA991C5';

$ascii_string = '';
foreach( str_split($hex_string,2) as $chunk )
$ascii_string .= chr(hexdec($chunk));

$base64_string = base64_encode($ascii_string);

echo $base64_string;

?>

[cesarcesar]

Thanks for your help. I think I'm almost there. I can get the encrypted string to change to base64 and it "looks" correct, but it still will not decrypt. Could I still be having an issue with the key string of "28d75A09ec63cxvxve870fad25e79b8c"? How do I change this into 16 bytes? Below is my current code.

 

$ascii_string = '';
foreach( str_split($text,2) as $chunk ){ $ascii_string .= chr(hexdec($chunk)); }
$base64_string = base64_encode($ascii_string);

$xtea = new XTEA('28d75A09ec63c32b1e870fad25e79b8c');
$output =$xtea->Decrypt($base64_string);

[xyph]

I showed you already, in my first reply. It's the same as converting to base64, only you skip the last step.

 

$hex = '28d75A09ec63cxvxve870fad25e79b8c';

$ascii = '';
foreach( str_split($hex,2) as $chunk ) $ascii .= chr(hexdec($chunk));

$xtea = new XTEA($ascii);

[cesarcesar]

I had tried that before, but with the MD5 function you have now removed. OK tried again.. no luck, the new "$ascii" var has a value of

(×Z	ìcÃ+‡­%盌

[xyph]

Yes, there's going to be some odd characters when switching from hex directly to ascii. There are a lot of white space and otherwise non-keyboard characters. If you want to generate your key from readable text, I'll give you a little code when I get home in an hour or so.

 

Which version of PHP do you have? On what OS? If you have access to /dev/urandom it would be ideal, or if you have PHP5.3, it supports Window's source of random data (via mcrypt)

 

This is all assuming you want to generate random keys.

[xyph]

Complex, but potentially 'better'. Limited to 6 bits of entropy per potential 8 bits due to simplifying with base64, so you lose 25%.

<?php

$key = make_base64_key(16);

echo $key;

function make_base64_key( $bytes ) {
// Based on methods implemented in PHPass by Openwall

// Converts byte size we want in ASCII to byte size needed in base64 ( 6 bits / 8 bits = .75 )
$base64_bytes = ceil($bytes * .75);
// Generate a 'somewhat random' state. Not ideal, but strong enough for salt generation when used in this way
$state = microtime();
$raw = '';
// Attempt to use /dev/urandom
if (is_readable('/dev/urandom') && ($handle = @fopen('/dev/urandom', 'rb'))) {
	$raw = fread($fh, $base64_bytes);
	fclose($fh);
}
// Check if using /dev/urandom produced incorrect results, or if it's inaccessible
if (strlen($raw) < $base64_bytes) {
	// Reset $raw to blank
	$raw = '';
	// Generate 'somewhat random' data in 16 byte chunks, and truncate at the end
	for ($i = 0; $i < $base64_bytes; $i += 16) {
		$state = md5(microtime().$state);
		$raw .= pack('H*', $state);
	}
	$raw = substr($raw, 0, $base64_bytes);
}
// Chop off the extra bytes we don't need
return substr(base64_encode($raw),0,$bytes);
}

?>

 

Simple, similar to above example if /dev/urandom isn't available. This one allows you to have a variable character set too

<?php

$chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!@#$%^&*()_+-=[]{};:,./<>?';
$max = strlen($chars)-1;
$key = '';
for( $i = 0; $i < 16; $i++ ) {
$key .= $chars[mt_rand(0,$max)];
}
echo $key.'<br>';

?>

 

It's possible to get /dev/urandom to produce values based on a variable character set, but you'd either have to use a base2 number of characters, or deal with rejection sampling or one of it's more complex adaptive algorithms.

[cesarcesar]

crap. still lost and its not decrypting. This is where I'm at.

 

// convert HEX key to ASCII (working)
$ascii_key = hexToAscii('28d75A09ec63c32b1e870fad25e79b8c');
// (×Z	ìcÃ+‡*%盌


// convert XTEA encrypted HEX value to ASCII (working)
$ascii = hexToAscii($text);
// °ŸO´jÔAŽQäàœlª:6b½ÂدjÓðgÊ9#¨QÖ9@'XÕ}IÌ}ïŒ{![KP¢Èÿ—¢žî¥õu÷¨b‹Û9wgGâDþ[iØÍc¤Ü€S`ðËK‰L¨kV虵Gþ£©ÿmnLd¶Ê{+3@Fçèdj0/co£IÃîøÄ\:tCU)+1ª"Í:Eçr-po1ë×ΰ¶í[Á`ëÖ/®6èEç…| 40WŠ<=묀íbÈß )*[_©‘Å


// base64 encode ASCII value (working)
$base64_string = base64_encode($ascii);
// sJ9PtGrUQY5R5OCcbBGqOjZij70cwtivatPwFGfKORAjHKhR1jlAJ1jVfUnMfRLvjHshW0tQosj/l6Ke7qX1dfeoYovbOXdnR+JE/ltp2M1jpNyAU2Dwy0uJTKhrVuiQmbVH/qONFqkCA/9tbkxktsp7KzMYQEbn6GRqMC9jb6NJw+74xFw6dEMDAlUpKzGqIs06RedyLXBvMevXzrC27VvBYOsc1i+uNuhF54V8nSA0MFeKPD3rrICPC+1iyN8gKSpbFF+pkcU=


// decrypt XTEA encrypted value (FAILING)
$xtea = new XTEA($ascii_key);
$output = $xtea->Decrypt($base64_string);
echo  nl2br(htmlentities(stripslashes($output)));
// |üÑ61}¢BhžB`û”¢od¼4HÁÉ]sZÐ’=8ÿ€SúóØrh©òÌ$0nÄ'Ãw¾çhüÌ£TÆñwp}±Ì4-8EŸšl³¯0SéS¥åFŒ|Ù}I„ÚY;L(b‹-iSÖcž4!ì»fôò¤”»ÑÙ[y4má—O"˜Eí&T‡Á'¸
œ7}ÎCVqòWC¢Þ_Ï&ƒšWn¨ðÏ}à›°„¢õ鍊ŽPÁÈ

 

As you can see the last result is not a legible string. It should look like a bunch of parameters after a url. HELP!!

[xyph]

Can you provide the strings you're testing this with?

 

If you're using the JavaScript program along with this, it really doesn't like odd ASCII characters for the key. The PHP implementation functions as you'd expect. I'd imagine it's some sort of injection prevention that's screwing with the JavaScript implementation.

 

Try using keys that only use Alpha-Numeric values, and see if that helps.

[cesarcesar]

B09F4FB46AD4418E51E4E09C6C11AA3A36628FBD1CC2D8AF6AD3F01467CA3910231CA851D639402758D57D49CC7D12EF8C7B215B4B50A2C8FF97A29EEEA5F575F7A8628BDB39776747E244FE5B69D8CD63A4DC805360F0CB4B894CA86B56E89099B547FEA38D16A90203FF6D6E4C64B6CA7B2B33184046E7E8646A302F636FA349C3EEF8C45C3A7443030255292B31AA22CD3A45E7722D706F31EBD7CEB0B6ED5BC160EB1CD62FAE36E845E7857C9D203430578A3C3DEBAC808F0BED62C8DF20292A5B145FA991C5

[xyph]

Sorry, I didn't mean the encrypted string, I meant plain text, but it's impossible for me to recreate your situation anyways.

 

What code produced that HEX output?

[cesarcesar]

Some XTEA script written in JAva

[xyph]

Seems like one of the implementations is different. That would be my only guess.

 

Perhaps one of them uses a different number of rounds, one uses ECB instead of CBC.

 

Figuring out what's going on here would require a thorough look at both implementations compared to the 'proper' implementation, and would be quite a bit of work.

[SureshReddy]

Hi, 

 

Have you got the solution for this? I'm also facing the same problem,

 

my client has sent the encrypted file (XTEA 32 cycles ECB mode), this file is not decrypted. Can you share some information, how can you decrypt?

 

File data: 

 

k~Ý

K€_Ñ É}†û_ן?[¾p£Žÿ ç<i~CQîP&'EÆ<¨9•vÉX$ê¬HqÒV‹òi¦¯éÉ

P«ÔÜ߬Þö*êCØ«*žúl‘o@‰÷|Í9™ì«$©ƒID¡Ùü\ßqGÉ_xÊ[Ÿ,æ<”W_-U4Þw«zƒë'Hšo {¸.úóUÝZ•ø î7/S¬Ü"t~8Âvü‹5Ãêh(u$R†><( @í:ÂO

¿J«B*bôe×0e_#¸²å8Ye·àí}H¹´å@{'µjAõÏUyæñR³Ÿ!dÔrv¦6ž»ÎÑb#œ9~VÊ8þLMdI†ÝP®,Œ—¨±¡—;{­U@_/·3/.\~OwÝßž {ÈDÚ0&ƒ…ÍɾBü¡A^Í‘7æÚ¹5:ÛÖ©°¯F>¯£ú®Œß

Vg㧂ЌžÖ¸?X°û¾7Ÿ„YC¾¡9êüâèükßíäÉí94