php xtea implementation (cfb)

Question

I came accross a weird behaviour that i could not comprehend.

I am using mcrypt xtea (cfb mode) to encrypt some data. Since php 7.2 is getting rid of mcrypt and since openssl does nor support Xtea, i had to implement the algorithm myself.

The problem is, no matter the algorithm used :

• I tested the one provided here: pear implementation which is an ECB mode only (no init vector)

• And the one provided on the wikipedia page taken from this stackoverflow topic

• And the one i developed here (for the CFB mode) basing myself on the two following articles from wikipedia here  and here and mcrypt source code that can be found here :

  /*
  * $v is the data, $k is the 128bits key and $iv is 64bits init vector (size = 8)
  * Code is not optimized
  */
  function encryptCfb($v, $k, $iv) {
  
      $v = array_values(unpack('N*', $v));
      $iv = array_values(unpack('N*', $iv));
      $k = array_values(unpack('N*', $k));
  
      $cipher = [];
  
      //IV ciphering using the 128bits key
      list ($v0, $v1) = cipher($iv[0], $iv[1], $k);
      //Xoring the cipherd block with the first 64bits of data (32bits in V0 and 32 others in V1)
      $cipher[0] =  $v0 ^ $v[0];
      $cipher[1] =  $v1 ^ $v[1];
  
      for ($i=2; $i < count($v); $i+=2) {
          //Now ciphering the latest "cipherd" data using the 128bits key
          list ($y, $z) = cipher($cipher[$i-2], $cipher[$i-1], $k);
  
          //Xoring the cipherd block with the second 64bits of data (32bits in V0 and 32 others in V1)
           $cipher[$i] =  $y ^ $v[$i];
           $cipher[$i+1] =  $z ^ $v[$i+1];
      }
  
  
      $output = "";
      foreach ($cipher as $i) {
          $output .= pack('N', $i);
      }
  
      return $output;
  }
  
  function cipher($v0, $v1, $k) {
  
      $delta=0x9e3779b9;
      $sum = 0;
      $limit = $delta * 32;
  
      for ($i=0; $i < 32; $i++) {
          $v0 += ((($v1<<4) ^ ($v1>>5)) + $v1) ^ ($sum + $k[$sum & 3]);
          $sum += $delta;
          $v1 += ((($v0 << 4) ^ ($v0 >> 5)) + $v0) ^ ($sum + $k[($sum>>11) & 3]);
      }
  
      return [$v0, $v1];
  }
  

i get a different result and furthmore, none of them gives the exact same result mcrypt gives using :

$cryptModule = mcrypt_module_open('xtea', '', 'ncfb', '');
mcrypt_generic_init($cryptModule, $key, $iv);
mcrypt_generic($cryptModule, $data);

You can check and test the different tests i made here using same data/key/IV :

• My implementation VS mcrypt in CFB mode. Note that :

  • The number of rounds changes nothing (32 or 64)
  • Packing/Unpacking using N mode (big endian) or V mode (little endian) changes nothings

• PEAR ECB mode vs mycrypt ECB mode!

• The wiki code in CBC mode code vs mcrypt in cbc mode!

Does anyone know why i get different result?

Answer 1

Does anyone know why i get different result?

i do not, but i suspect all the old (2006 and older?) userland-php-implementations were never tested on, and do not work on 64bit PHP.

i just had to use XTEA in a project, and like you, i tested all other available XTEA implementations, and they all were very old, and none of them produced the correct result (i suspect that all the 2006-and older implementations were never tested on 64bit systems, and that they don't work on 64bit systems)

long story short, i wrote a 64-bit compatible XTEA-implementation in PHP from scratch, the code can be found here: https://github.com/divinity76/php-xtea

examples

<?php 
require_once('XTEA.class.php');
$key_binary = "secret";
$keys_array = XTEA::binary_key_to_int_array($key_binary);
$data = "Hello, World!";
$encrypted = XTEA::encrypt($data, $keys_array);
$decrypted = XTEA::decrypt($encrypted, $keys_array);
var_dump($data, $encrypted, $decrypted);

should output something like:

string(13) "Hello, World!"
string(16) "□□Jx□□□□□□□ܴ9"
string(16) "Hello, World!   "

the length is different because of xtea length padding, which is possible to disable by instead doing

XTEA::encrypt($data, $keys_array, XTEA::PAD_NONE);

which will give you:

PHP Fatal error:  Uncaught InvalidArgumentException: with PAD_NONE the data MUST be a multiple of 8 bytes! in /cygdrive/c/projects/tibia_login_php/xtea.class.php:73
Stack trace:
#0 /cygdrive/c/projects/tibia_login_php/xtea_tests.php(8): XTEA::encrypt('Hello, World!', Array, 0)
#1 {main}
  thrown in /cygdrive/c/projects/tibia_login_php/xtea.class.php on line 73

because the XTEA algorithm requires data-to-encrypt to be in multiples of 8 bytes. but if we change it to

<?php 
require_once('XTEA.class.php');
$keys_binary = "secret";
$keys_array = XTEA::binary_key_to_int_array($keys_binary);
$data = "Hello, World!123";
$encrypted = XTEA::encrypt($data, $keys_array, XTEA::PAD_NONE);
$decrypted = XTEA::decrypt($encrypted, $keys_array);
var_dump($data, $encrypted, $decrypted);

you will get

string(16) "Hello, World!123"
string(16) "%t□□□n□□aʓ'□□H"
string(16) "Hello, World!123"

• no padding, no length change, no exception.

Answer 2

It should work with modulus on $v0 and $v1:

function cipher($v0, $v1, $k) {
    $delta = 0x9e3779b9;
    $sum = 0;
    $limit = $delta * 32;

    for ($i=0; $i < 32; $i++) {
        $v0 += ((($v1<<4) ^ ($v1>>5)) + $v1) ^ ($sum + $k[$sum & 3]);
        $v0 = $v0 % pow(2, 32);
        $sum += $delta;
        $v1 += ((($v0 << 4) ^ ($v0 >> 5)) + $v0) ^ ($sum + $k[($sum>>11) & 3]);
        $v1 = $v1 % pow(2, 32);
    }

    return [$v0, $v1];
}

You will also need to resize the input value $v to make sure it has a correct length, for example with the _resize(&$data, $size, $nonull = false) function of the PEAR module Crypt_Xtea you mention.