TRIPCODE QUINE!!!!

Can you hack it /PROG/?

Lain.

bumping a thread that is 4 years old. I'm trying to figure out how to get a specific tripcode in php. my logic would be the following:

if($tripcode == $desired){
echo $hashtext."==".$tripcode;
}
also testing shit.

>>43 more info?

@ ghosts of /prog/ past... nice idea, but there may well not even be one..
chances are there would be cyclic quines though.. (whether or not there is collisions, there Will be cycles in the hash.. (unless everything is a collision..)) ^^
might be better off looking for a name ->hash-> trip /and/ trip ->hash-> name (ie period-2 cycle) ;)

>>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.

>>46
so that the sum of all those j and j mod 281,474,976,710,656 is equal to x.

Should be:

so that the sum of all those j and x mod 281,474,976,710,656 is equal to x.

>>43
php

Of course you are testing shit

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

It's possible, but that too is highly unlikely.. mainly because it implies that all hashes chain together perfectly to form a single period-64^8 cycle. at most (?) the longest cycle (at random) should probably be at least a binary order of magnitude less... probably closer related to the longest run over n random bits ;D

is dependent on how many collisions the function has.

i'd also argue that it has more to do with the number of disjoint cycles than collisions =)

>>49

i'd also argue that it has more to do with the number of disjoint cycles than collisions

Each cycle is just the same as if you replaced the set of inputs X with Y, and reordered the set of all numbers j, which can be denoted as J.

The operations that come out of this, as noted in >>46, can just be treated as the generation of an n-dimensional vector, for n cycles, and the problem of finding the ``cyclic quine'' equivalent to checking if the vector is a linear combination over the space. Assuming random distribution, since it's a hash function, and little to no collision, you can calculate the chance of finding one of these quines by the size of the space, and each cycle adding another dimension. The more dimensions, the higher the chance. The number of disjoint cycles cannot be easily computed, due to the fact that hash functions are made to resist such things. But you can just compare the number of elements to the dimension of the vector.

>>50 =) sounds like we agree
This is kind of the concept i have.. there will be some number n cycles of assorted lengths.. smaller ones are of course harder to find individually, but there may or may not be many of them (probably quite a few at least, as they don't take up much room..) there will also be another component, i'm going to call these strands, which are formed where a chain of hashes collides with a member of a cycle.. strands are not cyclic, but will inevitably lead to a cycle.. ^^

>>51

You can probably just use a statistical approach for a large number of cycles. Hash functions tend to avalanche / converge to certain points over many cycles.

Pick a cycle number, and create a matrix that represents the distances between the output and input. Or you can just put that all in a vector, whichever way. After calculating some amount of these, you'll likely start to be able to discern patterns in the distances recorded in the vectors.

Then you can use those distances as a guide for which initial x to choose to have a higher chance of finding a quine.

Not sure how easy it would be to properly normalize those vectors so as to actually be able to gather starting points, though. Seems like it would get harder as the dimensions rise, unfortunately.

hm this is kind of neat..
Would it be fair to expect that for a hash function with at least one collision and one cycle, around 50% of the elements(?) might exist as part of a strand, and the other 50% as part of a cycle?
The number of collisions apparently is = to the number of strands(?!), and for each strand there is another end, ie an input which is not possible to output given any input.. funnily enough these are probably the hardest to find, but pretty much guaranteed to exist =)
Like you said, very difficult to know how many cycles there is exactly =/

oh, and a third thing can happen, which is where a new strand merges with an existing strand (via a collision), kind of like a tree leading to a cycle..
Probably a bit optimistic to expect a very long strand to link to a very short cycle.. but it could happen =)

>>53

Better define the term ``strand''. Also, it depends on the dimension of the cycle.

For a cycle of large dimension, probably more than 50% of the elements are part of the cycle. For a cycle of dimension 10, there's probably only a very small percentage of elements that are part of the cycle. Much less than 1%, I'd say.

Here I define cycle of dimension 2 to be f(f(x)). A cycle of dimension 1 would just be x = f(x).

Also, if the hash has collisions, the number of "unreachable" outputs is the same as the number of collisions. Obviously because if it outputs n hashes, and x of those hashes are the same, the number of different hashes is n - x, which leaves n ``holes''. Assuming the input and output space are the same.

You might want to look into linear regression for the statistical approach in finding these quines.

>>55

I meant, which leaves x ``holes''.

even better if it's a very large tree instead, with a short cycle, in terms of finding them =D

>>57

A large tree? Picking a random element as the top of the tree, and having other random elements as leaves, viewing edges as chainings, etc?

That's probably going to trap you in a local minima extremely quickly. The chain converge is likely decided early on in the operation sequence.

cycle of dimension 2 to be f(f(x)) = x
and yep, Assuming the input and output space are the same.
a strand is effectively defined as beginning at each of the x holes (inputs with no preimage at all - side-effect of collisions)... where they end can't really be said till you've completed a circuit of the attached cycle?

Are we sure 70 chars is "about right"? I've seen trips using accented characters and punctuation.

It's more likely to be UTF-8 or even 16, which means a much larger set of possible symbols.

Eg, the trip I am using is: #z水????????????

>>60
And then I realized you guys meant output. Shame on me.

well, a large and shallow tree would be ideal but would probably need lots of collisions..
random oracle model? ^^ / hmm wonder what will happen to this with a larger input -> output, or even just using salts....

>>60,61
The number of input characters is 95 + what you can fit in using Shift-JIS, I think.

>>59
beginning at each of the x holes
So, a strand is something where the first input in the chain, say, x₀ is not in the set of outputs?

A cause of this would be a unique first offset for the cycle, I suppose. Perhaps you can find these by computing many, many random short cycles, and seeing which "offsets" are never applied? The set of ``holes'' would be a subset of those.

I'll have to do some testing on this, myself. Also, actually look at the internals of DES, it's been a while since I did. Perhaps you can extract some properties from looking at how it handles things in the first few rounds.

i think statistically, for a hash with no collisions at all, there will be around log2(n) disjoint cycles? kind of like the birthday paradox, but each person only adds one instead of n-1 for the n-th person =)

and then for a normal hash the first strand+cycle+collision can be expected at n^0.5, with the birthday non-paradox (>>64) chance of just finding a cycle instead =D

>>64

Let me think. If for a function that takes n elements and outputs n elements, with no collisions, and the output is suitably random, then the chance of encountering a disjoint cycle in dimension N would be...

Taking a first random x, chance to find one that is disjoint, is 1/n. Chance of finding a disjoint sum taking x and two other random elements is n-1/((n-1)!)

With three elements its... what the hell is the equation for the number of all unique subsets of a set where each subset has n elements?

Just apply this, but with the mod n for the group. Due to the mod it'll go up for each dimension, otherwise the chance would diminish.

I'll work this out and see.

>>44
You wouldn't look so retarded if you stopped abusing emoticons so much, retard-kun.

>>66

Right, assuming that all permutations are possible, a cycle in dimension N creates n! / (n - N) subsets. Due to n being 281,474,976,710,656 this number is huge. The subset of that generated set, where the elements add up to a multiple of n is the number of disjoint cycles, and the chance of getting a disjoint cycle for dimension N can be arrived at by figuring out that number.

Though, I'm not sure how to calculate the number in higher dimensions with a mod.

I need a LaTeX to BBCode compiler. Making far too many errors in the equations. I meant n / N - (n - N) in the above post.

I think the number of possible disjoints might actually get lower the more collisions there are. Or, at least, it'll become unstable.

Fucking hell. Should be:

n! / N! (n - N)! in the above post.

i have a rather stupid question. if we try different password against tripcode algorithm (which is 10 last characters of crypt()'s hash for a given password) bruting for a specific string in the tripcode (like tripcode explorer does), does it matter how many possible characters our password can have? would more possible characters speed the process? apart from technical requirements (like passwords with 1 possible character would just crash your computer since the only way to change them it's to increase their length and you need hundred of millions different passwords etc), if we take 52 possible characters (alphabet only) and, say, 100 possible characters (alphabet + special symbols and other weird shit, if we don't care of possible tripcode compatibility problems), would it take the same time to brute a desirable string? i guess yes since i don't see how it matters. if any combination have an equal chance to pass it shouldn't matter how many different symbols it contains, we can have the same number of combination with any set of characters, if we have less characters we just should make passwords longer more soon but it shouldn't affect the speed. am i right?

It makes me feel better to see that people were still mean back in 2007. Maybe we didn't ruin /prog/ and it was always like this.

>>46
Now I need to wash my underwear. :\

>>70
just [b] the whole thing

asf

asd

asd

asd

asd

asd

asdafs