TRIPCODE QUINE!!!!

Can you hack it /PROG/?

>>44
That's (almost) equally unlikely.

If we just take the first 8 characters of the tripcode and feed that back into the hash function:

aaaabbbb -> zzzzcccc(xxx)
zzzzcccc -> aaaabbbb(xxx)

Equivalent to attempting to find x = f(f(x)) for some x. If x = f(x) doesn't exist for any x, then it's possible that neither does x = f(f(x)), because the set of all 8 char inputsX is equivalent to the map f(X) -> Y, just in different order.

Taking a simple ``hash'' function with no collisions:

f(x) = x+1%100 bounded on 0 <= x < 100, then there is no x that satisfies f(x) = x. Similarly, there is no f(f(x)) = x, due to the property of the function, you have to do 100 cycles before the input can equal the output. Which is equivalent, in this case, to feeding the entire set of its inputs to the function, until you get back to where you started.

So even in the DES hash, it's possible you'd have to perform 64⁸ = 281,474,976,710,656 cycles before you can satisfy the equation.

The chance is still absurdly low. It gets higher and higher the more cycles you use, but the rate at which the chance goes up is dependent on how many collisions the function has.

>>45
Expanding on this, to make it a bit clearer:

Chaining f(x) 100 times is equivalent to turning it into f(x) = (x+100) mod 100, which is just x.

If in DES, we create the set Y by feeding in all possible 8 char inputs in X, and we assume that X and Y are subsets of each other (they share all elements), then we can turn the DES hash function into a function that associates each input in X with a position, or index in Y.

So we can represent each element x in X as a natural number, from 0 to 281,474,976,710,656, and associate with it another number, j that maps x to its corresponding (equal) entry y in Y. If we restrict all numbers j to be positive, then the function for getting the y in Y associated to the x in X equivalent to:

f(x) = (x + j) mod 281,474,976,710,656.

Now, we see that this is equivalent to the previous ``simple'' hash function that just added 1 to x. The addition in the previous function was constant, whereas this one changes depending on x. If there are no collisions, then for any 2 distinct x and j, x + j is unique.

So, to find a ``cyclic quine'', we are trying to find a series of x in X that generate a series of j so that the sum of all those j and j mod 281,474,976,710,656 is equal to x.

In other words, you're trying to find a series of x and associated j, which, when all summed together, result in 281,474,976,710,656 + s, where s is the first x that fed to the chain.

Calculating the amount of cyclic quines for any amount of cycles c is the subset sum problem, which is NP-Complete.

So just calculating all quines for cycle c  through applying all j for all x would take more time than the lifetime of the Universe. Finding one by bruteforce is not likely.