Role of Hash Functions in Message Authentication & SHA-1 Algorithm

---

Role of Hash Functions in Authenticating Messages

A hash function is a mathematical function that takes a variable-length input message and produces a fixed-length output (called hash value or message digest) used to verify the integrity and authenticity of a message.

How Hash Functions Authenticate Messages:

• The sender computes a hash value (digest) of the original message.
• This hash is sent along with the message (or encrypted separately).
• The receiver recomputes the hash of the received message and compares it with the received hash.
• If both hash values match, the message is authentic and unaltered.
• If they don't match, the message has been tampered with.

Key Properties of Hash Functions for Authentication:

• One-way property — Given a hash value $h$, it is computationally infeasible to find message $m$ such that $H(m) = h$
• Collision resistance — It is infeasible to find two different messages $m_1$ and $m_2$ such that $H(m_1) = H(m_2)$
• Avalanche effect — A small change in input produces a drastically different hash output
• Fixed-length output — Regardless of input size, output is always fixed (e.g., 160 bits in SHA-1)

Common Authentication Schemes Using Hash Functions:

• Hash + Symmetric Key Encryption — Hash is encrypted with a shared secret key
• HMAC (Hash-based Message Authentication Code) — Combines hash function with a secret key
• Digital Signatures — Hash of message is signed with sender's private key

---

SHA-1 Algorithm (Secure Hash Algorithm - 1)

SHA-1 is a cryptographic hash function that takes an input message of length less than $2^{64}$ bits and produces a 160-bit (20-byte) message digest.

Overview:

• Designed by NSA and published by NIST in 1995
• Produces a 160-bit hash value
• Processes message in 512-bit blocks
• Uses 80 rounds of operations

Step-by-Step Working of SHA-1:

Step A: Padding the Message

• Append a single bit 1 to the message
• Append 0 bits until message length ≡ 448 mod 512
• Append a 64-bit representation of the original message length
• Final padded message is a multiple of 512 bits

Step B: Dividing into Blocks

• The padded message is divided into N blocks of 512 bits each
• Each block is further divided into 16 words of 32 bits each ($W_0$ to $W_{15}$)

Step C: Expanding Words

• From 16 words, 80 words ($W_0$ to $W_{79}$) are generated using:

$$W_t = (W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16}) \lll 1 \quad \text{for } t = 16 \text{ to } 79$$

Step D: Initialize Hash Buffers

• Five 32-bit registers are initialized:
• $H_0 = \text{67452301}$
• $H_1 = \text{EFCDAB89}$
• $H_2 = \text{98BADCFE}$
• $H_3 = \text{10325476}$
• $H_4 = \text{C3D2E1F0}$

Step E: Processing Each Block (80 Rounds)

• For each block, set: $a = H_0,\ b = H_1,\ c = H_2,\ d = H_3,\ e = H_4$
• For each round $t$ (0 to 79), compute:

$$T = (a \lll 5) + f_t(b, c, d) + e + W_t + K_t$$

• Then update: $e = d,\ d = c,\ c = (b \lll 30),\ b = a,\ a = T$

Round Functions $f_t$ and Constants $K_t$:

Rounds	Function $f_t(b,c,d)$	Constant $K_t$
0–19	$(b \land c) \lor (\lnot b \land d)$	5A827999
20–39	$b \oplus c \oplus d$	6ED9EBA1
40–59	$(b \land c) \lor (b \land d) \lor (c \land d)$	8F1BBCDC
60–79	$b \oplus c \oplus d$	CA62C1D6

Step F: Update Hash Values

• After processing all 80 rounds for a block:
• $H_0 = H_0 + a,\quad H_1 = H_1 + b,\quad H_2 = H_2 + c,\quad H_3 = H_3 + d,\quad H_4 = H_4 + e$

Step G: Final Output

• After all blocks are processed, the 160-bit message digest is:

$$\text{Hash} = H_0 \| H_1 \| H_2 \| H_3 \| H_4$$

---

Conclusion

Hash functions play a critical role in message authentication by ensuring data integrity and detecting any unauthorized modifications. SHA-1, with its 160-bit output and 80-round processing, provides a structured and secure method to generate message digests, though it is now considered deprecated in favor of SHA-256/SHA-3 due to discovered vulnerabilities.