/*
Code for breaking enRUPT in block cipher mode with a related key attack.
Breaks the full enRUPT for 256-bit keys, 128-bit block with about 2^65 chosen plaintexts.
The block hashing mode of enRUPT is also likely affected, but I didn't check.

Some explanation here...

Both XXTEA and enRUPT are
   m[i] += f(m[i-1], m[i+1], ...)

I broke XXTEA with an attack that uses a delta so that
   f(m[i-1], m[i+1], ...) == f(m[i-1]+delta, m[i+1], ...)
and
   f(m[i-1], m[i+1], ...) == f(m[i-1], m[i+1]+delta, ...)
with a relatively high probability.

This attack can't be directly used for enRUPT:
   - there's only one such delta for left-to-right propagation: 0x80000000.
   - there's no such delta for right-to-left propagation.

But, we can apply such a delta in the key!

So, I rigged spiffysolver, which is my special root finder designed for crypto, to find such deltas.

Here are the best ones I found:
02128292 29849/16777216
92021282 17197/16777216
49010941 14545/16777216
90109434 13031/16777216
96021282 11070/16777216
82920212 10772/16777216
01094149 10714/16777216

The first one is clearly the best, so we'll use that.

The round keys are used cyclically. For 256-bit key & 128-bit block each key word is used
only 8 times. We have to pass 7. The probability that the best delta works is roughly 2^-9.14,
though it's pretty weakly estimated. Nonetheless, it's clear that it's definitely enough to
break enRUPT.

Running multithreaded on a Core i7 920, I was able to break 40 of 64 rounds in a few hours.

04012009: initial release
*/

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

// a PRNG
void hrng_init(uint32_t seed);
uint32_t hrng();


/* Note: we lower the number of rounds with this.
   The default number of rounds for 256-bit keys, 128-bit block is 64. */
#define RNDS 32

#define rot(a,b) (((a)<<(b))|((a)>>(32-(b))))
#define rotr(a,b) rot(a,32-(b))
#define er1(k) (rotr(2*x[(r-1)%xw]^x[(r+1)%xw]^k^r,8)*9^k)
void enRUPT(uint32_t *x, const uint32_t xw, uint32_t *key, const uint32_t kw)
{
    uint32_t r, s=4, n=s*(2*xw+kw);
    for (r=1; r<=RNDS; r++) x[r%xw] ^= er1(key[r%kw]);
}

#define LEN 4
#define KLEN 8

/* This is the function for requesting chosen plaintexts. */
void encrypt(uint32_t *m, uint32_t *relation)
{
    // This is the key we'll try to recover by requesting encrypted blocks:
    uint32_t k[KLEN]={0xCAFEBABE, 0x56756756, 0x55555555, 0xDEADBEEF,
                      0x46354646, 0xab78f783, 0x12345678, 0x87654318};
    int i;
    for(i=0;i<KLEN;i++)
        k[i]^=relation[i];

    enRUPT(m,LEN,k,KLEN);
}




/* Key recovery part begins here */
// ------------------------------------------------------------------------

#define NUM 8 /* How many right pairs should we look for? */

#define DELTA (0x02128292)
#define F(lr,r,k) (rot((lr)^(k)^(r), 24)*9 ^ (k))

struct
{
    uint32_t lr, xy, mid1, mid2;
} inf[NUM];

struct
{
    uint32_t *keys;
    int count;
} rkeys;

void recurse_get_keys(uint32_t key, int pos)
{
    int j;
    for(j=0;j<NUM;j++)
    {
        inf[j].mid1 = F(inf[j].lr, RNDS, key);
        inf[j].mid2 = F(inf[j].lr, RNDS, key^DELTA);
        if(pos<32)
        {
            if((inf[j].mid1^inf[j].mid2^inf[j].xy)&((1<<pos)-1))
                break;
        } else
            if(inf[j].mid1^inf[j].mid2^inf[j].xy) // <<32 is actually <<0 on x86, this hack fixes it
                break;
    }
    if(j!=NUM)
        return;

    if(pos==32)
    {
        rkeys.count++;
        rkeys.keys=realloc(rkeys.keys, rkeys.count*4); // Hardly optimal but meh.
        rkeys.keys[rkeys.count-1]=key;
        return;
    }

    recurse_get_keys(key, pos+1);
    recurse_get_keys(key|rot(1<<8,pos), pos+1);
    return;
}

int count_keys(uint32_t m[NUM][2][LEN], uint32_t **outptr)
{
    uint32_t i;

    rkeys.keys=0;
    rkeys.count=0;
    for(i=0;i<NUM;i++)
    {
        inf[i].lr = m[i][0][LEN-1]*2 ^ m[i][0][1];
        inf[i].xy = m[i][0][0] ^ m[i][1][0];
    }

    recurse_get_keys(0, 0);
    *outptr=rkeys.keys;
    return rkeys.count;
}

// ------------------------------------------------------------------------


int main()
{
    hrng_init(12345);

    time(0);

    int i, j;
    uint32_t count=0;
    uint32_t *keys;

    uint32_t m[NUM][2][LEN];
    uint32_t rel[2][KLEN];

    memset(rel, 0, sizeof(rel));
    rel[1][0]=DELTA;

    printf("Searching for %u right pairs...\n", NUM);

    for(count=0;count<NUM;)
    {
        for(j=0;j<LEN;j++)
            m[count][0][j]=m[count][1][j]=hrng();

        encrypt(m[count][0], rel[0]);
        encrypt(m[count][1], rel[1]);

        if(memcmp(&m[count][0][1],&m[count][1][1],(LEN-1)*4)==0)
        {
            count++;
            printf("Found a right pair! %u/%u\n", count, NUM);
        }
    }

    printf("Searching for possible keys...\n");
    count=count_keys(m, &keys);

    printf("\nGot %u possible keys.\n",count);

    for(i=0;i<count;i++)
    {
        if(i%8==0)
            printf("\n");
        printf("%08X ", keys[i]);
    }

    free(keys);

    printf("\nDone.\n");

    return 0;
}


/*

PRNG code begins here, not relevant.

*/

// ------------------------------------------------------------------------

unsigned int hrng_pos=16;
uint32_t hrng_state[4];
uint32_t hrng_out[16];

static void hrng_scramble()
{
    // This is used to get the PRNG far from its initial
    // state. It's a bad idea to simply skip some of the
    // bitstream, as similar begin-states can lead to
    // similar states after some specific number of rounds.
    hrng_state[1] = rot(hrng_state[1],19)+0x9e3779b9;
    hrng_state[0] = rot(hrng_state[0]^hrng_state[1],5);
    hrng_state[2]-= hrng_state[0];
    hrng_state[3]-= hrng_state[2];
    hrng_state[3] = rot(hrng_state[3],19);
    hrng_state[2] = rot(hrng_state[2]^hrng_state[3],5);
    hrng_state[0]-= hrng_state[2];
    hrng_state[1]-= hrng_state[0];
}

void hrng_init(uint32_t seed)
{
    int i;
    for(i=0;i<4;i++)
        hrng_state[i]=seed^i;
    for(i=0;i<16;i++)
        hrng_scramble();
    hrng_pos=16;
    return;
}

uint32_t hrng()
{
    if(hrng_pos>=16)
    {
        int i;
        for(i=0;i<4*4;i+=4)
        {
            // manual unroll for great glory
            // each chunk generates one dword

            hrng_state[0]^= hrng_state[2];
            hrng_state[3]+= hrng_state[0];
            hrng_state[2] =~hrng_state[2];
            hrng_state[3] = rot(hrng_state[3],8)-hrng_state[0];
            hrng_out[i+0] = hrng_state[0];

            hrng_state[1]^= hrng_state[3];
            hrng_state[0]+= hrng_state[1];
            hrng_state[3] =~hrng_state[3];
            hrng_state[0] = rot(hrng_state[0],8)-hrng_state[1];
            hrng_out[i+1] = hrng_state[1];

            hrng_state[2]^= hrng_state[0];
            hrng_state[1]+= hrng_state[2];
            hrng_state[0] =~hrng_state[0];
            hrng_state[1] = rot(hrng_state[1],8)-hrng_state[2];
            hrng_out[i+2] = hrng_state[2];

            hrng_state[3]^= hrng_state[1];
            hrng_state[2]+= hrng_state[3];
            hrng_state[1] =~hrng_state[1];
            hrng_state[2] = rot(hrng_state[2],8)-hrng_state[3];
            hrng_out[i+3] = hrng_state[3];
        }
        hrng_pos=0;
    }
    return hrng_out[hrng_pos++];
}