SHA-1 Message Digest Algorithm
Presented By: Dr. Amjad Ali
Department of Computer Science
COMSATS University Islamabad, Lahore Campus
Outline
Introduction
Purpose
SHA-1 Framework
SHA-1Pseudo Code
Cryptanalysis and Limitation
Introduction
The Secure Hash Algorithm (SHA) was developed by the National
Institute of Standards and Technology (NIST) for the use of Digital
Signature and published in 1993.
The Secure hash standard specifies a SHA-1 for computing the
hash value of a message of any length less than 264 bits.
SHA-1 produces a 160-bit message digest.
Signing the message digest rather than the message often improves
the efficiency of the process because the message digest is usually
much smaller than the actual message.
Purpose: Authentication Not Encryption
Authentication Requirements:
Masquerade – Insertion of message from fraudulent source
Content Modification – Changing the message content
Sequence Modification – Insertion, deletion and reordering sequence
Timing Modification – Replaying valid sessions
Background Theory
Message Digest or “Fingerprint”
→ Condensed Representation of the message
→ Easy to generate for a given message.
Computationally it is infeasible to produce two messages with
the same message digest
Impossible to recreate a message from a given message digest.
Data Integrity and Comparison Checking
→ Message Integrity Validation
Authentication Using Hash Function
Fig. 1 Using Secret value
SHA-1 (160-bit digest): Algorithm Framework
Step 1: Appending Padding Bits
Message is “padded” with a 1 and as many 0’s as necessary to bring
the message length to 64 bits fewer than an even multiple of 512.
Step 2: Appending Length
64 bits are appended to the end of the padded message. These bits
hold the binary format of 64 bits indicating the length of the
original message.
f
SHA-1: Algorithm Framework
Fig. 1 Padding and adding length bits
f
SHA-1 Cont..
Step 3: Preparing Processing Functions….
SHA-1 requires 80 processing functions defined as:
f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) (0 <= t <= 19)
f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <=t <= 59)
f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79)
Step 4: Preparing Processing Constants.
SHA-1 requires 80 processing constant words defined as:
K(t) = 0x5A827999 (0 <= t <= 19)
K(t) = 0x6ED9EBA1 (20 <= t <= 39)
K(t) = 0x8F1BBCDC (40 <= t <= 59)
K(t) = 0xCA62C1D6 (60 <= t <= 79)
SHA-1 Cont..
Step 5: Initialize Buffers.
SHA-1 requires 160 bits or 5 buffers of words (32 bits):
H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0
SHA-1 Framework Final Step
Step 6: Processing Message in 512-bit blocks (L blocks in total message).
This is the main task of SHA-1 algorithm which loops through the
padded and appended message in 512-bit blocks.
Input and predefined functions:
M[1, 2, ..., L]: Blocks of the padded and appended message
f(0;B,C,D), f(1,B,C,D), ..., f(79,B,C,D): 80 Processing Functions K(0), K(1),…,
K(79): 80 Processing Constant Words H0, H1, H2, H3, H4, H5: 5 Word buffers
with initial values
SHA-1 Complete Framework
Fig. 3 Computing Message Digest
SHA-1 Operation
A = A<<<5 + f(t;B,C,D) + E + W(t) + K(t),
B = A, C = B<<<30, D = C, E = D
Fig. 2 SHA-1 Operation
SHA-1 Pseudo Code
Pseudo Code….
For loop on k = 1 to L
(W(0),W(1),...,W(15)) = M[k] /* Divide M[k] into 16 words */
For t = 16 to 79 do: /* Extending 16 words into 80 words */
W(t) = (W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)) <<< 1
A = H0, B = H1, C = H2, D = H3, E = H4
For t = 0 to 79 do:
TEMP = A<<<5 + f(t;B,C,D) + E + W(t) + K(t) E = D, D = C,
C = B<<<30, B = A, A = TEMP
End of for loop
H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E
End of for loop
Output:
H0, H1, H2, H3, H4, H5: Word buffers with final message digest
SHA-1 Message Digest
Example:
The message digest of the string:
“This is a test for theory of computation”
4480afca4407400b035d9debeb88bfc402db514f
https://slideplayer.com/slide/7635005/
Cryptanalysis and Limitation
Key Premises for Hash Functions:
1. Impossible to re-create a message given a message digest
2. Collision Free
SHA-1 failure using brute force attack in 280 operations
Collision failure found in 2005 in 233 operations
