Saturday, July 22, 2023

SHA-1 Hash Function: What is it and How to Implement?

SHA-1 (Secure Hash Algorithm - 1)

Hash functions are crucial for various security applications. SHA-1 (Secure Hash Algorithm - 1) is one of the widely used hash function. SHA-1 was developed by National Security Agency (NSA) in 1995. This function accepts an input of any size and generates hash value of 40 characters (160 bits). 

Let's get started with the Step-by-Step process of generating 40 character hash value using SHA-1 hash function.

Step - by - Step Process

On a high level steps involved in the process of generating hash value can be summarized as below. 
  • Message Preprocessing
  • Initializing State Variables 
  • Process Message Blocks
  • Compression Function
  • Iterate Through Blocks
  • Final Hash Value
Let's dive deeper to understand each of these steps in detail. 

Message Preprocessing

SHA-1 algorithm works on blocks, each one of size 512 bits. So, first thing to be done is to convert the input message to binary format and ensure that the input message (in binary format) is congruent to 448 modulo 512. To make it simple, let's break down this into the below. 
  • Converting the input message into binary format (if it is not already binary). 
  • Padding the binary input message to ensure the length of the message is congruent to 448 modulo 512. 
    • Similar to the padding in MD5, '1' bit is added to the end of the message and this '1' bit acts as a delimiter. 
    • Add the '0' bits to the binary input message until the length of the input message is congruent to 448 modulo 512. 
  • Add 64 bits, which indicate the actual length of the input message before any padding.
I'm not deep diving into how the padding works and calculating the number of bits to added, as this has been detailed with examples in my previous post on MD5. This can be found here

Below is the formula for calculating the number of bits to be padded for the quick reference. 

Padding Length = (448 - (Message Length + 1)%512) % 512

Let's find out the importance of 448 here, Whereas SHA-1 actually processes blocks of 512 bits size.

64 bits are to be mandatorily padded at the end of input message to indicate the length of actual input message. '512 - 64 = 448', Which would be the required length of the message after any padding ('1' bit, '0' bits). So, any input message which is congruent to 448 modulo 512 would become a multiple of 512 bits after adding it's length at the end.

Let's break down the above formula. 
  • Message Length: Length of the actual input message (before any padding). 
  • (Message Length + 1): '+1' here is to consider the mandatory delimiter '1' bit. 
  • Subtracting from 448: To get the actual number '0' bits to be padded.

Initialize State Variables

SHA-1 Algorithm uses five state variables, each variable is of size 32 bits (MD5 algorithm uses 4 state variables). These variables are initialized with pre-determined constant values (mentioned below). These state variables are usually referred as H0, H1, H2, H3 and H4. 

H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0

Initial values for the first four state variables are same as the state variables used in MD5 Hash function. Constant initial values for the state variables ensure a consistent starting point for generating SHA-1 Hash. 

SHA-1 algorithm does various calculations on each message block during the hash generation process and at each step, these Stage variables are used to store the intermediate values. 

After processing each message block, intermediate values of the Stage variables would be used as an input for the processing of next block. 

Process Message Blocks

As mentioned earlier, SHA-1 Algorithm works on blocks of size 512 bits. Hash generation process would split the input message (after padding) into blocks of 512 bits before doing any processing (This could be one block of size 512 bits or more depending on the input message).

Each block is processed individually by SHA-1 compressed function. Let's see what is a SHA-1 compressed function in a bit.

The compression function accepts the the message block of 512 bits and state variables as inputs. Compression function then applies a series of logical and bitwise operations on the input (message block and stage variables), this includes bitwise operations (like AND, OR, XOR), modular additions and bitwise rotations. 

These operations ensure the input message block and state variables are mixed up and generate the intermediate hash values which are then stored into state variables. These state variables are used as an input along side processing of next message block. 

Compression Function

Let's have a quick look into what SHA-1 compression function does. On a high level this can be split into the below steps. 
  • Breaking the input block into 16 words. 
  • Extend the 16 words into 80 words. 
  • Perform a series of logical and bitwise operations. 
  • Update state variables with intermediate hash value. 
Let's see what does each step involve in couple of lines. 

Breaking the input block

First thing the compression function would do is to break the input message block of 512 bits into 16 words with each word containing 32 bits. 

Each would then be labelled as W0, W1,...W15 which would be used in the further computation. 

Extending 16 words into 80 words

SHA-1 uses a specific expansion algorithm to expand the 16 words into 80 words. 

SHA-1's expansion algorithm uses a combination of logical and bitwise operations on the 16 words (W0 - W15) to generate the next set of words (W16 - W79). This process endures that the 80 words are mixed sufficiently and are influenced by the original 16 words. 

Perform logical and bitwise operations

The compression function performs a series of logical and bitwise operations on the 80 words generated from the input block and five input state variables (H0, H1, H2, H3 and H4). 
  • Bitwise AND, OR and XOR operations to combine bits from different words and/or state variables based on specific rules. 
  • These words and state variables go through modular addition (addition modulo 2^32) and produce new values.
  • Left bitwise rotations are applies to words and state variables that would shift bits and create new patterns. 

Update state variables

The output of the logical and bitwise operations performed by the compression function would generate intermediate hash value. These intermediate hash values would then be updated to the state variables. 

These state variables would become input for processing of the next message block of 512 bits. 

Iterate Through Blocks

The same process (i.e., Compression function) would be repeated for the each message block of the input message. 

In brief, first block would accept the constant state variables and message block would be input for the compression function which would generate the five intermediate hash values.

These intermediate hash values are then stored in state variables and act as an input alongside the next message block. 

This process would be repeated until the last message block.

Final Hash Value

After all the input message blocks have been processed, five state variables (each of 32 bits) contain the intermediate hash value. 

Concatenating the intermediate hash values from the five state variables to create a single hash value of 40 characters (of 160 bits). 

This 40 characters hash value is the final hash value generated by the SHA-1 hash function and represent a unique digest of the input message. Any small change to the input message would result in generating completely different hash value due to the operations performed at different steps of the input message processing. 

Implementing SHA-1 Hash

How to generate SHA-1 hash value for any given string? Let's look at an example in Python. 

For this example we will use the module 'HashLib'. There is a function 'sha1' in HashLib which accepts the encoded input string and generates Hash value.

1

2

3

4

5

6

7


8

9

10

11

import hashlib


# Accept the input string for generating Hash

input_string = input("Enter string: ")

# Input string needs to be encoded before generating Hash

encoded_input_string = input_string.encode()

# Encoded string would be passed to 'sha1' function from the HashLib module.

hash_value = hashlib.sha1(encoded_input_string)


print(hash_value.hexdigest())



In the above example, 
  • Line - 6: Input string needs to encoded. This can be done using the string method encode(). 
  • Line - 8: Encoded input string to be passed to the function sha1(), this returns the HASH object. 
  • Line - 10: Method 'hexdigest()' can be used on the HASH object to get the Hexadecimal Hash value. 
Below is the sample result. 

Enter string: This is a String

8416c466810d60718d66bfb5e7214af36ce868ab


Any minor change to the input string would result in generating a completely different Hash value. Below is the hash value with the same string by converting 'S' to lower case. 

Enter string: This is a string

f72017485fbf6423499baf9b240daa14f5f095a1



I hope this post has provided a good insight on what is a SHA-1 hash function and how we can generate Hash using SHA-1 algorithm in Python. Please note that SHA-1 is considered to be insecure for cryptographic purposes due to the vulnerabilities identified and more secure hash function (like SHA-256) is recommended. 


If you have any Suggestions or Feedback, Please leave a comment below or use Contact Form.

Saturday, July 8, 2023

MD5 Hash Function: What is it and How to Implement?

MD5 (Message Digest Algorithm 5)

MD5 hash function is one of the oldest and widely used hash function. MD5 stands for Message Digest Algorithm was developed in 1991 by Ronald Rivest. MD5 accepts input of any size and generates hash value of 32 characters (128 bits). 

Let's get straight into Step-by-Step process of MD5 algorithm and then look into some of the vulnerabilities of MD5 Algorithm.
 

Step-by-Step Process

On a high level below are the steps involved in generating hash value. 
  • Padding the Input
  • Breaking the Input into Blocks
  • Initializing the State variables
  • Processing the Blocks
  • Finalizing the Hash Value
Let's have a look into what does each step involve.

Padding the Input

MD5 Algorithm works on blocks of size 512 bits. So, first thing is to ensure the input message is of 512 bits (or multiples of 512 bits).

Before processing the input message, input would be padded with the below. 
  • '1' bit would be padded immediately after the input message. '1' bit works as a delimiter to indicate the end of the actual input message before any padding. This is mandatory irrespective of the input message size. 
  • '0' bits to be added as a filler to ensure that the input message is a multiple of 512 bits. This is only required if length of the input message (including '1' delimiter and 64 bits indicating the length) is not a multiple of 512. 
  • The last 64 bits representing the length of the actual input message would be padded.
Out of these, '1' bit (delimiter) and 64 bits (length representation) are mandatory and fixed. Number of '0' bits to be padded would be depending upon the length of the input message and calculated based on the below.

Length of the input message should be congruent to 448 modulo 512. Input message in this context is after padding the '1' bit and '0' bits. Below calculation can be used to ensure how many number of '0' bits to be added, so that length of input message would be congruent to 448 modulo 512. 

Padding Length = (448 - (Message Length + 1)%512) % 512

So, what is the importance of 448 here? When MD5 actually processes blocks of 512 bits size? 

64 bits are to be mandatorily padded at the end of input message to indicate the length of actual input message. '512 - 64 = 448', Which would be the required length of the message after any padding ('1' bit, '0' bits). So, any input message which is congruent to 448 modulo 512 would become a multiple of 512 bits after adding it's length at the end.

Let's break down the above formula. 
  • Message Length: Length of the actual input message (before any padding). 
  • (Message Length + 1): '+1' here is to consider the mandatory delimiter '1' bit. 
  • Subtracting from 448: To get the actual number '0' bits to be padded.
 This can be better understood 

If the input message is of 447 bits, 

Padding Length = (448 - (447 + 1)%512)%512 
               = (448 - 448%512)%512 
               = (448 - 448)%512
               = (0)%512 
               = 0

No additional padding is required if the input message is of 447 bits, this is because
  • mandatory '1' bit would make the input message length to 448 bits. 
  • mandatory '64' bits to represent the input length make the input message length to 512 bits, which is equal to the block size required by MD5
If the input message is of 512 bits, 

Padding Length = (448 - (512 + 1)%512)%512 
               = (448 - 513%512)%512 
               = (448 - 1)%512
               = (447)%512 
               = 447
  • mandatory '1' bit would make the input message length to 513 bits. 
  • As per the calculation 447 '0' bits are to be added to the input message after delimiter, this would make the input length to 960 bits
  • mandatory '64' bits to represent the input length make the input message length to 1024 bits, which is a multiple of 512. MD5 splits the message into two blocks of 512 bits and process.
For cases where the input message is greater than 512 bits (E.g.: 2000 bits),

Padding Length = (448 - (2000 + 1)%512)%512 
               = (448 - 2001%512)%512 
               = (448 - 465)%512
               = (-17)%512 # To avoid negative, we can add 512
               = (-17 + 512)%512
               = (495)%512 
               = 495
  • mandatory '1' bit would make the input message length to 2001 bits. 
  • As per the calculation 495 '0' bits are to be added to the input message after delimiter, this would make the input length to 2496 bits
  • mandatory '64' bits to represent the input length make the input message length to 2560 bits, which is a multiple of 512. MD5 splits the message into five blocks of 512 bits and process.

Breaking the Input into Blocks

Input message (which is padded as described above) to be broken into multiple blocks with each block size is of 512 bits. 

Initializing the State variables

State variables hold the internal state of the hash function and are initialized with a specific constant at the beginning of hashing process. 

MD5 algorithm uses four state variables, each of them are identified as A, B, C and D. These variables are initialized with the below values. 

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

Processing the Blocks

During the process of hash value generation, each block goes through 64 steps in four different rounds (with each round having 16 steps).

Each step involves some calculations and transformations applied to the current block's data and state variables. These operations are designed to ensure hash value is unique and unpredictable by introducing non-linearity and diffusion. 

Below are the four non-linear functions part of the each step, different non-linear function would be used in each round. 

Each of these functions would take the state variables as input and applies different combinations of logical functions, bitwise operations and modular arithmetic operations on the block. Using different combination for different functions produces different intermediate result. 

Intermediate result from each function would be combined with the corresponding state variables using bitwise addition modulo 2^32. 

The updated state variables would become input for the next step. Finalized state variables after processing all blocks represent the internal state of the MD5 Algorithm. 

Finalizing the Hash Value

Last step in generating the Hash is to process the finalized state variables after processing all the blocks, convert them to Little-Endian format, concatenate state variables and convert the concatenated value to Hexadecimal format. 
  • Convert each of the state variable (which is of 32 bit length) from actual Big-Endian format to Little-Endian format. Below is the brief on what is Big-Endian format and Little-Endian format. 
    • Big-Endian format: This format can be visualized as reading from left to right, with most significant byte (MSB) is stored at the lowest memory address and least significant byte (LSB) is stored at the highest memory address. This is similar to how we write the numbers.
    • Little-Endian format: This format is opposite to the Big-Endian format and can be visualized as reading from right to left, with lost significant byte (LSB) is stored at the lowest memory address and most significant byte (MSB) is stored at the highest memory address. This is different from the way how we write the numbers. 
    • E.g.: A 16 bit number 0x1234, is stored as 0x12 followed by 0x34 in big-endian format and it would be stored as 0x34 followed by 0x12 in little-endian format. 
  • Concatenate all the state variables (converted to little-endian format) in the order of A, B, C and D. The result would form a 128 bit value. 
  • Convert the concatenated 128 bit value to the hexadecimal format. 
  • The resulting 128 bit hexadecimal value is the final Hash value generated by the MD5 algorithm. 

Implementing MD5 Hash

How to generate MD5 for any given string? Let's look at an example in Python. 

For this example we will use the module 'HashLib'. There is a function 'md5' in HashLib which accepts the encoded input string and generates Hash value.

1

2

3

4

5

6

7


8

9

10

11

import hashlib


# Accept the input string for generating Hash

input_string = input("Enter string: ")

# Input string needs to be encoded before generating Hash

encoded_input_string = input_string.encode()

# Encoded string would be passed to 'md5' function from the HashLib module.

hash_value = hashlib.md5(encoded_input_string)


print(hash_value.hexdigest())



In the above example, 
  • Line - 6: Input string needs to encoded. This can be done using the string method encode(). 
  • Line - 8: Encoded input string to be passed to the function md5(), this returns the HASH object. 
  • Line - 10: Method 'hexdigest()' can be used on the HASH object to get the Hexadecimal Hash value. 
Below is the sample result. 

Enter string: This is a String

80b2959a8f7c38e52d7daa1660eafed7


Any minor change to the input string would result in generating a completely different Hash value. Below is the hash value with the same string by converting 'S' to lower case. 

Enter string: This is a string

41fb5b5ae4d57c5ee528adb00e5e8e74



I hope this post has provided a good insight on what is a MD5 hash function and how we can generate Hash using MD5 algorithm in Python. Please note that MD5 is considered to be insecure for cryptographic purposes due to the vulnerabilities identified and more secure hash function (like SHA-256) is recommended. 


If you have any Suggestions or Feedback, Please leave a comment below or use Contact Form.

Different Ways of Sorting Data in a List - Python

Sorting Data in a List List is a collection of data (of different data types), much like an array. Like any data structure or data set, dat...