4

A few days ago I found a fun fact, that finding a collision of 256-bit hash using brute-force is physically impossible in solar system.

That made me think, what would happen if we used a good (uniform) 256-bit hash in a hash map. I guess, we could consider, that there are never false key hash matches, so we could get rid of the actual value of key in favor of storing only its hash.

  1. Would be space efficient? (No value of key, just hash)
  2. Would it be fast? (No collision check, but bigger hash than usual)
  3. Would it be safe? (Statistically)
  4. Has anybody done this?

Yes, there could be way fewer buckets than 2^256. The goal is to calculate the hash, find bucket and then find the actual value inside the bucket using ONLY the full 256-bit hash and without actual value check. For example in hash map where keys are strings, there could be no equality confirmation, so no actual bytes comparison and no potentially big key storage.

There seems to be a lot of disregard towards 2^256 combinations. To give you the scale, the estimated number of atoms in the known universe is between 10^78 and 10^82, roughly 2^260 and 2^270. Humankind will probably never produce all possible 256-bit numbers.

Yes, the quantum computers will be able to find collisions in split seconds. But future cryptographic safety is not the point, the point is simplification of in-memory, std-lib grade collections for internal use in applications.

  • 3
    No, you can't. Look up the "pigeonhole principle" to see why. – Kilian Foth Mar 4 '18 at 23:27
  • 1
    Will your hash table have 2^256 buckets? Or will it only have 64ish buckets and use the lower 6ish bits of the hash? – immibis Mar 4 '18 at 23:45
  • 2
    Just because it's incredibly unlikely to flip a coin and have it land on edge doesn't mean it has no chance of happening. Things that have 1 in a billion chance of happening happen every day. – candied_orange Mar 5 '18 at 4:51
  • 2
    @KilianFoth - the pigeonhole principle (or rather the birthday paradox, which is related and more relevant here) suggests that with a 256 bit hash, you're likely to start seeing collisions when you have 2^128 items in storage. If you use the "short scale" for numbering, that's around 30 decillion items. Nobody has that much data. Nobody ever will have that much data. – Jules Mar 5 '18 at 17:07
  • 1
    @CandiedOrange: Which just means that you need code to recover from such an unlikely occurrence, code that would probably ask for a new hash. – Robert Harvey Mar 5 '18 at 18:21
7

Yes, it is possible to do this. Look up the details of ZFS for a deployed, production-quality system that uses this idea. In ZFS, any data that is to be stored is hashed with a cryptographic, 256-bit hash, and if it matches any existing data that is known to exist in the system it is assumed to be the same data, and the two blocks on disk are considered to be candidates for merging. This means that, as long as you have enough RAM (or, more realistically, fast SSD space) to keep a hashtable of a large proportion of the recently accessed blocks, you can store duplicated copies of files without needing extra space for the duplicates. The same facility is also used to provide snapshots for the system.

While it's handy for file systems, it's probably not that useful for in-memory storage, however, due to the fact that it's only really a good approach for very large objects that are expensive to access (i.e. due to disk access latency). For smaller objects with fast access, it's easier to compute a small hash and check them in detail when a hash collision occurs, because the hash functions for such an operation run much faster and the results need less memory to store than the large cryptographic hashes that are required to make ZFS reliable.

  • 4
    Another tool which relies on "If the hashes are the same, the files are the same" is Git. – Cort Ammon Mar 5 '18 at 21:19
  • @CortAmmon And idiotically chose a hash function known to not be collision resistant for the job... – CodesInChaos Mar 7 '18 at 11:01
7

You are right, a hash function which such a large hash space will see very few collisions. But a hash table uses a hash function for a specific purpose: mapping hash table entries into a specific bin. This is usually done by using a modulo operation, i.e. bucket = hash(key) % n_buckets. For a power-of-two sized table, this can be done very efficiently by masking off the high bits of the hash.

So a hash table isn't so much concerned about hash collisions as it is about bucket collisions. Or viewed differently, it doesn't directly use some hash function but that hash function modulo the number of buckets.

Because of this, a hash function with a big hash space is pointless, nearly all bits will be masked off. For a hash table with 256 buckets I only need 8 bits, any more would be a waste.

How can hash tables be secure if they only have so few bits? Especially for fast (non-cryptographic) hash functions, it is possible to pre-compute collisions. If an attacker feeds these colliding elements into a hash table (e.g. query string parameters into a web application) they will be mapped to the same bucket, thus degrading the O(1) lookup of a hash table to that of a linked list: O(n). This is usually prevented by parametrizing the hash function with a per-process or even per-table salt. As the salt is unknown to the attacker, they cannot precompute any collusions.

  • 1
    The point of doing something like this is to use the hash as a proxy for the actual key, so if the key is large and/or expensive to access (e.g. because it's stored on disk while your hash index is stored in RAM) you can compare the hashes as a proxy for comparing the keys themselves. In this circumstance, storing the full hash instead of storing the key itself in the table is a useful structure. It's rare, but reasons to do it do exist. – Jules Mar 5 '18 at 17:17
  • @Jules oh, you're right, I misread that the question seems to be about using the hash as the key, not as the hash table's usual hash function (which can then be simplified to the identity function). – amon Mar 5 '18 at 17:47
  • NOTE: when the number of buckets is an even power of two, you end up using far fewer buckets than you planned. A lot of that is due to the default implementation of getting a hashcode for an object in many languages (which is the memory address for the object). That's why most hashmap implementations use a prime number for the number of buckets. Trust me, lesson learned a long time ago when I created a custom concurrent safe hasmap in Java. Peer review and actual usage reports showed me the error of my ways. – Berin Loritsch Mar 5 '18 at 19:15
  • @BerinLoritsch You're not wrong, but this doesn't hold universally true either. Java, Python, … are unique because every object is hashable, often with a suboptimal hash function. There, a prime number leads to better bucket distribution. But with an evenly distributed hash function over a 2^n sized hash space, a power-of-two sized hash table and dynamic resizing by a factor of 2 is strictly superior. This guarantees amortized O(1) inserts and avoids memory fragmentation. If the bucket count doesn't divide the hash space evenly, you'll get a bias towards the lower-numbered buckets. – amon Mar 5 '18 at 19:37
  • Btw the OpenJDK HashMap implementation enforces power of two table sizes, and Oracle documents the default capacity as the very non-prime 16 – amon Mar 5 '18 at 19:37
0

With the right hashing algorithm, your idea might work, at least in some scenarios. For specialized applications, it could have a valuable performance advantage. But the quality of the hashing algorithm is crucial. Other answers and comments have mentioned software like Git and ZFS that assume equal hashes imply equal objects. They can get away with this because they do their own hashing with a known algorithm.

This is not the case for a general purpose collection. In Java, for example, every class supplies its own hashing method, and HashMap delegates hashing to the objects it stores. It's perfectly legal for a class to use a bad hashing algorithm that is likely to produce collisions. In fact, it's perfectly legal to return the same hash code for every object. The performance of hash based collections will suffer, but they will still produce correct results. Your map would not.

-1

The image you reference is an example of why I firmly believe that most cryptocurrency enthusiasts really don't understand the underlying technology. One huge flaw in it's claim is that if a 256-bit quantum computer were built (something that a lot of people think can be done in the near future), such a machine could crack the crypto 'protecting' bitcoin in a matter of seconds. In other words, the main claim in the image is bogus.

The other factor that this factoid fails to mention is that it's not simply the integer space (2^256) that is relevant here, it's also how well distributed the hashes are across that space. Here's an example of a 256 bit hash function:

byte[] hash(Object... data){
   byte[] hash = new byte[32];

   for (int i = 0; i < 32; i++) hash[i] = (byte)0xFF;

   return hash;
}

Now, ask yourself, is it really 'impossible' for a 256 bit hash to collide with another? Obviously, that hash function sucks. But history has shown us that over time, the hash functions that were thought to be secure turn out not to be so. It's important to understand that it's not just that the spaces of these hash functions weren't big enough, it's that the algorithms were weak.

In theory, this scheme is possible but it can only be guaranteed to work if you are using a perfect hash function and your inputs to that function never exceed 256 bits.

  • Hello? Anonymous coward? – JimmyJames Mar 5 '18 at 21:06
  • 1. I don't believe there is an existing, known quantum algorithm for generating SHA256 images. Even if there was, it would almost certainly not work on quantum annealing computers, which are the only kind we can do anything like 256 bits with. The largest "traditional" quantum computer ever produced is 50 bits. It's taken 12 years to get there from the 12 bits that the first working system had, so I think we can expect a while before we get to 256. As to the distribution of outputs, the output of SHA256 is known to have the avalanche property (i.e. roughly 50% of all the bits ... – Jules Mar 5 '18 at 21:34
  • ... toggle with every single bit change in the input), which means that its distribution is practically guaranteed to be good for anything other than engineered data (and that engineering would be extremely difficult). While SHA1 is no longer considered secure, that doesn't mean it is now expected for collisions to occur arbitrarily. None of the attacks on it allow for production of data to match a preexisting hash; all that can be done is two items can be produced through the same process that have the same hash ... that's not a realistic problem for the kind of system being discussed here) – Jules Mar 5 '18 at 21:39
  • @Jules There is such an algorithm. I added a link that provides more detail. I'm not saying this is going to occur soon. I'm not totally convinced that it's possible to build quantum machines at that scale. My point is that the original source provided is making a bogus argument. Actually when I looked at it again, it doesn't actually contain a real argument. It's just gobbledy-gook. So basing any idea off of this solar-system thermodynamics argument is suspect. – JimmyJames Mar 5 '18 at 21:39
  • 1
    the "vulnerability" described in that article is not really worth worrying about. Shor's algorithm is a potentially problematic attack, but doesn't attack the hash algorithm used but rather the public key system in use to securely identify the owners of a wallet. It would need a lot more than 256 qubits to successfully attack a bitcoin wallet, but has no relevance at all to this question. Grover's algorithm is directly relevant, but useless with any currently proposed technology. It reduces the number of steps required to reverse a hash from 2^256 to 2^128 ... – Jules Mar 5 '18 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.