A reduction function deterministically maps a hash digest into a valid candidate password for a defined password space. It is not a hash reversal: it produces a new guess that obeys constraints such as length and allowed characters. The same digest must always produce the same candidate, allowing repeated hash-and-reduce steps to form a hash chain. section 6.4.2
For a SHA-256 password target, an implementation can read digest bytes, use each byte to select a character from an allowed charset, and assemble a fixed-length candidate. Hashing that candidate and reducing the resulting digest again creates the next link. The mapping need only yield valid guesses; it need not recover the password that originally produced the digest. section 6.4.2
Listing 6.1 Go example code for reducing an SHA-256 digest
package main
import (
"crypto/sha256"
"encoding/hex"
"fmt"
)
const PasswordLength = 6
const PasswordCharset = ("ABCDEFGHIJKLMNOPQRSTUVWXYZ + #1
abcdefghijklmnopqrstuvwxyz")
func ReduceSHA256Hash(digest [sha256.Size]byte) []byte {
var result []byte
for i := 0; i < PasswordLength; i++ {
selector := (int(digest[i])) % len(PasswordCharset)
if selector < 0 {
selector += len(PasswordCharset)
}
value := PasswordCharset[selector]
result = append(result, value)
}
return result
}
func main() {
message := []byte("abcdef")
for i := 0; i < 5; i++ {
digest := sha256.Sum256(message)
fmt.Printf("message: %s, digest: %s\n", message, hex.EncodeToString(digest[:]))
message = ReduceSHA256Hash(digest)
}
}
This implementation reduces a SHA-256 digest to six characters by selecting charset positions from digest bytes, then repeatedly hashes and reduces the result. section 6.4.2
A chain of candidate passwords
Start with `abcdef`, hash it, reduce the digest to `ilWrlG`, then hash and reduce again to `kdhkjA`. Each generated value is a candidate password, while the deterministic sequence makes the chain reproducible from the same starting point. section 6.4.2
Hash chains trade storage for computation in dictionary attacks: store chain endpoints rather than every password–digest pair, then regenerate chains when looking for a target digest. Chains can merge when they reach the same candidate, reducing coverage. Rainbow tables address this by varying the reduction function by column, so identical digests at different positions are reduced differently. section 6.4.2 section 6.5
Reduction functions support attacks on constrained, unsalted password spaces rather than defeating hash one-wayness. Salts make hash output depend on an additional public value and invalidate tables computed without that salt. section 6.5
