Hash Functions and SHA-3 Implementation Guide

Introduction to Hash Functions in Modern Cryptography

Hash functions are the backbone of data integrity and security in countless applications, from blockchain to password storage. In CSCI 181, you're diving into the mathematics behind these functions and implementing parts of SHA-3, the latest Secure Hash Algorithm standard. This tutorial will help you understand the key concepts—collision resistance, one-way properties, and the inner workings of SHA-3—using relatable examples from gaming, AI, and school life.

Part 1: Hash Function Basics and the Birthday Problem

A hash function h: X → Y maps an input set X to a smaller output set Y. Because |X| is typically much larger than |Y|, collisions (distinct inputs mapping to the same output) are inevitable. This is similar to the birthday paradox: in a group of 23 people, there's a 50% chance two share a birthday, even though there are 365 possible birthdays.

For your homework, you're given a hash function that takes 1088-bit strings and outputs 256-bit strings. Let's compute the average number of preimages per output, denoted n. The number of possible inputs is 2^1088, and the number of possible outputs is 2^256. On average, each output has n = 2^1088 / 2^256 = 2^832 preimages. That's an astronomically large number, showing why finding a preimage by brute force is infeasible.

Now, the probability that a random 1088-bit string hashes to a specific output y is n / (2^1088) = 2^832 / 2^1088 = 1 / 2^256. This tiny probability illustrates the one-way property: given y, it's hard to find any x such that h(x) = y.

Part 2: Weak Collision Resistance Implies One-Way Property

Your assignment asks for an informal contrapositive proof that if a hash function is weakly collision resistant, it must be one-way. Let's break it down. Weak collision resistance means given an input x, it's infeasible to find a different input x' with the same hash. One-way means given a hash value y, it's infeasible to find any preimage x.

Assume the function is not one-way: there exists an efficient algorithm that, given y, finds some x with h(x) = y. Now, pick any arbitrary input x0. Compute y0 = h(x0). Use the algorithm on y0 to get x1 such that h(x1) = y0. If x1 ≠ x0, you've found a collision. If x1 = x0, the algorithm returned the same input. However, because the algorithm works for any y, you can repeat with a different x0 or modify the algorithm to always return a different preimage (e.g., by flipping a bit). Thus, breaking one-way allows breaking weak collision resistance. This is why modern hash functions aim for both properties.

Part 3: Implementing SHA-3's θ, ρ, and π Steps

SHA-3 (Keccak) uses a sponge construction with a 3D state array a[5][5][64] (1600 bits). Your homework tasks you to implement the mapping between 1D and 3D representations, and then the θ, ρ, and π steps. Let's walk through each.

3.1 Input and Output Functions

inputSHA3() converts a 1D array v[0..1599] to a 3D array a[i][j][k] using the formula: a[i][j][k] = v[64*(5*j + i) + k]. Note that the order is i (x), j (y), k (z). This mapping is crucial for the SHA-3 algorithm.

outputSHA3() does the reverse: v[64*(5*j + i) + k] = a[i][j][k]. Make sure your indexing matches exactly; a common mistake is swapping i and j.

3.2 The θ Step

The θ step is the first permutation step, designed to diffuse bits. It computes parity of columns and then adds them to the state. For each (i, j, k), the new value is: aout[i][j][k] = ain[i][j][k] ^ C[i][k] ^ C[(i-1) mod 5][k], where C[i][k] is the XOR of all ain[i][j][k] over j. To verify your implementation, your assignment states that for the provided input file, aout[4][3][9..18] should be 0011011000. After applying θ, you need to list aout[3][1][15..24].

Think of θ like a team huddle in esports: each player (bit) shares information with teammates to create a new strategy. The XOR operations ensure every bit is influenced by others, increasing security.

3.3 The ρ Step

The ρ step rotates bits within each lane (each a[i][j] 64-bit word) by a specific offset given by the rhomatrix. For each (i, j), the rotation offset is rhomatrix[i][j]. The operation: aout[i][j][k] = ain[i][j][(k + rhomatrix[i][j]) % 64]. Check your work: for the input file, aout[4][3][9..18] after ρ should be 0110011001. Then report aout[3][1][15..24].

This is like shuffling a playlist—each song (bit) gets a new position based on a fixed pattern, ensuring that bits from different parts of the state mix together.

3.4 The π Step

The π step permutes the lanes across the 5x5 grid. It moves the entire 64-bit lane at position (i, j) to a new position (j, (2*i + 3*j) % 5). For each (i, j), aout[j][(2*i + 3*j) % 5][k] = ain[i][j][k]. After π, the expected output for aout[4][3][9..18] is 0110110001. You'll then list aout[3][1][15..24].

Imagine rearranging seats in a classroom based on a formula—this ensures that students (bits) from different rows and columns interact, creating a more complex structure.

Practical Tips for Implementation

Use modulo arithmetic: All indices wrap around modulo 5 for i and j, and modulo 64 for k. In C/C++, use % operator but be careful with negative numbers—add 5 or 64 before modulo.
Test with small arrays: Create a test case with known values to verify your mapping functions. For example, use a 1D array where v[0] = 1, v[1] = 0, ... and check the 3D result.
Reference the NIST standard: The SHA-3 specification (FIPS 202) provides detailed pseudocode. Use it to double-check your logic.
Debug with the provided checks: Your assignment gives specific output bits for the θ, ρ, and π steps. Use these to verify each function independently before combining them.

Connecting to Real-World Trends

Hash functions are everywhere. When you log into a game like Valorant, your password is hashed before storage. In AI, hash functions help verify model integrity—ensuring that a downloaded neural network hasn't been tampered with. Even in finance, blockchain uses SHA-256 (similar to SHA-3) to secure transactions. Understanding these fundamentals gives you a leg up in cybersecurity, app development, and data science.

Conclusion

Homework 4 challenges you to both reason about hash function properties and implement core SHA-3 steps. By mastering the one-way and collision resistance concepts, and by coding the θ, ρ, and π functions, you're building a solid foundation in cryptography. Use the provided test vectors to validate your work, and don't hesitate to consult the SHA-3 standard for clarification. Good luck!