2
$\begingroup$

I have a long set of hashes (long hashes, long set) generated with the same algorithm. And for each hash I know that it belongs to one of two groups.

Are there any methods of hash analysis, that allow to determine with some probability which group (any) given hash belongs to?

update:

A simple example: I have a long set of 64 bit numbers. Some of them are less than 2^40. And these belong to group A. All the rest belong to group B. I calculate SHA of each. Then I analyse all SHAs with a magic algorithm trying to find a rule determining the group from given SHA with maximum possible accuracy. From other point of view a magic algorithm measures hash efficiency in some way. I do not know how to start with such task, and whether there are any known algorithms performing similar tasks.

Improve this question
$\endgroup$
4
  • $\begingroup$ What kind of groups are you referring to? Algorithms? Hash output is for cryptographic hashes is usually indistinguishable from random. $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 23, 2016 at 0:56
  • $\begingroup$ All hashes generated with the same algorithm. $\endgroup$
    – ardabro
    Commented Dec 23, 2016 at 7:33
  • $\begingroup$ So you mean the input belongs to one or two groups and you want to know with some certainty x that the hash belongs to one of these groups? $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 23, 2016 at 7:55
  • 2
    $\begingroup$ Apart from recovering the inputs by guessing it and comparing the hash, there is little you can do. $\endgroup$
    – CodesInChaos
    Commented Dec 23, 2016 at 8:54

1 Answer 1

Reset to default
2
$\begingroup$

For your example, sure there is:

  1. Precalculate the SHA hash of every number less than $2^{40}$. Store those hashes in a database.

  2. To check if a hash belong to a number less than $2^{40}$, look it up in the database. If you find it, the answer is yes, otherwise no.

Sure, that'll take a bunch of precalculation and a rather large database, but it's quite possible to do with modern hardware.

You could optimize the database size a little, e.g. down to 80 bits per entry by only storing the first 40 bits of the hash and the 40-bit number that produced it, letting you verify the match by hashing the number. Or you could even store just, say, the first 32 bits of each hash and a list of the all the (256 or so) numbers that produced it, getting down to only slightly over 40 bits per entry at the cost of 256 hash computations per lookup on average. If you don't mind some occasional false positives, even more impressive space savings are possible e.g. using a Bloom filter.

In the general case, though, assuming that:

  1. the groups you wish to distinguish are large enough that precalculating the hashes of all (or even most) elements of either of them is not practical, and
  2. the definitions of the groups don't have anything to do with the hash function used (i.e. you may not choose "strings whose hash begins with a zero" as one of the groups),

then it is generally not feasible to determine which group a string belongs to just from its hash.

Note that resistance to this kind of "generalized preimage attack" does not follow from the standard preimage and collision resistance properties that a secure cryptographic hash is expected to satisfy. Still, if anyone were to find an efficient distinguisher like that for a widely used hash, that would certainly be considered by most cryptographers a notable attack on the hash function.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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