Final Project – Secure Hash Algorithm (SHA-1) Solved

Description

Your final project is to implement the Secure Hash Algorithm (SHA-1) in C or C++.

• This algorithm takes a file, cuts up and mixes the data, and produces a hash value, which is a numberin a specific range.
• The hash value for SHA1 is 160 bits long, so it has a decimal value of 2¹⁶⁰, which is roughly the number of atoms on planet Earth.
• The SHA-1 hash value is often used in data security for such things as storing passwords securely, error detection, comparing files, and digital signatures.
  • Today, many applications still rely on SHA-1, even though theoretical attacks have been known since 2005, and SHA-1 was officially deprecated by NIST in 2011. For more on this see:https://shattered.io/
  • The attack proving SHA-1 vulnerability required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.
• For detailed specifications of the algorithm, see the NIST documentFIPS180-1-SecureHashStandard.pdfattached below.
  • The specifications are “a bit technical”, but you should spend some time reading it before attempting the project!
  • The description of the algorithm begins on page 6.
  • Appendices A-C have very detailed output that you can use to debug your program. Make sure you understand the document well enough to grasp what Appendix A is saying about the output.
  • The 3 input files described in the appendices are attached below.
    • Appendix A input file is: abc.txt
    • Appendix B input file is: alpha.txt
    • Appendix C input file is: a.txt
  • In the document, “word” refers to data type “int”, both which are 32 bits.

Development and Testing Procedure:

• Write your program using the document specifications and the instructions below.
• Make “debug” print statements so that it will print output like that shown Appendix A.
  • I suggest you make a global int to use as a boolean to turn debug printing on and off in all functions.
• TEST each function as you are writing them! DO NOT attempt to write a big chunk of this thing before you test, it will be impossible to debug!

1. Use abc.txt and Appendix A to write your functions. This is the shortest input file. It has only one “block” as described in the specifications. You should get your output to match all steps shown in Appendix A before moving to the next larger file alpha.txt.
2. Test alpha.txt and get your output to match all steps shown in Appendix B.
3. Before attempting to hash the largest file a.txt,  TURN OFF PRINTING for everything except the final “message digest” outcome! The output will be massive otherwise.

• Wikipedia also has example hashes and SHA-1 pseudocode at http://en.wikipedia.org/wiki/SHA-1
• The “message digest” is the SHA-1 hash that should be the final program output.

Instructions for required functions:

Instructions for readFile function:

unsigned int readFile(unsigned char buffer[])

• The entire contents of the file will be read into and stored in the buffer[]array
  • A 1 (one) bit is appended to the end of the buffer[]array
  • The function returns the number of characters in the file (size of file inbytes). You need this!
  • This is similar to the character counting program from Session 7: counting.c
• Input and count the characters from standard input (stdin) until the end-of-file (EOF).
  • For file input, create a text file or use the provided .txt files below, use the stdin redirection operator (<) on the commandline .
• The buffer array will store the characters. It will be a large array of UNSIGNED (not signed) characters.
  • The largest input file to test your program is 1 million characters, but set your array MAX_SIZE to 1048576 (1 megabyte), or larger.
    • Warning: Your program might not get the correct result for 1 million a’s file (a.txt), if you use 1000001 as the max.
  • Make sure that you have error checking to stop the program and tell the user when the input file is too big for your program.
• At this point you should check if your program puts the correct characters into your array, and counts the correct number of bytes in the file.
• This also might be a good place to append the 1 (one) bit at the end of the message.
  • Note that this is equivalent to adding the byte 0x80 after the last character in the buffer array.
  • For the abc.txt example: buffer[0] = ‘a’ = 0x61, buffer[1] = ‘b’ = 0x62, buffer[2] = ‘c’ = 0x63, and buffer[3] = 0x80.

 Instructions for calculateBlocks function:

unsigned int calculateBlocks(unsigned int sizeOfFileInBytes)

• The next step is to calculate the block count.
  • Since each block is 512 bits, divide the total bits (not bytes) in the file by 512.
  • Before dividing by 512,  make sure to add 1 (one) to the total count to account for the 1 (one) bit that is appended to the end of the data from the file.
• Since the last 64 bits at the end of the last block are reserved for the bit count (not byte count) of the file, one more block must be added for any message that has a final block that is greater than 448 (512 – 64) bits.

• This equation will calculate the block count:

(((8 * sizeOfFileInBytes) + 1) / 512) + 1

• This if statement will determine if an extra block needs to be added or not:

if((((8 * sizeOfFileInBytes) + 1) % 512) > (512 – 64))
blockCount = blockCount + 1

• For the abc.txt example:
  • blocks = ((((8 * sizeOfFileInBytes) + 1) / 512) + 1) = ((((8 * 3) + 1) / 512) + 1) = (0 + 1) = 1.
  • There is no extra block, because the statement if((((8 * sizeOfFileInBytes) + 1) % 512) > (512 – 64)) = if((((8 * 3) + 1) % 512) > (512 – 64)) = if(25 > 448) is false.

Instructions for convertCharArrayToIntArray function:

void convertCharArrayToIntArray(unsigned char buffer[], unsigned int message[], unsigned int sizeOfFileInBytes)

• It is easier to read from a file using an array of unsigned characters (buffer[]), but it is easier to process each block (512 bits or 16 integers) using an array of unsigned integers (here named message[])
  • You should convert your array of unsigned characters into an equivalent array of unsigned integers.
  • We did this in the assignment on C Bitwise Operators, where we packed 4 characters into 1 integer variable.

Instructions for addBitCountToLastBlock function:

void addBitCountToLastBlock(unsigned int message[], unsigned int sizeOfFileInBytes, unsigned int blockCount)

• You need to insert the size of the file in bits into the last index of the last block.

1. Calculate the index of last word (integer) in the message[] array.
   • In the document, “word” refers to data type “int”, both which are 32 bits.
2. Insert the number of bits in the file to the last integer (word) of the message[] array.
   • There are 8 bits in a byte, so sizeOfTheFileInBits = sizeOfFileInBytes * 8
   • There are 16 integer array elements in each block, so indexOfEndOfLastBlock = (blockCount * 16) – 1.

Instructions for computeMessageDigest function:

void computeMessageDigest(unsigned int message[], unsigned int blockCount)

• The final step is to compute the message digest, which is described in the document in parts 5, 6, and 7 (pages 9-12).

1. Initialize variables as described in the document on page 11.
   • H0 = 0x67452301
   • H1 = 0xEFCDAB89
   • ..
2. Loop through each block, and complete steps a, b, c, d, and e as described in the document.

Instructions for helper functions f and K

unsigned int f(unsigned int t, unsigned int B, unsigned int C, unsigned int D).

unsigned int K(unsigned int t)

These will return the values described in Part 5 (function f_t(B,C,D)) and Part 6 (constants K_t)

• note that the C/C++ code “if(0 <= t && t <=19)” is equivalent to the the pseudocode statement “if(0 <= t <=19)”.
• Equivalent C/C++ notation to document:

C/C++ operator: &  is equivalent to X AND Y = X & Y = bitwise “and” of X and Y
C/C++ operator: | is equivalent to  X OR Y = X | Y = bitwise “inclusive-or” of X and Y
C/C++ operator: ^ is equivalent to X XOR Y = X ^ Y = bitwise “exclusive-or” of X and Y
C/C++ operator: ~ is equivalent to NOT X = ~X = bitwise “complement” of X
C/C++ operator: + is equivalent to X + Y = 2³² modulus addition