* C PROGRAMMING ASSIGNMENT *

Password Recovery

For this assignment, you will write a program that will attempt to recover a salted and hashed password using a file of candidate passwords. The file could be interpreted as either a list of easy passwords that a proactive password checker would wish to exclude, or possibly as a list of possible passwords that an attacker would wish to use for matching against a possibly stolen hashed password file. The inputs to the program will be a dictionary file of candidate passwords and a numerical hash value that you will need to examine. You will also know in advance the hash algorithm to use and how passwords are salted before they are hashed.

Programming Language

The program must be written in C, you must use only the standard libraries, such as stdio.h, math.h, and the Standard Template Library.

Command Line Arguments

The program must read in two command line arguments.

The command line arguments for this program are as follows:

1. The first argument will be full name of the dictionary file to use. If the name, as given, does not contain ".txt", do not add ".txt" to the name. To be sure your program can handle file names with and without the ".txt" file extensions, you can download the sample dictionary files shortlist and names.txt, which are identical except for the names of the files.

==============================

names.txt

==============================

KNZAVM

CPKCCA

KMUAXP

QWHRBP

PYWXZC

HTMBRW

SFSNVV

TGEDED

NDBKCF

YPSEFK

OMKFXI

TOFHTP

GPOKMI

AVSCTG

JTBSWA

PTDYFK

RPOKQF

BPOOOJ

ZUOWGL

YXPUKC

TWAGXW

GKILNG

JXETAX

CQVSSM

QQXNLD

PCBXXA

RHTKBU

DEDKDK

XQDTJX

MCYFZJ

NDDWXZ

UYLHCC

PJRYVW

SVRWED

KYQXSH

FSGNGX

CAQIWT

QKXUKQ

NOHOUF

LTCKRH

XUWMNG

GCDOUY

ZXDODS

GYMXCV

QBHJEQ

ZCJPTR

XUHNWD

WHBKZO

CRUSDS

HXNKPY

VLOZWH

ZSWJVC

BVHMSX

AIHCHU

MFMNFE

CAEIEI

KWUMHG

FXGIEC

QJKEOR

JBMIUP

ALNTDJ

GZUKLL

PHBDUC

QHYBEG

VKHTWK

JVPJYL

WXMJZB

RJASZL

LBCVSQ

QQCZOT

JKZZIS

GGXSUV

CPKDBQ

XLPFZQ

AFCQJC

BAKDHK

RUQMNB

UJVWFA

MZRHLS

CWOFIW

BXXWJM

UFDWLS

EAWRJY

UEUQCF

PFBRRF

ELIENG

SFESTI

UROGXO

JJFCUO

CELIPS

OQHZVL

KCIOET

WFVHEE

IGXVHF

ZQQBVU

JRQLDM

GWGWKQ

MNODRM

XDHQVB

RVQTTM

========================

2. The second argument will be a numeric string representing the numeric hash value to examine, for example "9560204" (but without any quotation marks).

Dictionary Files

All dictionary files of candidate passwords that your program will be tested against will be text files that will contain random 6-character passwords, all upper case, where each character may be any letter of the alphabet from A to Z. There will be one password per line. All passwords will contain exactly 6 upper case letters. The following is an example of what a password file may look like:

Program Operation

Your program must perform the following operations each time it is executed:

1. The program must retrieve the command arguments and output them in the output header, which must also identify the course and program author(s), as described in the section on required output below.

2. The program must preprocess the dictionary file by reading up all entries, computing their ASCII values (as described below), and then report each candidate password and its ASCII value in a numbered list, as also illustrated in the required output section.

3. Following preprocessing, the program must do the following:

a. initialize a counter to count the number of salt-password combinations examined

b. for each candidate password in the dictionary

-for each possible salt value

--increment the counter of combinations

--prepending the salt value to the ASCII value for the candidate password

--compute the hash value of the salted password

--compare the computed hash value to the hash value that was received as the second command argument:

---if the two values are the same, report the password found, the salt value used, and the current count, as illustrated in the required output section

---else if the values do not match, loop to test the next salt-password combination

-if no match was found after testing all combinations, report that the password is not in the dictionary and the total number of combinations examined, as illustrated in the required output section

Computing the ASCII Value for a Password

The C, C++, and Java programming languages all read and interpret characters as integer values. The integer values for alphabetic characters are their ASCII values, so no special processing is required. For the upper case letters from A to Z, the ASCII values are in the range from 65 (for A) to 90 (for Z). The program preview lecture and slide set contains sample programs in C and Java that you can use to confirm this.

Therefore, the procedure for computing the ASCII value for a candidate password is to use your programming language to interpret each character of the password as an integer, and simply concatenate the ASCII decimal values for each character to get the ASCII value for the entire password.

For example, consider the candidate password KNZAVM. The ASCII values for the individual upper case characters are: 75 (for K), 78 (for N), 90 (for Z), 65 (for A), 86 (for V) and 77 (for M). Using these values, the ASCII value for the password is therefore 757890658677. Please note that the ASCII value for all candidate passwords will contain exactly 12 decimal digits since the value for each individual upper case letter will be in the range from 65 to 90.

How Passwords are Salted

The salt values for this assignment will consist of 3 decimal digits. Since each digit can be in the range from 0 to 9, there are therefore 1,000 possible salt values (from 000 to 999) for each candidate password.

The salt value is always prepended to the password, that is, it is added at the left of the ASCII value for the password. For example, if a salt value of, say, 372, is appended to the ASCII password value, the result will be the salted password 372757890658677. Please note that a salted password will always consist of exactly 15 decimal digits.

Computing the Hash Value

For this assignment, we will use a simple linear congruential generator as our hash function. This is how it should be applied:

1. Split the 15-digit salted password into two parts. The 7 leftmost digits will comprise the "left" part, and the remaining 8 rightmost digits will comprise the "right" part.

2. Interpret "left" and "right" as long integers in your programming language. For C programs, you can use the "atol(s)" function to do this.

3. Compute the hash value as follows:

Please note that the numbers 243 and 85767489 are fixed numbers and will not change. Feel free to hard code these numbers.

Please also note that the result of the remainder operator ("%") is to produce a value in the range from 0 to 85767488. This should be a sufficiently large range of values that is should be impractical for us to figure out the password and salt value given the hash value. This is why we need to use a dictionary for this assignment.

Required Output

All program output should be to the screen. The required format is illustrated in the screen shots below. The sections of the output are:

1. Output header section, containing:

40 hyphens (used to separate different test runs)

the course name and author(s)

echo of command arguments

2. Dictionary report section, containing:

a numbered list of each candidate password in the dictionary and its computed ASCII value

3. Success report, if the password was found in the dictionary, containing:

the password that was recovered

the ASCII value for the password

the salt value that was used

the count of the total number of salt-password combinations that had been examined at the time the password was recovered

4. Or a Failure report, if the password was not found in the dictionary, containing:

the statement, "Password not found in dictionary"

the total number of salt-password combinations that had been examined in the search

Output header and beginning of Dictionary report:

End of Dictionary report and Success report:

End of Dictionary report and Failure report (for input hash value 9560205):