//Jon King
//Impossible Differentials

#include <stdio.h>

int sbox[16] = {3, 14, 1, 10, 4, 9, 5, 6, 8, 11, 15, 2, 13, 12, 0, 7};
int sboxRev[16] = {14, 2, 11, 0, 4, 6, 7, 15, 8, 5, 3, 9, 13, 12, 1, 10};
int pbox[8] = {1, 6, 0, 7, 2, 3, 5, 4};
int pboxRev[8] = {2, 0, 4, 5, 7, 6, 1, 3};

int mySPBox[256];
int chars[256][256];

int revSPBox(int input)
{
    int c;
    for(c = 0; c < 256; c++)
    {
        if (mySPBox[c] == input) return c;
    }
}

int spBox(int input)
{
    int lefthalf = input / 16;
    int righthalf = input & 15;
    lefthalf = sbox[lefthalf];
    righthalf = sbox[righthalf];
    int combined = lefthalf * 16 + righthalf;

    int total = 0;
    int c;
    for(c = 0; c < 8; c++)
    {
         int inBit = combined % (int)(pow(2, c + 1));
         inBit = inBit / (int)(pow(2, c));
         total += inBit * pow(2, pbox[c]);
    }
    return total;
}

void createSPBox()
{
    int c;
    for(c = 0; c < 256; c++)
        mySPBox[c] = spBox(c);
}

int roundFunc(int input, int subkey)
{
    return mySPBox[input ^ subkey];
}

int encrypt(int input, int k0, int k1, int k2, int k3, int k4)
{
    int r0 = roundFunc(input, k0);
    int r1 = roundFunc(r0, k1);
    int r2 = roundFunc(r1, k2);
    int r3 = roundFunc(r2, k3);
    return roundFunc(r3, k4);
}

void genChars()
{
    printf("\nOne-round impossible differentials:\n");

    int c, d;

    for(c = 0; c < 256; c++)
        for(d = 0; d < 256; d++)
        {
            int indiff = c ^ d;
            int outdiff = mySPBox[c] ^ mySPBox[d];
            chars[indiff][outdiff]++;
        }

    for(c = 0; c < 256; c++)
    {
        for(d = 0; d < 256; d++)
        {
            if (chars[c][d] == 0)
            //if (c == 140)
                printf("  %i:  %i --> %i\n", chars[c][d], c, d);
        }
    }
}

int goodP0, goodP1, goodC0, goodC1;
int knownP0[10000];
int knownC0[10000];
int knownP1[10000];
int knownC1[10000];
int numPairs = 100;

int k0, k1, k2, k3, k4;

void chooseKey()
{
    k0 = rand() % 256;
    k1 = rand() % 256;
    k2 = rand() % 256;
    k3 = rand() % 256;
    k4 = rand() % 256;

    printf("\nREAL KEY = %i, %i, %i, %i, %i\n\n", k0, k1, k2, k3, k4);
}

void choosePairs(int indiff, int pairs)
{
    numPairs = pairs;

    int c;
    for(c = 0; c < numPairs; c++)
    {
        knownP0[c] = rand() % 256;
        knownP1[c] = knownP0[c] ^ indiff;
        knownC0[c] = encrypt(knownP0[c], k0, k1, k2, k3, k4);
        knownC1[c] = encrypt(knownP1[c], k0, k1, k2, k3, k4);
        knownC0[c] = revSPBox(knownC0[c]);
        knownC1[c] = revSPBox(knownC1[c]);
    }
}

int isPath(int src, int dest, int level)
{
        if (level == 1)
            if (chars[src][dest] == 0) return 0; else return 1;
        else
        {
            int c;
            for(c = 0; c < 255; c++)
            {
                if (chars[src][c] > 0)
                {
                    if (isPath(c, dest, level-1)) return 1;
                }
            }

        }


    return 0;
}

int impIn[10000];
int impOut[10000];
int numImp = 0;

void findImpossible(int length)
{
    printf("\n%i-round impossible differentials\n\n", length);
    int d;
    for(d = 1; d < 255; d++)
    {
        int c;
        for(c = 1; c < 255; c++)
        {
            if (isPath(d, c, length) == 0)
            {
                printf("  IMPOSSIBLE for %i rounds: %i -> %i\n",length, d , c);
                impIn[numImp] = d;
                impOut[numImp] = c;
                numImp++;
            }
        }
    }
}

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

    //OFFLINE PHASE

    printf("OFFLINE PHASE\n");
    printf("------------------------------\n\n");

    createSPBox();
    genChars();
    findImpossible(3);

    //ONLINE PHASE



    chooseKey();
    //genCharData();
    int d;
    int keyCandidate[256];
    for(d = 0; d < 255; d++) keyCandidate[d] = 0;

    printf("\n");
    printf("ONLINE PHASE\n");
    printf("------------------------------\n\n");


    int pairs = 100;

    for(d = 0;d < numImp; d++)
    {

        choosePairs(impIn[d], pairs);
        printf("  Generating %i pairs...Ruling out subkeys using: %i --> %i\n", numPairs, impIn[d], impOut[d]);
        int e, f;
        for(e = 0; e < numPairs; e++)
        {
            for(f = 0; f < 255; f++)
            {
                int revKnownC0 = revSPBox(knownC0[e] ^ f);
                int revKnownC1 = revSPBox(knownC1[e] ^ f);
                if ((revKnownC0 ^ revKnownC1) == impOut[d])
                {
                    keyCandidate[f] = 1;
                }
            }
        }
    }


    for(d = 0; d < 255; d++) if (keyCandidate[d] == 0) printf("LAST ROUND SUBKEY CANDIDATE: %i\n", d);

/*
    int s,t,u,v,w;

    for(s = 0; s < 255; s++)
        for(t = 0;t < 255; t++)
            for(u = 0; u < 255; u++)
                for(v = 0; v < 255; v++)
                    for(w = 0; w < 255; w++)
                        if (encrypt(knownP1[1], k0, k1, k2, k3, k4) == spBox(knownC1[1]))
                        {

                        }
*/


    printf("DONE\n");
    while(1){}
    return 0;
}