//Differential Cryptanalysis of FEAL-4
//Uses a chosen-plaintext attack to fully recover the last round subkey
//For use with tutorial at http://theamazingking.com/crypto-feal.php
//Hack the Planet!

#include <stdio.h>
#include <math.h>

unsigned long subkey[6];

unsigned long long shiftLeft2(unsigned long a)
{
    unsigned long b;

    unsigned long carry = (a >> 7LL);
    carry &= 0x1LL;
    b = a << 1LL;
    b += carry;
    b &= 0xFFLL;

    carry = (b >> 7LL);
    carry &= 0x1LL;
    b <<= 1LL;
    b += carry;
    b &= 0xFFLL;

    return b;
}

unsigned long gBox(unsigned long a, unsigned long b, unsigned long mode)
{
    return shiftLeft2((a + b + mode) % 256LL);
}

unsigned long fBox(unsigned long plain)
{
    unsigned long x0 = plain & 0xFFL;
    unsigned long x1 = (plain >> 8L) & 0xFFL;
    unsigned long x2 = (plain >> 16L) & 0xFFL;
    unsigned long x3 = (plain >> 24L) & 0xFFL;

    unsigned long t0 = (x2 ^ x3);
    unsigned long t1 = gBox(x0 ^ x1, t0, 1L);

    unsigned long y0 = gBox(x0, t1, 0L);
    unsigned long y1 = t1;
    unsigned long y2 = gBox(t0, t1, 0L);
    unsigned long y3 = gBox(x3, y2, 1L);

    unsigned long ret =  y3 << 24L;
                 ret += (y2 << 16L);
                 ret += (y1 << 8L);
                 ret += y0;

    return ret;
}

unsigned long long encrypt(unsigned long long plain)
{
    unsigned long left = (plain >> 32LL) & 0xFFFFFFFFLL;
    unsigned long right = plain & 0xFFFFFFFFLL;

    left = left ^ subkey[4];
    right = right ^ subkey[5];

    unsigned long round2Left = left ^ right;
    unsigned long round2Right = left ^ fBox(round2Left ^ subkey[0]);

    unsigned long round3Left = round2Right;
    unsigned long round3Right = round2Left ^ fBox(round2Right ^ subkey[1]);

    unsigned long round4Left = round3Right;
    unsigned long round4Right = round3Left ^ fBox(round3Right ^ subkey[2]);

    unsigned long cipherLeft = round4Left ^ fBox(round4Right ^ subkey[3]);
    unsigned long cipherRight = cipherLeft ^ round4Right;

    unsigned long long ret = (((unsigned long long)(cipherLeft)) << 32LL);
    ret += (((unsigned long long)(cipherRight)) & 0xFFFFFFFFLL);

    return ret;
}

void generateSubkeys(int seed)
{
    srand(time(NULL));

    int c;
    for(c = 0; c <  6; c++)
    {
        subkey[c] = rand() << 16L;
        subkey[c] += rand() & 0xFFFFL;
    }
}


int numPlain;
unsigned long long plain0[10000];
unsigned long long cipher0[10000];
unsigned long long plain1[10000];
unsigned long long cipher1[10000];

unsigned long key3winner;

void crackSubkey3ULTRA()
{

    unsigned long fakeK;
    for(fakeK = 0x00000000L; fakeK < 0xFFFFFFFFL; fakeK++)
    {
        int score = 0;

        int c;
        for(c = 0; c < numPlain; c++)
        {
            unsigned long cipherLeft = (cipher0[c] >> 32LL);
            cipherLeft ^= (cipher1[c] >> 32LL);
            unsigned long cipherRight = cipher0[c] & 0xFFFFFFFFLL;
            cipherRight ^= (cipher1[c] & 0xFFFFFFFFLL);

            unsigned long Y = cipherLeft ^ cipherRight;
            unsigned long Z = cipherLeft ^ 0x02000000L;

            unsigned long fakeRight = cipher0[c] & 0xFFFFFFFFLL;
            unsigned long fakeLeft = cipher0[c] >> 32LL;
            unsigned long fakeRight2 = cipher1[c] & 0xFFFFFFFFLL;
            unsigned long fakeLeft2 = cipher1[c] >> 32LL;

            unsigned long Y0 = fakeLeft ^ fakeRight;
            unsigned long Y1 = fakeLeft2 ^ fakeRight2;

            unsigned long fakeInput0 = Y0 ^ fakeK;
            unsigned long fakeInput1 = Y1 ^ fakeK;
            unsigned long fakeOut0 = fBox(fakeInput0);
            unsigned long fakeOut1 = fBox(fakeInput1);
            unsigned long fakeDiff = fakeOut0 ^ fakeOut1;

            if (fakeDiff == Z) score++; else break;
        }

        if (score == numPlain)
        {
            printf("DISCOVERED ROUND #4 SUBKEY = %08lx\n", fakeK);
            printf("    ACTUAL ROUND #4 SUBKEY = %08lx\n", fakeK);

            key3winner = fakeK;
            break;
        }
    }
}

void chosenPlaintext(unsigned long long diff)
{
    srand(time(NULL));

    printf("PLAINTEXT DIFFERENTIAL = %llx\n\n", diff);

    int c;
    for(c = 0; c < numPlain; c++)
    {
        plain0[c] = (rand() & 0xFFFFLL) << 48LL;
        plain0[c] += (rand() & 0xFFFFLL) << 32LL;
        plain0[c] += (rand() & 0xFFFFLL) << 16LL;
        plain0[c] += (rand() & 0xFFFFLL);

        cipher0[c] = encrypt(plain0[c]);
        plain1[c] = plain0[c] ^ diff;
        cipher1[c] = encrypt(plain1[c]);
    }
}

int main()
{
    generateSubkeys(time(NULL));

    numPlain = 6;
    chosenPlaintext(0x8080000080800000LL);

    unsigned long startTime = time(NULL);

        crackSubkey3ULTRA();

    unsigned long endTime = time(NULL);
    printf("Time to crack round #4 = %i seconds\n\n", (endTime - startTime));

    return 0;
}