4
$\begingroup$


We know that a good hash function is a one way/trapdoor function. Easy to calculate one way, harder to work out a previous state.
I was wondering if anyone knew a good hashing system that allowed you to calculate an arbitrary number of steps into the state future.
E.g. instead of running the hash function 10,000 times to find out the h^10000(X), you could use a function to calculate what that would be , e.g. H(X,10000).
Thus, having a "fast forwarding" hash function that is fast in one direction, but provably hard in the other.
Anyone have knowledge/experience/ideas here? Much appreciated.

$\endgroup$
  • $\begingroup$ Will the bear's Makwa suit your needs? $\endgroup$ – SEJPM Oct 16 '15 at 19:14
  • 1
    $\begingroup$ Knowing the fast path of Makwa also allows inverting the hash, however. Is that a problem? $\endgroup$ – otus Oct 17 '15 at 6:09
  • $\begingroup$ Many thanks, Though really needs to be a one way function. Being able to reverse == not a one way/trapdoor. $\endgroup$ – Zaphod1001 Oct 17 '15 at 8:03
  • $\begingroup$ @otus : $\:$ The abstract refers to "an optional fast path" (emphasis mine). $\;\;\;\;$ $\endgroup$ – user991 Oct 18 '15 at 11:13
1
$\begingroup$

Follow up to the answer (to some degree).
Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.

A linear congruential generator (LCG) can be skipped ahead [link], in fact many PRNG's can be skipped/jumped ahead [link].
The problem with fast-forwarding any hash/prng, is that if you know the cycle period (which you do with most PRNGs), by fastforwarding the period-1, you effectively move back 1 state.

Thus if we found a way to say move forward quickly with a SHA256, the first person to correctly estimate its cycle period would also have the ability to move backward as well.

The only fix for this is to have a system with a huge number of varied cycles. E.g. having 256 bits worth of different cycles lengths, which each cycle being 64-256 bits in cycle length, fitting in 512 bits of state.

No known way of doing this, but should one be found, you've solved multiple comp-sci and cryptology problems, and made efficient signing of messages trivial.

tl;dr - if you can go forward and calculate its cycle length, you can go backward.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Cryptographically secure PRNGs and hashes do not usually have a known period (and may have a variety of periods like you suggest) and there's no guarantee that the system can return to the same state. For example, it may be that $H^k(x) = H(x)$ for some $k$, but that $H^{k-1}(x) \neq x$. $\endgroup$ – otus Oct 18 '15 at 10:08
  • $\begingroup$ @otus: Hash inputs can be bigger than their outputs, so it's definitely likely that $H^{-1}(x)\neq x$. However, for the most common applications of hashes that I can think of, finding some $y = H^{-1}(x)$ such that $H(y) = H(x)$ is just as good as finding $x$ itself (for example, password cracking). It might even be better (for example, quietly replacing someone's valuable data file $x$ with worthless garbage $y$, without causing any detectable change in the file's hash). $\endgroup$ – Quuxplusone Feb 9 at 16:51
1
$\begingroup$

What you're asking for is akin to multiplication, which is just repeated addition. As we know from our grade school classes, these are reversible with subtraction and division.

My understanding of the current state of the art is that in order to make it not trivial to reverse, it requires the input of previous state to generate next state--each subsequent state is built on the previous state.

It's not inconceivable that someone could eventually invent such a thing... but given our current approaches and mathematical knowledge, it does seem it will require some breakthrough.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It dawned on me that you can kind of picture calculating a hash like operating a rubik's cube. This makes it pretty clear how you need to go through each intervening state to get to a final one. (So far we don't have the hash equivalent of taking the cube apart and reassembling it in a new state, as I did as a child ;-) $\endgroup$ – P Holder Nov 19 '15 at 9:37
  • $\begingroup$ This analogy doesn't make sense to me. It sounds like you're saying y = H(x) is like y = k+x and then y = H^1000(x) would be like y = k+x+x+...+x = k+1000x; and then saying that because we can easily reverse y = k+1000x with x = (y - k)/1000, therefore H^1000 must also be easily reversible. But doesn't your analogy even more clearly imply that because we can reverse y = k+x by saying x = y-k, therefore H must also be easily reversible? And that's just demonstrably false. So the analogy doesn't seem good. $\endgroup$ – Quuxplusone Feb 9 at 16:46
0
$\begingroup$

You might also want take a look at sponges function (f in the following image). enter image description here

your p0 ... pi is your input (absorbing phase), while z0 ... zp is what you get when squeeze it p times.

for more informations : sponge corner

Keccak (SHA-3) has been implemented using it.

You could consider the compression function f as your hashing algorithm and squeeze your sponge the number of time you want.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ So, how would you fast forward the sponge (say) 10,000 states without computing the $f$ function 10,000 times? $\endgroup$ – poncho Nov 17 '15 at 15:23
  • $\begingroup$ True, that you would have to calculate your f function 10,000 but the idea here is rather than using a full hash algorithm such as SHA-X, you rely on the compression function and sort of re-implement SHA-3 to your own need. $\endgroup$ – Biv Nov 17 '15 at 15:56

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.