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.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Will the bear's Makwa suit your needs? $\endgroup$– SEJPMCommented Oct 16, 2015 at 19:14
-
1$\begingroup$ Knowing the fast path of Makwa also allows inverting the hash, however. Is that a problem? $\endgroup$– otusCommented Oct 17, 2015 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$– Zaphod1001Commented Oct 17, 2015 at 8:03
-
$\begingroup$ @otus : $\:$ The abstract refers to "an optional fast path" (emphasis mine). $\;\;\;\;$ $\endgroup$– user991Commented Oct 18, 2015 at 11:13
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
-
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$– otusCommented Oct 18, 2015 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$ Commented Feb 9, 2020 at 16:51
$\begingroup$
$\endgroup$
2
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.
-
$\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 HolderCommented Nov 19, 2015 at 9:37
-
$\begingroup$ This analogy doesn't make sense to me. It sounds like you're saying
y = H(x)is likey = k+xand theny = H^1000(x)would be likey = k+x+x+...+x = k+1000x; and then saying that because we can easily reversey = k+1000xwithx = (y - k)/1000, thereforeH^1000must also be easily reversible. But doesn't your analogy even more clearly imply that because we can reversey = k+xby sayingx = y-k, thereforeHmust also be easily reversible? And that's just demonstrably false. So the analogy doesn't seem good. $\endgroup$ Commented Feb 9, 2020 at 16:46
$\begingroup$
$\endgroup$
2
You might also want take a look at sponges function (f in the following image).
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.
-
3$\begingroup$ So, how would you fast forward the sponge (say) 10,000 states without computing the $f$ function 10,000 times? $\endgroup$– ponchoCommented Nov 17, 2015 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$– BivCommented Nov 17, 2015 at 15:56