/*************************************************************
 * crack.c                                                   *
 *                                                           *
 * CS50 OpenCourseWare. PSET 2                               *
 *                                                           *
 * "crack" accepts a single command line argument:           *
 *                                                           *
 * an encrypted password (DES algorithm).                    *
 *                                                           *
 * The program attempts to crack the password using first a  *
 *                                                           *
 * dictionary attack and then if it fails a brute force      *
 *                                                           *
 * attack.                                                   *
 *************************************************************/

#define _XOPEN_SOURCE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <unistd.h>
#include <math.h>

#define CORRECT_ARG_COUNT              2
#define DES_ENCRYPTED_PASSWD_LEN      13
#define WORDLIST  "/usr/share/dict/words"
#define BUFFER_SIZE                   96
#define SALT_LEN                       2
#define MAX_PASSWD_LEN                 8
#define NBR_OF_PRINTBL_ASCII_CHARS    95
#define BASE  NBR_OF_PRINTBL_ASCII_CHARS
#define FIRST_PRINTBL_ASCII_CHAR      32

int check_cmdline_args(int argument_count, const char program_name[], const char ciphertext[]);
int usage(const char program_name[]);
int dictionary_attack(const char ciphertext[]);
int try_potential_passwd(const char potential_passwd[], const char ciphertext[]);
int brute_force_attack(const char ciphertext[]);

int
main(int argc, char *argv[])
{
	/* verify command line arguments number and ciphertex validity
	   if incorrect exit the program */	 
	if (check_cmdline_args(argc, argv[0], argv[1]))
		exit(EXIT_FAILURE);
	
	// if the dictionary attack is unsuccessful attempt a brute force attack
	if (dictionary_attack(argv[1]))
	    brute_force_attack(argv[1]);
  
	exit(EXIT_SUCCESS);
}

/*
 * Checks that the program received an appropriate
 * number of command line arguments. Prints usage if
 * it is not the case.
 * if number of command line arguments is correct,
 * checks that the ciphertext is a DES encrypted password.
 */
int
check_cmdline_args(int argument_count, const char program_name[], const char ciphertext[])
{	
	// check the number of command line arguments
	if (argument_count != CORRECT_ARG_COUNT) {
		if (argument_count < CORRECT_ARG_COUNT)
			fprintf(stderr, "%s: missing argument.\n", program_name);
		else
			fprintf(stderr, "%s: too many arguments.\n", program_name); 
		
		usage(program_name);
		return 1;
		
	} else {
		/* check the validity of the ciphertext.
		   The ciphertext should be a thirteen-character string 
		   chosen from the set [a–zA–Z0–9./] */

   		int ciphertext_len = strlen(ciphertext);

		if (ciphertext_len != DES_ENCRYPTED_PASSWD_LEN) {
			fprintf(stderr, "%s: Ciphertex is not a DES encrypted password\n", program_name);
			return 2;
		}
  
		for (int i = 0; i < ciphertext_len; i++) {
			if (   (ciphertext[i] >= 'a' && ciphertext[i] <= 'z')
			    || (ciphertext[i] >= 'A' && ciphertext[i] <= 'Z')
			    || (ciphertext[i] >= '0' && ciphertext[i] <= '9')
			    ||  ciphertext[i] == '/'
			    ||  ciphertext[i] == '.'  ) {
				
				// do nothing
				;
			
			} else {
				fprintf(stderr, "%s: Ciphertext is not a DES encrypted password\n", program_name);
				return 3;
			}
		}
	}
	
	return 0;
}

/*
 * Prints usage.
 */
int
usage(const char program_name[])
{
	// print to standard error (stderr).
	fprintf(stderr, "Usage: %s <CIPHERTEXT>\n", program_name);
	fprintf(stderr, "Decrypt DES encrypted password.\n");
	
	return 0;
}

/*
 * Attempts to crack a password
 * by trying all the words found in
 * a given wordlist (dictionary).
 */
int 
dictionary_attack(const char ciphertext[])
{	
	// open the worldlist
	FILE *wordlist = fopen(WORDLIST, "r");

	/* if the worldlist is not successfully opened print an error message and return 1
	   otherwise initiate the dictionary attack */
	if (!wordlist) {
		fprintf(stderr, "%s could not be opened.\n", WORDLIST);
		return 1;
	
	} else {
		// will be used to return the appropriate value 
		bool cracked = false;

		// will hold the dictionary's words
		char potential_passwd[BUFFER_SIZE] = {0};
		
		// read the wordlist one line at the time (there is one word per line) until end of the list
		while (fgets(potential_passwd, sizeof (potential_passwd), wordlist) != NULL) {
			const unsigned int potential_passwd_len = strlen(potential_passwd);
			
			// fgets also stores '\n' this last is consequently replaced by '\0' at the end of the string
			if (potential_passwd[potential_passwd_len - 1] == '\n')
				potential_passwd[potential_passwd_len - 1] = '\0';
		   	
			// encrypt the potential password and compare it the ciphertext
			if (!try_potential_passwd(potential_passwd, ciphertext)) {
				cracked = true;
				printf("%s\n", potential_passwd);
				break;
			}
		}
	    
		// close the wordlist
		fclose(wordlist);
		
		if (cracked)
			return 0;
		else 
			return 2;
	}
}

/*
 * Enciphers a given password and compare it to 
 * an already encripted password.
 * Returns 0 if the two match together or 2 if 
 * it is not the case.
 */ 
int 
try_potential_passwd(const char potential_passwd[], const char ciphertext[])
{
	// will hold the salt
	char salt[SALT_LEN + 1] = {0};
	
	// copy into the array salt the first two characters of the ciphertext (the salt)
	strncpy(salt, ciphertext, SALT_LEN);
	
	// add the null terminating byte
	salt[SALT_LEN] = '\0';

	/* the word stored in potential_passwd[] is encrypted and compared to 
	   the ciphertext passed as command line argument. If they match together, 
	   the word stored in potential_passwd[] is the cleartext version of the ciphertext */
	
	char *unciphered_potential_passwd = crypt(potential_passwd, salt);

	if (!unciphered_potential_passwd) {
		fprintf(stderr, "Could not encrypt %s\n", potential_passwd);
		return 1;
	}

	if (strcmp(unciphered_potential_passwd, ciphertext))
		return 2;
	else 
		return 0;
}

/*
 * Attempts to crack a password
 * by trying all possible characters
 * permutations (repetitions allowed).
 * Thanks to CaZe on ##c (freenode)
 */
int 
brute_force_attack(const char ciphertext[])
{
	//will be used to break out of the nested for loops
	bool cracked = false;

	// will hold the generated potential passwords
	char potential_passwd[MAX_PASSWD_LEN + 1] = {0};

	// will hold all the printable ascii characters
	char printbl_ascii_chars[NBR_OF_PRINTBL_ASCII_CHARS] = {0};

	// populate printbl_ascii_chars[] with the printable ascii characters
	for (int i = 0, j = FIRST_PRINTBL_ASCII_CHAR; i < NBR_OF_PRINTBL_ASCII_CHARS; i++, j++)
		printbl_ascii_chars[i] = j;

	/* To generate the characters permutations for a given password length,
	   let's count from zero to BASE raised to the power passwd_len.
	   when counting, instead of base 10, we use base 95 (the number of 
	   printable ascii characters).
	   When counting, instead of using digits, we use printable ascii characters. */
	
	for (int passwd_len = 1; passwd_len <= MAX_PASSWD_LEN; passwd_len++) {
		for (int count = 0; count < pow(BASE, passwd_len); count++) {			
			for (int index = 0, power = passwd_len - 1; index < passwd_len; index++, power--) {
				potential_passwd[index] = printbl_ascii_chars[(int) (count / (pow(BASE, power))) % BASE];
			}
			
			potential_passwd[passwd_len] = '\0';
			
			if (!try_potential_passwd(potential_passwd, ciphertext)) {
				cracked = true;
				printf("%s\n", potential_passwd);
				break;
			}
		}
		
		if (cracked)
			break;
	}
	
	return 0;
}