Cryptographic Hash Functions (Funções Hash Criptográficas)¶

Cryptographic hash functions are fundamental building blocks of modern security systems. They transform arbitrary-length input data into fixed-size outputs called "hashes" or "digests," enabling integrity verification, digital signatures, and secure password storage.

Mathematical Foundation¶

Definition¶

A cryptographic hash function $H$ maps an arbitrary-length message $M$ to a fixed-length output:

$$H: {0,1}^* \rightarrow {0,1}^n$$

Where: - Input $M$ can be any length (bits or bytes) - Output is always exactly $n$ bits (e.g., 256 bits for SHA-256)

Key Properties¶

1. Determinism¶

The same input always produces the same output: $$H(M_1) = H(M_2) \implies M_1 = M_2$$

2. Pre-image Resistance (One-way Property)¶

Given a hash $h$, it should be computationally infeasible to find any message $M$ such that: $$H(M) = h$$

3. Second Pre-image Resistance¶

Given an input $M_1$, it should be infeasible to find a different input $M_2$ such that: $$H(M_1) = H(M_2)$$

4. Collision Resistance¶

It should be computationally infeasible to find any two distinct messages $M_1, M_2$ such that: $$H(M_1) = H(M_2)$$

SHA-256 (Secure Hash Algorithm 256-bit)¶

SHA-256 is part of the SHA-2 family developed by NIST and published in 2001. It produces a 256-bit (32-byte) hash value.

Structure¶

SHA-256 processes input data in 512-bit blocks using: - 8 working variables ($a, b, c, d, e, f, g, h$), each 32 bits - 64 rounds of computation with different constants and functions - Message schedule expansion: Expands 512-bit block to 64 words

Pseudocode Overview¶

def SHA256(message):
    # Initialize hash values (first 32 bits of fractional parts of square roots)
    h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
         0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

    # Process each 512-bit block
    for block in message_blocks:
        # Expand message schedule (64 words)
        w = expand_message_schedule(block)

        # Initialize working variables
        a, b, c, d, e, f, g, h = h

        # Perform 64 rounds
        for i in range(64):
            S1 = right_rotate(e, 6)
            ch = (e & f) ^ ((~e) & g)
            temp1 = h + S1 + ch + K[i] + w[i]
            S0 = right_rotate(a, 2)
            maj = (a & b) ^ (a & c) ^ (b & c)
            temp2 = maj + constant

            h = g
            g = f
            f = e
            e = d + temp1
            d = c
            c = b
            b = a
            a = temp1 + temp2

        # Add to hash value
        for i in range(8):
            h[i] = (h[i] + result[i]) & 0xFFFFFFFF

    return concatenate(h)

Example Hashes¶

Input	SHA-256 Hash
"abc"	`ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad`
"" (empty)	`e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855`
"hello"	`a591a6d40bf420404a011733cfb7b190d62c65bf0bcda31b171af4bd51b39a6f`

Collision Attacks and Birthday Paradox¶

The Birthday Problem¶

The probability of finding a collision increases dramatically with the number of attempts. For SHA-256 (256-bit output):

Attempts	Probability of Finding Collision
$2^{128}$	~50%
$2^{129}$	~75%
$2^{256}$	Required for brute force (practically impossible)

This is known as the birthday attack - you only need $\sqrt{N}$ attempts to find a collision among $N$ possible outputs.

Real-World Collision Attacks¶

MD5 Collisions (2004-2017)¶

MD5 was broken for practical purposes:

# Example of finding MD5 collisions (simplified)
def create_md5_collision():
    # Two different files with same MD5 hash
    file1 = generate_file_with_prefix("A")
    file2 = generate_file_with_prefix("B")

    assert md5(file1) == md5(file2)  # True!

SHA-1 was also broken in 2017 (SHAttered attack), demonstrating that even "secure" algorithms can be compromised.

Java Implementation¶

SHA-256 Hash Function¶

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.nio.charset.StandardCharsets;

public class HashFunctions {

    /**
     * Computes the SHA-256 hash of a string.
     * @param input The input string to hash
     * @return Hexadecimal representation of the hash
     */
    public static String sha256(String input) throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] hashBytes = digest.digest(input.getBytes(StandardCharsets.UTF_8));

        StringBuilder hexString = new StringBuilder();
        for (byte b : hashBytes) {
            String hex = Integer.toHexString(0xff & b);
            if (hex.length() == 1) hexString.append('0');
            hexString.append(hex);
        }

        return hexString.toString();
    }

    /**
     * Computes the SHA-256 hash of raw bytes.
     */
    public static String sha256Bytes(byte[] input) throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        byte[] hashBytes = digest.digest(input);

        StringBuilder hexString = new StringBuilder();
        for (byte b : hashBytes) {
            String hex = Integer.toHexString(0xff & b);
            if (hex.length() == 1) hexString.append('0');
            hexString.append(hex);
        }

        return hexString.toString();
    }

    /**
     * Verifies a message against its expected hash.
     */
    public static boolean verify(String message, String expectedHash) throws NoSuchAlgorithmException {
        return sha256(message).equals(expectedHash);
    }

    public static void main(String[] args) throws Exception {
        String input = "Hello, World!";

        System.out.println("Input: " + input);
        System.out.println("SHA-256: " + sha256(input));

        // Verify
        boolean isValid = verify(input, sha256(input));
        System.out.println("Verification passed: " + isValid);
    }
}

Using Java's MessageDigest (Alternative)¶

import java.security.MessageDigest;
import java.nio.charset.StandardCharsets;

public class SimpleHash {

    public static String hash(String input) throws Exception {
        try (MessageDigest md = MessageDigest.getInstance("SHA-256")) {
            byte[] hashBytes = md.digest(input.getBytes(StandardCharsets.UTF_8));
            return bytesToHex(hashBytes);
        }
    }

    private static String bytesToHex(byte[] bytes) {
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            sb.append(String.format("%02x", b));
        }
        return sb.toString();
    }
}

Applications of Cryptographic Hash Functions¶

1. Password Storage¶

Never store passwords in plaintext! Use a hash function with salt:

public class PasswordStorage {

    private static final int SALT_LENGTH = 32; // bytes

    /**
     * Hashes a password with a random salt.
     */
    public static String hashPassword(String password) throws Exception {
        byte[] salt = generateRandomSalt();

        try (MessageDigest md = MessageDigest.getInstance("SHA-256")) {
            // Combine salt and password
            byte[] combined = new byte[salt.length + password.getBytes().length];
            System.arraycopy(salt, 0, combined, 0, salt.length);
            System.arraycopy(password.getBytes(), 0, combined, salt.length, password.getBytes().length);

            byte[] hash = md.digest(combined);

            // Store salt and hash together (e.g., "salt:hash")
            return base64Encode(salt) + ":" + bytesToHex(hash);
        }
    }

    /**
     * Verifies a password against stored hash.
     */
    public static boolean verifyPassword(String password, String storedHash) throws Exception {
        String[] parts = storedHash.split(":");
        byte[] salt = base64Decode(parts[0]);

        try (MessageDigest md = MessageDigest.getInstance("SHA-256")) {
            byte[] combined = new byte[salt.length + password.getBytes().length];
            System.arraycopy(salt, 0, combined, 0, salt.length);
            System.arraycopy(password.getBytes(), 0, combined, salt.length, password.getBytes().length);

            byte[] computedHash = md.digest(combined);
            return Arrays.equals(computedHash, base64Decode(parts[1]));
        }
    }

    private static byte[] generateRandomSalt() {
        // Use secure random source in production
        return new java.security.SecureRandom().generateNewByteArray(SALT_LENGTH);
    }
}

2. Digital Signatures¶

Hash functions are used to create digital signatures:

Hash the message $M$ to get $h = H(M)$
Sign the hash with private key (e.g., RSA)
Verify by hashing and comparing

3. Blockchain and Cryptocurrencies¶

Bitcoin uses SHA-256 for: - Mining proof-of-work - Creating block hashes - Ensuring chain integrity

# Simplified Bitcoin mining example
def mine_block(previous_hash, transactions, difficulty):
    nonce = 0

    while True:
        # Create block data
        block_data = previous_hash + str(transactions) + str(nonce)

        # Hash the block
        block_hash = sha256(block_data.encode())

        # Check if hash meets difficulty requirement
        if int(block_hash, 16)[:difficulty] == '0' * difficulty:
            return block_hash

        nonce += 1

4. File Integrity Verification¶

Downloaded files often include a checksum (hash) to verify integrity:

# Linux/Mac
sha256sum file.txt > file.txt.sha256
sha256sum -c file.txt.sha256

# Windows
certutil -hashfile file.txt SHA256

Security Considerations¶

1. Salt for Passwords¶

Always use a unique random salt per password to prevent: - Rainbow table attacks - Identifying duplicate passwords across users

2. Key Stretching¶

For password hashing, consider using specialized algorithms like: - bcrypt: Built-in cost factor, adaptive security - scrypt: Memory-hard function - Argon2: Winner of Password Hashing Competition (most secure)

// Using bcrypt for password hashing
import org.mindrot.jbcrypt.BCrypt;

public class SecurePasswordHashing {

    public static String hashPassword(String password) {
        // Cost factor 12 = ~4096 iterations
        return BCrypt.hashpw(password, BCrypt.gensalt(12));
    }

    public static boolean verifyPassword(String password, String hashed) {
        return BCrypt.checkpw(password, hashed);
    }
}

3. Hash Length Selection¶

Algorithm	Output Size	Status	Recommendation
MD5	128 bits	Broken	Never use
SHA-1	160 bits	Broken	Avoid
SHA-256	256 bits	Secure	Recommended
SHA-384	384 bits	Secure	For high security
SHA-512	512 bits	Secure	Alternative

4. Quantum Computing Threats¶

Future quantum computers could break current hash functions using Grover's algorithm, reducing effective security by half: - SHA-256 would provide ~128-bit security instead of 256-bit - Migration to post-quantum cryptography may be necessary

Common Attacks¶

Length Extension Attack¶

Some hash constructions (like Merkle-Damgård) are vulnerable to length extension attacks. Given $H(M)$ and the length of $M$, an attacker can compute $H(M || \text{padding} || \text{suffix})$ without knowing $M$.

Mitigation: Use HMAC or SHA-3 instead of raw hash functions for keyed operations.

Second Pre-image Attack¶

Finding a different message that produces the same hash as a given message. While theoretically possible, it's computationally infeasible for properly designed hash functions.

References¶

NIST Special Publication 800-180: SHA-2 and SHA-3
Stinson, D. R., & Trappe, W. (2015). Cryptography: Theory and Practice. CRC Press.
Daemen, J., & Rijmen, V. (2002). The Design of Rijndael. Springer.
Bernstein, D. J. (2009). "SHA-3 Candidate Designs".