Programming
Why is XOR the default way to combine hashes
In the intricate world of computer science and cybersecurity, hashing stands as a cornerstone for ensuring data integrity, uniqueness, and efficient data retrieval. Hash functions transform arbitrary-sized input into a fixed-size string of characters, a hash value or digest. When dealing with complex data structures or needing to combine multiple pieces of information into a single, compact identifier, the question often arises: how do we effectively merge existing hash values? It turns out that the bitwise Exclusive OR (XOR) operation is overwhelmingly the default way to combine hashes, a practice deeply rooted in its unique mathematical properties that perfectly align with the goals of robust hash combination. This seemingly simple operation plays a critical role in maintaining the integrity and randomness crucial for effective hashing, offering unparalleled advantages over alternative methods.
The Fundamentals of Hashing and Bitwise Operations
At its core, a hash function is a deterministic algorithm that takes an input (or ‘message’) and returns a fixed-size string of bytes, typically a hexadecimal number. These ‘hash values’ are designed to be unique, meaning even a tiny change in the input should result in a drastically different hash output – a property known as the avalanche effect. In cryptographic contexts, hash functions like SHA-256 or MD5 (though MD5 is now largely deprecated for security) are crucial for verifying data integrity, creating digital signatures, and securing passwords, requiring properties like pre-image resistance, second pre-image resistance, and collision resistance.
When we talk about combining hashes, we’re often dealing with these fixed-size binary strings. This is where bitwise operations become paramount. Bitwise operations manipulate individual bits of binary numbers. Unlike arithmetic operations (addition, subtraction) that treat numbers as a whole, bitwise operations work on a bit-by-bit basis. For instance, the bitwise AND (&) returns 1 if both corresponding bits are 1, and 0 otherwise. The bitwise OR (|) returns 1 if at least one corresponding bit is 1. The bitwise XOR (^) returns 1 if the corresponding bits are different, and 0 if they are the same.
Understanding these fundamental operations is key to grasping why XOR is so effective. Simple arithmetic addition or multiplication could lead to issues like overflow, loss of information, or predictable patterns that compromise the very randomness and uniqueness that hashes are designed to provide. XOR, however, operates within the fixed bit length of the hashes, ensuring that the output remains within the expected boundaries and that every bit from the input hashes contributes meaningfully to the combined result.
Understanding XOR’s Unique Properties for Hash Combination
XOR is the default way to combine hashes primarily because of its exceptional ability to diffuse changes, preserve entropy, and maintain collision resistance without introducing biases or information loss. When two hash values are XORed, the resulting hash incorporates information from both inputs in a way that maximizes bit variance. If any bit in either input hash changes, the corresponding bit in the XOR result is highly likely to change, contributing significantly to the desired avalanche effect crucial for cryptographic applications and robust data structures. This property ensures that the combined hash remains sensitive to alterations in any of its constituent parts, making it extremely difficult to reverse-engineer or predict outcomes.
One of XOR’s most powerful attributes is its reversibility. If you have two values, A and B, and you compute C = A ^ B, you can recover A by computing C ^ B, or recover B by computing C ^ A. While this isn’t about reversing the hash function itself (which is designed to be one-way), it illustrates how XOR effectively mixes bits without destroying information. Each bit of the output hash is determined by the exclusive OR of the corresponding bits from the input hashes. This means that if two input hashes are very similar, their XOR combination will still produce a highly varied output, preventing ‘clumping’ in the hash space.
Consider an alternative like bitwise AND or OR. If you use AND, any bit that is 0 in either input will force the output bit to 0, potentially losing information and reducing the entropy of the combined hash. Similarly, with OR, any bit that is 1 in either input will force the output bit to 1, also leading to information loss and a biased distribution. Addition, while seemingly simple, can suffer from carries that propagate unpredictably and can lead to values exceeding the bit length of the hash, requiring truncation that further compromises uniqueness. XOR, in contrast, ensures that every bit from both input hashes contributes to the final result, preserving the statistical properties that make hash functions effective. For more on bitwise operations, you can consult resources like Wikipedia’s page on Bitwise Operations.
Ensuring Collision Resistance and Entropy Preservation
Collision resistance is a paramount property for any robust hashing scheme. A collision occurs when two different inputs produce the exact same hash output. While collisions are theoretically unavoidable in a finite hash space, good hash functions make them computationally infeasible to find. When combining hashes, the goal is to maintain or even enhance this resistance. XOR excels here because its operation introduces maximal dispersion. If two inputs are nearly identical, XORing them will produce an output with many set bits, reflecting their differences, rather than a near-zero value which might happen with subtraction or a biased value with AND/OR.
Moreover, XOR is excellent at entropy preservation. Entropy, in this context, refers to the measure of randomness or unpredictability within a system. High entropy in a hash means that its bits are as random as possible, making it difficult for an attacker to predict or manipulate. When you XOR two hashes, you are essentially combining their individual bit patterns in a way that maximizes the randomness of the resulting pattern. This is because XOR ensures that the probability of a bit being 0 or 1 in the output is close to 50%, provided the input hashes themselves are reasonably random. This uniform distribution across the hash space is vital for applications like hash tables, where good distribution minimizes collisions and ensures efficient data access.
This method of hash combination is particularly beneficial in scenarios where multiple identifiers need to be securely aggregated without revealing individual components, such as in certain privacy-preserving data aggregation techniques or when creating a unique composite key from several attributes. The XOR operation ensures that the combined hash value remains distinct and unpredictable, directly supporting the principles of data integrity and security. It allows for the creation of a strong, unified identifier from disparate sources, underpinning many modern secure systems. For further reading on cryptographic hash functions and their properties, the National Institute of Standards and Technology (NIST) provides comprehensive guidelines and publications, such as those found on their Special Publications page.
Practical Applications and Best Practices for Combining Hashes
The practice of combining hashes using XOR is not merely an academic exercise Question & Answer :
Say you have two hashes H(A) and H(B) and you want to combine them. I’ve read that a good way to combine two hashes is to XOR them, e.g. XOR( H(A), H(B) ).
The best explanation I’ve found is touched briefly here on these hash function guidelines:
XORing two numbers with roughly random distribution results in another number still with roughly random distribution*, but which now depends on the two values.
…
* At each bit of the two numbers to combine, a 0 is output if the two bits are equal, else a 1. In other words, in 50% of the combinations, a 1 will be output. So if the two input bits each have a roughly 50-50 chance of being 0 or 1, then so too will the output bit.
Can you explain the intuition and/or mathematics behind why XOR should be the default operation for combining hash functions (rather than OR or AND etc.)?
xor is a dangerous default function to use when hashing. It is better than and and or, but that doesn’t say much.
xor is symmetric, so the order of the elements is lost. So "bad" will hash combine the same as "dab".
xor maps pairwise identical values to zero, and you should avoid mapping “common” values to zero:
So (a,a) gets mapped to 0, and (b,b) also gets mapped to 0. As such pairs are almost always more common than randomness might imply, you end up with far to many collisions at zero than you should.
With these two problems, xor ends up being a hash combiner that looks half decent on the surface, but not after further inspection.
On modern hardware, adding usually about as fast as xor (it probably uses more power to pull this off, admittedly). Adding’s truth table is similar to xor on the bit in question, but it also sends a bit to the next bit over when both values are 1. This means it erases less information.
So hash(a) + hash(b) is better than hash(a) xor hash(b) in that if a==b, the result is hash(a)<<1 instead of 0.
This remains symmetric; so the "bad" and "dab" getting the same result remains a problem. We can break this symmetry for a modest cost:
hash(a)<<1 + hash(a) + hash(b)
aka hash(a)*3 + hash(b). (calculating hash(a) once and storing is advised if you use the shift solution). Any odd constant instead of 3 will bijectively map a “k-bit” unsigned integer to itself, as map on unsigned integers is math modulo 2^k for some k, and any odd constant is relatively prime to 2^k.
For an even fancier version, we can examine boost::hash_combine, which is effectively:
size_t hash_combine( size_t lhs, size_t rhs ) { lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2); return lhs; }
here we add together some shifted versions of lhs with a constant (which is basically random 0s and 1s – in particular it is the inverse of the golden ratio as a 32 bit fixed point fraction) with some addition and an xor. This breaks symmetry, and introduces some “noise” if the incoming hashed values are poor (ie, imagine every component hashes to 0 – the above handles it well, generating a smear of 1 and 0s after each combine. My naive 3*hash(a)+hash(b) simply outputs a 0 in that case).
Extending this to 64 bits (using the expansion of pi as our constant for 64 bits, as it is odd at 64 bits):
size_t hash_combine( size_t lhs, size_t rhs ) { if constexpr (sizeof(size_t) >= 8) { lhs ^= rhs + 0x517cc1b727220a95 + (lhs << 6) + (lhs >> 2); } else { lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2); } return lhs; }
(For those not familiar with C/C++, a size_t is an unsigned integer value which is big enough to describe the size of any object in memory. On a 64 bit system, it is usually a 64 bit unsigned integer. On a 32 bit system, a 32 bit unsigned integer.)
