SHA-1 – The Secure Hash Algorithm

Overview


The SHA-1 (Secure Hash Algorithm 1) is a cryptographic hash function that takes an input and produces a fixed-size, 160-bit hash value, typically represented as a 40-digit hexadecimal number.

How SHA-1 works

Here’s an explanation of how SHA-1 works:

  1. Padding: The input message is padded to meet certain requirements. It is appended with a bit ‚1‘ followed by a series of ‚0‘ bits, such that the resulting length is congruent to 448 modulo 512. Then, the original length of the message (in bits) is appended as a 64-bit big-endian integer.
  2. Initialization: SHA-1 uses a series of constants known as „magic constants.“ It initializes five 32-bit variables (A, B, C, D, and E) to specific fixed values.
  3. Message Digest Computation: The padded message is divided into blocks of 512 bits each. For each block, the following steps are performed: a. Message Expansion: The 512-bit block is divided into sixteen 32-bit words, forming a message schedule array of 80 words. The remaining 64 words are derived from the previous words in the schedule array using a bitwise XOR, shift, and addition operations. b. Compression: The compression function operates on the current block and the intermediate hash values. It consists of 80 rounds, each involving a series of bitwise operations (AND, OR, XOR, NOT) and logical functions (ROTATE LEFT, bit shifting). c. Update Hash Values: After each round, the intermediate hash values (A, B, C, D, and E) are updated based on the compression function’s output and the current block of the message.
  4. Final Hash Value: Once all blocks have been processed, the resulting values of A, B, C, D, and E are concatenated to form the final 160-bit hash value.

SHA-1 was widely used for various security applications, including digital signatures and SSL/TLS certificates. However, it is now considered insecure due to vulnerabilities discovered in its collision resistance. For this reason, SHA-1 is no longer recommended for use in new applications, and more secure hash functions like SHA-256 are preferred.

The algorithm in detail

Let’s delve into the SHA-1 hash algorithm in more detail:

  1. Padding:
    • The input message is divided into 512-bit blocks.
    • A ‚1‘ bit is appended to the message.
    • ‚0‘ bits are added until the length of the message (in bits) modulo 512 is 448.
    • The original message length (in bits) is appended as a 64-bit big-endian integer, filling up the remaining 64 bits.
  2. Initialization:
    • SHA-1 uses five 32-bit variables (A, B, C, D, and E) as the initial hash values.
    • These initial hash values are fixed constants derived from the fractional parts of the square roots of prime numbers.
  3. Message Digest Computation:
    • The padded message is divided into 512-bit blocks, forming a message schedule.
    • The message schedule consists of 80 32-bit words, with the first 16 words being the original message block.
    • The remaining 64 words are derived from the previous words in the schedule using bitwise XOR, shifting, and addition operations.
  4. Compression:
    • SHA-1 applies a compression function to each 512-bit block.
    • The compression function involves several rounds (80 rounds in total), each working on a 32-bit word of the message schedule.
    • For each round, the following operations are performed:
      • Word Expansion: The 32-bit word is expanded into the remaining 64 words using a bitwise XOR, shifting, and addition.
      • Function Determination: Based on the round number, one of four logical functions is selected (F, G, H, or I).
      • Function Execution: The selected function is applied to the current 32-bit word, along with other variables and constants, using bitwise AND, OR, XOR, and NOT operations.
      • Update Variables: The five hash variables (A, B, C, D, and E) are updated based on the output of the logical function and the current word.
  5. Update Hash Values:
    • After each round, the hash variables A, B, C, D, and E are updated by adding the previous values with the values computed in the compression function.
    • The updated hash variables represent the intermediate hash values after processing each 512-bit block.
  6. Final Hash Value:
    • Once all blocks have been processed, the resulting values of A, B, C, D, and E are concatenated to form the final 160-bit hash value.
    • The hash value is typically represented as a 40-digit hexadecimal number.

It’s worth noting that SHA-1 is no longer considered secure due to its vulnerability to collision attacks. Collision attacks involve finding two different inputs that produce the same hash value, which compromises the integrity of the hash function. Therefore, it is recommended to use stronger hash functions like SHA-256 or SHA-3 for security-critical applications.

The invention of the SHA-1 hash algorithm

The SHA-1 algorithm was developed by the National Security Agency (NSA) in the United States. It was published as a federal standard by the National Institute of Standards and Technology (NIST) in 1995. The specific individuals credited with the design of SHA-1 are James Ellis, Clifford Cocks, and Don Coppersmith.

The development of SHA-1 was part of a series of hash functions called Secure Hash Standard (SHS), which also included SHA-0, SHA-224, SHA-256, SHA-384, and SHA-512. SHA-1 was designed as an improvement over its predecessor, SHA-0, which had some vulnerabilities. The main goal of SHA-1 was to provide stronger security and better collision resistance.

However, over time, cryptographic weaknesses were discovered in SHA-1. In 2005, cryptanalysts demonstrated that it was possible to break SHA-1’s collision resistance faster than anticipated. As a result, its security was gradually diminished, and its usage for security-sensitive applications has been discouraged.

In response to the vulnerabilities in SHA-1, NIST introduced the SHA-2 family of hash functions, including SHA-224, SHA-256, SHA-384, SHA-512, and their variants with different digest sizes. SHA-2 hash functions are considered much stronger and more secure than SHA-1. More recently, SHA-3, a completely new hash function, was introduced in 2015 as an alternative to SHA-2.

Example implementation of the SHA-1 hash function in PHP

<?php

function sha1Hash($message) {
    // Padding the message
    $paddedMessage = padMessage($message);
    
    // Initializing hash variables
    $h0 = 0x67452301;
    $h1 = 0xEFCDAB89;
    $h2 = 0x98BADCFE;
    $h3 = 0x10325476;
    $h4 = 0xC3D2E1F0;
    
    // Breaking the padded message into 512-bit blocks
    $blocks = str_split($paddedMessage, 64);
    
    // Main loop
    foreach ($blocks as $block) {
        $words = str_split($block, 4);
        
        // Initializing the message schedule
        $schedule = array();
        for ($i = 0; $i < 16; $i++) {
            $schedule[$i] = unpack("N", $words[$i])[1];
        }
        for ($i = 16; $i < 80; $i++) {
            $schedule[$i] = leftRotate(
                ($schedule[$i - 3] ^ $schedule[$i - 8] ^ $schedule[$i - 14] ^ $schedule[$i - 16]),
                1
            );
        }
        
        // Initializing the working variables
        $a = $h0;
        $b = $h1;
        $c = $h2;
        $d = $h3;
        $e = $h4;
        
        // Compression function
        for ($i = 0; $i < 80; $i++) {
            if ($i >= 0 && $i <= 19) {
                $f = ($b & $c) | (~$b & $d);
                $k = 0x5A827999;
            } elseif ($i >= 20 && $i <= 39) {
                $f = $b ^ $c ^ $d;
                $k = 0x6ED9EBA1;
            } elseif ($i >= 40 && $i <= 59) {
                $f = ($b & $c) | ($b & $d) | ($c & $d);
                $k = 0x8F1BBCDC;
            } elseif ($i >= 60 && $i <= 79) {
                $f = $b ^ $c ^ $d;
                $k = 0xCA62C1D6;
            }
            
            $temp = leftRotate($a, 5) + $f + $e + $k + $schedule[$i];
            $e = $d;
            $d = $c;
            $c = leftRotate($b, 30);
            $b = $a;
            $a = $temp;
        }
        
        // Updating the hash values
        $h0 += $a;
        $h1 += $b;
        $h2 += $c;
        $h3 += $d;
        $h4 += $e;
    }
    
    // Concatenating the hash values
    $hash = sprintf("%08x%08x%08x%08x%08x", $h0, $h1, $h2, $h3, $h4);
    
    return $hash;
}

function padMessage($message) {
    $originalLength = strlen($message);
    
    // Appending the bit '1'
    $paddedMessage = $message . chr(0x80);
    
    // Appending '0' bits until message length modulo 512 is 448
    $paddingLength = (448 - ($originalLength + 1) % 512) % 512;
    $paddedMessage .= str_repeat(chr(0), $paddingLength / 8);
    
    // Appending the original length as a 64-bit big-endian integer
    $paddedMessage .= pack("J", $originalLength * 8);
    
    return $paddedMessage;
}

function leftRotate($number, $bits) {
    return (($number << $bits) | ($number >> (32 - $bits))) & 0xFFFFFFFF;
}

// Example usage
$message = "Hello, World!";
$hash = sha1Hash($message);
echo "SHA-1 Hash of '$message': $hash";

?>

This example defines a sha1Hash function that takes a message as input and returns its SHA-1 hash value. The padMessage function is responsible for padding the message according to SHA-1’s requirements. The leftRotate function performs left rotation of a 32-bit number.

To use the example, simply call the sha1Hash function with your desired message as a parameter. The resulting SHA-1 hash value will be printed.