Inverse jump functions possible?

[lars szuwalski]

Hi group

I'm trying wrap my head around an issue which came up recently. I hope any of you can help. Thanks in advance!

My question:

Is it possible to compute when a specific output occurs in the period of a PRNG (an index into the sequence)? Sort of the inverse of a jump function.

Or more specifically the "distance" between two values? Such that given some value (seed) it can be computed how many iterations further down the sequence some other (given) value occurs?

Obviously one can iterate the function from the seed and look for the other value - but an answer I saw on crypto.stackoverflow (without any details however) seemed to imply that there is a more direct way to do this???

I'm not a mathematician so please excuse me if the above is obvious somehow. I haven't been able to formulate the question in any way as for google and friends to be able to help me. 

My intuition about the statistical properties of the PRNGs discussed in this forum is that any given value is equally likely to occur anywhere in the sequence and hence the information from that event is very low. Making it difficult to imagine (for me at least) an algorithm which could extract enough information to deduce the distance?

Also it would seem to me that such an algorithm would be linked to the PRNG function - ie no such general algoritme exist? Take a trivial example like x++ which obviously also encode the relative distance between any two points. But even an unsuffeled xorshift as a linear PRNG would seem to break such "leaks" - or?

Any insights or references on this matter would be very much appreciated.

Sincelery

Lars

[Sebastiano Vigna]

> On 17 Apr 2019, at 10:25, lars szuwalski <lars.sz...@gmail.com> wrote:
>
> Is it possible to compute when a specific output occurs in the period of a PRNG (an index into the sequence)? Sort of the inverse of a jump function.

Yes. It's computationally not nice though.

> Also it would seem to me that such an algorithm would be linked to the PRNG function - ie no such general algoritme exist? Take a trivial example like x++ which obviously also encode the relative distance between any two points. But even an unsuffeled xorshift as a linear PRNG would seem to break such "leaks" - or?
>
> Any insights or references on this matter would be very much appreciated.

Essentially, you compute a discrete logarithm with base x (in the field of the characteristic polynomial of the PRNG) on a jump polynomial obtained by solving a linear system. The polynomial is the jump polynomial leading you from the starting state to the ending state, and you can compute it easily (it's a simple linear system--you just consider the polynomial coefficients as variables and you build the system using the jump function). Once you have the polynomial p(x), there's only one value n such that x^n = p(x) modulo the characteristic polynomial, and that's the n you want. It's a discrete logarithm in the field associated with the characteristic polynomial of the linear transformation describing the PRNG, and you can compute it with Sage. It'll take time. Don't try > 128 bits of state (my advise, huh).

Disclaimer: there might be faster ways to do this, but I have no clue.

Ciao,

seba

[lars szuwalski]

Essentially, you compute a discrete logarithm with base x (in the field of the characteristic polynomial of the PRNG) on a jump polynomial obtained by solving a linear system. The polynomial is the jump polynomial leading you from the starting state to the ending state, and you can compute it easily (it's a simple linear system--you just consider the polynomial coefficients as variables and you build the system using the jump function). Once you have the polynomial p(x), there's only one value n such that x^n = p(x) modulo the characteristic polynomial, and that's the n you want. It's a discrete logarithm in the field associated with the characteristic polynomial of the linear transformation describing the PRNG, and you can compute it with Sage. It'll take time. Don't try > 128 bits of state (my advise, huh).

Disclaimer: there might be faster ways to do this, but I have no clue.

Thank you so much for your fast reply!

This really makes sense (even if it's disappointing :-) 

I'm (playing with) using xorshift as the foundation for key exchange / public-key - as a replacement for DH (which rests on discrete logarithm ..)

I have computed jump-functions for all powers of 2 up to the key-size. So the protocol is:

- Alice computes a secure random seed and a private-key. Iterate the seed using the jump-functions matching each bit in the private key (Done really fast - as you know). Send the seed and the result as challenge.

- Bob computes a secure random private key. Iterate the seed using the key - as response - and iterate the challenge (using the key) to get a shared secret.

- Alice iterate the response using her key to get to the same shared secret.

So I was of cause hoping it would not reduce to discrete logarithm - but since the problem really is the same as DH it makes sense that it actually does (as I said I'm not a mathematician). 

I'll probably keep playing for a while still - as I guess the jump functions might still be faster than exponentiation (and it's really just a hobby).

Do you know if this has been done before? Probably has. 

Regards,

Lars

[Mateusz Naściszewski]

Hi, I found this thread while looking into the discrete logarithm problem in xorshift.

In short, it *is* possible, but it's difficult. I have successfully found the index for a few 128-bit xorshift seeds in a few hours of time per seed. This is sufficiently weak to be useless for cryptography, but still too slow for my use-case.

The weakness originates from the fact that the order of xorshift128, 2^128-1 is highly factorizable into relatively small primes:
$ factor $(python -c "print(2**128-1)")
340282366920938463463374607431768211455: 3 5 17 257 641 65537 274177 6700417 67280421310721

This means that in the group of, say 'apply xorshift (2^128-1)/3 times', each element has order 3. You can relatively easily force any element from the full xorshift group onto a small cycle that contains the identity element by exponentiating it by that factor.

You can then easily get the residues of the index modulo the smaller primes, even by brute force, the issue starts with the 6.7 million prime, and then the 67 trillion prime. By using Pollard's rho algorithm (I mostly stole the implementation from Sage), you can relatively quickly find the residue modulo the smaller prime, but the algorithm takes hours for the largest prime.

The reason I'm still searching for something better is that I see a lot of mentions of algorithms that can solve discrete logarithm in some fields in some faster way, and xorshift does in fact form a certain (weird) field of characteristic 2 with some interesting linearity properties. There are papers like "A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic", which seems like exactly what I want, but the paper is unreadable, and assumes knowledge I don't have, and it doesn't seem like any implementations of it actually exists. Even if it does, how would I know if it applies to xorshift? It seems to need some sort of subfield with a squared prime order, but each prime in xorshift's order is unique, and those subgroups don't seem to form sub-fields anyway if I understand the term correctly.

That paper also mentions a Function Field Sieve, which is apparently exponential time in some weird L() notation I haven't come across before, but I don't know if it applies here either.

Back on topic, your proposed shared key scheme is trivially breakable, as you don't need to know the index of the seed values to be able to compute how to transform any seed into any other seed by some amount of xorshift applications. This is because of the odd linearity properties of the field that xorshift forms. You can consider each bit individually, making a matrix of which bit of input affects which bit of output. These matrices can be xored with each other to obtain another valid matrix that also represents applying xorshift some amount of times. You can then solve for such a matrix that changes a specific seed to another specific seed. I used a rather braindead algorithm for this and just solved 128 rows of the matrix separately by Gaussian elimination for each row, obtaining more relations between bits of data by applying xorshift to both the input seed and output seed to keep them at the same distance. (It should be possible to solve it faster, and without doing this with a smarter algorithm that exploits the linearity more directly.)

Having this matrix allows you to effectively know everything you need to know about Alice's private key, without actually knowing it. You can either do the same with the seed and Bob's response to 'obtain' his private key, or just apply the matrix to his response to obtain the shared key immediately.

If Bob is an attacker, he can also force any specific value for the derived key by doing this solving procedure to see how to transform Alice's result into that value, and using the matrix in place of his own private key, then sending the seed transformed by that matrix as his response.