Common Hashing Algorithms

Posted on July 21, 2011. Filed under: CompTIA Security+ |


A cryptographic hash function is similar to a checksum. The main difference is that while a checksum is designed to detect accidental alterations in data, a cryptographic hash function is designed to detect deliberate alterations. When data is processed by a cryptographic hash function, a small string of bits, known as a hash, is generated. The slightest change to the message typically makes a large change in the resulting hash. A cryptographic hash function does not require a cryptographic key.

Common Hashing Algorithms include, Message Digest 5 (MD5), Secure Hash Algorithm (SHA).

Message Digest 5 (MD5) is a widely used cryptographic hash function that produces a 128-bit (16-byte) hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity. However, it has been shown that MD5 is not collision resistant. cryptographers began recommending the use of other algorithms, such as SHA-1 (which has since been found also to be vulnerable). most U.S. government applications now require the SHA-2 family of hash functions.

MD5 processes a variable-length message into a fixed-length output of 128 bits.

Firstly, the input message is broken up into chunks of 512-bit blocks; the message is padded so that its length is divisible by 512.

Secondly, a 128-bit state, divided into four 32-bit words, denoted A, B, C and D, are initialized to certain fixed constants.

The main algorithm then operates on each 512-bit message block in turn, each block modifying the state. The processing of a message block consists of four similar stages, termed rounds; each round is composed of 16 similar operations based on a non-linear function F, modular addition, and left rotation. Figure 1 illustrates one operation within a round.

Figure 1. one round of MD5 operation. Mi denotes a 32-bit block of the message input, and Ki denotes a 32-bit constant, different for each operation. left shifts denotes a left bit rotation by s places; s varies for each operation. Addition denotes addition modulo 232

There are four possible functions F; a different one is used in each round:

F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z})
G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \neg{Z})
H(X,Y,Z) = X \oplus Y \oplus Z
I(X,Y,Z) = Y \oplus (X \vee \neg{Z})

\oplus, \wedge, \vee, \neg denote the XOR, AND, OR and NOT operations respectively.

Secure Hash Algorithm (SHA): The three SHA algorithms are structured differently and are distinguished as SHA-0, SHA-1, and SHA-2. SHA-1 is very similar to SHA-0, but corrects an error in the original SHA hash specification that led to significant weaknesses. The SHA-0 algorithm was not adopted by many applications. SHA-2 on the other hand significantly differs from the SHA-1 hash function.

 

SHA-1  processes a variable-length message into a fixed-length output of 160 bits, the process is similar to MD5.

Firstly, the input message is broken up into chunks of 512-bit blocks; the message is padded so that its length is divisible by 512.

Secondly, a 160-bit state, divided into five 32-bit words, denoted A, B, C, D and E, are initialized to certain fixed constants.

The main algorithm then operates on each 512-bit message block in turn, each block modifying the state. The processing of a message block consists of five similar stages, termed rounds; each round is composed of 16 similar operations based on a non-linear function F, modular addition, and left rotation. Figure 2 illustrates one operation within a round.

Figure 2. one round of SHA-1 operation. F is a nonlinear function that varies; left shiftn denotes a left bit rotation by n places; n varies for each operation; Wt is the expanded message word of round t; Kt is the round constant of round t; Addition denotes addition modulo 232

SHA-2 is a set of cryptographic hash functions (SHA-224, SHA-256, SHA-384, SHA-512) designed by the National Security Agency (NSA) and published in 2001 by the NIST as a U.S. Federal Information Processing Standard. SHA-2 includes a significant number of changes from its predecessor, SHA-1. SHA-2 consists of a set of four hash functions with digests that are 224, 256, 384 or 512 bits.

SHA-256 and SHA-512 are novel hash functions computed with 32- and 64-bit words, respectively. They use different shift amounts and additive constants, but their structures are otherwise virtually identical, differing only in the number of rounds. SHA-224 and SHA-384 are simply truncated versions of the first two, computed with different initial values.

At this point, we should already understood how MD5, SHA1 works, so I will paste the the processing diagram of SHA2 here without explainations.

Figure 3. One iteration in a SHA-2 family compression function. The blue components perform the following operations:
\operatorname{Ch}(E,F,G) = (E \and F) \oplus (\neg E \and G) \operatorname{Ma}(A,B,C) = (A \and B) \oplus (A \and C) \oplus (B \and C) \Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22) \Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)
The bitwise rotation uses different constants for SHA-512. The given numbers are for SHA-256. The red \color{red}\boxplus is an addition modulo 232

 

Algorithm and variant Output size
(bits)
Internal state
size (bits)
Block size
(bits)
Max message
size (bits)
Word size
(bits)
Rounds Operations Collisions
found?
SHA-0 160 160 512 264 − 1 32 80 add, and, or, xor, rotate Yes
SHA-1 Theoretical attack (251)
SHA-2 SHA-256/224 256/224 256 512 264 − 1 32 64 add, and, or, xor, shift, rotate No
SHA-512/384 512/384 512 1024 2128 − 1 64 80

Advertisements

Make a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: