/*

This demonstrates a constructed right pair through 6 cycles of XXTEA. 
Creating this through naive trial with the characteristic would take 
about 2^59 work. However, with additional techniques this can be 
reduced. Finding this pair took about an hour on a Core i7 920. I have 
a few ideas for constructing such pairs even faster, in just seconds. 
That would also allow practical full differential multicollisions. 
I'm not very motivated to invest time in that at the moment, though.


2010-11-08: my technique is mostly related to tunneling
2010-10-08: added more description
2010-10-04: initial release

cipherdev.org / yarrkov

*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>


// This XXTEA implementation is directly from Wikipedia.

  #define DELTA 0x9e3779b9
  #define MX ((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (k[(p&3)^e] ^ z));

  void btea(uint32_t *v, int n, uint32_t const k[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;
      sum = 0;
      z = v[n-1];
      do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++)
          y = v[p+1], z = v[p] += MX;
        y = v[0];
        z = v[n-1] += MX;
      } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v[0];
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--)
          z = v[p-1], y = v[p] -= MX;
        z = v[n-1];
        y = v[0] -= MX;
      } while ((sum -= DELTA) != 0);
    }
  }

#define block_len 64
uint32_t k[4] = {0x7536c3b5, 0x7536c3b5, 0x7536c3b5, 0x7536c3b5};
uint32_t v[2][block_len] =
{{
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x4334f0a8, 0x92929beb, 0xee2fd719,
0x00000000, 0xb9159fcd, 0x2243bd59, 0x38af9e77, 0xff0610bb, 0x5545d354, 0xff0610bb, 0xcc1d70fd,
0xff0610bb, 0x2492ce32, 0xff0610bb, 0x0ecd8fa8, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0x651b1efc,
0xff0610bb, 0xcc1d70fd, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0x5545d354,
0xff0610bb, 0x0ecd8fa8, 0xff0610bb, 0x3b35ed14, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0xff0610bb,
},
{
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x4334f0a8, 0x92929beb, 0xee2fd71a,
0x00000000, 0xb9159fcd, 0x2243bd59, 0x38af9e77, 0xff0610bb, 0x5545d354, 0xff0610bb, 0xcc1d70fd,
0xff0610bb, 0x2492ce32, 0xff0610bb, 0x0ecd8fa8, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0x651b1efc,
0xff0610bb, 0xcc1d70fd, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0x5545d354,
0xff0610bb, 0x0ecd8fa8, 0xff0610bb, 0x3b35ed14, 0xff0610bb, 0xff0610bb, 0xff0610bb, 0xff0610bb,
}};

void print_block(uint32_t *v, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        printf("%08x ", v[i]);
        if((i+1)%8 == 0)
            printf("\n");
    }
    printf("\n");
}

int main()
{
    int i;
    uint32_t diff[block_len];

    printf("XXTEA differential demo (yarrkov 2010-10-04)\n\n");

    printf("Block difference before encryption:\n");
    for(i=0; i<block_len; i++) diff[i] = v[1][i]-v[0][i];
    print_block(diff, block_len);

    btea(v[0], block_len, k);
    btea(v[1], block_len, k);

    printf("Block difference after encryption:\n");
    for(i=0; i<block_len; i++) diff[i] = v[1][i]-v[0][i];
    print_block(diff, block_len);

    return 0;
}