Secure Hash Algorithms

Nathan Landman, Christopher Williams, Eli Ross, and 1 other contributed

Secure Hash Algorithms, also known as SHA, are a family of cryptographic functions
designed to keep data secured. It works by transforming the data using a hash function: an
algorithm that consists of bitwise operations, modular additions, and compression functions.
The hash function then produces a fixed-size string that looks nothing like the original.
These algorithms are designed to be one-way functions, meaning that once they’re
transformed into their respective hash values, it’s virtually impossible to transform them
back into the original data. A few algorithms of interest are SHA-1, SHA-2, and SHA-3, each
of which was successively designed with increasingly stronger encryption in response to
hacker attacks. SHA-0, for instance, is now obsolete due to the widely exposed
vulnerabilities.

A common application of SHA is to encrypting passwords, as the server side only needs to
keep track of a specific user’s hash value, rather than the actual password. This is helpful in
case an attacker hacks the database, as they will only find the hashed functions and not the
actual passwords, so if they were to input the hashed value as a password, the hash
function will convert it into another string and subsequently deny access. Additionally, SHAs
exhibit the avalanche effect, where the modification of very few letters being encrypted
causes a big change in output; or conversely, drastically different strings produce similar
hash values. This effect causes hash values to not give any information regarding the input
string, such as its original length. In addition, SHAs are also used to detect the tampering of
data by attackers, where if a text file is slightly changed and barely noticeable, the modified
file’s hash value will be different than the original file’s hash value, and the tampering will be
rather noticeable.
 SHA Characteristics
Cryptographic hash functions are utilized in order to keep data secured by providing three
fundamental safety characteristics: pre-image resistance, second pre-image resistance, and
collision resistance.

The cornerstone of cryptographic security lies in the provision of pre-image resistance,

which makes it hard and time-consuming for an attacker to find an original message,
m, given the respective hash value, hm. This security is provided by the nature of one-way
functions, which is a key component of SHA. Pre-image resistance is necessary to ward off
brute force attacks from powerful machines.

The second safety characteristic is called second pre-image resistance, granted by SHA when a
message is known, m1, yet it’s hard to find another message, m2, that hashes to the same
value: Hm1=Hm2. Without this characteristic, two different passwords would yield the same hash
value, deeming the original password unnecessary in order to access secured data.

The last safety characteristic is collision resistance, which is provided by algorithms that
make it extremely hard for an attacker to find two completely different messages that hash
to the same hash value: Hm1=Hm2. In order to provide this characteristic, there must be a
similar number of possible inputs to possible outputs, as more inputs than outputs, by
the pigeonhole principle, will definitively incur potential collisions. For this reason, collision
resistance is necessary, as it implies that finding two inputs that hash to the same hash
value is extremely difficult. Without collision resistance, digital signatures can be
compromised as finding two messages that produce the same hash value may make users
believe two documents were signed by two different people when one person was able to
produce a different document with the same hash value.

Recent cryptographic functions have stronger security characteristics to block off recently
developed techniques such as length extension attacks, where given a hash value,
hash(m), and the length of the original message, m, an attacker can find a
message, m’, and calculate the hash value of the concatenation of the original message
and the new message: hash (m∣∣m’).
As a general guideline, a hash function should be as seemingly random as possible while
still being deterministic and fast to compute.

SHA-1
Secure Hash Algorithm 1, or SHA-1, was developed in 1993 by the U.S. government's
standards agency National Institute of Standards and Technology (NIST). It is widely used
in security applications and protocols, including TLS, SSL, PGP, SSH, IPsec, and S/MIME.

SHA-1 works by feeding a message as a bit string of length less than 264264 bits, and
producing a 160-bit hash value known as a message digest. Note that the message below
is represented in hexadecimal notation for compactness.

There are two methods to encrypt messages using SHA-1. Although one of the methods
saves the processing of sixty-four 32-bit words, it is more complex and time-consuming to
execute, so the simple method is shown in the example below. At the end of the execution,
the algorithm outputs blocks of 16 words, where each word is made up of 16 bits, for a total
of 256 bits.
If the string changed to ‘abcd’, for instance, the hashed value would be drastically different
so attackers cannot tell that it is similar to the original message. The hash value for 'abcd'
is 81fe8bfe87576c3ecb22426f8e57847382917acf.
Functions used in the algorithm

A sequence of logical functions are used in SHA-1, depending on the value of i,

The following equations describe the logical functions, where ¬ is the logical NOT, ∨ is the
where 0≤i≤79, and on three 32-bit words B, C, and D, in order to produce a 32-bit output.

logical OR, ∧ is the logical AND, and ⊕ is the logical XOR:

Albeit SHA-1 is still widely used, cryptanalysts in 2005 were able to find vulnerabilities on
this algorithm that detrimentally compromised its security. These vulnerabilities came in the
form of an algorithm that speedily finds collisions with different inputs, meaning that two
distinct inputs map to the same digest.

As of 2010, many organizations have recommended its replacement by SHA-2 or SHA-3.

Companies like Microsoft, Google, or Mozilla have announced that their browsers will stop
accepting SHA-1 encryption certificates by 2017.

SHA-2
Due to the exposed vulnerabilities of SHA-1, cryptographers modified the algorithm to
produce SHA-2, which consists of not one but two hash functions known as SHA-256 and
SHA-512, using 32- and 64-bit words, respectively. There are additional truncated versions
of these hash functions, known as SHA-224, SHA-384, SHA-512/224, and SHA-512/256,
which can be used for either part of the algorithm.

SHA-1 and SHA-2 differ in several ways; mainly, SHA-2 produces 224- or 256-sized
digests, whereas SHA-1 produces a 160-bit digest; SHA-2 can also have block sizes that
contain 1024 bits, or 512 bits, like SHA-1.

Brute force attacks on SHA-2 are not as effective as they are against SHA-1. A brute force
search for finding a message that corresponds to a given digest of length L using brute
force would require 2L evaluations, which makes SHA-2 a lot safer against these kinds of
attacks.
Common Attacks
Cryptography wouldn’t be as quickly developed if it weren’t for the attacks that compromise
their effectiveness. One of the most common attacks is known as the primeage attack,
where pre-computed tables of solutions are used in a brute-force manner in order to crack
passwords. The solution against these kinds of attacks is to compose a hash function that
would take an attacker an exorbitant amount of resources, such as millions of dollars or
decades of work, to find a message corresponding to a given hash value.

Most attacks penetrating SHA-1 are collision attacks, where a non-sensical message
produces the same hash value as the original message. Generally, this takes time
proportional to 2n/2 to complete, where n is the length of the message. This is the reason the
message digests have increased in length from 160-bit digests in SHA-1 to 224- or 256-bit
digests in SHA-2.

Other attacks exist that attempt to exploit mathematical properties in order to crack hash
functions. Amongst these is the birthday attack, where higher likelihood of collisions are
found when using random attacks with a fixed number of letter combinations (see
the pigeonhole principle), or the rainbow table attack, where a pre-computed hash table is
used to reverse a hash function in order to crack passwords.