7
$\begingroup$

I'm working on my miner for my "game" site that's basically a pre-image attack from a hash posted online. You submit a hash input, it's hashed, and your score is the hamming distance (the number of bits that differ) between the two values. If it matters, I'm using Skein-1024 v1.3

My miner up until now has been incrementing a value and hashing it. Increment, hash, increment, hash ad infinium. I wrote it so that when I close the miner, it saves it's current highest value that way when I restart it I won't start back over at 1 and hash all the same inputs again. I can pick up where I left off. This has proven to be some what successful. However, I'm curious if the miner might be more fruitful by generating random numbers instead of incrementing.

It seems to be a hard metric to measure. I know that most hashes will output wildly different values if their inputs are off by only a bit or two, but I feel that by incrementing the value I hash I'm usually only a few bits off. If I randomly generate values I'll probably do fewer hashes (because random number generation is more intensive than a simple num++ increment) but my gut tells me that I'll have a more diverse set of inputs and that it might produce a more diverse set of outputs. I know not to trust my gut without reason about this. I feel crazy just typing it out.

I also know that if I increment I'll never end up hashing the same value twice. Random is capable of that although the odds of generating the exact same 64 bit number twice is slim.

Can I expect different qualities of outputs from my miner by hashing random values instead of an incrementing value?

FULL DISCLOSURE: I am the owner and operator of the site above. There are no ads or even analytics on the page.

Improve this question
$\endgroup$
6
  • $\begingroup$ You could use Skein as deterministic random number generator and save the state of the Skein hash. Just joking of course, but this is just to indicate that using a random number generator as input for a hash function will likely mean that you spend a lot of time - maybe even more - for the generation of the random number. You may consider using a (PB)KDF instead of just a hash for the hash calculations (e.g. LiteCoin uses scrypt). $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 22, 2015 at 16:22
  • $\begingroup$ Hey, I have a new bottom score (559)! Do I get a consolation price? $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 22, 2015 at 16:26
  • $\begingroup$ @MaartenBodewes No prizes (yet...), but I have debated each user having a highest and lowest score because I think a score of 1024 would be just as impressive (and as difficult) as a score of 0. $\endgroup$
    – Corey Ogburn
    Commented Sep 22, 2015 at 16:28
  • $\begingroup$ @MaartenBodewes, actually I think lower is better and 559 isn't all that great (considering it's the highest listed value)... but congraz :P $\endgroup$
    – SEJPM
    Commented Sep 22, 2015 at 16:53
  • $\begingroup$ @SEJPM Obviously anything above 512 isn't "great" to say the least - half of the values should be the same or lower than that. It was kind of funny to get a score on the other end of the spectrum though. $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 22, 2015 at 16:56

2 Answers 2

Reset to default
4
$\begingroup$

For a good hash function, like Skein, diversity of inputs has no impact on diversity of outputs. So, if you have no information about the space of possible pre-images (e.g., it is not a human generated password, it is a completely random input from your prospective), then the expected number of attempts before retrieving the pre-image is the same in either case. Should also be the same number of attempts to find an input with a specific hamming-weight from the input.

As you note, however, there are benefits to using the counter. You can easily save state. You know you will never see the same input. If you are generating random 64-bit values, the odds of seeing a colliding input is actually not as small as you would think. You would expect to see a collision after $2^{32}$ inputs.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Oh yeah, isn't that called the birthday paradox? That may not be the name, but I remember that property. I'll switch back to my incremental version of the miner. $\endgroup$
    – Corey Ogburn
    Commented Sep 22, 2015 at 16:20
  • $\begingroup$ @CoreyOgburn Yep, birthday paradox. $\endgroup$
    – mikeazo
    Commented Sep 22, 2015 at 16:37
  • 2
    $\begingroup$ No, it's just called a distribution indistinguishable from random. On average, irrespective from input, you would expect a Hamming distance of half of the output for different inputs. It doesn't matter if you generate the new input using a RNG or by increasing the value. It does have something to do with the birthday problem; if your output is indistinguishable from random you can prove that collisions cannot be generated faster than using the birthday paradox. So in general, cryptographic hash function output is indistinguishable from random. $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 22, 2015 at 16:39
  • $\begingroup$ @MaartenBodewes good point. $\endgroup$
    – mikeazo
    Commented Sep 22, 2015 at 16:42
1
$\begingroup$

If you can use numbers larger than 64 bits, you can have your cake and eat it too.

By choosing a random starting point and then incrementing a counter, you do not need to save any state, but also do not need to generate expensive random numbers for every hash. An essentially similar idea is using a part of the previous hash as the next input (a hash chain). In both cases if one value collides with a previous try then the subsequent values will as well. However, with a large enough random value (e.g. 128 bits) this is unlikely to happen in practice.

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.