Contents
Introduction
In today’s world, the average person has 70-80 different passwords across multiple accounts. While users wouldn’t care if their Webkinz password got leaked, bank account details being stolen is much more detrimental to users. In order to keep them safe, banks are required by the FTC to have proper security to keep users passwords safe. The common algorithm used is hashing. Technically speaking, hashing is a method of making a finite string of characters into a fixed size. Early hashing algorithms weren’t used for the use of encryption but data compression.The first person to use hashing was HP Luhn. HP Luhn, in an internal memo of IBM written in 1953, talked about putting information into buckets to speed up a searches. For example, a phone number like 508 905 9318 would be broken down into 5 numbers (50,89,05,93,18) and a new set of numbers was generated by adding the digits together (5,17,5,12,9), or bucket 5175129. Now if we needed to retrieve this phone number and the relevant information that is grouped with the phone number, we just need to calculate the hash value. Although this hash bucket may have multiple values, it's easier to search through a smaller bucket versus the entire database. Over the years, computer scientists have improved his algorithms and is now used in a variety of contexts such as cryptography, graphics, and as we talk about in this article, security. The common type of hashing algorithm we use in the security sector is known as password hashing. Password hashing takes the plaintext password, and turns it into a series of unintelligible characters called ciphertext. This way if a hacker wants these passwords, they have to hack into the database to get these passwords,and they have to decrypt the ciphertext which is extremely complex if you don’t know the specifics of the algorithms. Our paper will be more specifically looking at a category of algorithms called Secure Hash Algorithm, or SHA.
What is SHA
SHA is a family of hashing algorithms developed by the NSA and is published by the National Institute of Standards and Technology (NIST). First SHA algorithm, SHA-0, can input 160 bit messages and outputs a hashed value that is 40 values. This type of algorithm didn’t have much of a use due to the fact that it had a security flaw and was replaced with SHA-1 in 1995. There are several uses for SHA-1. We obviously talked about the use of SHA-1 for password hashing, but there are also uses for verification. Say we want to download a file from a website other than the developers website. If we can use the SHA1 hashed value of the file from the website and compare it to the developers, if the values don’t line up, we know that the file is not only not the same but could also contain malware. These are just some of the uses for SHA 1. But the question remains, how exactly does the SHA 1 algorithm work?
SHA-1 Walkthrough
Step 1:
Initialize 5 strings as "Hash Values"
H1 = 0x67452301
H2 = 0xEFCDAB89
H3 = 0x98BADCFE
H4 = 0x10325476
H5 = 0xC3D2E1F0
Step 2:
Take the word you want to hash (in binary), and append a 1 to the end of it. Then append as many zeros as it takes to make it divisible by 512, with the length of the message in a 64 bit integer appended at the end of the string.
Example:
The word "Hello" in binary is:
01001000 01100101 01101100 01101100 01101111
(H) (e) (l) (l) (o)
Add 1 to the end:
= 01001000011001010110110001101100011011111
Since "Hello" is less than 448 we add 0’s until the string is 448 bits long:
= 01001000011001010110110001101100011011111000…0 (len = 448 bits)
Lastly take the length of the string before processing (40 bits in this case) append that as a 64 bit integer
= ...0000101000 (length of added bits = 64)
So total length is 512 in this example
010010000110010101101100011011000110111110………0101000
Step 3A:
Break message into 512-bit chunks
Taking the example from above, since it is 512 bits, we will only have one chunk
Step 3B:
Break each chunk into 16, 32-bit words
Example:
The words would be
W0 = 01001000011001010110110001101100
W1 = 01101111100000000000000000000000
W2-W14 = 00000000000000000000000000000000
W15 = 00000000000000000000000000101000
Step 4:
Extend the first chunk to 80 32-bit words using the function
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
Example:
Using the example we have been using, the first iteration would go like this:
w[16] = (w[16-3] xor w[16-8] xor w[16-14] xor w[16-16]) leftrotate 1 w[16] = (w[13] xor w[8] xor w[2] xor w[0]) leftrotate 1
The xor function will compare the bits of the two strings in in each index
and give an output based on the input of the the strings
A B A xor B
0 0 -> 0
0 1 -> 1
1 0 -> 1
1 1 -> 0
w[13] = 00000000000000000000000000000000
xor
w[8] = 00000000000000000000000000000000
xor
w[2] = 00000000000000000000000000000000
xor
w[0] = 01001000011001010110110001101100
= 01001000011001010110110001101100
The leftrotate x function shifts each bit x times to the left. Any bits
that are shifted past the beginning of the string are cycled back to the end of the string.
Taking the string we got, we leftrotate the string one bit
01001000011001010110110001101100
= 10010000110010101101100011011000
So, after the first iteration W16 is added to the chunk as:
W16 = 10010000110010101101100011011000
After all of the iterations, we should have a chunk of 2560 bits
(From now on we will be switching from binary representation to hex for simplicity)
Step 5A:
Initialize The "Holding Values" for the chunk with "Hash Values"
A = H1 B = H2 C = H3 D = H4 E = H5
Step 5B:
For each word in the chunk, obtain an F and K value
First 20 words:
K = 0x5A827999
F = (B ∧ C)∨((¬B) ∧ D)
Next 20 words:
K = 0x6ED9EBA1
F = B ⊕ C ⊕ D
Next 20 words:
K = 0x8F1BBCDC
F = (B ∧ C) v (B ∧ D) v (C ∧ D)
Last 20 words:
K = 0xCA62C1D6
F = B ⊕ C ⊕ D
Example:
On the first iteration,
K = 0x5A827999
F = (0xEFCDAB89 ∧ 0x98BADCFE) v ((NOT 0xEFCDAB89) ∧ 0x10325476)
(B) (C) (¬B) (D)
F = 0x32327676
Step 5C:
Assign new "Holding Values" after every iteration
Temp = (A leftrotate 5) + F + E + K + w[i]
E = D
D = C
C = (B leftrotate 30)
B = A
A = Temp
Example:
After iteration 1:
Temp = (A leftrotate 5) + F + E + K + w[0]
A leftrotate 5 = E8A4602C F = 32327676 E = C3D2E1F0 K = 5A827999 W0 = 48656C6C
So we assign the "Holding Values" as:
Temp = 281919E97
E = 10325476 D = 98BADCFE C = (leftrotate 30 B) = EFCDAB89 B = 67452301 A = 281919E97
Step 6:
Add "Holding Values" to "Hash Values"
H1 = H1 + A H2 = H2 + B H3 = H3 + C H4 = H4 + D H5 = H5 + E
Examples:
(Assume "Holding Values" from the last step are those of the final iteration)
H1 = 0x67452301 + 0x281919E97 = 0x2E8D6C198 H2 = 0xEFCDAB89 + 0x67452301 = 0x15712CE8A H3 = 0x98BADCFE + 0xEFCDAB89 = 0x188888887 H4 = 0x10325476 + 0x98BADCFE = 0xA8ED3174 H5 = 0xC3D2E1F0 + 0x10325476 = 0xD4053666
Repeat steps 5 and 6 for each chunk. After the last chunk, move on to step 7
Step 7
Complete hash by appending H values back together using:
HH = (H1 leftrotate 128) V (H2 leftrotate 96) V (H3 leftrotate 64) V (H4 leftrotate 32) V H5
Example: If these are the final hashes from iterating through all chunks
H1 = B3099B3DF4683F306175ED806E58C04AFFE622F6
H2 = 372AE26109B3DE38C9E56BB84E9D6DE2FB28ABFB
H3 = 28F142FF30F862A2405D9232E85714C23C567E9B
H4 = 91F2DF811E4615B20F161B86FD746874FA139A6E
H5 = ABED8613F2D98B8B7166B11E2AF8EFEC08197000
Then after doing the leftrotates
H1 leftrotate 128 = FFE622F6B3099B3DF4683F306175ED806E58C04A
H2 leftrotate 96 = 4E9D6DE2FB28ABFB372AE26109B3DE38C9E56BB0
H3 leftrotate 64 = 405D9232E85714C23C567E9B28F142FF30F862E0
H4 leftrotate 32 = F2D98B8B7166B11E2AF8EFEC0819700C91F2DF90
H5 stays the same
Finally, adding the strings together gives us:
HH = f7ff9e8b7bb2e09b70935a5d785e0cc5d9d0abf0
Weaknesses of Sha1
An intuitive way to break Sha1 relies on a simple concept in Mathematics known as the pigeonhole principle. Where there are 20 pigeon holes and 21 pigeons, if we fit all the pigeons in a box there will have to have more than one pigeon in a box. It is the case where a function maps a set m to a set n where the length of set n is less than m. The same applies for Sha1, but also Sha2 and all hashing functions since the inputs are [theoretically] infinite, but the output is finite. When two different inputs have the same output this is known as a “collision”.
The issue with collisions is that there is no way of knowing if the input given matches the original or intended input. So, if an attacker can consistently get a collision this would make Sha1 a weak algorithm.
Google was successfully able to find a collision and employed techniques that reduced the complexity of the computations making it 100,000 times faster than brute forcing it. Even with this Google still used expensive hardware making this only feasible for well funded adversaries, but this attack could get easier as computers get faster. As well, the Chosen-Prefix Collision reduces the complexity from <>2^80 (brute force) to 2^~61 which because it is exponential is a significant difference in terms of effort needed to accomplish this. This attack however still requires the adversaries to be well funded. Regardless, it is proof that Sha1 needs to be retired.
Now it would seem that the issue of using collisions to bypass a hashing algorithm would seem universal and it is, but it is more challenging when the output is longer, as it is in Sha2 (2^160 vs 2^224 Minimum), since the probability of getting a collision is less likely and Sha1 collisions attacks were mostly reserved for well funded parties. In addition to Sha2 being more complex as will be shown. Discorgaing adversaries from using it since it is not practical to do, which is why organizations have moved away from Sha1 to newer hashing algorithms.
