/* Homework 1 of Topics in Network Security
 * by Bettati, Klappenecker, and Reddy; Spring 2004. 
 */

/* This source code accompanies an executable that runs on 
 * typical windows/intel machines. This program implements 
 * a single round of a Feistel cipher operating on an input 
 * block of length 64 bits. You can provide the cipher with 
 * 16 consecutive digits in base 16, specifying the plaintext. 
 * The program will produces 16 digit ciphertext as output.
 * Your task is it to determine the key setting in the executable
 * using differential cryptanalysis. 
 */ 

/* Your C compiler needs to support the long long datatype. 
 * Use, for instance, gcc. You can compile this file with 
 * gcc test.c -o test
 */ 

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

typedef unsigned char u8;
typedef unsigned long u32;
typedef unsigned long long u64;

u8 S[8][64] /* S-boxes S[0]=S1,...,S[7]=S8 */ 	  
= {    /** S1 ******************************************************/
       {14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
	 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
	 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
	15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13},
       
       /** S2 ******************************************************/
       {15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
	 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
	 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
	13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9},

       /** S3 ******************************************************/
       {10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
	13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
	13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
	 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12},

       /** S4 ******************************************************/
       { 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
	13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
	10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
	 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14},

       /** S5 ******************************************************/
       { 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
	14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
	 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
	11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3},

       /** S6 ******************************************************/
       {12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
	10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
	 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
	 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13},

       /** S7 ******************************************************/
       { 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
	13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
	 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
	 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12},

       /** S8 ******************************************************/
       {13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
	 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
	 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
	 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11}	
};

/* An S-box is addressed using the most significant bit 
 * and the least significant bit to find the row
 * and the four middle bits to find the column */ 
u8 Sbox(u8 num, char x) { 
  u8 row, col;
 
  row = (0x20 & x)>>4 | (0x01 & x); 
  col = (0x1e & x)>>1;  
  return S[num][(row<<4)+col];
}

void apply_Sboxes(u8 * k) { 
  int i;

  for(i=0; i<8; i++) {
    k[i] = Sbox(i,k[i]);
  }
}

char E[48] = { /* the bit expansion */ 
  32,  1,  2,  3,  4,  5,
   4,  5,  6,  7,  8,  9,
   8,  9, 10, 11, 12, 13,
  12, 13, 14, 15, 16, 17,
  16, 17, 18, 19, 20, 21,
  20, 21, 22, 23, 24, 25,
  24, 25, 26, 27, 28, 29,
  28, 29, 30, 31, 32,  1
};

/* Get the bit at position pos using the odd convention that the
 * most significant bit is 1 and the least significant bit is 32 */ 
int get_bit(u32 x, int pos) { 
  return (  (x >> (32-pos)) & 0x1);
}

/* set a bit in an array of 8 characters, where each character 
 * stores 6 bits; pos should be in the range [0..47]. */
void set_bit(u8 *k, int pos) { 
 
  k[pos/6] |= 1<<(5-(pos % 6));
}       

void expand(u32 right, u8 *k) {
  int i;
  for(i=0; i<48; i++) 
    if(get_bit(right,E[i])) set_bit(k,i); 
}

int main(int argc, char ** argv) {
  u64 plaintxt;
  u32 left, right;
  u8 k[8] = {0,0,0,0,0,0,0,0};


  if(argc !=2) { 
    fprintf(stderr, "Usage: test <plaintext, 16 digits in base 16>."); 
    fprintf(stderr, " For instance,\n");
    fprintf(stderr, "test ff01020304050607");

    exit(1);
  }
   
  /* Step 0: read the input */
  plaintxt = strtoull(argv[1], NULL, 16);
  left     = (u32) (plaintxt >> 32); 
  right    = plaintxt & 0xffffffff;

  /* Step 1: expand bits of right part */ 
  expand(right, k); 

  /* Step 2: xor the key to the eight fields of k, where 
   * each key field should range from  0x00 to 0x3f */ 
  k[0] ^= 0x01;
  k[1] ^= 0x02;
  k[2] ^= 0x03;
  k[3] ^= 0x04;
  k[4] ^= 0x05;
  k[5] ^= 0x06;
  k[6] ^= 0x07;
  k[7] ^= 0x08;

  /* Step 3: apply  S-boxes */ 
  apply_Sboxes(k);

  /* Step 4: xor result to the left side */  
  left ^= k[0]<<28 | k[1]<<24 | k[2]<<20 | k[3]<<16
          | k[4]<<12 | k[5]<< 8 | k[6]<< 4 | k[7];  
  
  /* Step 5: output cryptogram */ 
  printf("%08lx%08lx\n",  left, right);
  
  exit(0);
}