Comprehensive Study Guide: Hash Functions and Cryptographic Hashing

Fundamentals of Hash Functions and Hashing

• Hash Function Definition: A hash function is a mathematical algorithm that maps or transforms an input message $x$ of arbitrary, variable length to a fixed-length output value $h$.      \n  h = H(x)\n  

• Hash / Hash Value: The output value returned by a hash function. It is commonly referred to as a digest, checksum, or fingerprint.

• Hashing: The process of applying a hash function to transform input data of variable length into a fixed-length output value.

• Input and Output Characteristics:

  • Input ($x$): Variable-length message or binary data block.

  • Hash Function ($H()$): Mathematical hashing algorithm.

  • Output ($h$): Fixed-length digest output.

• Algorithm Output Comparisons:

  • Hashing produces completely distinct outputs even for minor variations in input string capitalization (e.g., $\text{"nitin"}$ vs. $\text{"Nitin"}$).

  • Input 1: $\text{"nitin"}$

  • MD2 (16-byte / 128-bit output): 9C3A142F63CAF281392754763487DBE7

  • MD4 (16-byte / 128-bit output): 2E49964E628C2828B182D65E7D155253

  • MD5 (16-byte / 128-bit output): 5FB656D1D5AD05DDA6D710C7482AF4F2

  • SHA-1 (20-byte / 160-bit output): 4E74D099E4C9F9D6E7062217CA12029D9FCB5D21

  • Input 2: $\text{"Nitin"}$

  • MD2 (16-byte / 128-bit output): 9FAD624E2E4E3A4C0E4D65E1CCD04AD2

  • MD4 (16-byte / 128-bit output): 087E6F1F735C2E0D74470EB985E05AAE

  • MD5 (16-byte / 128-bit output): B585C4415B1FE50F2C31FA1698B271B7

  • SHA-1 (20-byte / 160-bit output): 44D16CBE12265F91D76BAD742DA61AB7194C0E5A

Mathematical Concepts and Pre-Image Calculations

• Pre-Image Definition: For a given hash value $h$ produced by an input $x$, the input $x$ is termed the pre-image of the hash image $h$.

  • Example: For MD5 hash digest $h = \text{B585C441 5B1FE50F 2C31FA16 98B271B7}$ , the pre-image is $x = \text{"nitin"}$.

• Mapping Scenarios:

  • One-to-One Mapping (Inputs = Hashes):

  • Every distinct pre-image input maps to a unique hash output image:       \n      H(x_1) = h_4\n             \n      H(x_2) = h_1\n             \n      H(x_3) = h_2\n             \n      H(x_4) = h_3\n      

  • Many-to-One Mapping (Inputs > Hashes):

  • Because a hash function maps a large domain of possible inputs into a smaller, finite set of fixed-length outputs, multiple distinct input values $(x_1, x_2, x_3, x_4, \dots)$ inevitably map to the same hash output image $h$.       \n      H(x_1) = h_1\n             \n      H(x_2) = h_1\n             \n      H(x_3) = h_2\n             \n      H(x_4) = h_2\n      

• Pre-Image Mathematical Calculations:

  • Input Space Size: For an input block size of $b$ bits, total possible input messages are:     \n    \text{Total Inputs} = 2^b\n    

  • Hash Space Size: For a hash output length of $n$ bits (where $n < b$), total possible hash outputs are:     \n    \text{Total Hashes} = 2^n\n    

  • Pre-Images per Hash: Under uniform output distribution, the number of pre-images mapping to each individual hash digest is:     \n    \text{Number of Pre-images} = 2^{b - n}\n    

  • Worked Example Calculation:

  • Let input size $b = 5$ bits, and output hash size $n = 4$ bits.

  • Total possible input messages: $2^b = 2^5 = 32$

  • Total possible hash digests: $2^n = 2^4 = 16$

  • Number of pre-images for each hash digest: $2^{b - n} = 2^{5 - 4} = 2^1 = 2$

Hash Collisions and Collision Security Risks

• Hash Collision Definition: A collision occurs when two distinct input messages $x_1$ and $x_2$ ($x_1 \neq x_2$) produce the exact same hash value:   \n  H(x_1) = H(x_2)\n  

• Theoretical Existence vs. Desirability: Collisions are guaranteed to exist theoretically whenever input space exceeds output space (Pigeonhole Principle). However, for any secure hash function, finding collisions must be computationally intractable.

• Hash Collision Attack:

  • A targeted effort to discover two different inputs that yield an identical output digest.

  • Security Breach Impact: An adversary can exploit a collision by replacing a trusted benign file ($x_1$) with an unauthorized malicious file ($x_2$) that shares the same hash digest, subverting cryptographic verification mechanisms.

Cryptographic Hash Functions (CHF) and Security Properties

• Cryptographic Hash Function Definition: A specialized cryptographic algorithm that takes an arbitrary amount of data input and produces a fixed-size enciphered digest specifically designed to enforce data integrity and authentication.

• One-Way Property: CHFs operate unidirectionally—generating a digest from an input message is straightforward, but deriving the original input message from a given hash digest is computationally impossible.

• Essential Security Properties of a CHF:

  1. Pre-Image Resistance (One-Way Function)

  2. Second Pre-Image Resistance (Weak Collision Resistance)

  3. Collision Resistance (Strong Collision Resistance)

  4. Avalanche Effect

  5. Determinism

  6. Computational Efficiency

Comprehensive Breakdown of CHF Security Requirements

• 1. Pre-Image Resistance (One-Way Function):

  • Definition: It must be computationally infeasible to reconstruct or calculate the original input message $x$ given only its hash digest $h$. There is no valid mathematical inverse operation for the hash function.

  • Formal Mathematical Rule: Given any output digest $h$, it is infeasible to find an input $x$ such that:     \n    H(x) = h\n    

  • Concrete Example: Given MD5 digest $h = \text{B585C441 5B1FE50F 2C31FA16 98B271B7}$, calculating the original plaintext $x = \text{"nitin"}$ is computationally impossible.

• 2. Second Pre-Image Resistance (Weak Collision Resistance):

  • Definition: Given a specific, fixed input message $x$, it must be computationally infeasible to find a second distinct message $y$ ($y \neq x$) that yields the exact same hash output.

  • Formal Mathematical Rule: Given $x$, finding $y$ where $y \neq x$ such that:     \n    H(y) = H(x)\n    

  • Concrete Example: Given fixed message $x = \text{"nitin"}$ with digest $\text{MD5}(\text{"nitin"}) = \text{B585C441 5B1FE50F 2C31FA16 98B271B7}$, finding a second distinct message $y$ such that $\text{MD5}(y) = \text{B585C441 5B1FE50F 2C31FA16 98B271B7}$ is computationally impossible.

• 3. Collision Resistance (Strong Collision Resistance):

  • Definition: It must be computationally infeasible to find any pair of two distinct input messages $x$ and $y$ ($x \neq y$) that evaluate to the same hash digest.

  • Formal Mathematical Rule: Finding any arbitrary pair $x$ and $y$ where $x \neq y$ such that:     \n    H(x) = H(y)\n    

  • Difference from Weak Collision Resistance: In Weak Collision Resistance, input message $x$ is fixed beforehand. In Strong Collision Resistance, an attacker has total freedom to pick both $x$ and $y$ freely.

  • MD5 Vulnerability: MD5 is NOT collision-resistant. It has been proven broken because collisions can be constructed efficiently.

  • Demonstrated MD5 Collision Example:

  • Two distinct byte sequences $x$ and $y$ ($x \neq y$) yield the identical MD5 digest:       \n      \text{MD5}(x) = \text{MD5}(y) = \text{79054025 255FB1A2 6E4BC422 AEF54EB4}\n      

  • Message 1 ($x$):       d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89       55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b       d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0       e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

  • Message 2 ($y$):       d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89       55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b       d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0       e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70 me

• 4. Avalanche Effect:

  • Definition: A minute alteration to an input message (such as flipping a single bit) must cause a dramatic, significant change in the output hash value so that the new hash appears statistically uncorrelated with the old hash.

  • Quantitative Metric: Changing a single bit in the input message should flip at least $50\%$ of bits in the output digest:     \n    \text{Difference}(h_1, h_2) \ge 50\%\n    

  • Avalanche Example 1 (Text Case Shift):

  • Input 1 ($x_1$): "Nitin is teaching Cryptography."

    • $\text{MD5}(x_1) = \text{78A07BB1 D4BA0449 56FFC8DD B672BC67}$

  • Input 2 ($x_2$): "nitin is teaching Cryptography." (only 'N' changed to 'n')

    • $\text{MD5}(x_2) = \text{65C5692F 23B1D37D A6CBA4FE 0F41DD81}$

  • Number of Flipped Output Bits: $65$ out of $128$ total bits.

  • Calculated Avalanche Percentage:       \n      \frac{65}{128} \times 100\% = 50.78\%\n      

  • Avalanche Example 2 (Binary 1-Bit Shift):

  • Input 1 ($x_1$): 00000000 (16 bytes input)

    • $\text{MD5}(x_1) = \text{DD4B21E9 EF71E129 1183A46B 913AE6F2}$

  • Input 2 ($x_2$): 00000001 (1-bit changed)

    • $\text{MD5}(x_2) = \text{CED16516 3E51E06E 01DC44C3 5FEA3EAF}$

  • Number of Flipped Output Bits: $57$ out of $128$ total bits.

  • Calculated Avalanche Percentage:       \n      \frac{57}{128} \times 100\% = 44.53\%\n      

• 5. Deterministic:

  • Definition: The algorithm must be completely deterministic; evaluating the function with the exact same input message $x$ must reliably produce the identical output digest $h$ every time.

  • Example: Input $x = \text{"nitin"}$ passed through MD5 will always generate digest $h = \text{B585C441 5B1FE50F 2C31FA16 98B271B7}$ across repeated executions.

• 6. Computationally Efficient:

  • Definition: The hash algorithm must be capable of processing and computing the output digest $h = H(x)$ for any given message $x$ rapidly and efficiently without excessive computational resource usage.

Practical Applications of Cryptographic Hash Functions

• Data Integrity and Authentication: Verifying that transmitted files or messages have not been altered or tampered with in transit.

• Digital Signatures: Used within Public Key Cryptography to sign compact message digests rather than large full-length documents.

• Message Authentication Codes (MAC): Combining secret keys with hashing algorithms (e.g., HMAC) to provide origin authentication and data verification.

• Pseudo-Random Number Generation (PRNG): Generating cryptographically secure deterministic bit streams.

• Key Generation and Key Update Protocols: Deriving cryptographic keys or periodically updating session keys.

• Code Recognition and Software Verification: Comparing binary checksums against published hash lists to detect malware or unauthorized system file modifications.

• One-Way Functions: Constructing cryptographic primitives, protocols, and commit schemes.

• Password Protection: Storing cryptographic hashes (typically salted) instead of plaintext passwords in databases.