Cryptographic Hash

A given input will always produce the same hash output. This is fundamental for verification; if the same data is hashed multiple times, the result must be identical. This property enables systems like Git and blockchain to verify data integrity by comparing hashes.

• Example: Hashing the string "Hello" with SHA-256 will always yield 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969.

It must be computationally infeasible to reverse the function—given a hash output h, it should be impossible to find the original input m such that hash(m) = h. This protects passwords and ensures data cannot be derived from its fingerprint.

• Core Security: This property underpins password storage and commitment schemes, where only the hash is stored or revealed.

Given an input m1, it must be infeasible to find a different input m2 that produces the same hash: hash(m1) = hash(m2). This protects against forgery, ensuring an attacker cannot substitute a malicious file that hashes to the same value as a legitimate one.

• Distinction: This is different from a collision (see below), as the attacker starts with a specific known input.

It must be infeasible to find any two distinct inputs m1 and m2 that produce the same hash output. This is a stronger condition than second pre-image resistance and is critical for digital signatures and blockchain Merkle trees.

• Birthday Paradox: Attacks exploit the probability of finding any collision, which is why hash functions like SHA-256 have a massive 256-bit output to make this computationally impossible.

A tiny change in the input (even a single bit) must produce a drastically different hash output. The new hash should appear completely random and uncorrelated with the original hash.

• Example: Changing "Hello" to "hello" (capital H) with SHA-256 results in 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824, which shares no discernible pattern with the original hash.

Regardless of the size of the input data (a single character or a terabyte file), the hash function produces a fixed-size output (digest). Common lengths are 256 bits (SHA-256) or 512 bits (SHA-512).

• Efficiency: This allows for efficient comparison, storage, and indexing of data fingerprints. The fixed output is a core feature enabling data structures like hash tables and Merkle Patricia Tries in Ethereum.

RIPEMD-160 (RACE Integrity Primitives Evaluation Message Digest) is a 160-bit hash function. It is primarily used in Bitcoin and other cryptocurrencies to create shorter, more manageable public key hashes (addresses) from the longer SHA-256 output.

• Property: Designed for high security against collisions.
• Process: A Bitcoin address is typically created by hashing a public key with SHA-256, then RIPEMD-160 (SHA256 → RIPEMD160).

Scrypt is a memory-hard key derivation function designed to be computationally expensive in both time and memory, making it resistant to large-scale custom hardware (ASIC) attacks. It is used as a proof-of-work algorithm.

• Purpose: Increase the cost of brute-force attacks by requiring large amounts of RAM.
• Blockchain Use: Originally used by Litecoin and several other altcoins.

A Pedersen Commitment is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden, with the ability to later reveal the value. It is a building block for confidential transactions and zero-knowledge proofs.

• Property: Hiding and binding.
• Application: Used extensively in Zcash and other privacy-focused protocols to conceal transaction amounts while allowing network validation.

A cryptographic hash function must be collision-resistant, meaning it is computationally infeasible to find two different inputs that produce the same output hash. A successful collision attack breaks this property, allowing an attacker to substitute a malicious input for a legitimate one. Related concepts include:

• Preimage Attack: Finding any input that hashes to a specific target output.
• Second Preimage Attack: Given one input, finding a different input that hashes to the same output. A practical example is the SHA-1 algorithm, which was deprecated after theoretical attacks became practically demonstrated, highlighting the need for robust, modern functions like SHA-256 or Keccak-256.

Certain hash functions like MD5, SHA-1, and SHA-256 are based on the Merkle–Damgård construction, which is vulnerable to length extension attacks. An attacker who knows Hash(message) can compute Hash(message || extension) without knowing the original message, where || denotes concatenation. This is critical in systems using hashes for authentication (e.g., H(secret || message)). Mitigations include:

• Using HMAC (Hash-based Message Authentication Code), which applies the hash function twice.
• Adopting functions with different constructions, such as SHA-3 (Keccak), which uses a sponge function and is not susceptible.

Grover's algorithm, a quantum algorithm, provides a quadratic speedup for searching unstructured databases. Applied to hash functions, it can find preimages and collisions in O(2^(n/2)) time for an n-bit hash, effectively halving the security level. For example, a 256-bit hash would offer only 128 bits of quantum security. Shor's algorithm can break the underlying number-theoretic problems of some hash-based signatures. The cryptographic community is developing post-quantum cryptography (PQC), including hash-based signature schemes like SPHINCS+, which are believed to be quantum-resistant.

Even a theoretically secure hash function can be compromised by flawed implementation. Common vulnerabilities include:

• Timing Attacks: Execution time variations can leak information about secret data being hashed (e.g., in HMAC comparisons).
• Power Analysis: Monitoring power consumption during computation can reveal intermediate hash states.
• Fault Injection: Introducing hardware glitches to cause incorrect hash computations, potentially enabling signature forgeries. Secure implementation requires constant-time comparison functions, protections against physical tampering, and rigorous code audits. The Heartbleed bug in OpenSSL, while not a hash flaw, exemplifies the catastrophic impact of implementation errors in core cryptographic libraries.

Cryptographic hash functions have a finite lifespan. As computational power increases and new cryptanalysis techniques emerge, previously secure algorithms become weak. A structured deprecation and migration strategy is essential for system longevity.

• MD5: Broken for collision resistance; considered cryptographically broken and unsuitable for further use.
• SHA-1: Deprecated for most purposes after practical collision demonstrations.
• Current Standard: SHA-256 and SHA-3 are the NIST-approved standards for most blockchain and security applications. Protocols must be designed with algorithm agility to allow for future upgrades without breaking system functionality.

In Proof-of-Work (PoW) consensus mechanisms, miners compete to find a nonce such that Hash(block_header) < target. The security of the chain relies on the hash function's preimage resistance and the inability to find inputs that produce hashes in a specific range more efficiently than brute force. Vulnerabilities here include:

• ASIC Centralization: Specialized hardware (ASICs) for specific hash functions (like SHA-256 in Bitcoin) can lead to mining centralization.
• Algorithm-Specific Attacks: If weaknesses are found in the PoW hash function (e.g., reduced preimage resistance), it could lower the cost of mining attacks. Some blockchains use ASIC-resistant hash functions (e.g., Ethash, now SHA-3 based) to promote decentralization.

A Merkle Tree (or hash tree) is a data structure that uses cryptographic hashes to efficiently and securely verify the contents of large datasets. It works by:

• Hashing individual data blocks (e.g., transactions) into leaf nodes.
• Recursively hashing pairs of child hashes to form parent nodes, culminating in a single root hash (the Merkle Root).
• Enabling efficient verification (proof-of-inclusion) that a specific piece of data is part of the set without needing the entire dataset, a core component of blockchain headers.

A Digital Signature scheme uses asymmetric cryptography (public/private key pairs) to provide authentication, integrity, and non-repudiation. It typically involves a cryptographic hash function as a critical component:

• The signer hashes the message to create a fixed-size digest.
• The digest is then encrypted with the signer's private key to create the signature.
• Anyone can verify the signature by hashing the received message, decrypting the signature with the signer's public key, and comparing the two hashes.

A Cryptographic Commitment Scheme allows one to commit to a chosen value while keeping it hidden, with the ability to reveal it later. It is binding (cannot change the value) and hiding (cannot discover the value).

• Commit Phase: A committer generates a commitment (often using a hash like commitment = hash(value, random_nonce)), which is sent to a verifier.
• Reveal Phase: Later, the committer reveals the original value and random_nonce. The verifier can hash them to check if they match the original commitment.
• This is fundamental to protocols like zero-knowledge proofs and certain blockchain consensus mechanisms.

A Key Derivation Function (KDF) is a cryptographic algorithm designed to derive one or more secret keys from a secret value (like a master key or password). It often uses a hash function as a core primitive.

• Purpose: To stretch keys, create multiple keys from one, or add computational work to slow down brute-force attacks.
• Common Examples: PBKDF2 (Password-Based Key Derivation Function 2) and modern functions like Argon2 and scrypt use repeated hashing (or other operations) with a salt to derive a cryptographically strong key from a weak password.

An HMAC is a specific construction for creating a message authentication code (MAC) using a cryptographic hash function in combination with a secret key. It verifies both the data integrity and the authenticity of a message.

• Construction: HMAC(K, m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)), where H is a hash function (e.g., SHA-256), K is the secret key, and m is the message.
• Security: Its strength depends on the underlying hash function's properties. It is widely used in network protocols (TLS, IPsec) and APIs for request verification.

A Proof-of-Work (PoW) system, as used in Bitcoin mining, is a cryptographic puzzle that requires finding an input (a nonce) which, when hashed with other block data, produces an output hash with a certain number of leading zeros.

• The Puzzle: Find nonce such that hash(block_header + nonce) < target_difficulty.
• Properties: The puzzle is computationally difficult to solve but trivial to verify (just one hash computation). This "work" secures the blockchain by making it economically impractical to rewrite history.
• It is the most prominent example of a hash function being used as a verifiable delay function.