/*********************************************************\
*  Password Probability Matrix   *    File: ppm_crack.c   *
***********************************************************
*                                                         *
*  Author:        Jon Erickson <matrix@phiral.com>        *
*  Organization:  Phiral Research Laboratories            *
*                                                         *
*  This is the crack program for the PPM proof of concept *
*  It uses an existing file called 4char.ppm, which       *
*  contains information regarding all possible 4          *
*  character passwords salted with 'je'.  This file can   *
*  be generated with the corresponding ppm_gen.c program. *
*                                                         *
\*********************************************************/

#define _XOPEN_SOURCE
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

#define HEIGHT 16384
#define WIDTH  1129
#define DEPTH 8
#define SIZE HEIGHT * WIDTH * DEPTH
#define DCM HEIGHT * WIDTH


int singleval(char a)
{
  int i, j;
  i = (int)a;
  if((i >= 46) && (i <= 57))
    j = i - 46;
  else if ((i >= 65) && (i <= 90))
    j = i - 53;
  else if ((i >= 97) && (i <= 122))
    j = i - 59;
  return j;
}

int tripleval(char a, char b, char c)
{
  return (((singleval(c)%4)*4096)+(singleval(a)*64)+singleval(b));
}

void merge(char *vector1, char *vector2)
{
  int i;
  for(i=0; i < WIDTH; i++)
    vector1[i] &= vector2[i];
}

int length(char *vector)
{
  int i, j, count=0;
  for(i=0; i < 9025; i++)
    count +=  ((vector[(i/8)]&(1<<(i%8)))>>(i%8));
  return count;
}

int grab(char *vector, int index)
{
  char val;
  int a, b;
  int word = 0;

  val = ((vector[(index/8)]&(1<<(index%8)))>>(index%8));
  if (!val)
    index = 31337;
  return index;
}

void show(char *vector)
{
  int i, a, b;
  int val;
  for(i=0; i < 9025; i++)
  {
    val = grab(vector, i);

    if(val != 31337)
    {
      a = val / 95;
      b = val - (a * 95);
      printf("%c%c ",a+32, b+32);
    }
  }
  printf("\n");
}

main()
{
  char plain[5];
  char pass[14];
  char bin_vector1[WIDTH];
  char bin_vector2[WIDTH];
  char temp_vector[WIDTH];
  char prob_vector1[2][9025];
  char prob_vector2[2][9025];
  int a, b, i, j, len, pv1_len=0, pv2_len=0;
  FILE *fd;

  if(!(fd = fopen("4char.ppm", "r")))
  {
    printf("Error: Couldn't open PPM file for reading.\n");
    exit(1);
  }

  printf("Input encrypted password (salted with 'je') : ");
  scanf("%s", &pass);

  printf("First 2 characters: \tSaturation\n");

  fseek(fd,(DCM*0)+tripleval(pass[2], pass[3], pass[4])*WIDTH, SEEK_SET);
  fread(bin_vector1, WIDTH, 1, fd);

  len = length(bin_vector1);
  printf("sing length = %d\t%f%\n", len, len*100.0/9025.0);

  fseek(fd,(DCM*1)+tripleval(pass[4], pass[5], pass[6])*WIDTH, SEEK_SET);
  fread(temp_vector, WIDTH, 1, fd);
  merge(bin_vector1, temp_vector);

  len = length(bin_vector1);
  printf("dual length = %d\t%f%\n", len, len*100.0/9025.0);

  fseek(fd,(DCM*2)+tripleval(pass[6], pass[7], pass[8])*WIDTH, SEEK_SET);
  fread(temp_vector, WIDTH, 1, fd);
  merge(bin_vector1, temp_vector);

  len = length(bin_vector1);
  printf("trip length = %d\t%f%\n", len, len*100.0/9025.0);

  fseek(fd,(DCM*3)+tripleval(pass[8], pass[9],pass[10])*WIDTH, SEEK_SET);
  fread(temp_vector, WIDTH, 1, fd);
  merge(bin_vector1, temp_vector);

  len = length(bin_vector1);
  printf("quad length = %d\t%f%\n", len, len*100.0/9025.0);
  show(bin_vector1);

  printf("Last 2 characters: \tSaturation\n");

  fseek(fd,(DCM*4)+tripleval(pass[2], pass[3], pass[4])*WIDTH, SEEK_SET);
  fread(bin_vector2, WIDTH, 1, fd);

  len = length(bin_vector2);
  printf("sing length = %d\t%f%\n", len, len*100.0/9025.0);

  fseek(fd,(DCM*5)+tripleval(pass[4], pass[5], pass[6])*WIDTH, SEEK_SET);
  fread(temp_vector, WIDTH, 1, fd);
  merge(bin_vector2, temp_vector);

  len = length(bin_vector2);
  printf("dual length = %d\t%f%\n", len, len*100.0/9025.0);

  fseek(fd,(DCM*6)+tripleval(pass[6], pass[7], pass[8])*WIDTH, SEEK_SET);
  fread(temp_vector, WIDTH, 1, fd);
  merge(bin_vector2, temp_vector);

  len = length(bin_vector2);
  printf("trip length = %d\t%f%\n", len, len*100.0/9025.0);

  fseek(fd,(DCM*7)+tripleval(pass[8], pass[9],pass[10])*WIDTH, SEEK_SET);
  fread(temp_vector, WIDTH, 1, fd);
  merge(bin_vector2, temp_vector);

  len = length(bin_vector2);
  printf("quad length = %d\t%f%\n", len, len*100.0/9025.0);
  show(bin_vector2);

  printf("Building probability vectors...\n");
  for(i=0; i < 9025; i++)
  {
    j = grab(bin_vector1, i);
    if(j != 31337)
    {
      prob_vector1[0][pv1_len] = j / 95;
      prob_vector1[1][pv1_len] = j - (prob_vector1[0][pv1_len] * 95);
      pv1_len++;
    }
  }
  for(i=0; i < 9025; i++)
  {
    j = grab(bin_vector2, i);
    if(j != 31337)
    {
      prob_vector2[0][pv2_len] = j / 95;
      prob_vector2[1][pv2_len] = j - (prob_vector2[0][pv2_len] * 95);
      pv2_len++;
    }
  }

  printf("Cracking remaining %d possibilites..\n", pv1_len*pv2_len);
  for(i=0; i < pv1_len; i++)
  {
    for(j=0; j < pv2_len; j++)
    {
      plain[0] = prob_vector1[0][i] + 32;
      plain[1] = prob_vector1[1][i] + 32;
      plain[2] = prob_vector2[0][j] + 32;
      plain[3] = prob_vector2[1][j] + 32;
      plain[4] = 0;
      if(strcmp(crypt(plain, "je"), pass) == 0)
      {
        printf("Password :  %s\n", plain);
        i = 31337;
        j = 31337;
      }
    }
  }
  if(i < 31337)
    printf("Password wasn't salted with 'je' or is not 4 chars long.\n");

  fclose(fd);
}