Comprehensive Notes on Cryptographic Hash Functions, HMAC, SHA-512, and Digital Signatures

Fundamentals of Cryptographic Hash Functions

• Definition: A cryptographic hash function is a mathematical algorithm that transforms input data into a fixed-length sequence of characters, known as a hash value or message digest.

• The primary formula for the operation is represented as:   $\text{Hash} = H(\text{message})$

• Core Operational Characteristics:

  • Input: Can be data of any size, including text, files, or passwords.

  • Output: Always a fixed size (for example, 256 bits or 512 bits).

  • Speed: The function is intended to be fast to compute.

  • Deterministic: The hash function consistently computes the same hash for the exact same input. Any alteration to the input leads to a totally unique hash.

  • One-Way Computation (Irreversibility): The algorithm is designed to be irreversible, meaning it is computationally impossible to recover the original input data from its hash value.

  • Avalanche Effect: A slight variation in the input yields a complete and significantly different hash value.

  • Collision Resistance: Functions are designed to minimize the probability of distinct inputs generating the same hash value. It is very unlikely for two different inputs to produce the same hash.

• Working Modules:

  • Input Processing: The function can process data of any length.

  • Fixed Output Size Generation: The function generates a fixed output size, providing equality regardless of the input size.

Comparison of Integrity and Authentication: MDC and MAC

• Modification Detection Code (MDC):

  • Concept: Based on message integrity to determine whether the message has been modified or not.

  • Also known as Message Hash Function or Message Digest.

  • Workflow: Message A is sent to B after performing the hash. The MDC is shared secretly, either by encrypting it using Symmetric or Public Key Cryptography.

• Message Authentication Code (MAC):

  • Concept: Used to verify that a message was actually sent by the claimed sender (A).

  • Functionality: MAC performs both the modification detection (integrity) and provide authentication.

  • Workflow: Sender and Receiver share a secret key, similar to Symmetric Cryptography.

  • The formula involved includes the Key ($K$) and the Message ($M$):     $MAC = H(K + M)$

  • Security Risk: If the key size is too small, the system is subjected to brute-force attacks.

Hash-Based Message Authentication Code (HMAC)

• Definition: HMAC is a specific technique for message authentication that ensures both data integrity and authentication using a hash function and a secret key.

• HMAC Algorithm Components:

  • Key: Left-padded with zeros to match the block size.

  • ipad (Inner Pad): Defined as the bit pattern $0011\,0110$ (Hexadecimal: $36$).

  • opad (Outer Pad): Defined as the bit pattern $0101\,1100$ (Hexadecimal: $5C$).

  • $M$: The message, often divided into blocks ($M_1, M_2, \dots, M_m$).

• Numerical Example of HMAC:

  • Definitions: $H(a) = a \pmod{10}$ , $k = 5$, $m = 7$, $ipad = 2$, $opad = 3$.

  • Step 1: Compute $k \oplus ipad = 5 \oplus 2 = 7$.

  • Step 2: Compute inner hash: $H(7 + 7) = H(14) = 4$ .

  • Step 3: Compute $k \oplus opad = 5 \oplus 3 = 6$.

  • Step 4: Final HMAC: $H(6 + 4) = H(10) = 0$.

Secure Hash Algorithm-512 (SHA-512) Architecture

• Overview: SHA-512 is a hacking technique that converts text of arbitrary length into a fixed-size string of 512 bits (64 bytes).

• Basic Properties:

  • Deterministic.

  • Irreversible.

  • Collision resistant.

  • Avalanche effect.

• Message Processing and Iteration:

  • The variable-length message is divided into fixed block sizes of 1024 bits.

  • This is an iterative process where each 1024-bit block (Block 1, Block 2, $\dots$, Block N) goes through a compression function ($C.F.$).

  • The initial value is 512 bits.

  • The final output is the 512-bit Message Digest.

• Padding and Length Field:

  • The last block may not contain exactly 1024 bits, necessitating padding.

  • Padding Rule: The original message needs to be padded if necessary, and finally, the length of the original message is attached.

  • The length field is assigned a size of 128 bits. The original length of the message ($M$) should be less than $2^{128}$ bits.

  • Padding bits ($P$) calculation example:

  • Let $M = 1100$ bits.

  • $M + \text{length} = 1100 + 128 = 1228$.

  • $P = -(M + L) \pmod{1024} = -1228 \pmod{1024} = 820$ padding bits.

  • Padding structure: A single "1" followed by 819 zeros ($1000\dots0$).

SHA-512 Compression Function and Word Expansion

• Word Conversion:

  • Each 1024-bit block is converted into 16 words, where each word is 64 bits ($1024 / 16 = 64$).

  • The 512-bit initial values/intermediate states are converted into 8 words labelled $A, B, C, D, E, F, G, H$ (each 64 bits).

• Word Expansion Logic:

  • 1024 bits are expanded into 80 words ($W_0$ to $W_{79}$).

  • $W_0$ through $W_{15}$ are taken directly from the 1024-bit message block.

  • For $i = 16$ to $79$, words are generated using the formula:     $W_i = W_{i-16} + RotShift(W_{i-15}) + W_{i-7} + RotShift(W_{i-2})$

  • The addition is performed $\pmod{2^{64}}$ to ensure the output stays within 64 bits.

• Rotation and Shift Operations:

  • $RotR_n(W)$: Perform Right Circular Shift $n$ times.

  • $ShiftLeft_n(W)$: Shift left $n$ positions (fill with zeros; not circular).

  • Example of $RotR_1(10111)$: Becomes $11011$.

• Initial Constants ($A_0, B_0, \dots, H_0$):

  • Generated by taking the square root of the first 8 prime numbers ($2, 3, 5, 7, 11, 13, 17, 19$) and expanding the fractional part to 64 bits.

  • Example values:

  • $A_0 = 6A09E667F3BCC908_{16}$

  • $H_0 = 5BE0CD19137E2179_{16}$

• Iterative Rounds:

  • There are 80 rounds ($0$ to $79$).

  • Each round uses one word $W_t$ and one constant $K_t$.

  • $K_t$ values are derived from the cube roots of the first 80 prime numbers.

SHA-512 Logic Functions

• Operations performed in each round involve bitwise logic:

  • $Majority(x, y, z) = (x \text{ AND } y) \oplus (x \text{ AND } z) \oplus (y \text{ AND } z)$

  • $Conditional(x, y, z) = (x \text{ AND } y) \oplus ((\text{NOT } x) \text{ AND } z)$

  • $Rotate(x) = RotR_{28}(x) \oplus RotR_{34}(x) \oplus RotR_{39}(x)$

Digital Signature Principles

• Technology: Based on Asymmetric Key Cryptography.

• Process:

  • Signing: The sender uses their Private Key to sign the message/digest.

  • Verification: The receiver uses the sender's Public Key to decrypt and verify the signature.

• Purpose:

  • Authentication: Proof of identity.

  • Non-repudiation: The sender cannot deny signing the message.

• Implementation:

  • Digital Signatures are typically one-to-one (one signature per file).

  • Signatures are normally applied to the Message Digest ($MD$) rather than the original message ($M$). This is because the $MD$ is unique and has a fixed length.

  • Non-repudiation can be proven via a Trusted Third Party.

RSA Digital Signature Scheme Example

• Scenario: Sender signs a message using their private key; receiver verifies with the sender's public key.

• Example Setup:

  • Choose primes: $P = 3, q = 11$.

  • Compute $n = P \times q = 33$.

  • Compute Euler's totient: $\Phi(n) = (P-1)(q-1) = (2)(10) = 20$.

  • Choose public exponent $e$ such that $gcd(e, 20) = 1$. Let $e = 3$.

  • Find private exponent $d$ such that $d \times e \equiv 1 \pmod{20}$.

  • $3d \equiv 1 \pmod{20}$; since $3 \times 7 = 21 \equiv 1 \pmod{20}$, then $d = 7$.

  • Keys:

  • Public Key: $(e=3, n=33)$

  • Private Key: $(d=7, n=33)$

• Signing Process:

  • Message $M = 4$.

  • Assume hash $H(M) = 4$.

  • Signature $S = M^d \pmod{n} = 4^7 \pmod{33}$.

  • Calculation: $4^7 = 16384$. $16384 / 33 = 496$ with remainder $16$. So $S = 16$.

• Verification Process:

  • Receiver receives $M = 4$ and $S = 16$.

  • Receiver calculates expected hash: $H(M) = 4$.

  • Receiver verifies signature: $S^e \pmod{n} = 16^3 \pmod{33}$.

  • Calculation: $16^3 = 4096$. $4096 / 33 = 124$ with remainder $4$.

  • Comparison: Since $4 = 4$, the signature is valid.